### The Rules, informally

Sum rule: add up sizes of disjoint sets to get size of union

(Generalized) Product rule: when making a sequence of choices, multiply the number of choices at each step to get the number of overall choices for the sequence

Bijection rule: you can count a set by counting a different set of the same size

Permutation rule: the number of ways to choose k out of n items **when order matters** is $$P(n,k)=\frac{n!}{(n-k)!}$$

Subset/combination rule: the number of ways to choose k out of n items **when order does *not* matter** is $$\binom{n}{k}=\frac{n!}{k!(n-k)!}$$

### Demo 1
Out of $$n$$ available servers, $$k$$ are to be deployed, with one acting as the primary server. Explain how to count the number of ways to do this in two different ways to show that $$k\binom{n}{k} = n\binom{n-1}{k-1}$$.

### Solution
Plan for choosing deployed and primary servers:

1. Choose k of the n servers to deploy: $$\binom{n}{k}$$ ways
2. Choose 1 of those k deployed servers to be primary: k ways (also equals $$\binom{k}{1}$$)

Total number of ways (by product rule): $$\binom{n}{k}k$$

Alternate plan:

1. Choose 1 of the n servers to be primary (and thus also deployed): n ways
2. Choose k-1 of the remaining n-1 servers to be deployed (and not primary): $$\binom{n-1}{k-1}$$

Total number of ways (by product rule): $$n\binom{n-1}{k-1}$$

Bonus alternate plan:

1. Choose k-1 of the n servers to be deployed but not primary: $$\binom{n}{k-1}$$
2. Choose 1 of the remaining n-(k-1) servers to be primary (and also deployed): n-k+1 ways

Total number of ways (by product rule): $$\binom{n}{k-1}(n-k+1)$$