This site is supported by donations to The OEIS Foundation.

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

### From OeisWiki

- For a long time I 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 page is under construction, Jun 10, 2001

### R. L. Graham, D. E. Knuth and O. Patashnik,

### Concrete Mathematics, Addison-Wesley, 2nd Ed., 1994

#### Chapter 1: Recuurent 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 2: Sums

#### 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. |