<s>[INST] The number of solutions of $a+b+c+d=n,\ a\geq b,\ d,\ {\rm and}\ c\geq b+1,\ d$ Define $P(n)$ to be the number of solutions : $a,\ b,\ c,\ d$ are nonnegative integers s.t.

$$a+b+c+d=n $$ and $$  a\geq b,\ d,\ {\rm and}\ c\geq b+1,\ d$$

Define $Q(n)$ to be the number of solutions : $x,\ y,\ z,\ w $ are nonnegative integers s.t.

$$ x+y+2z+3w= n-1 $$

Prove that $P(n)= Q(n)$ for all $n$
Proof : First we consider the case where $b=z,\ d=w$. I think that this is the easiest case. (Surely we can use the other case. For instance, $b={\rm max}\ \{w,z\} - {\rm min}\ \{ w,z\}$.)
If we set

$$a = x+{\rm max}\ \{w,z\},\ b=z,\ d=w,\ c=y+{\rm max}\ \{w,z+1\} $$

then we have the condition $$a\geq b,\ d\ {\rm and}\ c\geq b+1,\ d$$
If $w\geq z+1$, then $$ a+b+c+d = x+w+z+w+y+w =n-1-z$$
How can we prove this ?
 [/INST] Let
\begin{align*}
P_n &= \{(a, b, c, d) \in \mathbb{N}_0^4 : a + b + c + d = n, a \geq b, d, c \geq b + 1, d\}\\
Q_n &=\{(x, y, z, w) \in \mathbb{N}_0^4 : x + y + 2z + 3w = n - 1\}
\end{align*}
so $|P_n| = P(n)$ and $|Q_n| = Q(n)$.
We will proceed by induction to show $P(n) = Q(n)$ for all $n \geq 0$.
Note that the base cases are true since $P(0) = Q(0) = 0$ and $P(1) = Q(1) = 1$.
Now suppose true for $n$. Then for $n + 1$, we will show that $P(n+1) - P(n) = Q(n+1) - Q(n)$:
Note that if $(x, y, z, w) \in Q_n$, then $(x + 1, y, z, w) \in Q_{n+1}$ and for all $(x, y, z, w) \in Q_{n+1}$ such that $x \neq 0$, $(x - 1, y, z, w) \in Q_n$. Hence, $Q(n+1) - Q(n)$ represents the number of non-negative integer solutions to $y + 2z + 3w = n$.
Also note that if $(a, b, c, d) \in P_n$, then $(a + 1, b, c, d) \in P_{n+1}$ and for all $(a, b, c, d) \in P_{n+1}$ such that $a > \max(b, d)$, $(a - 1, b, c, d) \in P_n$. Hence, $P(n+1) - P(n)$ represents the number of non-negative integer solutions to $\max(b, d) + b + c + d = n + 1$ with $c \geq b + 1, d$.
In the case where $b \geq d$, we have $b = d + k$, $c = d + k + l + 1$ with $k, l \geq 0$, so $l + 3k + 4d = n$. Hence, this case counts the number of solutions to $y + 2z + 3w = n$ where $z$ is even ($z = 2d$).
In the case where $d > b$, we have $d = b + k + 1$, $c = b + k + l + 1$ with $k, l \geq 0$, so $l + 3k + 4b = n - 2$. Hence, this case counts the number of solutions to $y + 2z + 3w = n$ where $z$ is odd ($z = 2b + 1$).
But these two cases count the total number of solutions so we get that $Q(n+1) - Q(n) = P(n+1) - P(n)$.
Since $P(n) = Q(n)$, we get that $P(n+1) = Q(n+1)$.
Therefore, by induction we're done.

Note that this also yields the following bijection from $Q_n \to P_n$:
\begin{align*}
    (x, y, z, w) \mapsto \begin{cases}
        \left ( x + \frac{z}{2} + w, \frac{z}{2} + w, y + \frac{z}{2} + w + 1, \frac{z}{2}\right ) & \text{if $z$ is even}\\
        \left ( x + \frac{z + 1}{2} + w, \frac{z - 1}{2}, y + \frac{z + 1}{2} + w, \frac{z + 1}{2} + w\right ) & \text{if $z$ is odd}
    \end{cases}
\end{align*}
</s>