MathDB

B2

Part of 1992 Putnam

Problems(1)

Coefficient in (1+x+x^2+x^3)^n

Source:

11/29/2006
For nonnegative integers nn and kk, define Q(n,k)Q(n, k) to be the coefficient of xkx^{k} in the expansion (1+x+x2+x3)n(1+x+x^{2}+x^{3})^{n}. Prove that Q(n,k)=∑j=0k(nj)(nk−2j)Q(n, k) = \sum_{j=0}^{k}\binom{n}{j}\binom{n}{k-2j}. [hide="hint"] Think of (nj)\binom{n}{j} as the number of ways you can pick the x2x^{2} term in the expansion.
factorialPutnamStanfordcollege