Permutations, arrangements and combinations

Filling k ordered slots one at a time, with the pool of remaining eligible objects shrinking by one after every slot, is exactly the setting of the multiplication rule for independent sequential steps.

Step 1 (set up the positions): label the $k$ positions to be filled, in order, as position 1 through position $k$. Filling each position with one of the $n$ objects, without reusing an object already placed, is a task made of $k$ successive steps.

Step 2 (apply the multiplication rule): position 1 can be filled in $n$ ways. Once it is filled, one object has been used, so position 2 can be filled in $n-1$ ways, regardless of which object filled position 1. Continuing this way, position $k$ can be filled in $n-k+1$ ways, since $k-1$ objects have already been used. By the multiplication rule, the total count is the product $n(n-1)\cdots(n-k+1)$.

Step 3 (rewrite as a factorial quotient): multiplying and dividing by the missing tail $(n-k)!$ gives $n(n-1)\cdots(n-k+1) = \frac{n(n-1)\cdots(n-k+1)\cdot (n-k)!}{(n-k)!} = \frac{n!}{(n-k)!}$, which is exactly $A_n^k = \frac{n!}{(n-k)!}$.

Step 4 (special case $k=n$): substituting $k=n$ gives $A_n^n = \frac{n!}{0!} = \frac{n!}{1} = n!$ using $0! = 1$, which recovers the permutation count $P_n = n!$.

Every unordered subset of size k can be turned into an ordered arrangement in exactly k! ways, so the ordered count over-counts each subset by the same factor k!; dividing removes the over-counting.

Step 1 (group arrangements by their underlying subset): every arrangement of $k$ objects out of $n$ first selects some $k$-element subset and then orders it. Group the $A_n^k$ arrangements into buckets, one bucket per possible $k$-element subset, so that two arrangements land in the same bucket exactly when they use the same set of objects.

Step 2 (size of each bucket): fixing one $k$-element subset, the arrangements built from it correspond exactly to the orderings of that subset, and there are $k!$ such orderings (a permutation of $k$ objects). So every bucket has exactly $k!$ arrangements.

Step 3 (addition rule across buckets): the buckets are disjoint (an arrangement belongs to exactly one bucket) and there are $C_n^k$ buckets by definition, each of size $k!$. The addition rule ($k!$ added to itself $C_n^k$ times) gives $A_n^k = C_n^k \cdot k!$.

Step 4 (solve for the combination count): dividing both sides by $k!$ and substituting $A_n^k = \frac{n!}{(n-k)!}$ gives $C_n^k = \dfrac{A_n^k}{k!}$, that is $C_n^k = \frac{n!}{k!(n-k)!}$.

This is the addition rule in disguise: splitting all size-k subsets by whether or not they contain one fixed element gives two disjoint cases whose counts add up.

Step 1 (fix one element and split by membership): fix one object $x$ among the $n$ objects. Every $k$-element subset either contains $x$ or does not; these two cases are disjoint and together cover all $C_n^k$ subsets.

Step 2 (count subsets containing x): a subset containing $x$ is formed by choosing the remaining $k-1$ elements from the other $n-1$ objects, giving $C_{n-1}^{k-1}$ such subsets.

Step 3 (count subsets not containing x): a subset avoiding $x$ is formed by choosing all $k$ elements from the remaining $n-1$ objects, giving $C_{n-1}^k$ such subsets.

Step 4 (apply the addition rule): since the two cases are disjoint and exhaust all size-k subsets, the addition rule gives $C_n^k = C_{n-1}^{k-1} + C_{n-1}^k$.