Permutations, Combinations, and Sampling

Six students are available. How many ways can we select a president and a secretary, with no student taking both jobs? How many ways can we select a two-person committee?

The selected names alone determine the committee. They do not determine the officers: assigning Ari as president and Bo as secretary differs from reversing the jobs. We need to decide what constitutes one outcome before choosing a formula.

Ordered Selections

Definition

Permutations / Ordered Selections

For integers $0\leq k\leq n$ , an ordered selection of $k$ distinct objects from a set of $n$ is a list of length $k$ , drawn from that set, with no repetition. A permutation of all $n$ objects is an ordered selection with $k=n$ .

Theorem (Permutation Theorem)

For integers $0\leq k\leq n$ , the number of ordered selections of $k$ objects from $n$ is

$(n)_k=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.$

Proof

Count via the product rule. Fill list positions $1,\ldots,k$ in order. At position $i$ (for $i=1,\ldots,k$ ), the preceding $i-1$ positions have already been filled with $i-1$ distinct objects, so exactly $n-i+1$ objects remain (a count depending only on $i$ , not on which $i-1$ objects were chosen earlier), so the product rule applies with $n_i=n-i+1$ for $i=1,\ldots,k$ , giving $n_1n_2\cdots n_k=n(n-1)\cdots(n-k+1)$ .
Match the factorial form, $0<k<n$ . In $\frac{n!}{(n-k)!}=\frac{n(n-1)\cdots(n-k+1)\cdot(n-k)!}{(n-k)!},$ the factor $(n-k)!$ cancels, leaving exactly the product from step 1.
Boundary case $k=0$ . Both sides equal one: the product in step 1 is an empty product, and there is exactly one length-zero list, the empty list.
Boundary case $k=n$ . The denominator is $(n-n)!=0!=1$ , so the formula gives $n!$ , matching step 1's product run out to position $i=n$ , where $n_n=n-n+1=1$ .
Boundary case $k>n$ . No list of $k$ distinct objects can be drawn from only $n$ available objects: by step 1, position $i=n+1$ would need $n_i=n-i+1=0$ remaining objects to choose from — zero choices — and $n+1\leq k$ since $k>n$ . So the count is $0$ , not a factorial with a negative argument, which is undefined.

The notation $(n)_k$ is a falling factorial here. Other references may use different conventions.

∎

Definition

Combinations / Unordered Selections

For integers $0\leq k\leq n$ , a combination of size $k$ from a set of $n$ objects is a $k$ -element subset of it. The number of such subsets is written $\binom nk,$ read " $n$ choose $k$ ", and is known as the binomial coeffecient.

Theorem (combination theorem and the binomial coefficient)

For integers $0\leq k\leq n$ ,

$\binom nk=\frac{n!}{k!(n-k)!}.$

Proof

Count ordered lists two ways. By the Permutation Theorem, there are $(n)_k$ ordered $k$ -selections in total. Group them by the underlying $k$ -element subset each one uses (forgetting order).
Count each group. A fixed $k$ -element subset has $k!$ different orderings, again by the permutation theorem (a permutation of $k$ objects, with $n=k$ ). Every ordered list belongs to the group of exactly one subset (the set of objects it uses) and every subset's group has exactly $k!$ lists, so no group is empty or double-counted.
Combine. Since there are $\binom nk$ groups (one per subset, by the definition of a combination each of size $k!$ ), the sum rule applied to these disjoint groups of ordered lists gives
$(n)_k=\binom nk\,k!.$
Since $k!>0$ , dividing both sides by $k!$ and substituting the permutation formula for $(n)_k$ gives $\binom nk=\frac{n!}{k!(n-k)!}$ .

At $k=0$ there is one empty subset and one empty ordering (step 2's $k!=0!=1$ ), so the argument still works. The reason division by $k!$ is valid is that every group has the same size $k!.$ We have Equal group size, not just that some outcomes were "counted too much." If representations had unequal multiplicities, one common divisor would not repair them. We will show this case in a later example.

∎

Example: Students on a Committee

We resolve the opening question. Six students are available. How many ways can we select a president and a secretary, with no student taking both jobs? How many ways can we select a two-person committee?

For the officers, apply the permutation theorem with $n=6,k=2$ : an ordered pair (president, secretary) is an ordered selection of $2$ from $6$ , so there are $(6)_2=6\cdot5=30$ assignments. For the committee, apply the Combination Theorem's grouping argument directly: each $2$ -person committee corresponds to exactly $k!=2!=2$ of those $30$ ordered assignments (either student could be president), so there are $30/2=15$ committees. As a check, listing committees by their lowest-numbered member (five containing the first student, four new ones containing the second (excluding the first), then three, two, and one) gives $5+4+3+2+1=15$ , which matches the Combination Theorem's direct result: $\binom62=15$ .

Sampling With and Without Replacement

In sampling with replacement, an object is returned before another choice, so repetition is possible. In sampling without replacement, it is not returned.

Theorem (choices with replacement)

For $n\geq1$ , length- $k$ ordered selections with replacement from $n$ objects number $n^k$ : every position has the same $n$ choices regardless of earlier choices, so the product rule applies with every $n_j=n$ . Without replacement the count is $(n)_k$ , by the permutation theorem above. These are counting claims, probabilities additionally require a sampling law.

Example: tickets with and without replacement

Five distinct tickets include two marked ones.

First model. Let $\Omega$ be the set of ordered pairs of tickets, replacement allowed. By choices with replacement, with $n=5,k=2$ , $|\Omega|=5^2=25$ , so $N=25$ and each pair has weight $1/25$ by the uniform model. The event "both marked" again matches choices with replacement, now with $n=2$ marked tickets: $2^2=4$ ordered pairs, including a ticket repeated with itself, giving probability $4/25$ .
Second model. Let $\Omega'$ be the set of ordered pairs of distinct tickets. By the permutation theorem with $n=5,k=2$ , $|\Omega'|=(5)_2=5\cdot4=20$ , so each pair has weight $1/20$ . The event "both marked" has $(2)_2=2\cdot1=2$ outcomes, again by the permutation theorem, giving probability $2/20=1/10$ .

One can instead use unordered pairs in the second model: by the combination theorm, each of $\binom52=10$ unordered pairs is equally likely (the Permutation Theorem's grouping argument shows each corresponds to exactly $2!=2$ of the $20$ ordered pairs, so equal group size preserves equal likelihood). Exactly $\binom22=1$ is all marked. This gives the same $1/10$ .

example: Committees with selection & assignment

Choose a three-person committee from seven students and designate one member as coordinator.

First choose the subset by the combination theorem, with $n=7,k=3,$ then its coordinator among the $3$ chosen members:

$\binom73\cdot3=35\cdot3=105.$

Alternatively, choose the coordinator first in $7$ ways, then apply the combination theorem with $n=6,k=2$ to choose two other members from the remaining six:

$7 \cdot\binom6 2=7\cdot15=105.$

Both constructions produce exactly one record for each committee-with-coordinator.

example: unordered draws with repetition

Draw twice from $\{a,b\}$ with replacement, so by choices with replacement, the four ordered outcomes $aa,ab,ba,bb$ are equally likely, each with weight $1/4$ . Discard order to record only the unordered pair drawn. The unordered records $\{a,a\},\{a,b\},\{b,b\}$ have probabilities $1/4,1/2,1/4$ : $\{a,a\}$ comes only from $aa$ , $\{b,b\}$ only from $bb$ , but $\{a,b\}$ comes from both $ab$ and $ba$ .

The combination theorem's division by $k!$ relied on every group (every unordered result) having the same number of ordered representations. Unfortunately, here that fails: the repeated-symbol records have one ordering each, while the mixed record has two. Dividing all four ordered outcomes by the constant $2!$ would falsely give two records of weight $4/2!=2$ apiece instead of the correct three records of unequal weight.

This is why "order does not matter" does not by itself justify dividing by $k!$ when repetitions are allowed. The combination theorem's proof needs equal group size, and repetition breaks that.

Info

Before using a formula, state if objects are distinguishable, positions have roles, repetition is allowed, and complete outcomes are equally likely. The first three determine which of the Permutation, Combinations, or Choices with Replacement Theorem applies. The fourth determines if a favorable count divided by a total count gives probability.

Exercise

From five people, compare selecting a captain and a deputy with selecting a two-person delegation. Explain why the outcomes differ.

Exercise

Why should $\binom n0=1$ rather than 0 for a set of n objects? Check the factorial formula, including n=0.

Exercise

Seven distinct books are available for three labeled display positions. No book repeats. How many displays are possible?

Exercise

How many three-person subsets of eight people contain a specified person? Explain why that person is not chosen again.

Exercise

A uniform ordered sample of two distinct tickets is drawn from six, of which two are marked. Find the probability that exactly one is marked, using an unordered count and explaining why it is uniform.

Exercise

Three selections from four symbols are recorded in order. Count all possible records with replacement and without replacement. What if five distinct selections are demanded without replacement?

Exercise

For two draws from $\{a,b,c\}$ with replacement, stipulate that the nine ordered records are equally likely. After order is discarded, list the unordered records and their probabilities. Are these six records uniform?

Exercise

A five-person team is chosen from nine people, then a chair and a recorder are chosen as different members. Specify the final record and count it in two orders of construction.

Exercise

Prove $\binom nk=\binom n{n-k}$ for integers $0\leq k\leq n$ by matching objects, not by canceling factorials.

Exercise

A uniform permutation of five distinct labels is generated, and only its first two labels are kept as an unordered set. Is every two-element subset equally likely? Explain how you would count its representations.

Exercise

A learner counts unordered pairs with repetition from $\{a,b\}$ as $2^2/2!=2$ . Explain why that division fails and give the correct count.