Counting Principles, Permutations, Combinations & Advanced Techniques

TAKEAWAYS:

• Counting Basics: The Addition Principle (OR) and Multiplication Principle (AND) solve disjoint vs. sequential counting problems.
• Permutations vs. Combinations: Permutations ($P(n,r)$) order matters; combinations ($C(n,r)$) do not—use factorials ($n!$) to compute.
• Advanced Techniques: Inclusion-Exclusion Principle (for overlapping sets) and Generating Functions (for complex counting problems).
• Real-World Links: Used in Nepal’s Ncell (call routing), Daraz (order fulfillment), and Khalti (transaction security).
• Exam Focus: Prove counting formulas, solve word problems, and distinguish between scenarios requiring permutations vs. combinations.

1. Fundamental Counting Principles

1.1 Addition Principle (OR Rule)

Definition: If a task can be done in $m$ ways or in $n$ ways, and these ways are mutually exclusive, the total number of ways is $m+n$.

Example:

• Scenario: You can reach Kathmandu from Pokhara by bus (5 routes) or flight (3 routes). How many total ways?
• Solution: $5+3=8$ (since bus and flight routes are distinct).
• Visual:

  flowchart TD
    A["Start"] --> B["Bus: 5 ways"]
    A --> C["Flight: 3 ways"]
    B --> D["Kathmandu"]
    C --> D

Real-World Tie-In:

• eSewa: When you pay bills, you choose online (credit/debit card) or offline (bank counter). The Addition Principle counts total payment methods.

1.2 Multiplication Principle (AND Rule)

Definition: If a task requires $m$ sequential steps, where the $i^{th}$ step has $n_i$ options, the total number of ways is the product of all options: $n_1\times n_2\times \cdots \times n_k$.

Example:

• Scenario: A Daraz order has:
  • 3 product choices,
  • 2 shipping methods,
  • 4 payment options.
• Solution: $3\times 2\times 4=24$ total possible orders.
• Visual:

  flowchart TD
    A["Order"] --> B["Product: 3"]
    B --> C["Shipping: 2"]
    C --> D["Payment: 4"]
    D --> E["Total: 24"]

Real-World Tie-In:

• Ncell: Your 10-digit phone number is assigned by:
  • 7-digit prefix (e.g., 98xxxxxx),
  • 3-digit suffix (000–999). Total possible numbers: $10^7\times 10^3=10^{10}$ (though not all are used).

2. Permutations and Combinations

2.1 Permutations ($P(n,r)$): Order Matters

Definition: The number of ways to arrange $r$ items from $n$ distinct items where order is important. Formula: $$P(n,r)=\frac{n!}{(n-r)!}$$

Example:

• Scenario: How many ways can 3 friends (A, B, C) stand in a line for a Pathao ride?
• Solution: $$P(3,3)=\frac{3!}{(3-3)!}=6\text{ ways (ABC, ACB, BAC, BCA, CAB, CBA)}$$
• Visual:

  flowchart TD
    A["ABC"] --> B["ACB"]
    A --> C["BAC"]
    A --> D["BCA"]
    A --> E["CAB"]
    A --> F["CBA"]

Real-World Tie-In:

• NEPSE: Stock traders care about the order of trades. If you buy 3 stocks (A, B, C), the sequence matters for tax calculations.

2.2 Combinations ($C(n,r)$): Order Doesn’t Matter

Definition: The number of ways to choose $r$ items from $n$ without regard to order. Formula: $$C(n,r)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\frac{n!}{r!(n-r)!}$$

Example:

• Scenario: How many ways can you pick 2 fruits from 3 (apple, banana, orange) for a snack?
• Solution: $$C(3,2)=\frac{3!}{2!1!}=3\text{ (apple+banana, apple+orange, banana+orange)}$$
• Visual:

  flowchart TD
    A["Apple + Banana"] --> B["Apple + Orange"]
    A --> C["Banana + Orange"]

Real-World Tie-In:

• Khalti: When you transfer money to 2 friends out of 5, the order doesn’t matter—only the group does.

2.3 Permutations vs. Combinations: Comparison Table

3. Advanced Counting Techniques

3.1 Inclusion-Exclusion Principle

Definition: Counts the number of elements in overlapping sets without double-counting. Formula (for 2 sets): $$|A\cup B|=|A|+|B|-|A\cap B|$$ Example:

• Scenario: In a class of 30 students:
  • 18 like math,
  • 12 like physics,
  • 5 like both.
• Solution: $$|Math\cup Physics|=18+12-5=25\text{ students}$$
• Visual:

Real-World Tie-In:

• NTC: Counting subscribers who use both landline and mobile services without duplication.

3.2 Generating Functions (Introductory)

Definition: A formal power series where coefficients represent counts of combinations. Example:

• Scenario: Count the number of ways to make ₹5 using ₹1 and ₹2 coins.
• Solution:
  • Let $x$ represent ₹1, $y$ represent ₹2.
  • Generating function: $(1+x+x^2+\dots )(1+y+y^2+\dots )$.
  • Coefficient of $x^5$ gives the count (here, 3 ways: 5×₹1, 2×₹2+₹1, 1×₹2+3×₹1).

Visual:

graph LR
  A["₹1 coins"] --> B["₹2 coins"]
  B --> C["Total: ₹5"]

Real-World Tie-In:

• Daraz: Calculating discount combinations (e.g., 10% off + free shipping) for orders.

4. Recursive Counting and Trees

4.1 Recursive Definitions

Definition: A problem defined in terms of smaller versions of itself. Example:

• Scenario: Count the number of binary trees with $n$ nodes.
• Solution:
  • Base case: 1 tree for $n=0$ (empty tree).
  • Recursive step: For $n$ nodes, choose a root $k$ (1 ≤ $k$ ≤ $n$), then combine left and right subtrees.
  • Formula: $T(n)={\sum }_{k=1}^{n}T(k-1)\times T(n-k)$.

Visual:

Real-World Tie-In:

• WhatsApp: Message thread hierarchies (replies form recursive trees).

Exam Tip

1. Memorize Formulas:

   • $P(n,r)=\frac{n!}{(n-r)!}$
   • $C(n,r)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)$
   • Inclusion-Exclusion: $|A\cup B|=|A|+|B|-|A\cap B|$

2. Practice Word Problems:

   • Permutation: "Arrange," "order," "rank."
   • Combination: "Choose," "select," "group."

3. Draw Diagrams:

   • Use Venn diagrams for inclusion-exclusion.
   • Use trees for recursive counting.

4. Real-World Scenarios:

   • Ncell: Phone number generation (Multiplication Principle).
   • Khalti: Transaction groups (Combinations).
   • Daraz: Order fulfillment (Permutations).

5. Common Pitfalls:

   • Forgetting order matters in permutations.
   • Misapplying inclusion-exclusion (overlapping sets).
   • Confusing with/without repetition in combinations.

A labelled binary tree showing recursive node splitting. (Image: Public domain, via Wikimedia Commons) Overlapping circles for inclusion-exclusion. (Image: Sommacal alfonso, CC BY-SA 3.0, via Wikimedia Commons)