Counting Techniques: Permutations, Combinations, Inclusion-Exclusion & Advanced Counting

TAKEAWAYS:

• Counting rules solve problems by breaking them into independent/dependent choices (addition vs. multiplication).
• Permutations count ordered arrangements (e.g., passwords, race rankings), while combinations count unordered selections (e.g., lottery numbers, committee members).
• Inclusion-Exclusion Principle corrects overcounting in overlapping sets (e.g., counting students in multiple clubs).
• Generating functions encode combinatorial problems as polynomials for elegant solutions (e.g., counting change combinations).
• Pigeonhole Principle proves existence via counting (e.g., "at least two people share a birthday in a room of 23").
• Real-world ties: Pathao’s ride-matching uses permutations for driver assignments; Ncell’s network routing relies on counting paths in graphs.

1. Fundamental Counting Principles

1.1 Addition Rule (Disjoint Events)

Definition: If two events $A$ and $B$ are mutually exclusive (cannot occur simultaneously), the number of ways either can happen is: $$|A\cup B|=|A|+|B|$$

Visual:

Example: Counting ways to fail an exam (either by missing the test or getting <40%).

• Let $A$ = "missed test" (2 students), $B$ = "scored <40%" (3 students).
• Total failures: $2+3=5$.

Real World:

• eSewa: Counting failed transactions (either "network error" or "insufficient balance").
• NTC: Counting delayed buses (either "mechanical failure" or "driver strike").

1.2 Multiplication Rule (Independent Choices)

Definition: If one event has $m$ outcomes and another has $n$ outcomes, the total combinations are: $$m\times n$$

Visual:

graph LR
    A["Choice 1: 3 options"] --> B["Choice 2: 4 options"]
    B --> C["Total: 3 × 4 = 12 paths"]

Example: Counting license plates with 2 letters followed by 3 digits.

• Letters: $26\times 26=676$ combinations.
• Digits: $10\times 10\times 10=1000$ combinations.
• Total plates: $676\times 1000=676,000$.

Real World:

• Khalti: Generating unique transaction IDs (e.g., 4 letters + 6 digits).
• Daraz: Counting possible product SKUs (category × subcategory × variant).

2. Permutations and Combinations

2.1 Permutations (Order Matters)

Definition: Arrangements of $r$ items from $n$ distinct items where order is important. $$P(n,r)=\frac{n!}{(n-r)!}$$

Visual:

Example: Ranking top 3 students from 10. $$P(10,3)=\frac{10!}{7!}=720$$

Real World:

• Pathao: Assigning 3 drivers to 5 available slots (order matters for efficiency).
• NEPSE: Ranking stocks by daily volume (permutation of top 10 from 100).

2.2 Combinations (Order Doesn’t Matter)

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

Visual:

Example: Choosing 2 subjects from 5. $$C(5,2)=\frac{5!}{2!3!}=10$$

Real World:

• Ncell: Selecting 4 base stations to cover a city (order irrelevant).
• Lotto: Picking 6 numbers from 49 (combinations, not permutations).

3. Inclusion-Exclusion Principle

Definition: Corrects overcounting when sets overlap. For two sets: $$|A\cup B|=|A|+|B|-|A\cap B|$$ For three sets: $$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$$

Visual:

Example: Counting students in at least one club (Math, Chess, Debate).

• Math: 30, Chess: 25, Debate: 20
• Math ∩ Chess: 10, Math ∩ Debate: 8, Chess ∩ Debate: 5
• Math ∩ Chess ∩ Debate: 3 $$|A\cup B\cup C|=30+25+20-10-8-5+3=55$$

Real World:

• Khalti: Counting users with either a savings account or a loan (but not double-counting overlaps).
• NTC: Counting buses delayed by either rain or strikes (but not both).

4. Advanced Counting Techniques

4.1 Generating Functions

Definition: Polynomials where coefficients represent counts. Example: Counting ways to make ₹10 with ₹2 and ₹5 coins. Generating function: $$G(x)=(1+x^2+x^4+\dots )(1+x^5+x^{10}+\dots )=\frac{1}{(1-x^2)(1-x^5)}$$ Coefficient of $x^{10}$ gives the answer (3 ways).

Visual:

Real World:

• Daraz: Counting possible discount combinations (e.g., 10% off + free shipping).
• Ncell: Counting data plans with bundled minutes/calls.

4.2 Pigeonhole Principle

Definition: If $n$ items are placed into $m$ containers ($n>m$), at least one container holds ≥2 items.

Example: In a room of 23 people, at least two share a birthday. $$\text{Pigeonholes}=365\text{ days},\text{Items}=23\text{ people}⟹23>365/2$$

Real World:

• Pathao: With 101 drivers and 100 zones, at least one zone has ≥2 drivers (by Pigeonhole).
• NTC: With 500 buses and 499 stops, at least one stop has ≥2 buses.

5. Worked Example: Kathmandu Traffic Routes

Problem: How many ways can a taxi travel from Thamel to Lakshmi Chowk via exactly 2 intermediate stops (order matters)?

• Stops: Thamel (T), Durbar Square (D), Asan (A), Koteshwor (K), Lakshmi Chowk (L).
• Intermediate stops: Choose 2 from {D, A, K}, then arrange them.

Solution:

1. Combination step: Choose 2 stops from 3. $$C(3,2)=3$$
2. Permutation step: Arrange the 2 stops (order matters). $$P(2,2)=2!=2$$
3. Total paths: $3\times 2=6$.

Visual:

graph TD
    T --> D --> A --> L
    T --> D --> K --> L
    T --> A --> D --> L
    T --> A --> K --> L
    T --> K --> D --> L
    T --> K --> A --> L

6. Comparison Table: Permutations vs. Combinations

7. Common Mistakes to Avoid

1. Confusing permutations/combinations: Remember "permutation = order," "combination = group."
2. Ignoring dependencies: Multiplication rule applies only to independent choices.
3. Overcounting in inclusion-exclusion: Always subtract pairwise intersections, then add back triple intersections.
4. Factorial errors: $0!=1$, and $n!=n\times (n-1)!$.

In the Real World

1. Pathao’s Ride-Matching Algorithm:

   • Uses permutations to assign drivers to requests based on proximity (order of pickup matters for efficiency).
   • Example: If 5 drivers are available for 3 requests, the system calculates $P(5,3)=60$ possible assignments.

2. Ncell’s Network Routing:

   • Employs combinations to select optimal base stations for coverage (order irrelevant).
   • Example: Covering a city with 4 base stations from 10 available: $C(10,4)=210$ possible combinations.

3. Khalti’s Transaction IDs:

   • Generates unique IDs using the multiplication rule (e.g., 4 letters × 6 digits = $26^4\times 10^6$ possibilities).
   • Example: A transaction ID like ABCD123456 ensures uniqueness via combinatorial design.

4. NEPSE Stock Rankings:

   • Uses permutations to rank top 10 stocks by trading volume (order matters for investors).
   • Example: Ranking 5 stocks from 10: $P(10,5)=30,240$ possible orderings.

5. Daraz’s Inventory Management:

   • Applies the Pigeonhole Principle to ensure no product runs out of stock in all warehouses.
   • Example: With 100 products and 5 warehouses, at least one warehouse must stock ≥20 products.

Exam Tip

1. Spot the key phrase:

   • "Arranged in a line" → Permutation.
   • "Selected as a team" → Combination.
   • "At least one" → Inclusion-Exclusion.

2. Show all steps:

   • For $P(n,r)$ or $C(n,r)$, write the formula and simplify.
   • For inclusion-exclusion, draw a Venn diagram and label all regions.

3. Real-world twist:

   • Exams often ask: "How many ways can Pathao assign 3 drivers to 5 requests?" → $P(5,3)$.
   • Or: "How many Ncell base station pairs cover a city?" → $C(n,2)$.

4. Avoid memorization:

   • Focus on why you multiply/divide (e.g., "divide by $r!$ because order doesn’t matter").

5. Practice with variations:

   • "At least one" → Use inclusion-exclusion.
   • "Exactly one" → Use $C(n,1)\times \text{rest}$.

Final Note: Combinatorics is about logical breakdown. Break problems into smaller, independent choices, and let the rules guide you!