Concepts: identical objects and combinations

3.1 When some objects are alike

The simple nPr formula assumes that all objects are different. Words such as BANANA repeat letters, and swapping two identical letters does not create a new word. The correction is to divide by the factorials of the repeated counts: if n objects contain p1 alike of one kind, p2 alike of another, and so on, the number of arrangements is n factorial divided by the product of those factorials.

For the letters of the word AGAIN, the letter A appears twice and the other three letters are different, so the count is 5 factorial by 2 factorial equal to 60. For MISSISSIPPI there are 4 I's, 4 S's and 2 P's among the 11 letters, so the count is 11 factorial divided by 4 factorial times 4 factorial times 2 factorial. For ALLAHABAD the repeated letters are A and L, and the same division applies.

This formula also answers questions about identical coins, identical chairs or a mixed row of boys and girls of the same group. Count the total arrangements as if all were distinct, then divide by the internal arrangements of each group that look the same.

3.2 Combinations and the formula

A combination is a selection in which order does not matter. From three tennis players X, Y and Z, the number of pairs is three: XY, YZ and ZX. Writing YX instead of XY describes the same pair. In general, a selection of r objects out of n different objects is counted by nCr, which is n factorial divided by the product of r factorial and (n minus r) factorial.

The link to permutations is one line. Each selection of r objects can be arranged internally in r factorial ways, and every arrangement comes from exactly one selection. So nPr equals nCr times r factorial, which gives the combination formula on dividing by r factorial. This is why 4P2 is 12 while 4C2 is 6: the pairs are arranged in two orders.

The same formula answers handshakes (a handshake is a pair, so 12C2), chords of a circle (each chord is a pair of points, so 7C2), and committee questions (a committee is a set, so nCr). Spotting the selection word in the question is what decides the formula.

3.3 Identities you will use

Three identities appear again and again. Choosing r objects is the same as rejecting n minus r objects, so nCr equals nC(n minus r). Neighbouring selections add to the next row, so nCr plus nC(r minus 1) equals (n plus 1)Cr. And the sum of nC0 through nCn is 2 to the power n, because it counts all subsets of an n element set.

A fourth pattern handles restricted selections. If a committee of 5 is chosen from 4 girls and 7 boys with at least one girl, subtract the all-boy committees from the total: 11C5 minus 7C5. If the committee must have at least 3 girls, add the cases exactly 3 and exactly 4 girls: 4C3 times 7C2 plus 4C4 times 7C1.

When a question says exactly, count that exact composition. When it says at least, either add the allowed sizes or subtract the disallowed ones, whichever list is shorter. Both routes must give the same number, so use the second as a check.

3.4 Exercise 6.3 and 6.4 shapes

Exercise 6.3 mixes arrangement questions. Question 1 asks for three digit numbers from digits 1 to 9 without repetition, giving 9P3 equal to 504. Question 4 asks for four digit numbers from 1 to 5 and how many are even: the total is 5P4 equal to 120, and the even ones end in 2 or 4, so the last place is fixed in 2 ways and the first three places are filled in 4P3 ways, giving 48. Question 9 arranges the letters of MONDAY in three cases, and Question 10 counts the distinct permutations of MISSISSIPPI in which the four I's are not all together, using total minus the block case.

Exercise 6.4 is selection. Question 1 uses nC8 equal to nC2 to get n equal to 10 and then asks for 10C2, which is 45. Question 3 asks for chords through 21 points, which is 21C2 equal to 210. Question 6 asks for 5 card combinations with exactly one ace: choose the ace in 4 ways, then choose the other four cards from the 48 non-aces, giving 4 times 48C4. Question 9 requires 2 compulsory courses out of 5, so the student chooses the remaining 3 from the other 7, which is 7C3 equal to 35.