Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 36 ยท Permutations and Combinations

Combinations and Binomial Coefficients

Learn combinations, the number of ways to choose k items from n when order does not matter. Derive n choose k, its symmetry, and solve committee and hand problems.

A combination is a selection where order does not matter. Choosing a committee of three from ten people is a combination problem: the committee {Ann, Bo, Cy} is the same committee however you list it. The number of such selections is written C(n, k), nCk, or "n choose k", and displayed as a stacked pair with n over k.

Deriving n choose k

Start from ordered selections: there are P(n, k) = n! / (n-k)! ways to pick k items in order. Each unordered selection appears k! times among them, one for each way to order its k items. By the division rule from Counting Functions and Subsets:

C(n, k) = n! / (k! ยท (n-k)!)

For example C(5, 2) = 5! / (2! 3!) = 120 / 12 = 10. The ten pairs of {1, 2, 3, 4, 5} are 12, 13, 14, 15, 23, 24, 25, 34, 35, 45.

Python n choose k three ways

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

math.comb(n, k) is the built-in. For big values use it, since it avoids computing enormous factorials.

Symmetry and special values

Choosing k items to take is the same as choosing n - k items to leave. So C(n, k) = C(n, n-k). Also remember C(n, 0) = C(n, n) = 1, C(n, 1) = n, and C(n, k) = 0 for k > n.

Choosing 2 from 52 cards leaves 50, so C(52, 2) = C(52, 50) = 1326. Using the smaller of k and n-k makes by-hand work shorter.

Python Symmetry check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line prints 4096 twice: the sizes of all subsets add up to the total number of subsets, 2^n.

Typical problems

Committees. Choose 4 of 10 people: C(10, 4) = 210.

Committees with a condition. From 6 men and 5 women, pick a committee of 4 with exactly 2 women: C(5, 2) x C(6, 2) = 10 x 15 = 150. Pick the women and the men separately and multiply with the product rule.

At least one woman. Complement: all committees C(11, 4) = 330, minus those with no women C(6, 4) = 15, so 315.

Poker hands. A hand is 5 cards from 52: C(52, 5) = 2,598,960. A flush (all one suit, ignoring straight flushes) counts C(4, 1) x C(13, 5) = 5148 hands, including straight flushes.

Python Committees and cards

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Order matters or not? A decision guide

flowchart TD
    S["Choose k from n distinct items"] --> O{"Does order matter?"}
    O -->|yes| P["Permutations: n!/(n-k)!"]
    O -->|no| C["Combinations: n!/(k!(n-k)!)"]

If swapping two chosen items gives a different outcome, order matters.

A reliable test: imagine two selections that contain the same items in different orders. If the problem considers them the same (committee, hand of cards, subset), use combinations. If different (ranking, password, seating), use permutations.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is C(6, 2)?

    6 x 5 / 2 = 15.
  2. 2. C(10, 7) equals which of these?

    By symmetry C(n, k) = C(n, n-k): choosing 7 to take is choosing 3 to leave.
  3. 3. How many ways to choose 3 books from 8 to read (order does not matter)?

    C(8, 3) = 8 x 7 x 6 / 6 = 56.
  4. 4. A club has 7 boys and 5 girls. How many 3-person teams have exactly one girl?

    C(5, 1) x C(7, 2) = 5 x 21 = 105.

Summary

  • C(n, k) = n! / (k!(n-k)!) counts k-subsets of an n-set.
  • It equals P(n, k) / k!: ordered selections divided by the k! orderings.
  • Symmetry: C(n, k) = C(n, n-k), and the row sums to 2^n.
  • Combine combinations with the product rule for conditions, and with complements for "at least".

Next: Pascal's Triangle and the Binomial Theorem