I Counting: Basic ............................................ 1
1 Subsets of a Set ........................................ 3
2 Pascal's Triangle ....................................... 5
3 Binomial Coefficient Identities ........................ 11
II Counting: Intermediate .................................... 19
4 Finding a Polynomial ................................... 21
5 The Upward-Extended Pascal's Triangle .................. 25
6 Recurrence Relations and Fibonacci Numbers ............. 27
III Counting: Advanced ........................................ 37
7 Generating Functions and Making Change ................. 39
8 Integer Triangles ...................................... 49
9 Rook Paths and Queen Paths ............................. 53
IV Discrete Probability ...................................... 65
10 Probability Spaces and Distributions ................... 67
11 Markov Chains .......................................... 81
12 Random Tournaments ..................................... 91
V Number Theory ............................................. 95
13 Divisibility of Factorials and Binomial Coefficients ... 97
14 Covering Systems ...................................... 103
13 Partitions of an Integer .............................. 109
VI Information Theory ....................................... 121
16 What Is Surprise? ..................................... 123
17 A Coin-Tossing Game ................................... 133
18 Shannon's Theorems .................................... 139
VII Games .................................................... 153
19 A Little Graph Theory Background ...................... 155
20 The Ramsey Game ....................................... 165
21 Tic-Tac-Toe and Animal Games .......................... 173
VIII Algorithms ............................................... 181
22 Counters .............................................. 183
23 Listing Permutations and Combinations ................. 187
24 Sudoku Solving and Polycube Packing ................... 193
A Hints and Solutions to Exercises ........................... 201
В Notation ................................................... 259
Bibliography .................................................. 261
Index ......................................................... 263
| 
