Counting Principles: Rules, Trees & Real-World Applications

TAKEAWAYS:

• Addition Principle: Count either-or scenarios by summing possibilities (e.g., choosing a transport: bus or taxi).
• Multiplication Principle: Count and scenarios by multiplying choices (e.g., Daraz password: 3 letters and 3 digits).
• Permutations vs. Combinations: Order matters in permutations (e.g., ranking 3 winners), not in combinations (e.g., selecting 3 friends for a group).
• Tree Diagrams: Visualize step-by-step choices (e.g., Ncell’s call routing options).
• Pascal’s Triangle: Generates binomial coefficients for combinations (e.g., NEPSE stock picks).
• Inclusion-Exclusion: Adjust overcounts in overlapping sets (e.g., counting users on both eSewa and Khalti).

1. The Addition Principle: Counting "Either-Or" Scenarios

Definition: If an event $A$ can occur in $m$ ways and an event $B$ can occur in $n$ ways, and $A$ and $B$ are mutually exclusive (cannot happen simultaneously), then the total number of ways either $A$ or $B$ occurs is: $$m+n$$

How it works:

• Mutual exclusivity is key: $A$ and $B$ share no common outcomes.
• Example: Choosing between bus (5 routes) or taxi (3 companies) to Kathmandu from Pokhara. $$\text{Total ways}=5(\text{buses})+3(\text{taxis})=8$$

Visual:

graph TD
    A["Event A\n(m ways)"] -->|"Option 1"| B1["Outcome 1"]
    A -->|"Option 2"| B2["Outcome 2"]
    C["Event B\n(n ways)"] -->|"Option 1"| D1["Outcome 3"]
    C -->|"Option 2"| D2["Outcome 4"]

Real-World Tie:

• eSewa Payments: When you pay via either QR code (1 option) or phone number (5 saved contacts), the addition principle counts the total ways to initiate payment: $$1(\text{QR})+5(\text{contacts})=6\text{ ways}$$

2. The Multiplication Principle: Counting "And" Scenarios

Definition: If event $A$ has $m$ outcomes and event $B$ has $n$ outcomes (independent of $A$), then the total number of combined outcomes is: $$m\times n$$

How it works:

• Independence: Choosing $A$ does not restrict $B$.
• Example: Setting a Daraz account password with:
  • 3 lowercase letters (26 options each)
  • 3 digits (10 options each) $$\text{Total passwords}=26^3\times 10^3=17,576,000$$

Visual:

Real-World Tie:

• Pathao Ride Options: Choosing a driver (10 available) and a pickup location (3 nearby spots): $$10\times 3=30\text{ possible rides}$$
• Ncell SIM Activation: Selecting a plan (4 options) and a data bundle (5 options): $$4\times 5=20\text{ combinations}$$

3. Permutations: Order Matters

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

• Example: Ranking 3 winners (1st, 2nd, 3rd) from 10 contestants: $$P(10,3)=\frac{10!}{7!}=720$$

Visual:

graph TD
    A["10 contestants"] --> B["Choose 1st place\n9 left"]
    B --> C["Choose 2nd place\n8 left"]
    C --> D["Choose 3rd place\n7 left"]

Real-World Tie:

• NEPSE Stock Picks: If you rank your top 2 stocks from 5 options: $$P(5,2)=5\times 4=20\text{ ordered pairs}$$
• Khalti Transaction Codes: A 4-digit code where order matters (e.g., "1234" ≠ "4321"): $$P(10,4)=10\times 9\times 8\times 7=5040$$

4. Combinations: Order Doesn’t Matter

Definition: A combination of $n$ items taken $r$ at a time ($C(n,r)$) is the number of unordered subsets: $$C(n,r)=\frac{n!}{r!(n-r)!}$$

• Example: Forming a 3-person study group from 10 friends: $$C(10,3)=\frac{10!}{3!7!}=120$$

Visual:

Real-World Tie:

• Daraz Product Bundles: Selecting 2 items from 5 in a "Buy 2 Get 1 Free" deal: $$C(5,2)=10\text{ possible pairs}$$
• NTC Bus Routes: Choosing 3 stops from 6 on a Pokhara-Kathmandu route (order irrelevant): $$C(6,3)=20$$

5. Tree Diagrams for Counting

Purpose: Break complex problems into sequential steps. Example: Ncell Network Routing

• Step 1: Choose a tower (3 options).
• Step 2: Choose a frequency band (2 options).
• Total paths: $$3\times 2=6\text{ routes}$$

Visual:

graph TD
    A["Start"] --> B1["Tower 1"]
    A --> B2["Tower 2"]
    A --> B3["Tower 3"]
    B1 --> C1["Band A"]
    B1 --> C2["Band B"]
    B2 --> C3["Band A"]
    B2 --> C4["Band B"]
    B3 --> C5["Band A"]
    B3 --> C6["Band B"]

Worked Example: Problem: How many ways can you order a burger (3 types) with a drink (2 types) and fries (1 type) at a food court? Solution:

1. Burger: 3 choices.
2. Drink: 2 choices.
3. Fries: 1 choice. Total: $$3\times 2\times 1=6\text{ combinations}$$

6. Inclusion-Exclusion Principle

Definition: For two sets $A$ and $B$, the number of elements in $A\cup B$ is: $$|A\cup B|=|A|+|B|-|A\cap B|$$ Example: Counting users on eSewa (500 users) and Khalti (300 users), with 100 users on both: $$|A\cup B|=500+300-100=700$$

Visual:

Real-World Tie:

• NEPSE Investors: Tracking investors in Merchant Bank (200) and NIBL (150), with 50 in both: $$200+150-50=300\text{ unique investors}$$

7. Pascal’s Triangle and Binomial Coefficients

Purpose: Generate $C(n,r)$ values for combinations. Rows 0–4:

        1
      1   1
    1   2   1
  1   3   3   1
1   4   6   4   1

• Entry: $C(n,r)$ is the $r$-th number in the $n$-th row (starting at 0).
• Example: $C(4,2)=6$ (from row 4: 1, 4, 6, 4, 1).

Application:

• Daraz Discount Combinations: If a product has 5 discounts, the number of ways to choose 2 is $C(5,2)=10$.

8. Comparing Permutations and Combinations

9. Worked Example: Ncell Call Routing

Problem: Ncell has 4 towers in Pokhara. A call can route through:

1. Any 1 tower.
2. Any 2 towers (if the first fails). How many possible routing paths are there? Solution:
3. Single tower: $C(4,1)=4$ ways.
4. Two towers: $P(4,2)=4\times 3=12$ (order matters for backup). Total: $$4+12=16\text{ paths}$$

10. Common Pitfalls

1. Misapplying Addition vs. Multiplication:
   • ❌ Adding for "and" scenarios (e.g., $3\text{ shirts}+2\text{ pants}=5$ → wrong!).
   • ✅ Multiply: $3\times 2=6$.
2. Ignoring Order in Combinations:
   • ❌ Using permutations for unordered groups (e.g., $P(5,2)$ for a 2-person team).
   • ✅ Use $C(5,2)$.
3. Overcounting in Inclusion-Exclusion:
   • Forgetting to subtract the overlap $|A\cap B|$.

In the Real World

1. eSewa/Khalti Payments:

   • Idea: Addition Principle for payment methods (QR or phone number).
   • How: If you have 1 QR code and 4 saved contacts, total ways to pay: $$1+4=5\text{ options}$$

2. Daraz Order Fulfillment:

   • Idea: Multiplication Principle for order combinations.
   • How: Choosing 1 product from 10 categories and 1 shipping option (standard/express): $$10\times 2=20\text{ order types}$$

3. Ncell Network Optimization:

   • Idea: Permutations for call routing redundancy.
   • How: If a call can retry via 2 backup towers, the number of ordered backup paths is $P(3,2)=6$.

4. NEPSE Stock Analysis:

   • Idea: Combinations for portfolio selection.
   • How: An investor picking 3 stocks from 10 options: $$C(10,3)=120\text{ possible portfolios}$$

5. Pathao Driver Assignment:

   • Idea: Inclusion-Exclusion for overlapping ride requests.
   • How: If 50 users request rides in Thapathali and 30 in Lakshmi Chowk, with 10 requesting both, total unique requests: $$50+30-10=70$$

Exam Tip

1. Spot Keywords:

   • "Either...or" → Addition Principle.
   • "And" → Multiplication Principle.
   • "Order matters" → Permutations.
   • "Group/team" → Combinations.
   • "Overlap/both" → Inclusion-Exclusion.

2. Draw Diagrams:

   • Always sketch a tree diagram for sequential choices (e.g., password creation, routing).
   • Use Venn diagrams for inclusion-exclusion problems.

3. Unit Consistency:

   • Ensure answers are in the same unit (e.g., permutations vs. combinations).
   • Double-check factorial calculations (e.g., $5!=120$, not 60).

4. Real-World Links:

   • Examiners love ties to Nepalese tech. Mention eSewa, Daraz, or Ncell in explanations to stand out.

5. Common Exam Questions:

   • Calculate $C(n,r)$ or $P(n,r)$ for given $n,r$.
   • Solve word problems using tree diagrams (e.g., "How many ways can you...").
   • Apply inclusion-exclusion to user/data overlaps (e.g., "How many unique users...").

Final Note: Combinatorics is the backbone of algorithm design (e.g., sorting, hashing) and probability. Master these principles, and you’ll ace problems in graph theory (Unit 6), recurrence relations (Unit 9), and even database query optimization in later semesters. Practice with Nepalese examples—they make the concepts stick!