Distribution or drawing — slips and balls

The same four formulae can be told with two different mental pictures. It matters to keep them apart: mixing them is the commonest source of confusion.

Two models, same formulae

• Distribution (slips). I have $k$ slips in hand and I hand them out to $n$ people. The slips are all placed; some people may stay empty-handed. → $k$ = slips (objects), $n$ = people (destinations). This is the functions model $f:K\to N$.
• Drawing (balls). I have an urn with $n$ balls and I draw $k$ of them. → $n$ = balls in the urn, $k$ = draws.

Careful not to merge the two stories: “I draw $k$ slips from an urn of $n$” is an incorrect hybrid. Slips are distributed (to people); balls are drawn (from an urn). They are different physical stories leading to the same formulae.

How they correspond

In the urn model, the $k$ draws play the role of the slips (the domain) and the $n$ balls that of the people (the codomain). The two questions become:

• with / without replacement ↔ more than one / at most one per person (a ball may recur or not);
• order matters / does not matter ↔ numbered / blank slips.

drawing $k$ balls from $n$	formula	slips
ordered, with replacement	$n^k$	numbered, more than one
ordered, without replacement	$\dfrac{n!}{(n-k)!}$	numbered, at most 1
unordered, with replacement	$\dbinom{n+k-1}{k}$	blank, more than one
unordered, without replacement	$\dbinom{n}{k}$	blank, at most 1

The three readings of $\binom{n}{k}$

The same number $\dbinom{n}{k}$ answers three seemingly different questions:

• subsets: how many $k$-element subsets a set of $n$ has;
• drawing (urn): in how many ways you draw $k$ balls from a bag of $n$, order not counting;
• distribution (slips): in how many ways you distribute $k$ blank slips to $n$ people, at most one each.

They are the same thing seen from three sides. For instance, drawing $2$ balls from $5$ (order not counting) gives the $\dbinom{5}{2}=10$ pairs $\{1,2\},\{1,3\},\dots,\{4,5\}$.

Order or not: $8$ balls, draw $4$

From an urn with $8$ numbered balls I draw $4$ counting the order (e.g. $4242$ differs from $4422$):

• with replacement: $8^4 = 4096$;
• without replacement: $\dfrac{8!}{4!} = 8\cdot 7\cdot 6\cdot 5 = 1680$.

If instead the order did not matter, without replacement I would have $\dbinom{8}{4}=70$.

Links

Topics: Combinatorics
Concepts: Combinations · Arrangements
Methods: Slips table
Skills: Combinatorial calculus · Modelling