Self-Assessment Quiz: Permutations and Combinations

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+. The skill being tested most is the §16.3 reflex: classify first (order? repetition?), then compute.

Question 1

"Pick 3 of 10 servers to be primaries" (the three are interchangeable) is counted by:

A) $P(10, 3)$ B) $\binom{10}{3}$ C) $10^3$ D) $3^{10}$

Question 2

"Assign 3 of 10 servers to the distinct roles A, B, and C" is counted by:

A) $P(10, 3)$ B) $\binom{10}{3}$ C) $10^3$ D) $3!$

Question 3

The two questions that determine which counting model to use are:

A) "Is $n$ large?" and "Is $r$ large?" B) "Does order matter?" and "Is repetition allowed?" C) "Is it a sum or a product?" and "Is the set finite?" D) "Is it a permutation?" and "Is it a combination?"

Question 4

$P(n, r)$ and $\binom{n}{r}$ differ by a factor of:

A) $n!$ B) $(n-r)!$ C) $r!$ D) $n - r$

Question 5

The number of distinguishable rearrangements of the letters of LEVEL is:

A) $5! = 120$ B) $\frac{5!}{2!} = 60$ C) $\frac{5!}{2!\,2!} = 30$ D) $\binom{5}{2} = 10$

Question 6

The coefficient of $x^{n-k}y^k$ in the expansion of $(x + y)^n$ is:

A) $P(n, k)$ B) $\binom{n}{k}$ C) $n^k$ D) $k!$

Question 7

$\sum_{k=0}^{n}\binom{n}{k}$ equals:

A) $n!$ B) $2^n$ C) $n^2$ D) $\binom{2n}{n}$

Question 8

Pascal's rule states that, for $1 \le k \le n$:

A) $\binom{n}{k} = \binom{n}{k-1} + \binom{n}{k+1}$ B) $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ C) $\binom{n}{k} = \binom{n-1}{k} + \binom{n}{k-1}$ D) $\binom{n}{k} = k\binom{n-1}{k-1}$

Question 9

The number of distinct circular arrangements of $n$ distinct objects (rotations considered the same) is:

A) $n!$ B) $(n-1)!$ C) $\frac{n!}{2}$ D) $\binom{n}{2}$

Question 10

A brute-force algorithm that enumerates all subsets of $n$ items does work that grows like:

A) $n^2$ B) $n!$ C) $2^n$ D) $\binom{n}{2}$

Question 11

For fixed $k$, the number of $k$-subsets of an $n$-set, $\binom{n}{k}$, grows like:

A) a polynomial of degree $k$ in $n$ B) $2^n$ C) $n!$ D) a constant

Question 12

Why is $\binom{n}{r} = \frac{n!}{r!(n-r)!}$ always a whole number?

A) Because $n!$ is even B) Because it counts something (the $r$-subsets), and a count is a non-negative integer C) Because $r!$ always divides $n!$ by a theorem of Gauss only D) It is not always a whole number

Question 13 (True/False, justify)

True or false: "Pick a 4-doughnut box from 9 available kinds, repeats allowed" is counted by $\binom{9}{4}$. Justify in one sentence.

Question 14 (True/False, justify)

True or false: A combinatorial (double-counting) proof is less rigorous than an algebraic proof because it "tells a story." Justify in one sentence.

Question 15 (True/False, justify)

True or false: $\binom{52}{5}$ counts the number of ordered 5-card deals from a 52-card deck. Justify in one sentence.

Question 16 (True/False, justify)

True or false: Computing $P(10^6, 2)$ as math.factorial(10**6) // math.factorial(10**6 - 2) and as the falling product $10^6 \times (10^6 - 1)$ give the same answer, so the two approaches are equally good. Justify in one sentence.

Question 17

The committee–chair identity $k\binom{n}{k} = n\binom{n-1}{k-1}$ is proved by counting which set two ways?

A) All subsets of an $n$-set B) All (committee of $k$, designated chair) pairs from $n$ people C) All orderings of $n$ people D) All functions from a $k$-set to an $n$-set

Question 18 (Short answer)

State, in one sentence each, the four cells of the §16.3 decision table (the model for each combination of order matters / does not and repetition allowed / not).

Question 19 (Short answer)

Setting $x = 1, y = -1$ in the binomial theorem gives $\sum_{k=0}^{n}(-1)^k\binom{n}{k} = 0$ for $n \ge 1$. State, in one sentence, what this says about the even-sized vs. odd-sized subsets of a non-empty set.

Question 20 (Short answer)

You must enumerate all orderings of 20 items at $10^9$ checks per second. Estimate the count ($20! \approx 2.4 \times 10^{18}$) and state, in one sentence, whether brute force is feasible.

Answer Key

Topics to review by question