0
$\begingroup$

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?

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

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.