This site is supported by donations to The OEIS Foundation.

# Sequences from Stanley's Enumerative Combinatorics

## Sequences from Stanley's Enumerative Combinatorics

Keywords: Stanley, Enumerative Combinatorics, Integer Sequences, Concordance

• For a long time I have had the idea of making a series of concordances which would list the integer sequences to be found in certain classical books (Riordan, Comtet, Harary and Palmer, Knuth, Graham-Knuth-Patashnik, etc.). Here is the first of these, a concordance to
Richard P. Stanley's Enumerative Combinatorics
Vol. 1, Wadsworth, 1986; Vol. 2, Cambridge, 1999
• 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.
• Only the first half of Volume 2 of Stanley has been dealt with in any thoroughness so far. Suggestions for additional entries mentioning sequences described in either volume will be welcomed. Send them to me at this address: njas@research.att.com
• Thanks to Valery Liskovets (liskov@im.bas-net.by) for comments on Problem 5.13 of Volume 2.

### Richard P. Stanley: Enumerative Combinatorics, Volume 1

#### Chapter 1: What Is Enumerative Combinatorics?

Page 1 Example 1.1.1 2^n A000079
Page 1 Example 1.1.2 derangements A000166
Page 2 Example 1.1.3 f(n) A001501
Page 9 Example 1.1.14 Moebius function mu(n) A008683
Page 36 S A048993 A008277
Page 36 s A048994 A008275

#### Chapter 2: Sieve Methods

Page 67 Example 2.2.1 D(n) A000166
Page 88 Problem 8(a): A000757
Page 89 Problem 10: A033815
Page 93, Problem 7: A000266

#### Chapter 3: Partially Ordered Sets

Page 112 Catalan numbers C_n A000108
Page 146 Preferential arrangements A000670
Page 172 Problem 77 Fibonacci numbers F_n A000045

#### Chapter 4: Rational Generating Functions

Page 203 Example 4.1.2 f(n) A001333
Page 221 Example 4.5.18 A006858
Page 233 H_4(n) A001496
Page 233 H_3(n) (i.e. F_3(lambda)) A002817
Page 234 F_4 A001496
Page 234 F_5 A003438
Page 235 G_3 A019298
Page 235 G_4 A053493
Page 235 G_5 A053494
Page 244 line 4 A033303
Page 244 (36) A033304
Page 246 (37) Fibonacci numbers F_n A000045
Page 246 (38) g(n) A000252
Page 246 Lucas numbers L(n) A000204 A000032
Page 251 Example 4.7.14 A007598
Page 252 Example 4.7.15 g(n) A000252
Page 252 Example 4.7.16 f(n) A033305
Page 253 Example 4.7.16 f*(n) A002524
Page 253 f(n) A001169
Page 292 F_3 A001835
Page 292 F_4 A005178
Page 292 F_5 A003775
Page 292 F_6 A028468

### Richard P. Stanley: Enumerative Combinatorics, Volume 2

#### Chapter 5: Trees and the Composition of Generating Functions

Page 2 Example 5.1.2 A010842 A053484 A053485
Page 4 h(n) A029767
Page 9 Example 5.1.14 A053488
Page 11 (5.22) A001187
Page 12 last line A007113
Page 13 line 3 A053489 A053490
Page 13 Example 5.2.4 B(n) A000110
Page 13 B_2 A000258
Page 13 B_3 A000307
Page 14 (5.22) A000311
Page 15 b(n) A001147
Page 17 S_n(2) A000985
Page 17 S*_n(2) A002137
Page 17 T_n(2) A002137
Page 17 T*_n(2) A001205
Page 19 L(n) A002135
Page 20 (5.31) A005388 A001470 A001472 A053495 A053496 A053497 A053498 A053499 A053500 A053501 A053502 A053504 A053505
Page 20 (5.32) A000085
Page 23 5.3.1 r(n) A000055
Page 25 p_k(n) A053506 A053507 A053508
Page 25 r(n) A000169
Page 25 t(n) A000272
Page 25 p(n) A000272
Page 53 H(n,2) A000681
Page 53 H*(n,2) A001499
Page 62 (5.85) A006237
Page 65 B_0(n) A016031
Page 72 Problem 5.1(b) A053524
Page 73 Problem 5.4(a) T A005840
Page 73 Problem 5.4(a) S A053525
Page 73 Problem 5.4(b) A000670
Page 73 Problem 5.5 A000217 A050534 A053526 A053527 A053528
Page 73 Problem 5.7 E_n A000111
Page 74 Problem 5.8(a) T(n,k) A008957 A036969
Page 74 Problem 5.8(d) G_n A039698 A001469
Page 76 Problem 5.11(a) A003483
Page 76 Problem 5.12 A053529

Pages 76 and 112, Problem 5.13(b), Eq. (5.89):
j_n(F_r) = number of subgroups of index n in a free group of rank r:
Main array is A049290. See also A003319 (r=2), A027837 (r=3), A049291 (r=4); A049294 (n=3), A049295 (n=4); A057014 (n=r).

Pages 76 and 112, Problem 5.13(c):
u_n(F_r) = number of conjugacy classes of subgroups of index n in a free group of rank r:
Main array is A057004. Rows, columns, main diagonal give A057005-A057013.
Enumerated by J. H. Kwak and J. Lee, J. Graph Th., 23 (1996), 105-109.
For a recent reference, see V. Liskovets, Reductive enumeration under mutually orthogonal group actions, Acta Applic. Math., 52 (1998), 91-120.

Pages 76 and 112, Problem 5.13(c), Formula (5.125):
j_n(F_2 x Z) = A027838, j_n(F_3 x Z) = A027839 (see V. Liskovets and A. Mednykh, Enumeration of subgroups in the fundamental groups of orientable circle bundles over surfaces, Commun. in Algebra, 28, No. 4 (2000), 1717-1738).
j_n(Z x Z) = sigma(n) = A000203.

Pages 76 and 113, Problem 5.13(d):
j_n(ZxZxZ) = A001001 (see V. Liskovets and A. Mednykh, Enumeration of subgroups in the fundamental groups of orientable circle bundles over surfaces, Commun. in Algebra, 28, No. 4 (2000), 1717-1738; or the paper by Bryan and Fulman (1998) referred to on p. 113).

Page 78 Problem 5.16(b) A005155
Page 79 Problem 5.18 A003510
Page 80 Problem 5.20(b) A013922 A053549
Page 80 Problem 5.22 A002135
Page 80 Problem 5.23 A001205
Page 80 Problem 5.24(b) A006847
Page 81 Problem 5.25(b) A053553
Page 81 Problem 5.26 F A005640
Page 81 Problem 5.26 G A005172
Page 81 Problem 5.27 A007830
Page 82 Problem 5.29(b) A000169
Page 84 Problem 5.32(d) h A006153
Page 84 Problem 5.32(d) g A000248
Page 86 Problem 5.34(c) mu_n A001818
Page 88 Problem 5.39 A053554
Page 89 5.40(a) S A006351
Page 90 Problem 5.41(a) A007889
Page 94 Problem 5.48(a) A052121
Page 98 Problem 5.52(c) A052104 A052105 A052122 A052123
Page 100 Problem 5.64(b) f_4 A052127
Page 100 Problem 5.64(d) g'_2(n) A052140
Page 100 Problem 5.65(a) f(1,n) A000217
Page 101 Problem 5.65(b) f(n,n) A049088
Page 104 Problem 5.1(b) h(n) A053524
Page 105 Problem 5.12 A053529
Page 115 Problem 5.15(a) A001205 A053532 A053533
Page 115 Problem 5.15(b) A053530
Page 115 Problem 5.15(c) A053531
Page 115 Problem 5.15(d) A011800
Page 123 Problem 5.17 A007830
Page 145 Problem 5.55 B_n A027641/A027642
Page 151 Problem 5.62(b) f_3(n) A001044

#### Chapter 6: Algebraic, D-Finite and Noncommutative Generating Functions

Page 172 Catalan numbers C_n A000108
Page 178 s_2(n) and s_n A001003
Page 178 r_n A006318
Page 178 s_3(n) A001147
Page 178 s_4(n) A000311
Page 185 Example 6.3.8 y A001850
Page 185 Example 6.3.8 D(m,n) A008288
Page 186 Example 6.3.8 (6.29) A002426
Page 191 u_1 A000364
Page 191 u_2 A008990
Page 191 u_3 A052142
Page 191 u_4 A000110
Page 191 u_5 A052143
Page 191 u_7 A052144
Page 219 Problem 6.17(b) r_n A006318
Page 219 Problem 6.19 Catalan numbers C_n A000108
Page 231 Problem 6.24 A051785
Page 231 Problem 6.25 Catalan numbers C_n A000108
Page 233 Problem 6.28(c) y_d A000027 A000290 A055232 A055383 A055384
Page 233 Problem 6.30 A006531
Page 237 Problem 6.36(a) N(n,k) A001263
Page 238 Problem 6.37 Motzkin numbers M_n A001006
Page 239 r_n A006318
Page 239 s_n A001003
Page 241 Problem 6.40 a_n A002464
Page 241 Problem 6.40 r_n A006318
Page 241 Problem 6.41 S_2(n) A000139
Page 242 Problem 6.44 A007817
Page 242 Problem 6.45 A006251
Page 243 Problem 6.46(a) A005773
Page 243 Problem 6.47(b) A032351
Page 243 Problem 6.48 A022558
Page 244 Problem 6.49(a) A001850
Page 244 Problem 6.50 A007901
Page 245 Problem 6.51 Has irrational coefficients!
Page 245 Problem 6.52 A001190
Page 245 Problem 6.53 f(n) A007489
Page 246 Problem 6.55(a) B(n) A001181

#### Chapter 7: Symmetric Functions

Page 450 Problem 7.2(d) A052146
Page 450 Problem 7.2(f) A006463
Page 452 Problem 7.14(a) A019298
Page 452 Problem 7.16(b) y_2(n): A001405
Page 452 Problem 7.16(b) y_3(n): A001006
Page 452 Problem 7.16(b) y_4(n): A005817
Page 452 Problem 7.16(b) y_5(n): A049401
Page 453 Problem 7.16(e) A005802
Page 472 Problem 7.68(d) A052145
Page 489 Problem 7.112(a) A000031 A001867 A001868 A001869
Page 489 Problem 7.112(b) A003239
Page 558 Problem 7.112(b) A003239