Counting Principles, Permutations, Combinations & Advanced Techniques

TAKEAWAYS:

• Counting rules (addition/multiplication) solve problems where order or grouping matters.
• Permutations count arrangements where order is critical (e.g., passwords, race rankings).
• Combinations count selections where order is irrelevant (e.g., lottery draws, committee picks).
• Inclusion-exclusion adjusts overcounts in overlapping sets (e.g., students in multiple clubs).
• Advanced techniques (stars and bars, derangements) model real-world constraints like resource allocation.

Core Counting Principles

1. Addition and Multiplication Rules

Definitions:

• Addition Rule: If two events $A$ and $B$ are mutually exclusive (cannot occur simultaneously), the total number of ways either can occur is: $$|A\cup B|=|A|+|B|$$
• Multiplication Rule: If $A$ and $B$ are independent events, the number of ways both can occur is: $$|A\times B|=|A|\times |B|$$

Worked Example: Nepalese License Plates

Nepal’s new license plates use:

• 2 letters (A–Z, 26 options each)
• 4 digits (0–9, 10 options each)
• 1 special symbol (e.g., *, 5 options)

Question: How many unique plates are possible? Solution: Letters and digits are independent choices → Multiplication Rule: $$26\times 26\times 10\times 10\times 10\times 10\times 5=26^2\times 10^4\times 5=67,600,000$$

Visual: License Plate Structure

2. Permutations: Order Matters

Definition:

A permutation of $n$ distinct items taken $r$ at a time is: $$P(n,r)=\frac{n!}{(n-r)!}$$

• With repetition: $n^r$ (e.g., PIN codes).
• Without repetition: $P(n,r)$ (e.g., ranking students).

Worked Example: Pathao Driver Routes

A Pathao driver must pick up 3 passengers in Kathmandu’s Thapathali area, where 5 streets intersect. How many unique routes can they take if no street is repeated? Solution: $$P(5,3)=\frac{5!}{2!}=60\text{ routes}$$

Visual: Permutation Tree for $P(3,2)$

graph TD
    A["Start"] --> B["Option 1"]
    A --> C["Option 2"]
    A --> D["Option 3"]
    B --> E["Option 2"]
    B --> F["Option 3"]
    C --> G["Option 1"]
    C --> H["Option 3"]
    D --> I["Option 1"]
    D --> J["Option 2"]

3. Combinations: Order Doesn’t Matter

Definition:

A combination of $n$ items taken $r$ at a time is: $$C(n,r)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\frac{n!}{r!(n-r)!}$$

• Used for committees, lottery draws, or subsets where order is irrelevant.

Worked Example: NEPSE Stock Picks

An investor picks 4 stocks from 10 available. How many unique portfolios? Solution: $$C(10,4)=\frac{10!}{4!6!}=210\text{ portfolios}$$

Visual: Combination vs. Permutation

Advanced Techniques

4. Inclusion-Exclusion Principle

Definition:

For two sets $A$ and $B$: $$|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|$$

Worked Example: eSewa Users

• 80% use eSewa for bills.
• 60% use it for transfers.
• 30% use both. Question: What % use eSewa for either bills or transfers? Solution: $$|A\cup B|=80+60-30=110\%(\text{But max is 100\%!})$$ Correction: Use probabilities (80% = 0.8, etc.): $$0.8+0.6-0.3=1.1\text{(Cap at 1.0 or 100\%)}$$ Visual:

5. Stars and Bars: Distributing Indistinguishable Items

Definition:

The number of ways to distribute $n$ identical items into $k$ distinct boxes is: $$C(n+k-1,k-1)$$

Worked Example: Khalti Cash Distribution

Khalti wants to distribute ₹100 among 3 merchants. How many ways can this be done if merchants can receive ₹0? Solution: $$C(100+3-1,3-1)=C(102,2)=5151\text{ ways}$$

Visual: Stars and Bars for $n=5,k=3$

6. Derangements: Counting Permutations with No Fixed Points

Definition:

A derangement is a permutation where no element appears in its original position. The number of derangements $D(n)$ is: $$D(n)=n!\sum _{i=0}^n\frac{(-1{)}^i}{i!}$$ or recursively: $$D(n)=(n-1)\times (D(n-1)+D(n-2))$$

Worked Example: Ncell Password Scrambling

A 4-digit PIN (0000–9999) is scrambled so no digit stays in its original position. How many valid scrambles exist for PIN 1234? Solution: $$D(4)=9(\text{since }D(4)=9\text{ derangements})$$

Visual: Derangement of 3 Items

graph TD
    A["Original: 1 2 3"] --> B["Derangement 1: 2 3 1"]
    A --> C["Derangement 2: 2 1 3"]
    A --> D["Derangement 3: 3 1 2"]

In the Real World

1. Pathao’s Route Optimization: Uses permutations to calculate the fastest delivery routes for riders, avoiding repeated streets (like the driver’s problem above).

2. NEPSE’s Portfolio Combinations: Investors use combinations to evaluate $C(10,4)=210$ stock portfolios from 10 options, ensuring diversification.

3. eSewa’s User Overlap Analysis: The inclusion-exclusion principle helps eSewa estimate unique users by subtracting overlaps (e.g., users paying bills and transferring money).

4. Khalti’s Merchant Payouts: Stars and bars model how ₹100 can be split among merchants, ensuring fair distribution in microtransactions.

5. Bank Loan Interest Calculations: Permutations model loan repayment schedules where order of payments affects interest (e.g., early principal payments reduce total interest).

Exam Tip

1. Spot the Keyword:

   • "Arrange" → Permutation.
   • "Select" → Combination.
   • "Overlap" → Inclusion-Exclusion.

2. Draw Diagrams: For problems involving sets or distributions, sketch Venn diagrams or stars-and-bars visuals. Examiners reward clarity.

3. Watch Units:

   • Permutations: $n!$ or $P(n,r)$.
   • Combinations: $C(n,r)$ or $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$.
   • Inclusion-Exclusion: Alternate signs for intersections.

4. Real-World Tie-Ins: Questions often disguise scenarios (e.g., "How many ways can a Pathao driver visit 3 customers?" → Permutation).

5. Common Pitfalls:

   • Forgetting to subtract overlaps in inclusion-exclusion.
   • Confusing $P(n,r)$ and $C(n,r)$ (order vs. no order).
   • Misapplying stars and bars (items must be identical; boxes distinct).

Final Note: Master these formulas and their visual counterparts. In exams, if stuck, ask: "Does order matter?" or "Are there overlaps?" to guide your approach.