Combinatorics: Counting Principles, Permutations, Combinations & Advanced Techniques

TAKEAWAYS:

• Counting principles (addition/multiplication) solve problems by breaking them into simpler, disjoint cases or sequential choices.
• Permutations ($P(n,r)$) count ordered arrangements, while combinations ($C(n,r)$) count unordered selections—key distinction: order matters vs. doesn’t.
• The binomial theorem ($(x+y{)}^n={\sum }_{k=0}^{n}C(n,k)x^{n-k}{y}^k$) connects combinations to polynomial expansion and probability.
• Advanced techniques (inclusion-exclusion, generating functions) extend basic counting to overlapping cases or recursive structures.
• Applications span cryptography, network routing, algorithm analysis (e.g., Big-O), and probability (e.g., poker hands, birthdays).
• Exam focus: Prove formulas, solve word problems, and distinguish between permutations/combinations—common pitfall is misapplying order.

---

1. Fundamental Counting Principles

1.1 Addition Principle

Definition: If a task can be completed in $m$ distinct ways or in $n$ distinct ways (with no overlap), the total number of ways is $m+n$.

How it works:

• Disjoint cases: The two methods of completion are mutually exclusive.
• Example: Counting students who passed either Math or Physics.
  • Let $A$ = students who passed Math = 30.
  • $B$ = students who passed Physics = 25.
  • $A\cap B$ = students who passed both = 5.
  • Total passing at least one subject = $|A|+|B|-|A\cap B|=30+25-5=50$. (Note: This is actually inclusion-exclusion; pure addition applies only if $A\cap B=0$.)

Worked Example: How many 3-digit numbers use digits {1, 2, 3, 4} with no repetition, where the first digit is either 1 or 2?

• Case 1: First digit = 1 → remaining 2 digits from {2, 3, 4} → $P(3,2)=6$.
• Case 2: First digit = 2 → remaining 2 digits from {1, 3, 4} → $P(3,2)=6$.
• Total = $6+6=12$ (addition principle).

Comparison Table:

---

1.2 Multiplication Principle

Definition: If a task can be completed in $m$ ways and a second task in $n$ ways (independent of the first), the total number of ways is $m\times n$.

How it works:

• Sequential choices: Each step’s outcome depends on previous choices.
• Example: Passwords with 2 letters followed by 2 digits.
  • Letters: 26 × 26 = 676.
  • Digits: 10 × 10 = 100.
  • Total passwords = $676\times 100=67,600$.

Worked Example: A restaurant offers 3 starters, 4 mains, and 2 desserts. How many full meals can be ordered?

• Starters: 3 choices.
• Mains: 4 choices (independent of starter).
• Desserts: 2 choices.
• Total meals = $3\times 4\times 2=24$.

Key Insight:

• Order matters: The multiplication principle assumes a specific sequence (e.g., starter → main → dessert).
• Pitfall: Misapplying it to overlapping cases (use addition instead).

---

2. Permutations

2.1 Definition and Formula

Definition: A permutation is an ordered arrangement of $r$ objects from a set of $n$ distinct objects. Notation: $P(n,r)$.

Formula: $$P(n,r)=\frac{n!}{(n-r)!}=n\times (n-1)\times \cdots \times (n-r+1)$$

Why it works:

• First position: $n$ choices.
• Second position: $n-1$ remaining choices (no repetition).
• ...
• $r$-th position: $n-r+1$ choices.

Worked Example: How many 4-digit PINs can be formed using digits {0, 1, 2, ..., 9} with no repetition?

• First digit: 10 choices (0–9).
• Second digit: 9 choices (remaining digits).
• Third digit: 8 choices.
• Fourth digit: 7 choices.
• Total = $10\times 9\times 8\times 7=5040$ or $P(10,4)$.

Special Cases:

• Permutations of all $n$ objects: $P(n,n)=n!$.
• Circular permutations: $(n-1)!$ (fix one object to break rotational symmetry).

---

2.2 Applications

Pitfall:

• Repetition allowed? If yes, use $n^r$ (e.g., PINs with repeats: $10^4=10,000$).

---

3. Combinations

3.1 Definition and Formula

Definition: A combination is an unordered selection of $r$ objects from a set of $n$ distinct objects. Notation: $C(n,r)$ or $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$.

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

Why it works:

• Permutations overcount by $r!$ (all orderings of the same $r$ objects are identical in combinations).

Worked Example: How many ways can a committee of 3 be formed from 5 people?

• Order doesn’t matter: {A, B, C} is the same as {B, A, C}.
• Total = $C(5,3)=\frac{5!}{3!2!}=10$.

Comparison with Permutations:

---

3.2 Key Properties

1. Symmetry: $C(n,r)=C(n,n-r)$.
   • Proof: Selecting $r$ items to include is equivalent to selecting $n-r$ items to exclude.
2. Pascal’s Identity: $C(n,r)=C(n-1,r-1)+C(n-1,r)$.
   • Application: Used in binomial coefficients and dynamic programming.

Worked Example: Prove $C(5,2)=C(5,3)$.

• $C(5,2)=\frac{5!}{2!3!}=10$.
• $C(5,3)=\frac{5!}{3!2!}=10$.
• Conclusion: Symmetry holds.

---

4. Binomial Theorem

4.1 Statement

The binomial theorem expands $(x+y{)}^n$ as a sum of terms involving combinations: $$(x+y{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^{n-k}{y}^k$$

Example: $$(x+y{)}^3=(\genfrac{}{}{0ex}{}{3}{0})x^3{y}^0+(\genfrac{}{}{0ex}{}{3}{1})x^2{y}^1+(\genfrac{}{}{0ex}{}{3}{2})x^1{y}^2+(\genfrac{}{}{0ex}{}{3}{3})x^0{y}^3=x^3+3x^{2}y+3x{y}^2+y^3$$

4.2 Applications

1. Probability:
   • Binomial distribution: $P(k\text{ successes in }n\text{ trials})=\left(\genfrac{}{}{0ex}{}{n}{k}\right)p^k(1-p{)}^{n-k}$.
2. Algebra:
   • Simplifying expressions like $(2a-3b{)}^4$.
3. Combinatorics:
   • Counting subsets with specific properties (e.g., exactly 2 red balls in 5 draws).

Worked Example: Expand $(3x-2{)}^4$ using the binomial theorem. $$(3x-2{)}^4=\sum _{k=0}^4(\genfrac{}{}{0ex}{}{4}{k})(3x{)}^{4-k}(-2{)}^k$$ $$=\left(\genfrac{}{}{0ex}{}{4}{0}\right)(3x{)}^4(-2{)}^0+\left(\genfrac{}{}{0ex}{}{4}{1}\right)(3x{)}^3(-2{)}^1+\cdots +\left(\genfrac{}{}{0ex}{}{4}{4}\right)(3x{)}^0(-2{)}^4$$ $$=81x^4-216x^3+216x^2-96x+16$$

---

5. Advanced Counting Techniques

5.1 Inclusion-Exclusion Principle

Problem: Count elements in multiple sets with overlaps. Formula: $$|A\cup B|=|A|+|B|-|A\cap B|$$ For 3 sets: $$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$$

Worked Example: In a class of 30 students:

• 18 like Math,
• 12 like Physics,
• 10 like Chemistry,
• 5 like both Math and Physics,
• 4 like both Math and Chemistry,
• 3 like both Physics and Chemistry,
• 2 like all three. How many like at least one subject? $$|M\cup P\cup C|=18+12+10-5-4-3+2=28$$

Generalization: For $n$ sets, the principle alternates between adding and subtracting intersections.

---

5.2 Generating Functions

Definition: A generating function encodes a sequence $\{a_n\}$ as coefficients in a power series: $$G(x)=\sum _{n=0}^{\infty }{a}_n{x}^n$$

Example:

• Counting subsets: The generating function for subsets of $\{1,2,\dots ,n\}$ is $(1+x{)}^n$, where the coefficient of $x^k$ is $C(n,k)$.

Application: How many ways can you make $5 using coins of $1 and $2?

• Generating function: $(1+x+x^2+\dots )(1+x^2+x^4+\dots )=\frac{1}{(1-x)(1-x^2)}$.
• Coefficient of $x^5$: 3 ways (1+1+1+1+1, 1+1+1+2, 2+2+1).

---

5.3 Recursive Counting

Definition: Define a problem in terms of smaller subproblems. Example:

• Fibonacci numbers: $F(n)=F(n-1)+F(n-2)$ (counting tile arrangements).
• Catalan numbers: $C_n={\sum }_{i=0}^{n-1}{C}_i{C}_{n-1-i}$ (counting valid parentheses expressions).

Worked Example: Count the number of binary strings of length $n$ with no two consecutive 1s.

• Let $a_n$ = valid strings of length $n$.
• Recurrence:
  • Ends with 0: $a_{n-1}$ choices.
  • Ends with 01: $a_{n-2}$ choices.
• Base cases: $a_1=2$ (0, 1), $a_2=3$ (00, 01, 10).
• Solution: $a_n=a_{n-1}+a_{n-2}$ (Fibonacci-like).

---

6. Common Pitfalls and Exam Tips

6.1 Mistakes to Avoid

1. Confusing permutations/combinations:
   • Wrong: Using $C(n,r)$ for ordered arrangements (e.g., passwords).
   • Fix: Use $P(n,r)$ when order matters.
2. Ignoring constraints:
   • Example: Counting 3-digit numbers with digits {0, 1, 2} without repetition.
     • Error: $P(3,3)=6$ (forgets first digit can’t be 0).
     • Correct: $P(2,1)\times P(3,2)=2\times 6=12$ (first digit: 1 or 2).
3. Overlapping cases in addition:
   • Example: Counting students in Math or Physics without subtracting the intersection.
4. Misapplying formulas:
   • Example: Using $C(n,r)$ when repetition is allowed (use combinations with repetition: $C(n+r-1,r)$).

6.2 Exam Strategies

1. Diagram problems:
   • Draw Venn diagrams for inclusion-exclusion.
   • Use tree diagrams for counting sequences.
2. Verify with small numbers:
   • For $n=3,r=2$, check $P(3,2)=6$ and $C(3,2)=3$ manually.
3. Watch for hidden constraints:
   • "No repetition," "at least one," "exactly two" — translate to mathematical conditions.
4. Memorize key formulas:
   • $P(n,r)=\frac{n!}{(n-r)!}$
   • $C(n,r)=\frac{n!}{r!(n-r)!}$
   • Binomial theorem expansion
5. Practice word problems:
   • Translate English to combinatorial terms (e.g., "committee" → combination, "schedule" → permutation).

6.3 Sample Exam Questions

1. Direct Application:

   • Question: How many 5-letter words can be formed from {A, B, C, D, E} with no repetition?
   • Answer: $P(5,5)=120$.

2. Combination Problem:

   • Question: A pizza shop offers 8 toppings. How many 3-topping pizzas can be made?
   • Answer: $C(8,3)=56$.

3. Inclusion-Exclusion:

   • Question: In a group of 40 people, 25 like tea, 20 like coffee, and 10 like both. How many like neither?
   • Answer: $40-(25+20-10)=5$.

4. Binomial Expansion:

   • Question: Find the coefficient of $x^3$ in $(2x+3{)}^5$.
   • Answer: $\left(\genfrac{}{}{0ex}{}{5}{2}\right)\times 2^3\times 3^3=10\times 8\times 27=2160$.

5. Advanced Technique:

   • Question: Count the number of ways to distribute 10 identical candies to 3 children where each gets at least 1.
   • Answer: $C(10-1,3-1)=C(9,2)=36$ (stars and bars).

---

7. Summary Table

---

8. Further Reading and Practice

1. Books:
   • Discrete Mathematics and Its Applications by Kenneth Rosen (Chapters 6–7).
   • Concrete Mathematics by Graham, Knuth, Patashnik (for advanced techniques).
2. Online Resources:
   • Khan Academy: Combinatorics Playlist.
   • Brilliant.org: Combinatorics Course.
3. Practice Problems:
   • Solve all end-of-chapter problems from Rosen (Sections 6.1–6.5).
   • TU/PU past papers (focus on word problems).
   • NEB questions on permutations/combinations in probability units.

---

9. Exam Tip

What Examiners Look For:

1. Correct formula application: Always justify why $P(n,r)$ or $C(n,r)$ is used.
2. Step-by-step reasoning: Break problems into subparts (e.g., "Case 1: first digit is 1; Case 2: first digit is 2").
3. Units and constraints: Clearly state assumptions (e.g., "no repetition," "order matters").
4. Verification: For small $n$, compute manually to verify your formula.
5. Diagrams: Use Venn diagrams for inclusion-exclusion or tree diagrams for counting paths.

Common Exam Patterns:

• Part (a): Direct application (e.g., "Calculate $P(7,3)$").
• Part (b): Word problem (e.g., "How many ways can a team captain and 3 members be chosen from 10 people?").
• Part (c): Proof or derivation (e.g., "Prove $C(n,r)=C(n,n-r)$").

Time Management:

• Spend ~3 minutes per subpart.
• If stuck, move on and return later (combinatorics problems often have multiple approaches).

---

10. Quick Reference Cheat Sheet

### FORMULAS
1. Permutations: P(n, r) = n! / (n-r)!
2. Combinations: C(n, r) = n! / (r!(n-r)!)
3. Binomial Coefficient: C(n, k) = "n choose k"
4. Inclusion-Exclusion: |A ∪ B| = |A| + |B| - |A ∩ B|
5. Generating Function: G(x) = Σ aₙ xⁿ

### WHEN TO USE
- **Permutations**: Order matters (passwords, rankings).
- **Combinations**: Order doesn’t matter (committees, subsets).
- **Addition**: "OR" with no overlap.
- **Multiplication**: "AND" with independent choices.
- **Inclusion-Exclusion**: Overlapping sets.

---

11. Final Worked Problem (Synthesis)

Question: A club has 10 members. It wants to form a 4-person committee with:

1. A president and vice-president (order matters for these roles).
2. Two additional members (order doesn’t matter).
3. No member can hold more than one role. How many ways can this be done?

Solution:

1. Choose president and vice-president:
   • Ordered selection → $P(10,2)=10\times 9=90$.
2. Choose 2 additional members from remaining 8:
   • Unordered selection → $C(8,2)=28$.
3. Total ways:
   • Multiply choices (independent steps) → $90\times 28=2520$.

Alternative Approach:

• Total ordered arrangements for 4 distinct roles: $P(10,4)=5040$.
• But the last two roles are identical (no order), so divide by $2!$: $5040/2=2520$.

Answer: $\boxed{2520}$.