Source: CS182 Quiz 8 Solutions, Purdue University
Tags: permutations, combinations, binomial theorem, binomial coefficient, overcounting, indistinguishable objects, constrained arrangements, discrete mathematics, combinatorics
Difficulty: Intermediate Prerequisites: Fundamental counting principles (product rule, sum rule, subtraction rule). Comfortable with factorials and basic algebra.
Once you can count independent choices with the product rule, the next step is learning to handle order and repetition. Permutations count arrangements where order matters; combinations count selections where it does not. Most exam problems sit somewhere between, often requiring you to count naively and then correct for overcounting. The binomial theorem ties these ideas to algebra by telling you the coefficient of any term in a binomial expansion. This material shows up repeatedly in probability, algorithm analysis, and data science.
Permutations care about order; combinations do not. When objects are indistinguishable, you divide out the redundant arrangements. The binomial theorem uses C(n, k) to expand (a + b)ⁿ, and finding a specific coefficient means identifying the right value of k and accounting for any constants raised to a power.
Permutation, P(n, k)
The number of ways to arrange k items chosen from n distinct items, where order matters. P(n, k) = n! / (n − k)!. In simple terms, it is the number of ordered sequences of length k you can make from n options.
Combination, C(n, k)
The number of ways to choose k items from n distinct items, where order does not matter. C(n, k) = n! / (k!(n − k)!). Think of it as: pick a group, ignore the arrangement within the group.
Factorial (n!)
The product of all positive integers from 1 to n. By convention, 0! = 1. Factorials count the total number of ways to arrange n distinct objects in a line.
Overcounting
A situation where a naive count assigns multiple labels to the same outcome. The fix is to divide by the number of redundant labels per outcome.
Indistinguishable objects
Objects that cannot be told apart. Swapping two indistinguishable objects does not produce a new arrangement, so you divide by the number of internal swaps.
Binomial coefficient
Another name for C(n, k). It gives the coefficient of aᵏbⁿ⁻ᵏ in the expansion of (a + b)ⁿ.
Binomial theorem
(a + b)ⁿ = Σ (k = 0 to n) C(n, k) · aⁿ⁻ᵏ · bᵏ. Each term in the expansion corresponds to choosing k of the n factors to contribute b (and the rest contribute a).
Problem: arrange a family of 5 (father, mother, 3 children) in a row so that the parents sit next to each other.
Technique: "glue" the constrained elements together and treat them as a single block.
The parent block can be internally arranged in 2! = 2 ways (father-mother or mother-father).
Treating the block as one unit, there are now 4 entities to arrange: 4! = 24 ways.
By the product rule: 2! × 4! = 48 seating arrangements.
Problem: seat 15 CS majors and 5 DS majors in a row so that no two DS majors are adjacent and no DS major sits at either end.
Technique: arrange the unrestricted group first, then place the restricted group into the available gaps.
Arrange 15 CS majors: 15! orderings.
This creates 14 internal gaps (between consecutive CS majors). End seats are excluded by the problem.
Place 5 DS majors into 14 gaps, order matters, no two in the same gap: P(14, 5).
Total: 15! × P(14, 5).
Problem: how many 5-card hands from a standard 52-card deck contain at least one card from each suit?
Approach: choose one card per suit (13⁴ ways), then choose a fifth card from the remaining 48.
Naive count: 13⁴ × 48.
This overcounts by a factor of 2, because the fifth card shares a suit with one of the first four, and swapping it with the card already chosen for that suit produces the same hand.
Corrected answer: (13⁴ × 48) / 2.
Problem: place 2 white rooks and 2 black rooks on an 8×8 board so that no two rooks share a row or column.
Place rooks sequentially, then correct for indistinguishability.
First rook: 8 rows × 8 columns = 8² choices.
Second rook: 7 × 7 = 7².
Third: 6² . Fourth: 5².
Naive count: 8² × 7² × 6² × 5².
The two white rooks are interchangeable (dividing by 2!), and so are the two black rooks (dividing by another 2!).
Final answer: (8² × 7² × 6² × 5²) / 2² = (8² × 7² × 6² × 5²) / 4.
Problem: how many length-9 DNA sequences (bases A, C, T, G) contain exactly four Cs?
Step 1: choose positions for the 4 Cs. The Cs are indistinguishable from each other, so order does not matter: C(9, 4) ways.
Step 2: fill the remaining 5 positions. Each can be A, T, or G (3 options), independently: 3⁵ ways.
By the product rule: C(9, 4) × 3⁵.
Problem: find the coefficient of x¹⁰y⁶ in the expansion of (x² + 3y)¹¹.
Rewrite x¹⁰y⁶ as (x²)⁵ · y⁶. In the expansion (x² + 3y)¹¹, identify the term where x² is raised to the 5th power and 3y to the 6th.
Binomial coefficient: C(11, 6) = 11! / (5! · 6!).
The 3y factor contributes 3⁶ = 729.
Overall coefficient: 729 × 11! / (5! · 6!).
Permutation: P(n, k) = n! / (n − k)!
Combination: C(n, k) = n! / (k!(n − k)!)
Correcting for indistinguishable objects: divide by m! for each group of m identical items
Binomial theorem: (a + b)ⁿ = Σ C(n, k) · aⁿ⁻ᵏ · bᵏ
Coefficient of a specific term: identify the exponent split, extract any multiplicative constants raised to a power, multiply by the binomial coefficient
Permutations and combinations underpin everything from cryptographic key spaces (how many possible keys exist?) to sports brackets (how many ways can teams be seeded?). The binomial theorem appears in finance for option pricing models and in computer science for analysing the expected behaviour of randomised algorithms.
Students often forget to correct for overcounting when objects are indistinguishable. If you count ordered placements of identical objects, you must divide out the redundant orderings.
A common mistake with the binomial theorem is forgetting to raise the constant (here, 3 in "3y") to the appropriate power. The coefficient is not just C(n, k); it includes any constants attached to the variable.
When using the "glue" technique for adjacent constraints, students sometimes forget to count the internal arrangements of the glued block. The block of two people can sit in 2! = 2 internal orders.
In gap-method problems, the number of available gaps depends on whether end positions are included. 15 people in a row create 14 internal gaps but 16 positions if the ends are also allowed.
⚠️ "Order matters" vs "order does not matter" is the single most important decision in any counting problem. If you get this wrong, you will be off by a factor of k!.
⚠️ Overcounting correction questions (dividing by 2, by k!, etc.) appear frequently. The quiz tests whether you can recognise the source of the overcounting and apply the right divisor.
⚠️ Binomial theorem questions almost always involve a hidden constant (like the 3 in 3y). Read the base expression carefully before identifying the exponent split.
⚠️ Constrained-seating problems (adjacent, non-adjacent, ends excluded) are a staple. Know both the "glue" method and the "gaps" method.
True or false: C(n, k) = C(n, n − k). (True.)
Fill in the blank: P(n, k) = C(n, k) × ____. (k!)
True or false: in the expansion of (a + b)⁸, the coefficient of a³b⁵ is C(8, 3). (True, which also equals C(8, 5).)
Fill in the blank: if you place 3 identical red balls and 2 identical blue balls into a row of 5 slots, the total distinct arrangements are 5! / (____ × ____). (3! × 2!)
True or false: P(14, 5) = 14! / 9!. (True.)
Q: How many ways can you arrange the letters in the word MISSISSIPPI?
A: 11 letters total: 1 M, 4 Is, 4 Ss, 2 Ps. Arrangements = 11! / (1! × 4! × 4! × 2!) = 34,650.
Q: A committee of 3 is chosen from 10 people. How many committees are possible?
A: Order does not matter: C(10, 3) = 120.
Q: What is the coefficient of x⁴y³ in (2x + y)⁷?
A: The term is C(7, 3) × (2x)⁴ × y³ = C(7, 3) × 2⁴ × x⁴y³. C(7, 3) = 35, and 2⁴ = 16. Coefficient = 35 × 16 = 560.
Q: Five friends sit in a row. Two of them insist on sitting next to each other. How many arrangements are there?
A: Glue the pair into one block (2! internal arrangements). Arrange 4 units: 4! ways. Total: 2! × 4! = 48.
Q: You draw 5 cards from a standard deck. Using the pigeonhole principle, are you guaranteed to have at least two cards of the same suit?
A: There are 4 suits. With 5 cards and 4 suits, by the pigeonhole principle, at least two cards must share a suit. Yes.
Combinations are the foundation of the binomial distribution in probability, where C(n, k) counts the number of ways to get exactly k successes in n trials. The overcounting techniques here extend naturally to multinomial coefficients, which appear when expanding expressions with three or more terms. Constrained arrangement problems connect to graph theory (e.g., counting colourings of a path graph where adjacent vertices differ).
permutations, combinations, nCr, nPr, binomial theorem, binomial coefficient, Pascal's triangle, factorial, overcounting, indistinguishable objects, constrained seating, glue method, gaps method, DNA sequence counting, rook placement, card hand counting, CS182, discrete math, Purdue, combinatorics