Contents
Foreword xv
About the Author xvii
I Counting sequences related to set partitions and permutations 1
1 Set partitions and permutation cycles 3
1.1 Partitions and Bell numbers . . . . . . . . . . . . . . . . . . 3
1.2 Partitions with a given number of blocks and the Stirling numbers of the second kind . . . 6
1.3 Permutations and factorials . . . . . . . . . . . . . . . . . . 10
1.4 Permutation with a given number of cycles and the Stirling numbers of the first kind . 11
1.5 Connections between the first and second kind Stirling numbers . . . . 15
1.6 Some further results with respect to the Stirling numbers . 16
1.6.1 Rhyme schemes . . . . . . . . . . . . . . . . . . . . 16
1.6.2 Functions on finite sets . . . . . . . . . . . . . . . . 16
1.7 d-regular partitions . . . . . . . . . . . . . . . . . . . . . . . 18
1.8 Zigzag permutations . . . . . . . . . . . . . . . . . . . . . . 21
1.8.1 Zigzag permutations and trees . . . . . . . . . . . . 23
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2 Generating functions 33
2.1 On the generating functions in general . . . . . . . . . . . . 33
2.2 Operations on generating functions . . . . . . . . . . . . . . 35
2.2.1 Addition and multiplication . . . . . . . . . . . . . 35
2.2.2 Some additional transformations . . . . . . . . . . . 38
2.2.3 Differentiation and integration . . . . . . . . . . . . 38
2.2.4 Where do the name generating functions
come from? . . . . . . . . . . . . . . . . . . . . . . . 40
2.3 The binomial transformation . . . . . . . . . . . . . . . . . 42
2.4 Applications of the above techniques . . . . . . . . . . . . . 45
2.4.1 The exponential generating function of the Bell
numbers . . . . . . . . . . . . . . . . . . . . . . . . 45
2.4.2 Dobi´nski’s formula . . . . . . . . . . . . . . . . . . . 46
2.4.3 The exponential generating function of the second
kind Stirling numbers . . . . . . . . . . . . . . . . . 46
2.4.4 The ordinary generating function of the second kind
Stirling numbers . . . . . . . . . . . . . . . . . . . . 49
2.4.5 The generating function of the Bell numbers and a
formula for . . . . . . . . . . . 50
2.4.6 The exponential generating function of the first kind
Stirling numbers . . . . . . . . . . . . . . . . . . . . 52
2.4.7 Some particular lower parameters of the first kind
Stirling numbers . . . . . . . . . . . . . . . . . . . . 52
2.5 Additional identities coming from the generating functions . 53
2.6 Orthogonality . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.7 Horizontal generating functions and polynomial identities . 59
2.7.1 Special values of the Stirling numbers of the first kind
– second approach . . . . . . . . . . . . . . . . . . . 63
2.8 The Lah numbers . . . . . . . . . . . . . . . . . . . . . . . . 64
2.8.1 The combinatorial meaning of the Lah numbers . . 66
2.9 The total number of ordered lists and the horizontal sum of
the Lah numbers . . . . . . . . . . . . . . . . . . . . . . . . 68
2.10 The Hankel transform . . . . . . . . . . . . . . . . . . . . . 70
2.10.1 The Euler-Seidel matrices . . . . . . . . . . . . . . . 71
2.10.2 A generating function tool to calculate the Hankel
transform . . . . . . . . . . . . . . . . . . . . . . . . 73
2.10.3 Another tool to calculate the Hankel transform
involving orthogonal polynomials . . . . . . . . . . 75
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3 The Bell polynomials 85
3.1 Basic properties of the Bell polynomials . . . . . . . . . . . 85
3.1.1 A recursion . . . . . . . . . . . . . . . . . . . . . . . 85
3.1.2 The exponential generating function . . . . . . . . . 86
3.2 About the zeros of the Bell polynomials . . . . . . . . . . . 88
3.2.1 The real zero property . . . . . . . . . . . . . . . . 88
3.2.2 The sum and product of the zeros of Bn(x) . . . . . 89
3.2.3 The irreducibility of Bn(x) . . . . . . . . . . . . . . 90
3.2.4 The density of the zeros of Bn(x) . . . . . . . . . . 90
3.2.5 Summation relations for the zeros of Bn(x) . . . . . 92
3.3 Generalized Bell polynomials . . . . . . . . . . . . . . . . . 95
3.4 Idempotent numbers and involutions . . . . . . . . . . . . . 96
3.5 A summation formula for the Bell polynomials . . . . . . . 99
3.6 The Fa`a di Bruno formula . . . . . . . . . . . . . . . . . . . 99
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4 Unimodality, log-concavity, and log-convexity 105
4.1 “Global behavior” of combinatorial sequences . . . . . . . . 105
4.2 Unimodality and log-concavity . . . . . . . . . . . . . . . . 106
4.3 Log-concavity of the Stirling numbers of the second kind . . 109
4.4 The log-concavity of the Lah numbers . . . . . . . . . . . . 112
4.5 Log-convexity . . . . . . . . . . . . . . . . . . . . . . . . . . 114
4.5.1 The log-convexity of the Bell numbers . . . . . . . . 114
4.5.2 The Bender-Canfield theorem . . . . . . . . . . . . 115
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5 The Bernoulli and Cauchy numbers 123
5.1 Power sums . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.1.1 Power sums of arithmetic progressions . . . . . . . . 126
5.2 The Bernoulli numbers . . . . . . . . . . . . . . . . . . . . . 126
5.2.1 The Bernoulli polynomials . . . . . . . . . . . . . . 128
5.3 The Cauchy numbers and Riordan arrays . . . . . . . . . . 130
5.3.1 The Cauchy numbers of the first and second kind . 130
5.3.2 Riordan arrays . . . . . . . . . . . . . . . . . . . . . 132
5.3.3 Some identities for the Cauchy numbers . . . . . . . 134
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
6 Ordered partitions 141
6.1 Ordered partitions and the Fubini numbers . . . . . . . . . 141
6.1.1 The definition of the Fubini numbers . . . . . . . . 141
6.1.2 Two more interpretations of the Fubini numbers . . 142
6.1.3 The Fubini numbers count chains of subsets . . . . 143
6.1.4 The generating function of the Fubini numbers . . . 143
6.1.5 The Hankel determinants of the Fubini numbers . . 144
6.2 Fubini polynomials . . . . . . . . . . . . . . . . . . . . . . . 145
6.3 Permutations, ascents, and the Eulerian numbers . . . . . . 147
6.3.1 Ascents, descents, and runs . . . . . . . . . . . . . . 148
6.3.2 The definition of the Eulerian numbers . . . . . . . 149
6.3.3 The basic recursion for the Eulerian numbers . . . . 150
6.3.4 Worpitzky’s identity . . . . . . . . . . . . . . . . . . 150
6.3.5 A relation between Eulerian numbers and Stirling
numbers . . . . . . . . . . . . . . . . . . . . . . . . 152
6.4 The combination lock game . . . . . . . . . . . . . . . . . . 153
6.5 Relations between the Eulerian and Fubini polynomials . . 155
6.6 An application of the Eulerian polynomials . . . . . . . . . 157
6.7 Differential equation of the Eulerian polynomials . . . . . . 158
6.7.1 An application of the Fubini polynomials . . . . . . 159
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
7 Asymptotics and inequalities 167
7.1 The Bonferroni-inequality . . . . . . . . . . . . . . . . . . . 168
7.2 The asymptotics of the second kind Stirling numbers . . . . 170
7.2.1 First approach . . . . . . . . . . . . . . . . . . . . . 170
7.2.2 Second approach . . . . . . . . . . . . . . . . . . . . 172
7.3 The asymptotics of the maximizing index of the Stirling
numbers of the second kind . . . . . . . . . . . . . . . . . . 173
7.3.1 The Euler Gamma function and the Digamma
function . . . . . . . . . . . . . . . . . . . . . . . . 174
7.3.2 The asymptotics of Kn . . . . . . . . . . . . . . . . 175
7.4 The asymptotics of the first kind Stirling numbers and Bell
numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
7.5 The asymptotics of the Fubini numbers . . . . . . . . . . . 179
7.6 Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7.6.1 Polynomials with roots inside the unit disk . . . . . 181
7.6.2 Polynomials and interlacing zeros . . . . . . . . . . 182
7.6.3 Estimations on the ratio of two consecutive sequence
elements . . . . . . . . . . . . . . . . . . . . . . . . 182
7.6.4 Dixon’s theorem . . . . . . . . . . . . . . . . . . . . 184
7.6.5 Colucci’s theorem and the Samuelson–Laguerre
theorem and estimations for the leftmost zeros of
polynomials . . . . . . . . . . . . . . . . . . . . . . 185
7.6.6 An estimation between two consecutive Fubini
numbers via Lax’s theorem . . . . . . . . . . . . . . 189
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
II Generalizations of our counting sequences 195
8 Prohibiting elements from being together 197
8.1 Partitions with restrictions – second kind r-Stirling numbers 197
8.2 Generating functions of the r-Stirling numbers . . . . . . . 200
8.3 The r-Bell numbers and polynomials . . . . . . . . . . . . . 204
8.4 The generating function of the r-Bell polynomials . . . . . . 207
8.4.1 The hypergeometric function . . . . . . . . . . . . . 207
8.5 The r-Fubini numbers and r-Eulerian numbers . . . . . . . 210
8.6 The r-Eulerian numbers and polynomials . . . . . . . . . . 215
8.7 The combinatorial interpretation of the r-Eulerian numbers 218
8.8 Permutations with restrictions – r-Stirling numbers of the first
kind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
8.9 The hyperharmonic numbers . . . . . . . . . . . . . . . . . 225
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
9 Avoidance of big substructures 239
9.1 The Bessel numbers . . . . . . . . . . . . . . . . . . . . . . 239
9.2 The generating functions of the Bessel numbers . . . . . . . 240
9.3 The number of partitions with blocks of size at most two . 242
9.4 Young diagrams and Young tableaux . . . . . . . . . . . . . 244
9.5 The differential equation of the Bessel polynomials . . . . . 247
9.6 Blocks of maximal size m . . . . . . . . . . . . . . . . . . . 249
9.7 The restricted Bell numbers . . . . . . . . . . . . . . . . . . 251
9.8 The gift exchange problem . . . . . . . . . . . . . . . . . . . 252
9.9 The restricted Stirling numbers of the first kind . . . . . . . 255
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
10 Avoidance of small substructures 267
10.1 Associated Stirling numbers of the second kind . . . . . . . 267
10.1.1 The associated Bell numbers and polynomials . . . 271
10.2 The associated Stirling numbers of the first kind . . . . . . 273
10.2.1 The associated factorials An,≥m . . . . . . . . . . . 274
10.2.2 The derangement numbers . . . . . . . . . . . . . . 275
10.3 Universal Stirling numbers of the second kind . . . . . . . . 279
10.4 Universal Stirling numbers of the first kind . . . . . . . . . 284
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
III Number theoretical properties 295
11 Congruences 297
11.1 The notion of congruence . . . . . . . . . . . . . . . . . . . 297
11.2 The parity of the binomial coefficients . . . . . . . . . . . . 298
11.2.1 The Stolarsky-Harborth constant . . . . . . . . . . 299
11.3 Lucas congruence for the binomial coefficients . . . . . . . . 299
11.4 The parity of the Stirling numbers . . . . . . . . . . . . . . 301
11.5 Stirling numbers with prime parameters . . . . . . . . . . . 303
11.5.1 Wilson’s theorem . . . . . . . . . . . . . . . . . . . 304
11.5.2 Wolstenholme’s theorem . . . . . . . . . . . . . . . 305
11.5.3 Wolstenholme’s theorem for the harmonic numbers 305
11.5.4 Wolstenholme’s primes . . . . . . . . . . . . . . . . 306
11.5.5 Wolstenholme’s theorem for Hp−1,2 . . . . . . . . . 306
11.6 Lucas congruence for the Stirling numbers of both kinds . . 309
11.6.1 The first kind Stirling number case . . . . . . . . . 309
11.6.2 The second kind Stirling number case . . . . . . . . 311
11.7 Divisibility properties of the Bell numbers . . . . . . . . . . 311
11.7.1 Theorems about Bp and Bp+1 . . . . . . . . . . . . 311
11.7.2 Touchard’s congruence . . . . . . . . . . . . . . . . 312
11.8 Divisibility properties of the Fubini numbers . . . . . . . . 313
11.8.1 Elementary congruences . . . . . . . . . . . . . . . 313
11.8.2 A Touchard-like congruence . . . . . . . . . . . . . 314
11.8.3 The Gross-Kaufman-Poonen congruences . . . . . . 315
11.9 Kurepa’s conjecture . . . . . . . . . . . . . . . . . . . . . . 316
11.10 The non-integral property of the harmonic and hyperharmonic
numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
11.10.1 Hn is not integer when n > 1 . . . . . . . . . . . . . 319
11.10.2 The 2-adic norm of the hyperharmonic numbers . . 321
11.10.3 H1 + H2 + ・ ・ ・ + Hn is not integer when n > 1 . . . 323
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
12 Congruences via finite field methods 341
12.1 An application of the Hankel matrices . . . . . . . . . . . . 341
12.2 The characteristic polynomials . . . . . . . . . . . . . . . . 344
12.2.1 Representation of mod p sequences via the zeros of
their characteristic polynomials . . . . . . . . . . . 345
12.2.2 The Bell numbers modulo 2 and 3 . . . . . . . . . . 346
12.2.3 General periodicity modulo p . . . . . . . . . . . . . 348
12.2.4 Shortest period of the Fubini numbers . . . . . . . . 350
12.3 The minimal polynomial . . . . . . . . . . . . . . . . . . . . 350
12.3.1 The Berlekamp – Massey algorithm . . . . . . . . . 351
12.4 Periodicity with respect to composite moduli . . . . . . . . 354
12.4.1 Chinese remainder theorem . . . . . . . . . . . . . . 354
12.4.2 The Bell numbers modulo 10 . . . . . . . . . . . . . 355
12.5 Value distributions modulo p . . . . . . . . . . . . . . . . . 356
12.5.1 The Bell numbers modulo p . . . . . . . . . . . . . 356
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
13 Diophantic results 363
13.1 Value distribution in the Pascal triangle . . . . . . . . . . . 363
13.1.1 Lind’s construction . . . . . . . . . . . . . . . . . . 363
13.1.2 The number of occurrences of a positive integer . . 366
13.1.3 Singmaster’s conjecture . . . . . . . . . . . . . . . . 367
13.2 Equal values in the Pascal triangle . . . . . . . . . . . . . . 368
13.2.1 The history of the equation . . 368
13.2.2 The particular case . . 368
13.3 Value distribution in the Stirling triangles . . . . . . . . . . 369
13.3.1 Stirling triangle of the second kind . . . . . . . . . 369
13.3.2 Stirling triangle of the first kind . . . . . . . . . . . 371
13.4 Equal values in the Stirling triangles and some related
diophantine equations . . . . . . . . . . . . . . . . . . . . . 372
13.4.1 The Ramanujan-Nagell equation . . . . . . . . . . . 372
13.4.2 The diophantine equation 373
13.4.3 A diophantic equation involving factorials and
triangular numbers . . . . . . . . . . . . . . . . . . 374
13.4.4 The Klazar – Luca theorem . . . . . . . . . . . . . . 374
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
Appendix 381
Basic combinatorial notions . . . . . . . . . . . . . . . . . . . . . . 381
The polynomial theorem . . . . . . . . . . . . . . . . . . . . . . . 384
The Lambert W function . . . . . . . . . . . . . . . . . . . . . . . 386
Formulas 387
Tables 405
Bibliography 433
Index 473