Self-Assessment Quiz: Advanced Counting

Twenty questions to check your grip on pigeonhole, stars and bars, inclusion–exclusion, and generating functions. Answer before opening the key. Aim for 16+.

Question 1

The pigeonhole principle guarantees that some box holds at least two objects precisely when:

A) $n \ge m$ B) $n > m$ C) $n = m$ D) $n < m$

Question 2

Restated as a statement about a function $f\colon A \to B$ with $A, B$ finite, the pigeonhole principle says:

A) if $\lvert A\rvert > \lvert B\rvert$ then $f$ is not injective B) if $\lvert A\rvert > \lvert B\rvert$ then $f$ is not surjective C) if $\lvert A\rvert < \lvert B\rvert$ then $f$ is not injective D) $f$ is always a bijection

Question 3

By the generalized pigeonhole principle, distributing 100 objects into 9 boxes forces some box to hold at least:

A) 10 B) 11 C) 12 D) 9

Question 4

Which is the CS payoff of the pigeonhole principle highlighted in this chapter?

A) sorting is $O(n\log n)$ B) hash collisions are unavoidable once there are more possible keys than slots C) every graph has an Euler circuit D) recursion always terminates

Question 5

The number of ways to distribute $n$ identical objects into $k$ distinct boxes, boxes allowed to be empty, is:

A) $\binom{n}{k}$ B) $k^n$ C) $\binom{n+k-1}{k-1}$ D) $n!/k!$

Question 6

"Choose $n$ items from $k$ types, repetition allowed, order irrelevant" is counted by:

A) $\binom{n}{k}$ (combinations without repetition) B) $P(n,k)$ (permutations) C) $\binom{n+k-1}{n}$ (the stars-and-bars formula) D) $k^n$

Question 7

If every one of the $k$ boxes must be non-empty, the number of solutions of $x_1+\cdots+x_k=n$ is:

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

Question 8

In the general inclusion–exclusion formula, a $t$-fold intersection term enters with sign:

A) always $+$ B) always $-$ C) $(-1)^{t}$ D) $(-1)^{t+1}$

Question 9

The inclusion–exclusion proof shows that an element lying in exactly $s$ of the sets contributes, to the right-hand side, a total of:

A) $s$ B) $0$ C) $1$ D) $2^s$

Question 10

For the ordinary generating function $A(x) = \sum_n a_n x^n$, the symbol $x$ is:

A) a real number you eventually substitute B) a formal marker; convergence is irrelevant C) always equal to $1/2$ D) the base of the natural logarithm

Question 11

The generating function $\dfrac{1}{1-x}$ models:

A) $n$ distinct items, each in or out B) an unlimited supply of one kind of object C) at most one of an item D) an even number of an item

Question 12

To count distributions of $n$ identical objects into $k$ boxes with generating functions, you use:

A) $(1+x)^k$ B) $\dfrac{1}{(1-x)^k}$ C) $(1-x)^k$ D) $\dfrac{1}{1-x^k}$

Question 13

A derangement of $n$ objects is a permutation with:

A) exactly one fixed point B) no fixed point C) all points fixed D) at least one fixed point

Question 14

As $n \to \infty$, the fraction of permutations of $n$ objects that are derangements approaches:

A) $0$ B) $1/2$ C) $1/e \approx 0.3679$ D) $1$

Question 15

The number of surjections from an $n$-set onto an $m$-set is:

A) $m^n$ B) $\sum_{j=0}^{m}(-1)^j\binom{m}{j}(m-j)^n$ C) $\binom{m}{n}$ D) $n!/(n-m)!$

Question 16 (True/False, justify)

True or false: If a hash table has $m$ slots and you insert $m-1$ keys, the pigeonhole principle guarantees no collision. Justify in one sentence.

Question 17 (True/False, justify)

True or false: The stars-and-bars count $\binom{n+k-1}{k-1}$ assumes the $n$ objects being distributed are distinguishable. Justify in one sentence.

Question 18 (True/False, justify)

True or false: For two sets, the general inclusion–exclusion formula reduces to $\lvert A\cup B\rvert = \lvert A\rvert + \lvert B\rvert - \lvert A\cap B\rvert$. Justify in one sentence.

Question 19 (Short answer)

A load balancer sends 1000 requests to 7 servers. State the guaranteed lower bound on the busiest server's load, and give the formula you used.

Question 20 (Short answer)

In the "make change with pennies and nickels" generating function $\frac{1}{1-x}\cdot\frac{1}{1-x^5}$, explain in one sentence what the coefficient of $x^{10}$ counts, and give its value.

Answer Key

Topics to review by question