Permutations and combinations

Counting outcomes before choosing a formula

Combinatorics studies counting problems. The source outline covers addition and multiplication, permutations and combinations, and arrangements in rows or circles with repetition or restrictions. Its opening four-wheel lock asks for a count of settings; try that question below. The printed combinatorics reference is retained as a learning pointer.

Add mutually exclusive alternatives

If E₁ and E₂ cannot occur together and have n₁,n₂ outcomes, the number of ways for E₁ or E₂ is $n_1+n_2$. More generally, for k≥1 pairwise mutually exclusive alternatives, the number for at least one is $n_1+\cdots+n_k$. Here at most one can occur, so none is counted twice. Example 1 chooses one air or sea service.

Multiply ordered stages

If an outcome requires E₁ followed by E₂, with n₁ ways for the first stage and n₂ continuations for each first choice, there are $n_1n_2$ outcomes. For k ordered stages, the product is $n_1\cdots n_k$. If continuation counts depend on an earlier choice, separate disjoint cases before adding. This is a counting rule, not a probability-independence assumption. Example 2 pairs each of two A–B roads with each of three B–C roads.

Arrange all n distinct objects in a row

A permutation is an arrangement of all or some objects where order matters. With no replacement, each chosen object is removed from the later choices.

Position	1st	2nd	3rd	…	(n−1)th	nth
Available objects	n	n−1	n−2	…	2	1

Multiplication gives $n(n-1)(n-2)\cdots3\cdot2\cdot1=n!$ for positive integer n. Example 3 uses all 10 seats.

Arrange r of n distinct objects without replacement

Position	1st	2nd	3rd	…	(r−1)th	rth
Available objects	n	n−1	n−2	…	n−(r−2)	n−(r−1)

The last two entries are completed in the Teacher copy. There are r decreasing factors:

$${}^nP_r=n(n-1)(n-2)\cdots[n-(r-1)].$$

Multiply and divide by the missing tail $(n-r)!$ to obtain

$${}^nP_r=\frac{n(n-1)\cdots[n-(r-1)](n-r)!}{(n-r)!}=\frac{n!}{(n-r)!}.$$

Here n,r are integers with $0\le r\le n$. The empty-product convention gives ${}^nP_0=1$. The source remarks that ${}^nP_n=n!/(n-n)!=n!$ because $0!=1$. Example 4 uses r=3,n=10. The calculator steps for both factorial and nPr are retained with those examples.

Keep the same number of choices when repetition is allowed

The source paints three labelled rooms using five colours: red, green, yellow, blue and purple. Each room still has five choices, so the position table is

Room	1st	2nd	3rd
Colour choices	5	5	5

There are $5\times5\times5=5^3=125$ colour assignments. In general, r ordered positions with n choices available each time give $n^r$.

Source qualification: both copies print $0\le r\le n$ beside the repetition formula on page 5. The upper bound is unnecessary when replacement or repetition is allowed: r can exceed n. Use positive integer n and any nonnegative integer r; $n^0=1$ counts the empty arrangement. Example 5 uses repeated letters and digits.

Remove overcounting from identical objects

First pretend the letters A,B,B are A,B₁,B₂. Their 3!=6 labelled arrangements fall into pairs:

Same unlabelled arrangement	First labelled version	Second labelled version
ABB	AB₁B₂	AB₂B₁
BAB	B₁AB₂	B₂AB₁
BBA	B₁B₂A	B₂B₁A

Swapping the two identical B copies does not create a new arrangement. Each unlabelled result is counted 2! times, so there are $3!/2!=3$ distinct arrangements.

For N objects consisting of n₁ of type 1,…,nₖ of type k, with $n_1+\cdots+n_k=N$, the count is

$$\frac{N!}{n_1! n_2!\cdots n_k!}.$$

Follow the source proof by choosing positions

Use N boxes, one for each position. Write $s_j=n_1+\cdots+n_j$, with $s_0=0$.

1. Choose n₁ boxes for type 1: $\binom N{n_1}$.
2. Choose n₂ from the remaining N−n₁: $\binom{N-n_1}{n_2}$.
3. Continue to type k, choosing $\binom{N-s_{k-1}}{n_k}$.
4. If there are m=N−sₖ remaining distinct objects, arrange them in m! ways, as in the source’s final stage. In the boxed all-types formula sₖ=N, so m=0 and this is 0!=1. The proof switches the total’s letter from N to n; N is used consistently here.

Multiplication gives

$$\left[\prod_{j=1}^k\binom{N-s_{j-1}}{n_j}\right]m! =\left[\prod_{j=1}^k\frac{(N-s_{j-1})!}{n_j!(N-s_j)!}\right]m! =\frac{N!}{n_1!\cdots n_k!\,m!}\,m! =\frac{N!}{n_1!\cdots n_k!}.$$

The intermediate factorials cancel. If every object is included among the types, m=0; if m counts additional distinct objects, their ordering supplies the final m! factor. Examples 6 and Self-Practice 1 apply this to repeated letters.

Select without caring about order

A combination is a selection from distinct objects where order does not matter. An r-combination of a set S is a subset with r elements. For $S=\{A,B,C\}$, the three 2-combinations are $\{A,B\}$, $\{A,C\}$ and $\{B,C\}$. Reversing their written order changes nothing: $\{A,B\}=\{B,A\}$, $\{A,C\}=\{C,A\}$ and $\{B,C\}=\{C,B\}$.

The notation ${}^nC_r$, also written $\binom nr$ in the source’s MF27 reference, has formula

$${}^nC_r=\binom nr=\frac{n!}{r!(n-r)!},\qquad0\le r\le n,$$

for nonnegative integers n,r. There is one way to select all or none: ${}^nC_n={}^nC_0=1$. Selecting r objects is equivalent to rejecting the other n−r, so ${}^nC_r={}^nC_{n-r}$.

Choose the seats, then arrange the people

Revisit Example 4: first choose 3 of the 10 seats in $\binom{10}{3}$ ways, then arrange the 3 distinct people in those seats in 3! ways. Thus ${}^{10}P_3=\binom{10}{3}3!=120\times6=720$. In general,

$${}^nP_r={}^nC_r\,r!,\qquad\frac{n!}{(n-r)!}={}^nC_r\,r!,\qquad{}^nC_r=\frac{n!}{(n-r)!r!}.$$

The source calculator evaluates ${}^{10}C_3$ by typing 10, selecting MATH → PROB → 3:nCr, typing 3 and pressing ENTER. Its input 10 nCr 3 returns 120. Compare that 120 with the 720 ordered seatings in Example 4.

Build a committee by cases or complements

For a committee with no assigned roles, choose members using combinations. Multiply independent selection stages in the counting sense, such as choosing boys and girls from separate sets; then add disjoint cases. Reversing the order of those two stages does not change the committee count.

At most one means zero or one. At least one can be counted directly by all positive cases, or by subtracting none from the unrestricted total. The source recommends the complement method when there would otherwise be too many cases. Example 8 retains both routes.

If A or B must be included, both may be included: the or is inclusive. Add the count including A and the count including B, then subtract the overlap once. The Teacher note asks for a Venn diagram; Example 8 includes one with all three membership regions. Alternatively count A only, B only, and both as disjoint cases.

Remove the ordering of indistinguishable groups

Distinct children remain distinct, but a partition into unlabelled groups does not record which group was selected first. Example 10 shows the same C₁,…,C₅ and C₆,…,C₁₀ groups selected in opposite stage orders. Divide their ordered-selection count by 2! to count each partition once.

In general, r equal-sized indistinguishable groups can be arranged in ${}^rP_r=r!$ orders. Each of those orders represents the same unlabelled partition, so divide by r!. Apply a separate correction for each set of interchangeable groups. Do not divide for groups with distinct labels, roles, functions or sizes. The source’s repeated section number 4.2 labels both distinct-group formation and indistinguishable-group formation; these are separate counting situations.

Count selections from repeated types by cases

The source distinguishes physical objects from distinguishable outcomes. Applying $\binom nr$ directly to n labelled objects is not the right model when same-type copies are indistinguishable. Identify all permitted multiplicity cases instead. Example 11 selects three beads from supplies R,R,R,B,B,W,G using patterns 1+1+1,2+1, and 3. Self-Practice 4 applies the same idea to ELEVEN. The supply limits matter: blue cannot supply a triple, and E is the only repeated letter in ELEVEN.

Handle a restriction before arranging the rest

The source’s general problem-solving tip is to account for restrictions first, before counting the unrestricted choices.

Objects together: group the required items into a single block. Arrange the outer objects, then count the arrangements within the block, correcting for identical copies at each level. Example 12 has outer objects I,I,U,[MMMN]. Example 14(a)has a block containing A,T, with both AT and TA counted.

Objects separated: arrange the objects that need not be separated first. They create gaps, including both ends. Select different gaps for the items that must be separated, then arrange those items within the chosen gaps. Example 13 uses three consonants to create four gaps for three vowels.

A selection ignores order; a codeword records it. Example 14(b)therefore selects a permitted multiset from CELEBRATE, then orders it. Self-Practice 4 only selects from ELEVEN, so permuting a selected multiset does not give extra outcomes.

Choose constrained positions before unrestricted ones

The Teacher notes explain that positions need not be filled from left to right. Usually start with the position with the most constraints.

In Example 15, first fix the thousands digit as 3 or 4, then fill the even units digit; the available units choices depend on that first digit. Complete tens and hundreds afterward.

A quoted fixed digit in the source boxes is a value, whereas an unquoted number counts choices.

State the selection model

Example 16 uses blocks and alternating gender patterns for distinct people. In part (iii), the source intends a contiguous WMMW block: exactly two intervening men.

Example 17 instead counts unordered subsets of five rides, each selected or not selected. Its two methods count all binary decisions except the empty set, or add the five possible positive subset sizes. These methods both give 31.

Self-Practice 5 combines fixing positions, grouping adjacent letters and subtracting the adjacent case from all arrangements.

Decide whether rotations make a new arrangement

For three distinct people, the six row orders are ABC, CAB, BCA, ACB, BAC, CBA. Put them at clockwise seats 1,2,3 around a circle. The first three placements form one rotation class; the last three form the other. If seat numbers are ignored, each class is one arrangement, giving $3!/3=2!$. Clockwise and anticlockwise orders still differ: reflection is not being identified.

In general, for n≥1 distinct objects at unlabelled circular positions, each circular order has n rotations of its linear listing, so $n!/n=(n-1)!$. Alternatively, fix one object as a reference and arrange the other n−1. This distinct-object assumption matters; repeated circular objects can have rotational symmetries, so dividing a general repeated-object row count by n is not automatically valid. Example 19 instead fixes its unique ACE block.

Labeled circular positions restore the seat choices

If three men sit in three differently coloured chairs, first fix M1 as a reference and arrange the other men in $(3-1)!=2!$ ways. M1 then has three distinct seats, restoring $2!\times3=6$. For n distinct objects in n distinct circular positions, the source formula is $(n-1)!\times n=n!$.

Example 18 uses unlabelled circular seats, alternating-gender gaps and a contiguous boy-girl-boy block. Example 19 keeps A,C,E consecutive clockwise, with one internal order. Its two conditions are independent: separated asterisks at unlabelled positions, then labelled symbol positions without the separation restriction. When restoring labels, count all eleven original symbol positions rather than the nine compressed objects.