Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren 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) Cited in 21 ReviewsCited in 1287 Documents 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 × Cite Format Result Cite Review PDF Digital Library of Mathematical Functions: §1.2(iii) Partial Fractions ‣ §1.2 Elementary Algebra ‣ Topics of Discussion ‣ Chapter 1 Algebraic and Analytic Methods §1.2(ii) Finite Series ‣ §1.2 Elementary Algebra ‣ Topics of Discussion ‣ Chapter 1 Algebraic and Analytic Methods §1.2(i) Binomial Coefficients ‣ §1.2 Elementary Algebra ‣ Topics of Discussion ‣ 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(n) = n + Sum_{k=1..n} (n mod k). Row sums of A372727. 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)!). Triangle read by rows: T(n, k) = n if k = 0, otherwise n - k*floor(n/k). The binary modulo operation.