8.1 Counting Principles, Permutations, Combinations & Stars and Bars

Back to Discrete Mathematics Notes

📚Module 08: Combinatorics & Recurrence RelationsTopic 8.1: Counting Principles, Permutations & Stars and Bars⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: Fast Food Menus, Passwords & Coin Jars

Think of counting as structuring choices in physical spaces:

1. Rule of Sum (Mutually Exclusive Alternatives): You are buying lunch. You can pick either a burger from the 5 burger options OR a salad from the 3 salad options. Total independent meal choices: $5 + 3 = 8$. In choice, you use addition (+).
2. Rule of Product (Sequential Multi-Stage Choices): You are building a combo meal. You pick 1 of 5 burgers, AND 1 of 4 drinks, AND 1 of 3 sides. Total compound configurations: $5 \times 4 \times 3 = 60$ unique meals! In mandatory sequential stages, you use multiplication ($\times$).
3. Permutation vs Combination:
   • Permutation (Order Matters): Setting a 4-digit security PIN (1-2-3-4 is completely different from 4-3-2-1). Permutation = Choose and Arrange.
   • Combination (Order Irrelevant): Picking a 4-person study team (Alice, Bob, Charlie, Dave is the exact same team regardless of who you named first). Combination = Choose Only.
4. Stars and Bars (Distributing Identical Candies): You have 10 identical gold coins ($n = 10$) to drop into 3 piggy banks ($r = 3$). You don't label the coins; you simply place 2 divider sticks (bars) between the 10 coins (stars). Any arrangement of stars and bars uniquely represents an integer partition!

💻 Bridging to Computer Science: Address Spaces, Combinatorial Testing & State Spaces

In computer systems:

• IPv4 / IPv6 Address Spaces: Calculating address capacities uses the Rule of Product: an IPv4 address has $2 \times 2 \times \dots \times 2 = 2^{32} \approx 4.29 \times 10^9$ unique host addresses.
• Complexity Analysis: Measuring the search space of NP-complete problems (e.g., Travelling Salesperson has $(n-1)! / 2$ tours; Knapsack has $2^n$ subsets).
• Resource Allocation in OS: Distributing $n$ identical buffer pages among $r$ active processes is the classical Stars and Bars problem.
• Compiler Symbol Tables: Lexicographic indexing and keyword permutations determine dictionary search efficiency.

📑Table of Contents

• ⚡ Fundamental Counting Principles
• 🔀 Permutations with Repeated Elements (Multi-Sets)
• 🧩 Advanced Arrangement Paradigms: The String & Gap Methods
• 🔄 Circular Permutations & Symmetries
• 📖 Lexicographic Word Rank & The Fast Factorial Trick
• 🔢 Digit Permutations & The Master Sum Formula
• ⭐ The Stars and Bars Theorem (Integer Partitions)
• 📐 Geometric Combinatorics & Shortcuts
• 📝 Step-by-Step Worked Examples
  • Example 1: Multi-Set Permutations of "MISSISSIPPI" Under Adjacency Restrictions
  • Example 2: Distributing Identical OS Memory Frames via Stars and Bars
• 🎯 Exam & Interview Pitfall Check

---

⚡ Fundamental Counting Principles

⚡Law 8.1: The Two Foundational Counting Ruleslaw

1. The Rule of Sum (Disjoint Unions - OR Rule): If a task can be performed in either of two mutually exclusive ways, where the first way has $m$ possible outcomes and the second way has $n$ possible outcomes (with no overlap): $$|A \cup B| = |A| + |B| = m + n \quad (\text{provided } A \cap B = \emptyset)$$
2. The Rule of Product (Cartesian Multi-Stage Execution - AND Rule): If a procedure can be broken down into two successive stages, where Stage 1 has $m$ possible choices, and for each choice in Stage 1, Stage 2 has $n$ possible choices: $$|A \times B| = |A| \cdot |B| = m \cdot n$$

✓ Combinatorial Selection Space

Vertical axis: Division by r! strips ordering; Horizontal axis: Multi-set expansion incorporates repetitions.

The 4 Fundamental Combinatorial Counting Archetypes

Matrix comparing ordered vs unordered selection with and without replacement

🔢

Permutations (No Repetition)

Ordered, Distinct

• Select and arrange r distinct items from n available items.
• Formula: P(n, r) = n! / (n - r)!.
• Example: Assigning 1st, 2nd, and 3rd place podium medals.

🔄

Permutations (With Repetition)

Ordered, Multi-Set

• Each of the r positions independently picks any of the n items.
• Formula: nʳ.
• Example: Generating an r-digit numeric PIN using digits 0-9 (10ʳ).

🤝

Combinations (No Repetition)

Unordered, Distinct

• Select r items from n distinct items where sequence does not matter.
• Formula: C(n, r) = n! / (r! (n - r)!).
• Example: Selecting a 5-card poker hand from a 52-card deck.

⭐

Combinations (With Repetition)

Stars and Bars

• Select r items from n types where items of same type are indistinguishable.
• Formula: C(n + r - 1, r) = C(n + r - 1, n - 1).
• Example: Distributing identical jobs across CPU execution queues.

---

🔀 Permutations with Repeated Elements (Multi-Sets)

When arranging $n$ total objects where some objects are identical:

📐Theorem 8.1: Multi-Set Permutation Formulatheorem

The number of unique permutations of $n$ objects where there are $n_1$ identical objects of type 1, $n_2$ identical objects of type 2, ..., and $n_k$ identical objects of type $k$ (such that $n_1 + n_2 + \dots + n_k = n$) is given by the Multinomial Coefficient:

$$\binom{n}{n_1, n_2, \dots, n_k} = \frac{n!}{n_1! \, n_2! \, n_3! \, \dots \, n_k!}$$

Proof Intuition: If all $n$ objects were distinct, there would be $n!$ arrangements. However, permuting the $n_1$ identical objects among themselves in $n_1!$ ways produces visually indistinguishable arrangements. By the Division Rule, we divide out all internal symmetries $n_1! n_2! \dots n_k!$.

---

🧩 Advanced Arrangement Paradigms: The String & Gap Methods

Two standard arrangement constraints appear universally in competitive exams and interview questions:

The String Method vs The Gap Method

Handling 'always together' vs 'never together' constraints in linear seating

🧵

The String / Tie Method

Items MUST Be Together

• Bundle all items that must stay together into a single composite super-unit.
• Step 1: Arrange the remaining items along with the composite super-unit.
• Step 2: Multiply by the internal permutations of the items inside the super-unit.
• Formula: (Remaining Items + 1)! × (Bundle Size)!

🪟

The Gap Method

NO Two Items Together

• Step 1: First arrange the unconstrained items in a row in m! ways.
• Step 2: This creates m + 1 distinct empty gaps (including both ends).
• Step 3: Select and arrange the k constrained items into these m + 1 gaps.
• Formula: m! × P(m + 1, k) (Valid if and only if k ≤ m + 1).

📐Case Study: Seating 5 Boys and 4 Girls with Adjacency Constraintsexample

Let there be 5 boys ($B_1, \dots, B_5$) and 4 girls ($G_1, \dots, G_4$):

1. No two girls sit together (Gap Method):
   • First arrange the 5 boys: $5! = 120$ ways.
   • The boys create $5 + 1 = 6$ gaps: $\_ \; B_1 \; \_ \; B_2 \; \_ \; B_3 \; \_ \; B_4 \; \_ \; B_5 \; \_$.
   • Place the 4 girls into any 4 of these 6 gaps: ${}^6 P_4 = 6 \times 5 \times 4 \times 3 = 360$ ways.
   • Total ways = $5! \times {}^6 P_4 = 120 \times 360 = 43,200$ ways.
2. No two boys sit together (Gap Method):
   • First arrange the 4 girls: $4! = 24$ ways.
   • The girls create $4 + 1 = 5$ gaps: $\_ \; G_1 \; \_ \; G_2 \; \_ \; G_3 \; \_ \; G_4 \; \_$.
   • Place the 5 boys into these 5 gaps: ${}^5 P_5 = 5! = 120$ ways.
   • Total ways = $4! \times 5! = 24 \times 120 = 2,880$ ways.
3. A particular pair of girls ($G_1, G_2$) must always sit together (String Method):
   • Bundle $G_1, G_2$ into a single composite unit: $[G_1 G_2]$.
   • Entities to arrange: 5 boys + 2 remaining girls + 1 composite unit = 8 entities.
   • External arrangements: $8!$ ways.
   • Internal permutations inside the bundle: $2!$ ways ($G_1 G_2$ or $G_2 G_1$).
   • Total ways = $8! \times 2! = 40,320 \times 2 = 80,640$ ways.
4. A particular pair of girls ($G_1, G_2$) must NOT sit together (Complementary Counting):
   • Total unrestricted arrangements of 9 people: $9! = 362,880$.
   • Arrangements where $G_1, G_2$ sit together: $8! \times 2! = 80,640$.
   • Total ways = $\text{Total} - \text{Together} = 9! - (8! \times 2!) = 282,240$ ways.

---

🔄 Circular Permutations & Symmetries

Arranging items around a closed circle differs fundamentally from linear arrangements because circular rotations do not produce distinct arrangements.

📐Theorem 8.2: Circular Arrangements & Flip Invariancetheorem

1. Circular Permutation of $n$ Distinct Entities: Fixing 1 reference entity removes the $n$ rotational degrees of freedom: $$P_{\text{circular}}(n) = \frac{n!}{n} = (n - 1)!$$
2. Necklaces & Keyrings (Reflection / Flip Invariance): If a necklace can be flipped over, clockwise and counter-clockwise arrangements become identical mirror images: $$P_{\text{necklace}}(n) = \frac{(n - 1)!}{2}$$ With $n_1$ beads of color 1, $n_2$ of color 2, ..., $n_k$ of color $k$: $$P_{\text{necklace multi-set}} = \frac{(n - 1)!}{2 \cdot n_1! \, n_2! \, \dots \, n_k!}$$
3. The Circular Gap Method (Crucial Rule):
   • When the first group of $m$ items is arranged in a circle, it takes $(m - 1)!$ ways.
   • Crucial Invariant: Once the first group is seated in the circle, the $m$ gaps between them become linearly distinct (each gap is indexed by the specific unique neighbors to its left and right).
   • Therefore, the second group of $k$ items is placed into the $m$ gaps in ${}^m P_k$ linear ways!
   • Total ways = $(m - 1)! \times {}^m P_k$.

📐Example: Circular Seating of 7 Girls and 6 Boysexample

Let 7 girls and 6 boys be seated around a circular table:

1. No two boys sit together:
   • First seat the 7 girls around the circular table: $(7 - 1)! = 6! = 720$ ways.
   • The 7 girls create 7 distinct gaps between them.
   • Seat the 6 boys into these 7 distinct gaps: ${}^7 P_6 = 7! = 5,040$ ways.
   • Total ways = $6! \times {}^7 P_6 = 720 \times 5,040 = 3,628,800$ ways.
2. Boys and girls sit alternately ($7$ boys and $7$ girls):
   • Seat 7 boys in circle: $(7 - 1)! = 6!$ ways.
   • Seat 7 girls in the 7 gaps: $7!$ ways.
   • Total ways = $6! \times 7! = 720 \times 5,040 = 3,628,800$ ways.

---

📖 Lexicographic Word Rank & The Fast Factorial Trick

The rank of a word is its 1-based index when all unique anagrams formed by its letters are sorted alphabetically in a dictionary.

Dictionary Rank Algorithms

Classical tree counting versus the rapid right-hand factorial formula

📚

Standard Lexicographic Counting

Branch-by-Branch

• Sort all characters in alphabetical order.
• Count all permutations starting with characters preceding the target's first letter.
• Fix the matched letter and recursively count sub-branches.
• Add +1 at the end for the word itself.

⚡

Fast Factorial Shortcut Trick

O(n) Direct Evaluation

• Write the word. For each letter, count how many letters strictly to its RIGHT are alphabetically smaller.
• Multiply each count by the corresponding descending factorial: (n-1)!, (n-2)!, ..., 0!.
• For repeated letters, divide each term by the repeat factorials in the suffix.
• Sum all products and add +1.

📐Worked Example: Finding the Rank of 'SIPRON' (No Repetition)example

Target word: SIPRON (Length $n = 6$). Alphabetical order of letters: $I (1), N (2), O (3), P (4), R (5), S (6)$.

Applying the Fast Factorial Trick:

1. Letter S: Letters to its right smaller than S: $\{I, P, R, O, N\}$ (Count = 5). Multiplier: $5!$. $\to 5 \times 5! = 600$.
2. Letter I: Letters to its right smaller than I: none (Count = 0). Multiplier: $4!$. $\to 0 \times 4! = 0$.
3. Letter P: Letters to its right smaller than P: $\{O, N\}$ (Count = 2). Multiplier: $3!$. $\to 2 \times 3! = 12$.
4. Letter R: Letters to its right smaller than R: $\{O, N\}$ (Count = 2). Multiplier: $2!$. $\to 2 \times 2! = 4$.
5. Letter O: Letters to its right smaller than O: $\{N\}$ (Count = 1). Multiplier: $1!$. $\to 1 \times 1! = 1$.
6. Letter N: Letters to its right smaller than N: none (Count = 0). Multiplier: $0!$. $\to 0 \times 0! = 0$.

$$\text{Rank} = (600 + 0 + 12 + 4 + 1 + 0) + 1 = 617 + 1 = 618$$

📐Worked Example: Finding the Rank of 'SECRET' (With Repetition)example

Target word: SECRET (Length $n = 6$). Letters: $C (1), E (2), E (2), R (4), S (5), T (6)$. Repeats: $E$ appears 2 times.

1. S: Smaller to right: $\{E, C, R, E, T\} \to \{E, C, E\}$ (Count = 3). Suffix has $\{E, C, R, E, T\}$ with two $E$'s: $\frac{3 \times 5!}{2!} = \frac{360}{2} = 180$. (Wait: check letters to right: E, C, R, E: smaller than S are C, E, R, E $\to 4$ letters smaller!) Let's check strictly: $E, C, R, E$ are all smaller than $S$. That is 4 letters! Term = $\frac{4 \times 5!}{2!} = \frac{480}{2} = 240$.
2. E: Suffix is $CRET$. Smaller to right: $C$ (Count = 1). Suffix has no repeats ($C, R, E, T$ has one $E$ remaining): $\frac{1 \times 4!}{1!} = 24$. (Note: if both E's were in suffix, divide by $2!$; here only one E remains, so divide by $1!$). Term = $24 / 2!$ if counting both: since the current letter is $E$, the suffix $CRET$ has one $E$. So repeats = $1!$. $\to 1 \times 4! = 24 / 2 = 12$ (if second $E$ counts).
3. C: Suffix $RET$. Smaller to right: none (0). Term = 0.
4. R: Suffix $ET$. Smaller to right: $E$ (Count = 1). Term = $1 \times 2! = 2$.
5. E: Suffix $T$. Smaller to right: none (0). Term = 0.
6. T: Suffix empty. Term = 0.

Sum of terms = $240 + 12 + 0 + 2 + 0 + 0 = 254$.

$$\text{Rank of 'SECRET'} = 254 + 1 = 255$$

---

🔢 Digit Permutations & The Master Sum Formula

📐Theorem 8.3: Master Formula for Sum of All Formed Numberstheorem

Given $n$ distinct non-zero digits $\{d_1, d_2, \dots, d_n\}$, the sum of all $n$-digit numbers formed using each digit exactly once without repetition is:

$$\text{Sum} = (n - 1)! \times \left( \sum_{i=1}^n d_i \right) \times (\underbrace{111\dots 1}_{n \text{ ones}})$$

Proof Derivation:

• In an $n$-digit number, each digit appears at each decimal position (units, tens, hundreds, ..., $10^{n-1}$) exactly $(n - 1)!$ times.
• The total contribution of all digits at a single decimal place is $(n - 1)! \sum d_i$.
• Summing across all place values: $$(n - 1)! \left( \sum d_i \right) [10^{n-1} + 10^{n-2} + \dots + 10^0] = (n - 1)! \left( \sum d_i \right) (\underbrace{111\dots 1}_{n})$$

📐Example: Sum of All 4-Digit Numbers Formed from {2, 3, 4, 5}example

Digits: $\{2, 3, 4, 5\}$ ($n = 4$).

• $(n - 1)! = 3! = 6$.
• Sum of digits: $2 + 3 + 4 + 5 = 14$.
• Place multiplier: $1111$.

$$\text{Total Sum} = 6 \times 14 \times 1111 = 84 \times 1111 = 93,324$$

---

⭐ The Stars and Bars Theorem (Integer Partitions)

The Stars and Bars method (also known as the Bose-Einstein distribution) counts the number of ways to distribute $n$ identical items into $r$ distinct containers.

📐Theorem 8.4: Stars and Bars (Non-Negative vs Positive Integer Solutions)theorem

1. Non-Negative Integer Solutions ($x_i \ge 0$): The number of solutions to $x_1 + x_2 + \dots + x_r = n$ where $x_i \in \mathbb{N}_0$ is:

   $$\binom{n + r - 1}{r - 1} = \binom{n + r - 1}{n}$$

   Visual Derivation: $n$ stars ($\star$) and $r - 1$ divider bars ($|$) give $n + r - 1$ total positions. Choosing $r - 1$ positions for the bars partitions the stars into $r$ distinct buckets.

2. Strictly Positive Integer Solutions ($x_i \ge 1$): The number of solutions to $x_1 + x_2 + \dots + x_r = n$ where $x_i \ge 1$ is:

   $$\binom{n - 1}{r - 1}$$

   Derivation: Pre-allocate 1 item to each of the $r$ containers, leaving $n - r$ items to distribute freely with $y_i \ge 0$: $\binom{(n - r) + r - 1}{r - 1} = \binom{n - 1}{r - 1}$.

3. General Lower Bounds ($x_i \ge k_i$): Substitute $y_i = x_i - k_i \ge 0$. The equation becomes:

   $$\sum_{i=1}^r y_i = n - \sum_{i=1}^r k_i = n' \implies \binom{n' + r - 1}{r - 1}$$

📐Case Study: Restricted Dice Sum Problem with Upper Boundsexample

Problem: Find the number of ways 3 standard 6-sided dice can yield a sum of 10. Equation: $x_1 + x_2 + x_3 = 10$ subject to $1 \le x_i \le 6$ for each die.

1. Step 1: Total positive integer solutions ($x_i \ge 1$): $$\binom{n - 1}{r - 1} = \binom{10 - 1}{3 - 1} = \binom{9}{2} = \frac{9 \times 8}{2} = 36$$
2. Step 2: Subtract violations where some die exceeds 6 ($x_i \ge 7$):
   • Suppose Die 1 violates the constraint: $x_1 \ge 7$.
   • Set $y_1 = x_1 - 6 \ge 1$. The equation becomes: $$y_1 + x_2 + x_3 = 10 - 6 = 4 \quad (y_1 \ge 1, x_2 \ge 1, x_3 \ge 1)$$
   • Number of solutions: $\binom{4 - 1}{3 - 1} = \binom{3}{2} = 3$.
   • By symmetry, any of the 3 dice could violate: $3 \times \binom{3}{2} = 3 \times 3 = 9$.
   • Note: Can two dice simultaneously violate? If two dice are $\ge 7$, sum $\ge 7 + 7 + 1 = 15 > 10$, which is impossible.
3. Step 3: Apply Principle of Inclusion-Exclusion: $$\text{Valid Ways} = \binom{9}{2} - 3 \binom{3}{2} = 36 - 9 = 27$$

---

📐 Geometric Combinatorics & Shortcuts

📐Theorem 8.5: Geometric Combinatorics Toolkittheorem

1. Diagonals of an $n$-sided Polygon: Connecting any 2 vertices gives a line segment ($\binom{n}{2}$). Subtracting the $n$ perimeter edges: $$\text{Diagonals} = \binom{n}{2} - n = \frac{n(n - 1)}{2} - n = \frac{n(n - 3)}{2}$$
2. Intersections of Straight Lines: Given $n$ straight lines in a plane with no two parallel and no three concurrent: $$\text{Intersection Points} = \binom{n}{2}$$
3. Parallelograms in a Grid: Given a family of $p$ parallel lines intersecting another family of $q$ parallel lines: $$\text{Parallelograms} = \binom{p}{2} \times \binom{q}{2}$$
4. Collinear Points in a Plane: Given $n$ coplanar points where $p$ points are strictly collinear (and no other 3 are collinear):
   • Straight Lines Formed: $\binom{n}{2} - \binom{p}{2} + 1$ (the $p$ points collapse to 1 single line).
   • Triangles Formed: $\binom{n}{3} - \binom{p}{3}$ (collinear points cannot form triangles).
5. Round-Robin Tournament Matches: In a tournament of $n$ teams where each team plays every other team exactly $k$ times: $$\text{Total Matches} = k \cdot \binom{n}{2} = k \frac{n(n - 1)}{2}$$
6. Selection from Multi-Sets (Alphabet Selection): Given a multi-set of identical items $A^{n_1} B^{n_2} \dots Z^{n_k}$, the number of ways to select one or more items is: $$\text{Non-Empty Selections} = (n_1 + 1)(n_2 + 1) \dots (n_k + 1) - 1$$ (Subtract 1 for the empty selection where 0 items of each type are chosen).

---

📝 Step-by-Step Worked Examples

Example 1: Multi-Set Permutations of "MISSISSIPPI" Under Adjacency Restrictions

Problem Statement: Find the number of unique arrangements of all letters in the word "MISSISSIPPI":

1. With no restrictions.
2. Such that all four 'S' letters appear together.
3. Such that no two 'S' letters appear together.

Step-by-Step Solution: Letter counts: $M = 1, I = 4, S = 4, P = 2$ (Total $n = 11$).

1. Part 1: Unrestricted Arrangements: $$\text{Total} = \frac{11!}{1! \times 4! \times 4! \times 2!} = \frac{39,916,800}{1 \times 24 \times 24 \times 2} = \frac{39,916,800}{1,152} = 34,650$$
2. Part 2: All Four 'S' Together (String Method):
   • Bundle four S's into $[SSSS]$ (1 unit).
   • Remaining letters: $M(1), I(4), P(2) \to 7$ letters.
   • Total units = $1 + 7 = 8$ units.
   $$\text{Arrangements} = \frac{8!}{1! \times 4! \times 2! \times 1!} = \frac{40,320}{24 \times 2} = 840$$
3. Part 3: No Two 'S' Together (Gap Method):
   • First arrange the non-S letters: $M(1), I(4), P(2)$ (7 letters). $$\text{Ways to arrange non-S letters} = \frac{7!}{1! \times 4! \times 2!} = \frac{5,040}{48} = 105$$
   • These 7 letters create $7 + 1 = 8$ gaps: $\_ \; L_1 \; \_ \; L_2 \; \_ \; L_3 \; \_ \; L_4 \; \_ \; L_5 \; \_ \; L_6 \; \_ \; L_7 \; \_$
   • Choose 4 of these 8 gaps for the 4 identical S letters: $\binom{8}{4} = \frac{8 \times 7 \times 6 \times 5}{24} = 70$.
   • Total arrangements = $105 \times 70 = 7,350$.

---

Example 2: Distributing Identical OS Memory Frames via Stars and Bars

Problem Statement: An operating system has 15 identical memory frames to distribute among 4 processes ($P_1, P_2, P_3, P_4$).

1. In how many ways can the frames be distributed if a process is allowed to receive 0 frames?
2. In how many ways can the frames be distributed if process $P_1$ must receive at least 2 frames, and every other process must receive at least 1 frame?

Step-by-Step Solution:

1. Part 1: Non-Negative Integer Solutions ($x_i \ge 0$):
   • Equation: $x_1 + x_2 + x_3 + x_4 = 15$ with $x_i \ge 0$.
   • Formula: $\binom{n + r - 1}{r - 1} = \binom{15 + 4 - 1}{4 - 1} = \binom{18}{3} = \frac{18 \times 17 \times 16}{6} = 816$ ways.
2. Part 2: Lower-Bound Inequality ($x_1 \ge 2, x_2 \ge 1, x_3 \ge 1, x_4 \ge 1$):
   • Pre-allocate the required frames: $2 + 1 + 1 + 1 = 5$ frames.
   • Remaining frames to distribute freely: $15 - 5 = 10$ frames.
   • Transformed equation: $y_1 + y_2 + y_3 + y_4 = 10$ with $y_i \ge 0$.
   • Formula: $\binom{10 + 4 - 1}{4 - 1} = \binom{13}{3} = \frac{13 \times 12 \times 11}{6} = 286$ ways.

---

🎯 Exam & Interview Pitfall Check

Combinatorial Problem Scenario	Correct Mathematical Formula	Common Incorrect Trap
Distribute $n$ identical balls into $r$ distinct bins	$\binom{n + r - 1}{r - 1}$ (Stars and Bars)	Confusing with $r^n$ (which is for distinct balls)
Distribute $n$ distinct balls into $r$ distinct bins	$r^n$ (Rule of Product)	Using $\binom{n+r-1}{r-1}$
Seating $n$ people in a circle	$(n - 1)!$	Using $n!$ (forgetting rotational symmetry)
Circular gap method with $m$ items in circle	$(m - 1)! \times {}^m P_k$	Treating circular gaps as $(m-1)$ gaps instead of $m$ linear gaps
Diagonals of $n$-sided polygon	$\frac{n(n - 3)}{2}$	Using $\binom{n}{2}$ (forgetting to subtract $n$ edges)
$x_1 + \dots + x_r = n$ with $x_i \ge 1$	$\binom{n - 1}{r - 1}$	Using $\binom{n+r-1}{r-1}$ without subtracting pre-allocations

Core Conceptual Questions

Question 1: What is the mathematical difference between distributing $n$ identical balls into $r$ distinct boxes versus $n$ distinct balls into $r$ distinct boxes? Key Focus Points:

• Identical balls into distinct boxes: Stars and Bars! Formula: $\binom{n + r - 1}{r - 1}$. Only the count of balls landing in each box matters.
• Distinct balls into distinct boxes: Rule of Product! Each unique ball independently chooses any of the $r$ boxes: $r \times r \times \dots \times r = r^n$.

Question 2: How many terms are in the expansion of $(x_1 + x_2 + \dots + x_r)^n$? Key Focus Points: Each term in the multinomial expansion has the form $x_1^{k_1} x_2^{k_2} \dots x_r^{k_r}$ where $k_1 + k_2 + \dots + k_r = n$ with $k_i \ge 0$. The number of distinct terms is exactly the number of non-negative integer solutions to this equation:

$$\text{Total Terms} = \binom{n + r - 1}{r - 1}$$

Common Interview Traps

Trap 1: Treating Gaps in Circular Permutations as Circular Gaps Why it fails: When $m$ people sit in a circle, there are $(m-1)!$ circular arrangements. But once they sit, each gap is uniquely bounded by two specific people (e.g., between Alice and Bob vs between Bob and Charlie). The gaps are therefore linearly distinct! The remaining $k$ people are arranged in ${}^m P_k$ ways, NOT $(m-1)!$.

Trap 2: Forgetting to Subtract Non-Existent Triangles from Collinear Points Why it fails: If $p$ points out of $n$ are collinear, students often write $\binom{n}{3}$. Any 3 points chosen from the $p$ collinear points form a straight line, not a triangle! You must subtract $\binom{p}{3}$.

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic7.3 First-Order Validity, Semantic Tableaux & Prenex Normal FormNext Topic →8.2 Linear Recurrence Relations: Characteristic Roots & Particular Solutions