Enumerative combinatorics

cover
......Page 1
Preface......Page 8
The Author......Page 12
Contents......Page 16
1.1   Introduction......Page 20
1.2.1   Basic notions......Page 22
1.2.2   Cartesian product......Page 24
1.2.4   Maps......Page 26
1.2.6   Set  operations......Page 28
1.2.7   Divisions  and partitions of a  set......Page 32
1.3   The principles  of addition  and multiplication......Page 33
1.4   Discrete probability......Page 43
1.5   Sums and products......Page 46
1.6   Bibliographic notes......Page 54
1.7   Exercises......Page 55
2.1   Introduction  0......Page 58
2.2   Permutations......Page 59
2.3   Combinations     0......Page 70
2.4   Divisions  and partitions  of a  finite  set......Page 81
2.5   Integer  solutions of a  linear equation......Page 87
2.6   Lattice paths......Page 94
2.7.1   Classical problems  in  discrete probability......Page 101
2.7.2   Ordered and unordered  samples 0......Page 105
2.7.3   Probability models  in  statistical mechanics......Page 108
2.8   Bibliographic notes......Page 109
2.9   Exercises......Page 110
3.1   Introduction......Page 122
3.2   Factorials......Page 123
3.3   Binomial  coefficients......Page 129
3.4   Multinomial  coefficients......Page 142
3.6   Exercises......Page 143
4.1    Introduction......Page 150
4.2   Number  of elements  in  a union  of sets......Page 151
4.3   Number  of elements in a  given number  of sets......Page 163
4.4   Bonferroni  inequalities......Page 171
4.5   Number  of elements of a  given rank......Page 174
4.6   Bibliographic notes......Page 177
4. 7   Exercises......Page 178
5.2   Permutations with  fixed  points......Page 188
5.3   Ranks  of permutations......Page 193
5.4   Permutations with  successions......Page 195
5.5   Circular permutations  with  successions......Page 199
5.7   Exercises......Page 203
6.1   Introduction......Page 210
6.2.1     Definitions  and basic  properties......Page 211
6.2.2     Power,  factorial  and Lagrange series......Page 221
6.3   Combinations  and permutations......Page 227
6.4   Moment  generating functions......Page 234
6.5   Multivariate  generating functions......Page 238
6.7   Exercises......Page 242
7.2   Basic notions......Page 252
7.3   Recurrence relations  of the  first  order......Page 254
7.4   The method  of characteristic roots......Page 258
7.5   The method of generating functions......Page 269
7.7   Exercises......Page 283
8.1   Introduction......Page 296
8.2   Stirling numbers  of the  first  and  second kind......Page 297
8.3   Explicit  expressions and  recurrence relations......Page 308
8.4   Generalized factorial  coefficients......Page 320
8.5   Non-central  Stirling and related  numbers......Page 333
8.6   Bibliographic notes......Page 338
8.7   Exercises......Page 340
9.1   Introduction......Page 358
9.2   Classical occupancy  and modifications......Page 359
9.3   Ordered  distributions  and occupancy......Page 367
9.4   Balls of general  specification and distinguishable urns......Page 369
9.5   Generating functions......Page 372
9.6   Bibliographic notes......Page 377
9.7   Exercises......Page 378
10.1  Introduction......Page 388
10.2  Recurrence relations  and generating functions......Page 389
10.3  A universal  generating function......Page 395
10.4  Interrelations among partition  numbers......Page 402
10.5  Combinatorial identities......Page 410
10.7  Exercises......Page 415
11.1  Introduction......Page 430
11.2  Exponential Bell  partition  polynomials......Page 431
11.3  General partition  polynomials......Page 438
11.4  Logarithmic partition polynomials......Page 443
11.5  Potential partition polynomials......Page 447
11.6  Inversion of power  series......Page 452
11.7  Touchard polynomials......Page 461
11.8  Bibliographic notes......Page 466
11.9  Exercises......Page 467
12.1  Introduction......Page 480
12.2  Permutations with  a  given number  of cycles......Page 481
12.3  Even  and odd permutations......Page 487
12.4  Permutations with  partially  ordered  cycles......Page 490
12.6  Exercises......Page 497
13.1  Introduction......Page 506
13.2  Cycle indicator of a permutation  group......Page 507
13.3  Orbits of elements of a finite  set......Page 512
13.4  Models  of colorings of a finite  set......Page 518
13.6  Exercises......Page 526
14.2  Eulerian  numbers......Page 532
14.3  Carlitz numbers......Page 541
14.4  Permutations with  a  given number  of runs......Page 549
14.5  Permutations with  repetition  and  a  given number  of runs......Page 552
14.6  Bibliographic  notes......Page 556
14.7  Exercises......Page 557
HINTS  AND  ANSWERS  TO EXERCISES......Page 564
BIBLIOGRAPHY......Page 610
INDEX......Page 620