Ross, chapter 1: Combinatorial analysis (pp 13–33)
Notes on the text
1.1 "Combinatorial analysis" is nerd talk for "counting."
1.2 The "basic principle": independent possibilities multiply.
Suppose that two experiments are to be performed. Then if experiment 1 can result in any one of \(m\) possible outcomes and if, for each outcome of experiment 1, there are \(n\) possible outcomes of experiment 2, then together there are \(mn\) possible outcomes of the two experiments.
"We can prove this is how you count things by enumerating them, pretending that 'enumerating' isn't just another way to say 'counting.'"
1.3 Permutations
Suppose you have $n$ but some of them are indistinguishable. There are $n_1$ indistinguishable items of one type, and $n_2$ indistinguishable items of another type, for a total of $r$ types of things. Then the number of distinct permutations is \[ \text{number of permutations} = \frac{n!}{n_1!n_2!\cdots n_r!} \]
This includes $n!$ permutations of $n$ distinct objects.
1.4 Combinations
If I have $n$ things and I want to select $r$ of them into a group, the number of possible groups is $$ \text{number of groups} = {n \choose r} = \frac{n!}{r!(n-r)!}. $$
Pascal's identity tells you something about adding one more item to a collection: $$ {n\choose r} = {n-1\choose r-1} + {n-1\choose r}. $$ Proof (mostly quoted):
Suppose I pick are particular object from a group of $n$, like object number $A$. There are ${n-1\choose r-1}$ groups of size $r$ which include object $A$, because object $A$ is already accounted for, and ${n-1\choose r}$ groups of size $r$ which exclude object $A$. These have to add up to $n\choose r$ groups – which they do, if you work through the algebra.
These are the "binomial coefficients," which you can prove several ways.
1.5 Multinomial coefficients
The multinomial coefficients $$ {n\choose n_1, n_2, \cdots n_r} = \frac{n!}{n_1!n_2!\cdots n_r!} $$ have the same rule as the number of permutations of partially-distinguishable lists of objects. We also have a "multinomial theorem": $$ (x_1 + x_2 + \cdots + x_k)^n = \sum {n \choose n_1,n_2,\cdots n_k} x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k} $$ where the sum is taken over all the combinations $(n_1,n_2,\cdots n_k)$ which add up to $n$ total items.
1.6 The number of integer solutions to an equation.
How many terms are in the sum above, with $ n_1 + n_2 + \cdots + n_r = n $? I've encountered this before (or something like it) in old notes about multiplicity and entropy in Einstein solids.
The result here is that there are $n-1\choose r-1$ solutions with $n_i > 0$, and $n+r-1\choose r-1$ solutions with $n_i \geq 0$. The argument has to do with how many ways you can insert partitions into a string of identical characters, so that each substring represents several identical items.
Problems
Self-test problems
19: License plate permutations.
If there are no restrictions on where the digits and letters are placed, how many 8-place license plates consisting of 5 letters and 3 digits are possible if no repetitions of letters or digits are allowed? What if the 3 digits must be consecutive?
With no restrictions, there are $26\choose5$ sets of letters and $10\choose3$ sets of numbers, which can be ordered in $8!$ ways. Total is
>>> from math import comb, factorial >>> comb(26,5) * comb(10,3) * factorial(8) 318269952000
If the digits must be consecutive, you have to permute the letters and numbers separately, and then there are $5+1=6$ places to insert the three consecutive digits:
>>> comb(26,5) * comb(10,3) * factorial(5) * factorial(3) * 6 34100352000
These are $3.2\times10^{11}$ and $3.4\times10^{10}$, respectively. The textbook gives the same results using slightly different logic.