Introduction to Combinatorics (Chapman and Hall Mathematics Series)

Contents......Page 5
Why combinatorics?......Page 8
Counting problems......Page 9
What you need to know......Page 10
Are you sitting comfortably?......Page 11
Acknowledgements......Page 12
1.2 Permutations......Page 13
1.3 Combinations......Page 17
1.4 Applications to probability problems......Page 23
2.1 Double counting......Page 31
2.2 Derangements......Page 37
3.1 What are partitions?......Page 41
3.2 Dot diagrams......Page 44
3.3 What is a formula?......Page 48
3.4 A lower bound for p_k(n)......Page 52
4.1 Asymptotic functions......Page 55
4.2 Stirling\'s formula......Page 59
4.3 A note on James Stirling......Page 66
4.4 A lower bound for p(n)......Page 67
5.1 Introduction......Page 70
5.2 Generating functions......Page 74
5.3 Applications to partition numbers......Page 78
5.4 Euler\'s identity......Page 82
5.5 The Hardy-Ramanujan formula......Page 85
5.6 The story of Hardy and Ramanujan......Page 88
6.1 What is a recurrence relation?......Page 92
6.2 The use of generating functions......Page 94
6.3 Homogeneous linear recurrence relations......Page 98
6.4 Inhomogenous linear recurrence relations......Page 105
6.5 Some non-linear recurrence relations......Page 112
6.6 Partial fractions......Page 116
7.1 Permutations......Page 121
7.2 Groups of permutations......Page 125
7.3 Symmetry groups......Page 132
7.4 Subgroups and Lagrange\'s Theorem......Page 135
7.5 Orders of group elements......Page 141
7.6 The orders of permutations......Page 143
8.1 Colourings......Page 148
8.2 The axioms for group actions......Page 151
8.3 Orbits......Page 154
8.4 Stabilizers......Page 156
9.1 What are graphs?......Page 162
9.2 Labelled graphs......Page 166
10.1 Burnside\'s Theorem......Page 170
10.2 Applications of Burnside\'s Theorem......Page 172
11.1 Colourings and group actions......Page 179
11.2 Pattern inventories......Page 182
11.3 The cycle index of a group......Page 185
11.4 Pólya\'s Theorem: statement and examples......Page 189
11.5 Pólya\'s Theorem: the proof......Page 193
11.6 Counting simple graphs......Page 197
11.7 Conclusion......Page 205
Supplementary exercises......Page 206
Solutions......Page 215
Suggestions for further reading......Page 277
List of special symbols......Page 279
Index......Page 281