Number of solutions to $a + b + c + d + f = n$ in nonnegative integers $a, b, c, d, f,$ given restrictions on $a, b,$ and $f$

Question

Count the number of solutions to $a + b + c + d + f = n$ in nonnegative integers $a, b, c, d, f,$ such that $a$ is a multiple of 4, $b$ is at most 1, and $f$ is either 0 or 2.

My attempt:

As far as I know, you can solve these types of problems using generating functions or multisets. For this problem, it makes sense to use generating functions. Here's what I have so far:

For $a$: $(x^4 + x^8 + x^{12} + ... ) = \frac{1}{1-x^4}$

For $b$: $(x^0 + x^1) = \frac{1-x^2}{1-x}$

I'm stuck at what to do for $f$.

Answer 1

The generating function is \begin{eqnarray*} \underbrace{\frac{1}{(1-x^4)}}_{a} \underbrace{(1+x)}_{b} \underbrace{\frac{1}{(1-x)^2}}_{c \text{ and } d } \underbrace{(1+x^2)}_{f}. \end{eqnarray*} Which can be simplified to \begin{eqnarray*} \color{blue}{\frac{1}{(1-x)^3}}. \end{eqnarray*}

Answer 2

A non-generating function approach: Note that given any integer $m$ there is exactly one triple $a,b,f$ such that $m=a+b+f$ and $a$ is a multiple of $4$, $b\in\{0,1\}$ and $f\in\{0,2\}$. (Hint: Write $m$ in base $2$.)

So the number of such solutions is exactly the same as the number of solutions to $c+d+m=n$.

[This can be seen with the generating function approach because $1-x^4=(1-x)(1+x)(1+x^2)$.]

---

You'd get the same result of you required $a$ to be a multiple of $9$, $b\leq 2$ and $f\in\{0,3,6\}$. Then you'd write $n$ is base $3$.

Answer 3

I would follow another plan:

1) Set all variables to zero. If $n$ is zero, that is the only solution. If $n$ is not zero, there is no solution.

2) Now, $x \in \{a,b,c,d,f \}$ with $x \ne 0$, all others are zero. You gain 5 solution for each variable.

3) Now, two of variables are not zero ( you have $\binom{5}{2}$ ways to choose these ). The number of solutions for each pair is the number of partions of $n$ into the sum of two integers.

4) Similarly for 3,4,5 elements.

5) After you got all the possible solutions, apply the restrictions you have - substract all $a$-s that are not multiple of $4$, etc.

Maybe you will get a nice but tricky formula for that...