Partitions and Permutations

How many ways can you arrange 5 books on a shelf? Easy: $ 5 \times 4 \times 3 \times 2 \times 1 \equiv 5! $ This is a permutation.

Now, how many ways can you pull 4 books from a stack of 10? This is the same as partitioning the ten books into a stack on the shelf, and a stack in your hands.   An ambiguity arises: does the order of the books drawn, matter?  If no matter, then we want the number of ways all the books can be permuted, divided by the number of ways the books on the shelf can be permuted, divided again by the number of ways the books in hand can be permuted:

$$
\frac{10!}{4! \, 6!}
$$

This is sometimes referred to as a combination: the order of selection does not matter.  If the order of books drawn does matter,  then those permutations must not be divided out:  $ \frac {10!} {6!}$, and this kind of selection is called a permutation.

To generalize: the number of ways to permute N things is $N!$ and if some number of those things are identical, divide out those permutations:  $ \frac{N!}{ n_1! \, n_2! \, n_3! \, ... }$

What if we allow replacement?  Like with a combination lock, where we select 3 numbers but the same number can appear all three times.  This situation can not be understood as a partition, but this case is simple: if we have K slots that can take N different values, the number of possibilities is $N^K$.

If, however, we allow replacement but order does not matter, the situation becomes more difficult to count.  For that case, the trick is to observe that choosing, say, four from 10 things is the same as tossing four (indentical) things into 10 bins.  In other words, how many ways can you permute 4 X's with 9 partitions?   X|  |  |  |X|  |  |XX|  |  |