This site is supported by donations to The OEIS Foundation.

# Sequences from Graham, Knuth, Patashnik "Concrete Math"

• For a long time I (njas) have had the idea that it would be useful to have a series of concordances which would list the integer sequences to be found in certain classical books (Riordan, Comtet, Harary and Palmer, Stanley, Knuth, etc.). Here is the fourth of these, a concordance to: R. L. Graham, D. E. Knuth and O. Patashnik's Concrete Mathematics, Addison-Wesley, 2nd Ed., 1994, based on a first draft prepared by Olivier Gerard, ogerard@ext.jussieu.fr
• The idea is that when you are reading one of these books, these files will give pointers to the On-Line Encyclopedia of Integer Sequences whenever an interesting sequence is mentioned. This will enable you to see the terms of the sequence, recurrences, formulae, other references, links, most recent progress, etc.
• Furthermore, the preparation of these concordances will supply additional sequences for the database, and additional references for existing sequences.
• This version is only a preliminary draft and needs to be expanded. If you can help, please either edit this page, or contact Neil Sloane, njasloane@gmail.com.
• For the current list of these concordances, see here.

#### Chapter 1: Recurrent Problems

 page A-number Description ? Eulerian numbers 2^n - n - 1. (Column 2 of Euler's triangle A008292.) ? Euclid numbers: 1 + product of first n consecutive primes. ? floor(3n/4) ? floor(2n/5) ? floor(3n/5) ? floor(2n/7) ? floor(3n/7) ? floor(4n/7) ? floor(5n/7) ? floor(3n/8) ? floor(5n/8) ? floor(5n/13) ? floor(8n/13) ? floor(8n/21) ? floor(13n/21) ? floor(7n/19) ? floor(11n/30) 10 Josephus problem. 18 Tower of Hanoi with cyclic moves only. 18 Tower of Hanoi with cyclic moves only.

#### Chapter 3: Integer Functions

 page A-number Description 66 Golomb's sequence: a(n) is the number of times n occurs. 66 Perfect powers: m^k where m is an integer and k >= 2. 77 A Beatty sequence: [ n * sqrt 2 ]. 77 A Beatty sequence: [ n * (2 + sqrt(2)) ]. 78 If n is present so are 2n+1 and 3n+1. 78 Knuth's sequence: a(n+1) = 1 + min ( 2 a[ n/2 ],3 a[ n/3 ] ). 97 n appears n times. 99 Quarter-squares: floor(n/2)*ceiling(n/2). Equivalently, floor(n^2/4). 111 (10^n)-th prime. 117 Numerators of Farey (or Stern-Brocot) tree fractions. 122 Numerators of approximations to e. 122 Denominators of approximations to e. 138 Number of fractions in Farey series of order n (1 + A002088). 147 Ron Graham's sequence. 164 Triangle of binomial coefficients C(-n,k). 194 Triangle T(n,k) of rencontres numbers (number of permutations of n elements with k fixed points). 194 Triangle of rencontres numbers. 231 Superfactorials: product of first n factorials. 244 Triangle of Stirling numbers of 2nd kind, S2(n,k), n>=1, 1<=k<=n. 244 Triangle of Stirling numbers of 2nd kind, S(n,k), n>=0, 0<=k<=n. 245 Triangle of Stirling numbers of 1st kind, s(n,k), n>=1, 1<=k<=n. 245 Triangle of Stirling numbers of 1st kind, s(n,k), n>=0, 0<=k<=n. 254 Sum of upward diagonals of Eulerian triangle. 254 Multiplicative encoding of the Eulerian number triangle. 254 Triangle of Eulerian numbers. 254 Triangle of Eulerian numbers with rows multiplied by 1+x. 254 Numbers in the triangle of Eulerian numbers (A008292) that are not 1. 254 Even numbers in the triangle of Eulerian numbers. 254 Odd numbers in the triangle of Eulerian numbers. 254 Odd numbers in the triangle of Eulerian numbers that are not 1. 254 Triangular array formed from elements to right of middle of rows of the triangle of Eulerian numbers. 254 Triangular array formed from elements to right of middle of rows of the triangle of Eulerian numbers that are greater than 1. 254 Triangular array formed from odd elements to right of middle of rows of the triangle of Eulerian numbers (A008292). 254 Triangular array formed from odd elements to right of middle of rows of the triangle of Eulerian numbers that are greater than 1. 254 Triangular array formed from even elements to right of middle of rows of the triangle of Eulerian numbers. 254 Central Eulerian numbers A(2n-1, n). 256 Second-order Eulerian numbers. 256 Second-order Eulerian numbers: 2^(n+1) - 2n - 2. 256 Second-order Eulerian numbers. 256 Maximal Eulerian numbers of second kind. 256 Second-order Eulerian triangle a(n,k), 1<=k<=n. 259 Wolstenholme numbers: numerator of harmonic number H(n)=Sum_{i=1..n} 1/i. 259 Denominators of harmonic numbers H(n)=Sum 1/i. 259 Books required for n books of overhang. 269 Numerator of n/12. 269 Denominator of n/12. 269 Numerator of n(n-1)(n-2)/720. 269 Denominator of n(n-1)(n-2)/720. 316 Ways of making change for n cents using coins of 1, 2, 5, 10 cents. 316 Ways of making change for n cents using coins of 1, 5, 10, 25 cents. 316 Ways of making change for n cents using coins of 1, 5, 10, 25, 50 cents. 316 Ways of making change for n cents using coins of 1, 2, 5, 10, 25 cents. 316 Ways of making change for n cents using coins of 1, 2, 5, 10, 25, 50 cents. 316 Ways of making change for n cents using coins of 1, 5, 10, 20, 50, 100 cents. 316 Ways of making change for n cents using coins of 1, 2, 4, 10, 20, 40, 100 cents. 316 Ways of making change for n cents using coins of 1, 2, 5, 10, 50, 100 cents. 316 Ways of making change for n cents using coins of 1, 2, 5, 10, 20, 50 cents. 316 Ways of making change for n cents using coins of 2, 5 (two kinds), 10, 20, 50 cents. 316 Ways of making change for n cents using coins of 2, 5, 10, 20, 50 cents. 316 Ways of making change for n cents using coins of 5, 10, 20, 50, 100 cents. 316 Ways of making change for n cents using coins of 1, 2, 4, 10 cents. 316 Ways of making change for n cents using coins of 1, 2, 4, 12, 24, 48, 96, 120 cents (based on English coinage of 1939). 316 Ways of making change for n Euro-cents using the Euro currency (coins and bills of size 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000 cents). 327 a(n) = a(n-1)+2.a(n-2)+(-1)^n. 329 a(n) = 4a(n-1) - a(n-2). 329 a(n) = 4a(n-1) - a(n-2). 329 Bisection of A001353. (Indices of square numbers which are also octagonal.) 360 Stacking bricks. 477 Hyperfactorials: Product k^k, k = 1 . . n. 481 From an asymptotic expansion for Pi. 528 Genocchi numbers (of first kind): expansion of tan(x/2). 528 Genocchi numbers (of first kind): expansion of 2x/(exp(x)+1). 575 Central trinomial coefficient: largest coefficient of (1+x+x^2)^n. 575 a_0 = 1, a_{n+2} = 3 * a_{n+1} - F_n*(F_n + 1), where F_n is n-th Fibonacci number.