Leave lesson

Statistics · Probability

1 / 10

Permutations and combinations

Counting arrangements and selections — factorials, arrangements with repeated items, ordered selections (nPr), unordered selections (nCr), and the standard restriction tricks: objects kept together, objects separated, and "at least" counts built case by case or by complement.

Statistics · Probability

Permutations and combinations

Counting arrangements and selections — factorials, arrangements with repeated items, ordered selections (nPr), unordered selections (nCr), and the standard restriction tricks: objects kept together, objects separated, and "at least" counts built case by case or by complement.

Why it works

Arrangements. nn different objects can be arranged in a line in n!=n×(n−1)×⋯×2×1n! = n \times (n-1) \times \cdots \times 2 \times 1 ways: nn choices for the first position, n−1n-1 for the second, and so on. That "multiply the choices" idea is the whole subject; everything else is bookkeeping.

Repeated objects. If some objects are identical, arrangements that only swap identical objects look the same, so the count shrinks. With nn objects of which pp are alike of one kind, qq alike of another, …: n!p! q!⋯.\frac{n!}{p!\,q!\cdots}. For BANANA (66 letters: three As, two Ns): 6!3! 2!=60\dfrac{6!}{3!\,2!} = 60.

Ordered selections — permutations. Choosing rr objects from nn *and arranging them in order*: nPr=n!(n−r)!=n(n−1)⋯(n−r+1).{}^{n}P_{r} = \frac{n!}{(n-r)!} = n(n-1)\cdots(n-r+1).

Unordered selections — combinations. Choosing rr from nn when order does not matter divides out the r!r! orderings of each chosen set: nCr=(nr)=n!r! (n−r)!.{}^{n}C_{r} = \binom{n}{r} = \frac{n!}{r!\,(n-r)!}. The test for which to use: *would swapping two chosen items give a different outcome?* A committee is the same committee in any order (CC); a 4-digit code is not (PP).

Restrictions — the three standard moves.
  • Together: tie the items that must be together into one block, arrange the
blocks, then arrange within the block. Vowels together in FIGURE (66 distinct letters, vowels I, U, E): 4!×3!=1444! \times 3! = 144.
  • Apart (no two adjacent): arrange the others first, then slot the restricted
items into the gaps (including the two ends). Consonants F, G, R make 3!3! arrangements with 44 gaps; place the 33 vowels in distinct gaps: 3!×4C3×3!=1443! \times {}^{4}C_{3} \times 3! = 144.
  • "At least" counts: either add the cases (33 girls ++ 44 girls +⋯+ \cdots)
or subtract the unwanted cases from the total — whichever is fewer cases. Never mix the two.

Positions with special rules go first. For even numbers, fix the last digit first; for numbers that must not start with 00, fix the first digit first. Fill the most constrained slot, then multiply out the rest.