Permutation and combination
Counting problems ask in how many ways something can be chosen or arranged. The first decision is always whether order matters: if it does, you are arranging (permutations), and if it does not, you are choosing (combinations). Restrictions are handled by splitting into cases or by treating a group as a block.
Formulas and when they apply
- Multiplication rule: if one step has m ways and a second step has n ways, together they have m × n waysApplies when: the steps happen one after the other
- Addition rule: if a job can be done in m ways or in n different ways, there are m + n ways in allApplies when: the two ways cannot happen together
- n! = n × (n − 1) × ... × 2 × 1, and arranging n different things in a row gives n! ways
- nPr = n!/(n − r)!, the number of ordered arrangements of r things chosen from n
- nCr = n!/(r! × (n − r)!) = nC(n − r), the number of selections when order does not matter
- Arrangements of n items with p of one kind, q of another and so on = n!/(p! × q! × ...)Applies when: identical items in each kind
- Arrangements round a circle = (n − 1)!Applies when: rotations count as the same, no seat is special
Worked examples
Example 1. A group has 4 men and 3 women. In how many ways can a team of 3 be chosen with exactly 1 woman?
Solution. Choose 1 woman from 3: 3C1 = 3 ways. Choose 2 men from 4: 4C2 = 6 ways. Multiply: 3 × 6 = 18 teams.
Example 2. How many 4-letter codes can be made from the letters A, B, C, D, E, F if no letter may be repeated?
Solution. Order matters in a code, so use permutations: 6P4 = 6 × 5 × 4 × 3 = 360.
Example 3. In how many different ways can the letters of the word MISSION be arranged?
Solution. MISSION has 7 letters, with I twice and S twice. Arrangements = 7!/(2! × 2!) = 5,040/4 = 1,260.
Shortcuts and their limits
- Use nCr = nC(n − r) to shorten the work: 10C8 = 10C2 = 45.Does not apply when: Only valid for selection (order does not matter).
- For 'at least' or 'at most' conditions, count the total and subtract the cases that break the condition, when those are fewer.Does not apply when: Check that you subtract every excluded case, and not more than once.
- For 'must be together', glue the items into one block, arrange the block with the rest, and multiply by the arrangements inside the block.Does not apply when: Do not use it for 'must not be together'. Count all arrangements and subtract the 'together' ones instead.
Common mistakes
- Using permutations when the order does not matter, such as for a team or committee.
- Forgetting to divide by the factorial of repeated letters.
- Forgetting to multiply by the internal arrangements of a block of items kept together.
- Adding when the steps happen one after the other, or multiplying when the choices are alternatives.
- Using n! instead of (n − 1)! for a circular arrangement, or (n − 1)! when seats are numbered or distinct.
Independent practice made by EduVistaHQ with original questions. It is not an official examination paper, it is not affiliated with or endorsed by any examination body or company, and a practice score does not predict a real result.