Combination Identities Quiz: Practice Core Counting Formulas

Pascal's triangle is built by adding adjacent entries: each entry in row n+1 at position k+1 equals the sum of the two entries above it from row n. Combinatorially this combines subsets that include a new element with those that do not. Option A is the symmetry identity. Option C is the subset sum identity.

The answer is True. Binomial coefficients increase as k approaches n/2 and then decrease symmetrically. Subsets of medium size are most numerous because there are many more ways to choose roughly half the elements than to choose very few or nearly all. The peak occurs at k = floor(n/2) for odd n and k = n/2 for even n.

n choose 0 = 1 (one empty subset) and n choose 1 = n (n single-element subsets). Their sum is 1+n = n+1. This represents the first two entries of row n in Pascal's triangle. Option A gives only n, omitting the empty subset. Option C gives the full row sum. Option D doubles n incorrectly.

When k exceeds n, it is impossible to select k items from only n available. By convention and by the formula, n choose k = 0 for k greater than n. This preserves consistency in Pascal's triangle at the boundary edges. Options B, C, and D give positive values which are mathematically incorrect when k exceeds n.

Vandermonde's identity states that choosing r items from two groups of sizes m and n can be done by choosing k from the first group and r-k from the second, for all valid k. Summing over all k gives the total (m+n) choose r. Options B, C, and D do not correctly express this convolution identity.

For even n, the sum of even-index binomial coefficients equals 2^(n-1). For n=8: 2^7 = 128. This follows from symmetry in Pascal's triangle where exactly half of all 2^8=256 subsets contain an even number of elements. Option A gives 2^6=64. Option D gives 2^8=256, the full row sum.

(3 choose 0)² + (3 choose 1)² + (3 choose 2)² + (3 choose 3)² = 1+9+9+1 = 20. By the identity, this equals 6 choose 3 = 20. Option A gives 10, option B gives 16, option C gives 18. Only 20 correctly squares each coefficient and sums.

The sum (2 choose 2)+(3 choose 2)+(4 choose 2)+(5 choose 2)+(6 choose 2) = 1+3+6+10+15 = 35. By the hockey-stick identity this equals 7 choose 3 = 35. Option A gives 6 choose 3 = 20. Option C gives 7 choose 4 = 35 also but the identity specifies 7 choose 3. Option D gives 8 choose 3 = 56.

The hockey-stick identity states that the diagonal sum from r choose r up to n choose r equals (n+1) choose (r+1). Here r=3 and n=5: (3 choose 3)+(4 choose 3)+(5 choose 3) = 1+4+10 = 15 = 6 choose 4 = 15. Option D gives (7 choose 4)=35, which is too large.

By Pascal's identity, (n-1 choose k-1) + (n-1 choose k) = n choose k. Here 5 choose 2 + 5 choose 3 = 6 choose 3. Numerically: 10+10=20 = 6!/(3!×3!) = 20. Option A gives 6 choose 2 = 15. Option C gives 6 choose 4 = 15. Option D gives 5 choose 4 = 5.

The combination formula n!/(k!(n-k)!) counts unordered subsets. The n! in the numerator counts all ordered arrangements. Dividing by k! removes repeated orderings of the chosen items. Dividing by (n-k)! removes repeated orderings of the unchosen items. Option A omits (n-k)!. Option B omits k!. Option D allows repetition.

This sums all entries in row 4 of Pascal's triangle: 1+4+6+4+1 = 16 = 2^4. Each element in a 4-item set can be included or excluded independently, giving 2^4 = 16 total subsets. Options A, B, and D do not match the row 4 sum.

Pascal's identity partitions every k-subset into those not containing a fixed element (counted by n-1 choose k) and those containing it (counted by n-1 choose k-1). These two disjoint groups together account for all k-subsets of the n-element set.

10!/(3!×7!) = (10×9×8)/(3×2×1) = 720/6 = 120. By symmetry, choosing 3 to include is the same as choosing 7 to exclude. Option A gives 60, option B gives 90, option D gives 720 which is 6! not a combination value.

By symmetry, 7 choose 4 = 7 choose 3 since 4+3=7. Computing 7!/(3!×4!) = (7×6×5)/(3×2×1) = 210/6 = 35. Option A gives 21 = 7 choose 2. Option B gives 28. Option D gives 42. Only 35 correctly applies the symmetry and formula.

The answer is True. Each element can independently be included or excluded from a subset, giving 2 choices per element and 2^n total subsets. Summing all n choose k values for k from 0 to n counts subsets of each possible size, and their total is exactly 2^n.

n choose 0 = n!/(0!×n!) = 1 for any n since there is exactly one empty subset. Similarly n choose n = 1 since there is exactly one way to select all n items. Both equal 1 regardless of n. Option A gives 0 incorrectly. Options C and D are also wrong.

The answer is True. Any k-subset of n elements either includes the last element or does not. Subsets not including it are counted by (n-1 choose k) and those including it by (n-1 choose k-1). These two disjoint cases cover all k-subsets, making the identity universally valid.

5!/(2!×3!) = (5×4)/(2×1) = 20/2 = 10. There are exactly 10 distinct 2-element subsets from a set of 5 items. Option A gives 5, option C gives 20 without dividing by 2!, option D gives 15 which does not result from this formula.

The answer is True. Selecting exactly one item from n gives n possible single-element subsets, one for each item. Algebraically: n!/(1!(n-1)!) = n!/((n-1)!) = n. This is one of the boundary cases of the combination formula and holds for all positive integers n.