Basics of combinatorics

Combinatorics answers the question "in how many ways?": how many numbers can be formed, how many groups chosen, how many orders obtained. Probability theory rests on this counting too. The main difficulty is not the formula itself but knowing which formula to use: does order matter, are repetitions allowed?

§1. The sum and product rules

• Product rule ("and"): if a choice is made in stages — the first in m ways, the second in n ways — there are m·n ways in total.
• Sum rule ("or"): if an object is taken either from the first group (m ways) or from the second (n ways) and the groups do not overlap — m + n ways.

All the formulas below are built on these two rules.

Worked example

How many three-digit numbers have all digits different?

1. Hundreds digit: cannot be 0 — 9 ways.
2. Tens digit: 0 is allowed, but the first digit cannot repeat — 9 ways.
3. Units digit: the remaining 8 digits.
4. 9·9·8 = 648.

If digits may repeat: there are 5⁴ = 625 four-digit numbers made of the digits 1, 2, 3, 4, 5.

§2. Permutations

The number of ways to arrange n different objects in a row:

Why? There are n choices for the first place, n − 1 for the second, …, 1 for the last — the product rule.
Permutations with repetition: if some objects are identical, swapping them gives no new order:

For example, the letters of MAMA give 4!/(2!·2!) = 6 different "words".
Around a circle n people can be seated in (n − 1)! ways (rotations count as the same).

Worked example

5 different books are put on a shelf, and two particular books must stand together. How many ways?

1. Treat the two books as one "block": 4 objects → 4! = 24.
2. Inside the block the books can be ordered in 2! = 2 ways.
3. 24·2 = 48.

§3. Arrangements and combinations

We choose k objects out of n.

Why divide by k!? Each group can be listed in k! orders, and in combinations they all count as one.
How to tell them apart: if the chosen objects get different "roles" or "places" (chair, deputy; digit positions) — A; if we just pick a "set" (a team, a group, handshakes) — C.

Worked example

From 10 students, in how many ways can we choose: a) a group of 3; b) a chair, a deputy and a secretary?

1. a) Order does not matter: C₁₀³ = 10·9·8/6 = 120.
2. b) The positions differ: A₁₀³ = 10·9·8 = 720.

Worked example

How many diagonals does a decagon have?

1. Segments joining two vertices: C₁₀² = 45.
2. 10 of them are sides: 45 − 10 = 35.

General formula: n(n − 3)/2.

§4. Compound choices and "at least one"

If we choose independently from several groups, multiply. For "at least one" it is easier to subtract the opposite case.

Worked example

In how many ways can a committee of 3 boys and 2 girls be formed from 6 boys and 5 girls?

1. C₆³ = 20, C₅² = 10.
2. 20·10 = 200.

Worked example

From the same 11 people we choose 3, and at least one must be a girl.

1. All ways: C₁₁³ = 165.
2. Boys only: C₆³ = 20.
3. 165 − 20 = 145.

§5. The binomial theorem

• The coefficients form a row of Pascal's triangle; their sum is 2ⁿ.
• The sum of the coefficients of any polynomial is its value at x = 1.

Worked example

Find the coefficient of x³ in the expansion of (2x − 1)⁵.

1. General term: C₅ᵏ(2x)⁵⁻ᵏ(−1)ᵏ.
2. 5 − k = 3 → k = 2.
3. C₅²·2³·(−1)² = 10·8 = 80.

Worked example

Find the constant term (the term without x) in the expansion of (x + 1/x)⁶.

1. General term: C₆ᵏ x⁶⁻ᵏ (1/x)ᵏ = C₆ᵏ x⁶⁻²ᵏ.
2. For the constant term the power is zero: 6 − 2k = 0 → k = 3.
3. C₆³ = 20. Also, the sum of the coefficients (at x = 1) is 2⁶ = 64.

§6. Arrangements and selections with repetition

The earlier formulas assumed that the elements are not repeated. But in problems about PIN codes, phone numbers or number plates, the same digit may be used again and again. Then the number of choices for each position stays the same, and the multiplication rule gives the formula at once.

For example, there are 10⁴ = 10 000 four-digit PIN codes made from the digits 0 to 9, because each position can hold any of the 10 digits.
There are also selections where order does not matter but a kind may be taken more than once: buying 3 ice creams from 4 flavours (the same flavour may be chosen twice). These are called combinations with repetition:

The idea behind the formula: write a row of k ‘stars’ (the chosen items) and n − 1 ‘bars’ separating the kinds; it is enough to choose k places for the stars out of n + k − 1. For example, 3 ice creams from 4 flavours: C(6, 3) = 20 ways.
To choose a formula, answer two questions: 1) does order matter? 2) is repetition allowed? These two answers pick one of four cases — Aₙᵏ, Cₙᵏ, nᵏ or C(n + k − 1, k).

Worked example

A four-digit PIN code is made from the digits 0–9. In how many codes does at least one digit repeat?

1. All codes (repetition allowed, order matters): 10⁴ = 10 000.
2. Codes with no repeated digit: A₁₀⁴ = 10·9·8·7 = 5040.
3. ‘At least one repeat’ is the complement: 10 000 − 5040 = 4960.

Check yourself

1. Compute 6!/4!.

2. How many two-digit numbers with distinct digits can be made from 1, 2, 3, 4, 5?

3. In how many ways can 2 dishes be chosen from 7?

4. How many different "words" can be made from the letters of ANANAS?

5. The coefficient of x² in (1 + x)⁸.

6. Find n if Cₙ² = 15.

7. How many three-digit numbers can be formed from the digits 0, 1, 2, 3 (digits may repeat)?

8. You must take 2 pastries from 5 kinds (the same kind may be taken twice). How many ways are there?

Common mistakes

• Picking a formula without deciding whether order matters (C instead of A or vice versa).
• Forgetting that the first digit of a number cannot be 0.
• Forgetting that 0! = 1.
• Writing n! when some objects are identical.
• Counting "at least one" directly and counting some cases twice.
• Losing the sign (−1)ᵏ in a binomial term with a negative second summand.
• Using Aₙᵏ or Cₙᵏ when repetition is allowed: if every position can take any of the n options, the answer is nᵏ.