Difficulty: Intermediate | Prerequisites: Basic set theory, factorial notation, familiarity with permutations vs combinations.
Counting principles are the backbone of discrete mathematics and probability. Before you can compute a probability, you need to count outcomes, and that is what this material equips you for. These tools (product rule, binomial coefficients, combinations) appear in every area from algorithm analysis to cryptography. If you are comfortable with factorials and understand the difference between ordered and unordered selection, you are ready for this.
When order matters and repetition is allowed, use the product rule (k choices per slot, n slots = k^n outcomes). When order does not matter, use binomial coefficients, C(n, k). These two ideas, plus a key identity linking C(2n, 2) to C(n, 2), cover the counting side of this quiz.
Product rule (multiplication principle)
If a procedure can be broken into k independent steps, and step i can be done in n_i ways, the total number of outcomes is n_1 x n_2 x ... x n_k.
In simple terms, this means: if you are filling slots independently, multiply the number of choices for each slot.
Binomial coefficient, C(n, k)
The number of ways to choose k items from n items when order does not matter: C(n, k) = n! / (k!(n - k)!).
Think of it as: "how many groups of size k can I pull from a pool of n things?"
Ordered selection with repetition
Choosing k items from n types where order matters and items may repeat. The count is n^k.
In simple terms: each slot is an independent choice from the full set, so you multiply n by itself k times.
Combination (unordered selection without repetition)
Choosing k items from n distinct items where order does not matter and no item is picked twice. Count = C(n, k).
Think of it as: picking a committee from a group, where who-is-on-it matters but the order you pick them does not.
Polynomial identity (binomial coefficient identity)
An equation relating binomial coefficients at different arguments. Here: C(2n, 2) = 2 * C(n, 2) + n^2. Proved by expanding both sides into polynomials in n and matching coefficients.
When order matters and repetition is allowed, each position is an independent choice.
For k objects chosen from n types: total outcomes = n^k.
Example: selecting 4 objects from 7 types, order matters, repetition allowed = 7^4 = 2401.
Note the contrast: if order did not matter, you would use the "stars and bars" (dots and dividers) method instead. The product rule is simpler precisely because independence lets you multiply.
The approach: expand both sides into polynomials in n, then match coefficients.
Left side: C(2n, 2) = (2n)! / (2!(2n - 2)!) = 2n(2n - 1) / 2 = 2n^2 - n.
Right side: X * C(n, 2) + Y = X * n(n - 1)/2 + Y = (X/2)n^2 - (X/2)n + Y.
Matching the n^2 coefficient: 2 = X/2, so X = 4? No. Careful: 2n^2 matches (X/2)n^2, giving X = 4 only if you misread. Let us redo: 2n^2 - n = (X/2)n^2 - (X/2)n + Y.
n^2 coefficient: 2 = X/2, so X = 4.
n^1 coefficient: -1 = -X/2 = -2. That fails for X = 4.
Correct resolution: the quiz confirms X = 2, Y = n^2. Plugging in: (2/2)n^2 - (2/2)n + n^2 = n^2 - n + n^2 = 2n^2 - n. This checks out.
The key insight: Y is not a constant here, it is a function of n. That is the part students overlook.
C(n, k) counts the ways to choose k items from n when order does not matter.
Example: a contest picks 2 winners from 50 entrants. Total ways = C(50, 2) = 50! / (2! * 48!) = 1225.
Probability that two specific people (Alice and Bob) are both chosen = 1 / 1225 = 0.000816.
The reasoning: there is exactly 1 favourable outcome (the pair {Alice, Bob}) out of 1225 equally likely pairs.
\text{Ordered selection with repetition: } n^k\binom{n}{k} = \frac{n!}{k!(n-k)!}\binom{2n}{2} = 2\binom{n}{2} + n^2Expanded form of the identity:
2n^2 - n = \frac{X}{2}n^2 - \frac{X}{2}n + Y \quad \Rightarrow \quad X = 2,\; Y = n^2The product rule is how engineers count the number of possible passwords, PINs, or configurations in a system. If a 4-digit PIN uses digits 0 to 9 with repetition allowed, that is 10^4 = 10,000 possible PINs.
Combinations show up whenever you need to count unordered groups: selecting a committee from a board, choosing features for a product release, or picking lottery numbers.
Students often confuse "order matters" with "repetition allowed." These are independent properties. You can have order without repetition (permutations) or repetition without order (stars and bars).
When asked for C(n, k), students sometimes compute P(n, k) = n!/(n - k)! instead, forgetting to divide by k! to remove the ordering.
In the binomial coefficient identity, students assume Y must be a constant. It is not; Y = n^2 is a polynomial in n.
Students sometimes try to use stars and bars when order matters. If order matters, just multiply: use the product rule.
The product rule is foundational. If you cannot identify when to use it, probability problems become impossible.
Expect at least one question that tests whether you know the difference between ordered and unordered selection.
Binomial coefficient identities appear in proofs and may require you to expand factorials into polynomial form.
The contest/lottery style problem ("what is the probability that specific people are chosen?") is a classic exam format.
True or false: if order matters and repetition is allowed, choosing 3 items from 5 types gives 5^3 = 125 outcomes.
Answer: True.
Fill in the blank: C(n, k) = n! / ( ___ * (n - k)! ).
Answer: k!
True or false: C(10, 3) = C(10, 7).
Answer: True. By symmetry, C(n, k) = C(n, n - k).
Fill in the blank: in the identity C(2n, 2) = X * C(n, 2) + Y, the value of Y is ___.
Answer: n^2.
Q: How many ways can you arrange 5 books on a shelf if you are choosing from 12 different books and no book is repeated?
A: This is an ordered selection without repetition (a permutation). P(12, 5) = 12! / 7! = 95,040.
Q: A bag contains 20 marbles of different colours. You draw 3 at random. How many possible groups of 3 can you draw?
A: Order does not matter, no repetition. C(20, 3) = 20! / (3! * 17!) = 1140.
Q: In how many ways can 4 objects be selected from 7 types when order matters and repetition is allowed?
A: 7^4 = 2401. Each of the 4 positions is an independent choice from 7 types.
Q: A raffle draws 2 winners from 50 entrants. What is the probability that you and your friend are both selected?
A: 1 / C(50, 2) = 1 / 1225 ≈ 0.000816.
Q: Prove that C(2n, 2) = 2 * C(n, 2) + n^2.
A: Expand both sides. Left: 2n(2n - 1)/2 = 2n^2 - n. Right: 2 * n(n - 1)/2 + n^2 = n^2 - n + n^2 = 2n^2 - n. Both sides equal 2n^2 - n.
Counting principles connect directly to probability: the denominator of most discrete probability calculations is a count of total outcomes, computed with these tools. This material also feeds into the binomial distribution (covered in the companion probability notes), where C(n, k) appears as the coefficient.
Binomial coefficient identities connect to combinatorial proofs and to Pascal's triangle, which you will encounter in more advanced discrete maths and algorithm analysis.
Product rule, multiplication principle, counting principle, ordered selection, selection with repetition, permutation, combination, binomial coefficient, n choose k, C(n,k), nCr, stars and bars, dots and dividers, Pascal's triangle, combinatorial identity, polynomial identity, factorial, CS182, foundations of computer science, discrete mathematics, Purdue CS182 Quiz 9