##
**Concrete mathematics: a foundation for computer science.
2nd ed.**
*(English)*
Zbl 0836.00001

Amsterdam: Addison-Wesley Publishing Group. xiii, 657 p. (1994).

A refined and improved version of what has already become a classic. The only totally new section comes at the end of the chapter on binomial coefficients. It describes Zeilberger’s algorithm which enables computers to discover and prove binomial coefficient identities. Zeilberger’s computer specialist, Shalosh B. Ekhad, has now become a prolific author. See Zbl 0668.00003 for the review of the first edition (1989).

Reviewer: D.M.Bressoud (St.Paul)

### MSC:

00A05 | Mathematics in general |

68-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science |

11B65 | Binomial coefficients; factorials; \(q\)-identities |

11Axx | Elementary number theory |

05A10 | Factorials, binomial coefficients, combinatorial functions |

### Keywords:

basic techniques of mathematical sciences; elementary number theory; combinatorics; probability; asymptotic arguments; binomial coefficients; Zeilberger’s algorithm; binomial coefficient identities### Citations:

Zbl 0668.00003
PDFBibTeX
XMLCite

\textit{R. L. Graham} et al., Concrete mathematics: a foundation for computer science. 2nd ed. Amsterdam: Addison-Wesley Publishing Group (1994; Zbl 0836.00001)

### Digital Library of Mathematical Functions:

§1.2(iii) Partial Fractions ‣ §1.2 Elementary Algebra ‣ Areas ‣ Chapter 1 Algebraic and Analytic Methods§1.2(ii) Finite Series ‣ §1.2 Elementary Algebra ‣ Areas ‣ Chapter 1 Algebraic and Analytic Methods

§1.2(i) Binomial Coefficients ‣ §1.2 Elementary Algebra ‣ Areas ‣ Chapter 1 Algebraic and Analytic Methods

§24.15(ii) Tangent Numbers ‣ §24.15 Related Sequences of Numbers ‣ Properties ‣ Chapter 24 Bernoulli and Euler Polynomials

Calculus of Finite Differences ‣ §24.17(i) Summation ‣ §24.17 Mathematical Applications ‣ Applications ‣ Chapter 24 Bernoulli and Euler Polynomials

§26.14(iii) Identities ‣ §26.14 Permutations: Order Notation ‣ Properties ‣ Chapter 26 Combinatorial Analysis

§26.14(ii) Generating Functions ‣ §26.14 Permutations: Order Notation ‣ Properties ‣ Chapter 26 Combinatorial Analysis

§26.14(i) Definitions ‣ §26.14 Permutations: Order Notation ‣ Properties ‣ Chapter 26 Combinatorial Analysis

§26.14(iv) Special Values ‣ §26.14 Permutations: Order Notation ‣ Properties ‣ Chapter 26 Combinatorial Analysis

Alternative Notations ‣ §26.1 Special Notation ‣ Notation ‣ Chapter 26 Combinatorial Analysis

Alternative Notations ‣ §26.1 Special Notation ‣ Notation ‣ Chapter 26 Combinatorial Analysis

§26.8(iii) Special Values ‣ §26.8 Set Partitions: Stirling Numbers ‣ Properties ‣ Chapter 26 Combinatorial Analysis

§26.8(iv) Recurrence Relations ‣ §26.8 Set Partitions: Stirling Numbers ‣ Properties ‣ Chapter 26 Combinatorial Analysis

§26.8(v) Identities ‣ §26.8 Set Partitions: Stirling Numbers ‣ Properties ‣ Chapter 26 Combinatorial Analysis

Notations

Notations

### Online Encyclopedia of Integer Sequences:

Euler totient function phi(n): count numbers <= n and prime to n.Second-order Eulerian numbers <<n+1,n-1>>.

Second-order Eulerian numbers <<n,2>>.

Number of distinct autocorrelations of binary words of length n.

Second-order Eulerian numbers: a(n) = 2^n - 2*n.

Second-order Eulerian numbers <<n,3>>.

Triangle T(n,k) = n!/(n-k)! (0 <= k <= n) read by rows, giving number of permutations of n things k at a time.

Second-order Eulerian triangle T(n,k), 1 <= k <= n.

Triangle read by rows: T(n, k) is the number of diagonal dissections of a convex n-gon into k+1 regions.

Number of edges in all simple (loopless) paths, connecting any node with all the remaining ones in optimal graphs of degree 4.

a(n) = -1 + number of odd divisors of n.

Array of coefficients of denominator polynomials of the n-th approximation of the continued fraction x/(1+x/(2+x/(3+..., related to Laguerre polynomial coefficients.

Triangle read by rows: coefficients of Genocchi polynomials G(n,x); n times the Euler polynomials.

A variant of the Josephus Problem in which three persons are to be eliminated at the same time.

Triangle of Eulerian numbers T(n,k), 0 <= k <= n, read by rows.

a(n) = 2*n^2 - n + 1.

Zeckendorf representation of natural numbers.

a(n) = 3*a(n-1) + 2*a(n-2) for n>1, a(0)=2, a(1)=3.

Array for a certain labeled Morse code, recorded in standard order.

Write 2^n in base 3, add up the ”digits”.

Triangle T(n, k) read by rows: row n gives for n >= 0 the coefficients of the exponential numerator polynomial used for the exponential generating function of {Sum_{j=1..m} (1 + 2*j)^n}_{m>=0}.

Number of permutations of the multiset {1,1,2,2,...,2n,2n} having exactly n ascents and no number smaller than k between the two occurrences of any number k.

Least q > 1 letting Josephus survive if he finds himself at position j in the circle of m persons, but is allowed to name the elimination parameter q such that every q-th person is executed, written as triangle T(m,j), m > 1, j <= m.

E2(n, k), the second-order Eulerian numbers with E2(0, k) = δ_{0, k}. Triangle read by rows, E2(n, k) for 0 <= k <= n.

Triangle T from the array A(k, n) giving the sums of k+1 consecutive squares starting with n^2, read as upwards antidiagonals, for k >= 0 and n >= 0.

Triangle read by rows. T(n, k) are the coefficients of polynomials p_n(x) based on the Eulerian numbers of first order representing the Bernoulli numbers as B_n = p_n(1) / (n + 1)!.

Triangle read by rows. T(n, k) are the coefficients of polynomials p_n(x) based on the Eulerian numbers of second order representing the Bernoulli numbers as B_n = p_n(1) / (2*(2*n - 1)!).