# A combinatorial Problem

I just ran into the following problem in my research.

Assume that v and i are natural numbers. Let $a_1+...+a_n=i$ and $b_1+...+b_n=v.$

If $a_j$ is less than $b_j$(not equal) for all $j,$

Then how many solutions does the above system of equations have?

• So the solutions would be values for $a_1,a_2\dots a_n,b_1,b_2\dots b_n$? – Jorge Fernández Hidalgo Oct 1 '15 at 3:11
• Do you want the solutions to be nonnegative integers? – Charlie Oct 1 '15 at 3:12

Assuming you want the $a_k$'s and $b_k$'s to be nonnegative integers, define $$p(x,y)=\sum_{a<b}x^a y^b = \sum_a x^a y^{a+1}/(1-y) = \frac{y}{(1-y)(1-xy)}.$$ You want the coefficient of $x^i y^v$ in $p(x,y)^n$, which can be computed as follows: \begin{align} &[x^i y^v]\frac{y^n}{(1-y)^n(1-xy)^n}\\ =&[x^i y^{v-n}]\sum_a (-1)^a\binom{-n}{a}y^a\,\sum_b (-1)^b\binom{-n}{b}(xy)^b\\ =&[x^i y^{v-n}]\sum_a \binom{n+a-1}{a}y^a\,\sum_b \binom{n+b-1}{b}(xy)^b\\ =&\binom{n+i-1}{i}[y^{v-n}]\sum_a\binom{n+a-1}{a}y^{a+i}\\ =&\binom{n+i-1}{i}\binom{v-i-1}{n-1}. \end{align}
It's easy to see this directly; there are $\binom{n+i-1}{i}$ solutions to the first equation in nonnegative integers. For any of these, we can take any solution of $c_1+\cdots+c_n=v-i$ in positive integers, and set $b_i=a_i+c_i$.