GeneratingFunction Difficult

Problem - 2536

How many different $5$-digit numbers can be formed using $1$, $2$, $3$, and $4$ that satisfy the following conditions:

  • the digit $1$ must appear either $2$ or $3$ times,
  • the digit $2$ must appear even times,
  • the digit $3$ must appear odd times, and
  • the digit $4$ has no restriction

The result is the coefficient of $x^5$ in the expanded form of the following polynomial which is $\boxed{4}$: $$(x^2+x^3)(x^0+x^2+x^4)(x^1 + x^3 + x^5)(x^0+x^1+x^2+x^3+x^4 + x^5)$$

The four brackets are corresponding to the four digits, respectively. Within each bracket, the exponent of each term represents the number of times this digit appears. Let this polynomial be $f(x)$, then $$f(x)=x^3(1+x)(1+x^2+x^4)(1+x^2+x^4)(1+x+x^2+x^3+x^4+x^5)$$

The $x^5$ term in $f(x)$ must be the $x^2$ in $$g(x)=(1+x)(1+x^2)(1+x^2)(1+x+x^2)$$

Here, terms with exponents higher than $2$ in each bracket have already discarded. Now if $1$ is chosen from the first bracket, then among the other three brackets one of the must contribute an $x^2$ term and the other two must contribute the constant $1$ in order to obtain an $x^2$ term. The sum of coefficients in these cases is $3$. When the first bracket contributes the $x$ term, then the second and forth brackets must also contribute $1$ and third bracket must contribute the $x$ term. The coefficient in this case is $1$. Adding them together gives the final result as $\boxed{4}$.

Given the limited number of possibilities, this problem can also be solved using casework.

report an error