Training Discrete Mathematics & Number Theory Counting and Combinatorics
2 / 5

Counting and Combinatorics

23 min Discrete Mathematics & Number Theory
Counting and combinatorics answer the question 'how many ways?' The multiplication principle says that if task A can be done in m ways and task B in n ways, the combined tasks can be done in m × n ways. Permutations count ordered arrangements: P(n, r) = n!/(n − r)!, while combinations count unordered selections: C(n, r) = n!/(r!(n − r)!). These tools extend to problems with repetition, circular arrangements, and the inclusion-exclusion principle for counting elements in overlapping sets. Combinatorics underpins probability, algorithm analysis, and cryptography.

Counting and Combinatorics

Counting principles organize how many ways an arrangement or selection can happen.

Counting Rules

Product rule: if one task has $m$ choices and the next has $n$ choices, then the pair has $mn$ outcomes.

Permutation: $$P(n,r)=\frac{n!}{(n-r)!}$$

Combination: $$\binom{n}{r}=\frac{n!}{r!(n-r)!}$$

Example 1

How many 3-letter arrangements can be formed from 5 distinct letters without repetition?

  1. $P(5,3)=5\cdot4\cdot3=60$.
Example 2

How many 3-person committees can be chosen from 8 people?

  1. Set up the problem.
  2. $$\binom{8}{3}=56$$

Practice Problems

1. Use the product rule for 3 shirt choices and 2 pants choices.
2. Compute $4!$.
3. Compute $P(6,2)$.
4. Compute $\binom{5}{2}$.
5. When do you use combinations instead of permutations?
Show Answer Key

1. $6$ outfits

2. $24$

3. $30$

4. $10$

5. When order does not matter

🔢 Permutation & Combination Calculator
n!
P(n,r)
C(n,r)
C(n,r) with repetition
Logic and Sets Sequences, Recursion, and Induction