Combinatorics (Kombinatorik)

15 min · 2 drills

Combinatorics deals with counting objects. The good news: all problems boil down to a few basic formulas, which we'll cover below.

---

Part 1. Counting Principles

Two fundamental rules form the foundation of all combinatorics:

Addition Rule (OR)

If a choice can be made in $m$ ways OR $n$ ways, and these ways don't overlap, then the total number of ways is:

$$\boxed{m+n}$$

Example: A menu has 5 types of soup and 8 types of salad. How many options for a light lunch (one dish)?

$$5++8==13\text{options}$$

Multiplication Rule (AND)

If the first choice can be made in $m$ ways, AND for each of them the second choice can be made in $n$ ways, then the total number of ways is:

$$\boxed{m\cdot n}$$

Example: A cafe offers 3 soups, 4 main courses, and 2 drinks. How many combo meal options?

$$3\cdot \cdot 4\cdot \cdot 2==24\text{options}$$

How to Tell "OR" from "AND"

Combining Rules

Complex problems often require using both rules together.

Example: A group has 8 boys and 5 girls. Two people need to be chosen: one captain and one assistant of different genders. Either a boy as captain and girl as assistant, or vice versa.

• Case 1: $8\cdot 5=40$
• Case 2: $5\cdot 8=40$

$$40++40==80\text{ways}$$

Counting with Restrictions

If there's a restriction: fill the restricted position first!

Example: How many even three-digit numbers from digits 1-5 without repetition?

• Last digit (must be even): 2 options (2 or 4)
• First digit: 4 options (any remaining)
• Middle digit: 3 options

$$2\cdot \cdot 4\cdot \cdot 3==24\text{numbers}$$

---

Part 2. Factorial

The factorial of $n$ is the product of all positive integers from 1 to $n$:

$$\boxed{n!=1\cdot 2\cdot 3\cdot \dots \cdot n}$$

Key property: $n!=n\cdot (n-1)!$

For example: $5!=5\cdot 4!=5\cdot 24=120$

---

Part 3. Permutations

Permutations Without Repetition

Permutation: an ordered arrangement of all $n$ elements. Order matters: ABC ≠ BAC.

$$\boxed{P_n=n!}$$

Example: How many ways to arrange 5 books on a shelf?

$$P_5==5!==120\text{ways}$$

Arrangements (Partial Permutations)

Arrangement: selecting $k$ elements from $n$ with order considered.

$$A_n^k==\frac{n!}{(n-k)!}=$$

$$n\cdot \cdot (n--1)\cdot \cdot \dots \cdot \cdot (n--k++1)$$

Example: How many ways to choose a president, vice-president, and secretary from 10 people?

$$A_{10}^3==10\cdot \cdot 9\cdot \cdot 8==720\text{ways}$$

Permutations With Repetition

If among $n$ elements there are identical ones: $n_1$ of the first type, $n_2$ of the second, etc.

$$P_n^{n_1,n_2,\dots ,n_k}==\frac{n!}{n_1!\cdot n_2!\cdot \dots \cdot n_k!}$$

Intuition: We divide by the factorials of repeated elements because rearranging identical elements among themselves creates duplicates.

Example: How many distinct rearrangements of the letters in MISSISSIPPI?

Total 11 letters: M(1), I(4), S(4), P(2)

$$P_{11}^{1,4,4,2}==\frac{11!}{4!\cdot 4!\cdot 2!}==\frac{39916800}{1152}==34650$$

Circular Permutations

Arranging $n$ elements in a circle (no fixed starting point). Each linear arrangement can be "rotated" $n$ ways, so we divide by $n$:

$$\boxed{P_{\text{circle}}=(n-1)!}$$

Example: 6 people around a circular table: $(6-1)!=5!=120$ ways.

---

Part 4. Combinations

What is a Combination?

Combination: a selection of $k$ elements from $n$ where order doesn't matter.

Compare:

Where Does the Formula Come From?

Step 1. With order: select 3 from 5 = $5\cdot 4\cdot 3=60$ (this is $A_5^3$)

Step 2. Each trio was counted $3!=6$ times (all internal permutations)

Step 3. Divide: $C_5^3=\frac{60}{6}=10$

The Formula

$$\boxed{C_n^k=\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}}$$

In EPM exams, the notation $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ is common (read as "n choose k" or in German "n uber k").

Quick Calculation Method

Instead of computing full factorials, cancel immediately:

$$C_n^k==\frac{n\cdot (n-1)\cdot \dots \cdot (n-k+1)}{k!}$$

The numerator contains $k$ consecutive numbers starting from $n$. The denominator is $k!$.

Examples:

$$C_5^2==\frac{5\cdot 4}{2\cdot 1}==10$$ $$C_8^3==\frac{8\cdot 7\cdot 6}{3\cdot 2\cdot 1}==56$$ $$C_7^3==\frac{7\cdot 6\cdot 5}{3!}==\frac{210}{6}==35$$

Properties of Combinations

Symmetry:

$$C_n^k==C_n^{n-k}$$

Choosing 3 from 10 is the same as choosing 7 to leave behind. This helps with calculations: $C_{100}^{98}=C_{100}^2=\frac{100\cdot 99}{2}=4950$.

Edge cases:

• $C_n^0=1$: one way to choose nothing
• $C_n^n=1$: one way to choose everything
• $C_n^1=n$

Pascal's formula:

$$C_n^k==C_{n-1}^{k-1}++C_{n-1}^k$$

The last element is either included in the selection ($C_{n-1}^{k-1}$) or not ($C_{n-1}^k$).

Relationship with arrangements:

$$A_n^k==C_n^k\cdot \cdot k!$$

Arrangements = combinations × permutations of selected elements.

---

Combinations $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ are also used in the binomial distribution (Bernoulli formula) to calculate probabilities of repeated independent trials; see the dedicated topic for details.

---

EPM Exam Problems

Problem 1: Balls from an Urn

An urn has 5 red and 4 blue balls. You draw 3 balls. How many ways to draw exactly 2 red?

• Choose 2 red from 5: $C_5^2=10$
• Choose 1 blue from 4: $C_4^1=4$
• By the multiplication rule: $10\cdot 4=40$ ways

Problem 2: Probability

From the same urn, draw 3 balls. What's the probability all three are the same color?

Total outcomes: $C_9^3=84$

Favorable: all red $C_5^3=10$ + all blue $C_4^3=4$ = 14

$$P==\frac{14}{84}==\frac{1}{6}$$

Problem 3: Committee with Constraints

From 6 men and 4 women, select a committee of 5. There must be at least 2 women. How many ways?

Total: $120+60+6=186$

Problem 4: Bookshelf with Grouping

A shelf has 4 math textbooks and 3 physics textbooks. How many ways to arrange them if books of the same subject must be together?

1. Groups: $2!=2$ ways to arrange (M and P)
2. Within M: $4!=24$
3. Within P: $3!=6$

$$2!\cdot \cdot 4!\cdot \cdot 3!==2\cdot \cdot 24\cdot \cdot 6==288\text{ways}$$

Problem 5: Permutations with Repetition

How many distinct 5-digit numbers from digits 1, 1, 2, 2, 3?

$$P_5^{2,2,1}==\frac{5!}{2!\cdot 2!\cdot 1!}==\frac{120}{4}==30$$

---

Common Mistakes

Mistake 1: Confusing "or" and "and"

Choosing soup or salad uses addition. Choosing soup and salad uses multiplication.

Mistake 2: Confusing combinations and arrangements

Ask yourself: does order matter?

• "Pick a team": order doesn't matter, use combinations
• "Award places": order matters, use arrangements

Mistake 3: Not starting with the restriction

If there's a condition (even number, starts with a specific digit), first fill the restricted position.

Mistake 4: Adding instead of multiplying when selecting from different groups

When simultaneously selecting from different groups, multiply, don't add:

$C_5^2\cdot C_4^1=40$ (correct)

$10+4=14$ (incorrect)

Mistake 5: Forgetting repeated elements

Word MAMA: not $4!=24$, but $\frac{4!}{2!\cdot 2!}=6$

---

How to Choose the Formula

• Does order matter?
  • YES: All elements?
    • YES: Permutations, $P=n!$
    • NO: Arrangements, $A=\frac{n!}{(n-k)!}$
  • NO: Combinations, $C=\frac{n!}{k!(n-k)!}$

---

Check Your Understanding

Your turn1 of 2

An access code consists either of two different letters from A, B, C, D, E or of three different digits from 1, 2, 3, 4. How many different codes are there?

A$14$B$44$C$480$D$40$

Check

Your turn2 of 2

Five people sit down at a round table, and two of them, Anna and Ben, want to sit next to each other. Seatings that turn into each other by a rotation count as the same. How many seatings are there?

A$24$B$12$C$48$D$6$

Check

---

All Formulas

Addition Rule (OR): $m+n$

Multiplication Rule (AND): $m\cdot n$

Factorial: $n!=1\cdot 2\cdot 3\cdot \dots \cdot n$, with $0!=1$

Permutations: $P_n=n!$

Arrangements: $A_n^k=\frac{n!}{(n-k)!}$

Permutations with repetition: $P_n^{n_1,\dots ,n_k}=\frac{n!}{n_1!\cdot \dots \cdot n_k!}$

Circular permutations: $P_{\text{circle}}=(n-1)!$

Combinations: $C_n^k=\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$

Quick calculation: $C_n^k=\frac{n\cdot (n-1)\cdot \dots \cdot (n-k+1)}{k!}$

Symmetry: $C_n^k=C_n^{n-k}$

Pascal's formula: $C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$

Relationship: $A_n^k=C_n^k\cdot k!$