This site is supported by donations to The OEIS Foundation.

Sequences from Graham, Knuth, Patashnik "Concrete Math"

From OeisWiki

Jump to: navigation, search

Contents

Sequences from Graham, Knuth and Patashnik's "Concrete Mathematics"

  • 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
 ?

A000295

Eulerian numbers 2^n - n - 1. (Column 2 of Euler's triangle A008292.)

 ?

A006862

Euclid numbers: 1 + product of first n consecutive primes.
 ?

A057353

floor(3n/4)
 ?

A057354

floor(2n/5)
 ?

A057355

floor(3n/5)
 ?

A057356

floor(2n/7)
 ?

A057357

floor(3n/7)
 ?

A057358

floor(4n/7)
 ?

A057359

floor(5n/7)
 ?

A057360

floor(3n/8)
 ?

A057361

floor(5n/8)
 ?

A057362

floor(5n/13)
 ?

A057363

floor(8n/13)
 ?

A057364

floor(8n/21)
 ?

A057365

floor(13n/21)
 ?

A057366

floor(7n/19)
 ?

A057367

floor(11n/30)
10

A006257

Josephus problem.
18

A005665

Tower of Hanoi with cyclic moves only.
18

A005666

Tower of Hanoi with cyclic moves only.

Chapter 2: Sums

Chapter 3: Integer Functions

page A-number Description
66

A001462

Golomb's sequence: a(n) is the number of times n occurs.
66

A001597

Perfect powers: m^k where m is an integer and k >= 2.
77

A001951

A Beatty sequence: [ n * sqrt 2 ].
77

A001952

A Beatty sequence: [ n * (2 + sqrt(2)) ].
78

A002977

If n is present so are 2n+1 and 3n+1.
78

A007448

Knuth's sequence: a(n+1) = 1 + min ( 2 a[ n/2 ],3 a[ n/3 ] ).
97

A002024

n appears n times.
99

A002620

Quarter-squares: floor(n/2)*ceiling(n/2). Equivalently, floor(n^2/4).
111

A006988

(10^n)-th prime.
117

A007305

Numerators of Farey (or Stern-Brocot) tree fractions.
122

A006258

Numerators of approximations to e.
122

A006259

Denominators of approximations to e.
138

A005728

Number of fractions in Farey series of order n (1 + A002088).

147

A006255

Ron Graham's sequence.
164

A027555

Triangle of binomial coefficients C(-n,k).
194

A008290

Triangle T(n,k) of rencontres numbers (number of permutations of n elements with k fixed points).
194

A008291

Triangle of rencontres numbers.
231

A000178

Superfactorials: product of first n factorials.
244

A008277

Triangle of Stirling numbers of 2nd kind, S2(n,k), n>=1, 1<=k<=n.
244

A048993

Triangle of Stirling numbers of 2nd kind, S(n,k), n>=0, 0<=k<=n.
245

A008275

Triangle of Stirling numbers of 1st kind, s(n,k), n>=1, 1<=k<=n.
245

A048994

Triangle of Stirling numbers of 1st kind, s(n,k), n>=0, 0<=k<=n.
254

A000800

Sum of upward diagonals of Eulerian triangle.
254

A007338

Multiplicative encoding of the Eulerian number triangle.
254

A008292

Triangle of Eulerian numbers.
254

A008518

Triangle of Eulerian numbers with rows multiplied by 1+x.
254

A014449

Numbers in the triangle of Eulerian numbers (A008292) that are not 1.

254

A014450

Even numbers in the triangle of Eulerian numbers.
254

A014459

Odd numbers in the triangle of Eulerian numbers.
254

A014461

Odd numbers in the triangle of Eulerian numbers that are not 1.
254

A014467

Triangular array formed from elements to right of middle of rows of the triangle of Eulerian numbers.
254

A014468

Triangular array formed from elements to right of middle of rows of the triangle of Eulerian numbers that are greater than 1.
254

A014469

Triangular array formed from odd elements to right of middle of rows of the triangle of Eulerian numbers (A008292).

254

A014470

Triangular array formed from odd elements to right of middle of rows of the triangle of Eulerian numbers that are greater than 1.
254

A014472

Triangular array formed from even elements to right of middle of rows of the triangle of Eulerian numbers.
254

A025585

Central Eulerian numbers A(2n-1, n).
256

A004301

Second-order Eulerian numbers.
256

A005803

Second-order Eulerian numbers: 2^(n+1) - 2n - 2.
256

A006260

Second-order Eulerian numbers.
256

A007347

Maximal Eulerian numbers of second kind.
256

A008517

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

A001008

Wolstenholme numbers: numerator of harmonic number H(n)=Sum_{i=1..n} 1/i.
259

A002805

Denominators of harmonic numbers H(n)=Sum 1/i.
259

A014537

Books required for n books of overhang.
269

A051724

Numerator of n/12.
269

A051725

Denominator of n/12.
269

A051726

Numerator of n(n-1)(n-2)/720.
269

A051727

Denominator of n(n-1)(n-2)/720.
316

A000008

Ways of making change for n cents using coins of 1, 2, 5, 10 cents.
316

A001299

Ways of making change for n cents using coins of 1, 5, 10, 25 cents.
316

A001300

Ways of making change for n cents using coins of 1, 5, 10, 25, 50 cents.
316

A001301

Ways of making change for n cents using coins of 1, 2, 5, 10, 25 cents.
316

A001302

Ways of making change for n cents using coins of 1, 2, 5, 10, 25, 50 cents.
316

A001306

Ways of making change for n cents using coins of 1, 5, 10, 20, 50, 100 cents.
316

A001310

Ways of making change for n cents using coins of 1, 2, 4, 10, 20, 40, 100 cents.
316

A001312

Ways of making change for n cents using coins of 1, 2, 5, 10, 50, 100 cents.
316

A001313

Ways of making change for n cents using coins of 1, 2, 5, 10, 20, 50 cents.
316

A001314

Ways of making change for n cents using coins of 2, 5 (two kinds), 10, 20, 50 cents.
316

A001319

Ways of making change for n cents using coins of 2, 5, 10, 20, 50 cents.
316

A001343

Ways of making change for n cents using coins of 5, 10, 20, 50, 100 cents.
316

A001362

Ways of making change for n cents using coins of 1, 2, 4, 10 cents.
316

A001364

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

A057537

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

A006904

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

A001353

a(n) = 4a(n-1) - a(n-2).
329

A001835

a(n) = 4a(n-1) - a(n-2).
329

A028230

Bisection of A001353. (Indices of square numbers which are also octagonal.)

360

A006253

Stacking bricks.
477

A002109

Hyperfactorials: Product k^k, k = 1 . . n.
481

A019267

From an asymptotic expansion for Pi.
528

A001469

Genocchi numbers (of first kind): expansion of tan(x/2).
528

A036968

Genocchi numbers (of first kind): expansion of 2x/(exp(x)+1).
575

A002426

Central trinomial coefficient: largest coefficient of (1+x+x^2)^n.
575

A011769

a_0 = 1, a_{n+2} = 3 * a_{n+1} - F_n*(F_n + 1), where F_n is n-th Fibonacci number.

Personal tools