Enumerative Combinatorics presents elaborate and systematic coverage of the theory of enumeration. The first seven chapters provide the necessary background, including basic counting principles and techniques, elementary enumerative topics, and an extended presentation of generating functions and recurrence relations. The remaining seven chapters focus on more advanced topics, including, Stirling numbers, partitions of integers, partition polynomials, Eulerian numbers and Polya's counting theorem.Extensively classroom tested, this text was designed for introductory- and intermediate-level courses in enumerative combinatorics, but the far-reaching applications of the subject also make the book useful to those in operational research, the physical and social science, and anyone who uses combinatorial methods. Remarks, discussions, tables, and numerous examples support the text, and a wealth of exercises-with hints and answers provided in an appendix--further illustrate the subject's concepts, theorems, and applications.
Author(s): Charalambos A. Charalambides
Series: Discrete Mathematics and Its Applications
Edition: 1
Publisher: Chapman and Hall//CRC
Year: 2002
Language: English
Pages: 624
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
