Skip to main content

Enumerative Combinatorics · Binomial and multinomial coefficients, identities, and lattice paths

Let a,b ≥ 0 and let k be an integer

Problem

Enumerative Combinatorics practice problem

Let a,b≥0a,b\ge 0 and let kk be an integer. Prove Vandermonde's identity∑j∈Z(aj)(bk−j)=(a+bk),\sum_{j\in\mathbb Z}\binom aj\binom b{k-j}=\binom{a+b}{k},where only finitely many terms are nonzero. Give both a subset proof and a proof by comparing coefficients in (1+x)a(1+x)b(1+x)^a(1+x)^b.

Eight distinct silver badges and five distinct copper badges are available. Count the four-badge selections by their number of silver badges and verify the resulting total. Explain why the possible values of jj are automatically enforced by the zero convention.

Hint

Hint

Split a kk-element selection by how many objects came from the first class.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Enumerative Combinatorics sample problem: Try the free sample problem.

More Enumerative Combinatorics practice problems