Combinatorics and Number Theory of Counting Sequences PDF by Istvan Mezo

By

Combinatorics and Number Theory of Counting Sequences
By Istvan Mezo

Combinatorics and Number Theory of Counting Sequences

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

This book is US$10
To get free sample pages OR Buy this book


Share this Book!

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.