3
$\begingroup$

In the jungle of posts on math.stackexachange related to this subject I have been searching quite a while now. I read some very useful posts however I can't solve my own problem. My version of the number of integer solutions sounds like this:

Question: Let $x + y + z \leq 13$ with the following restrictions: $x \leq y \leq x+2$ and $x \leq z$. Find the number of possibilities using a generating function.

Related to this problem I found this post. I tried so for the equation $x + y + z =13$:

Say $z=x+z'$, $x+2=y+x'$ and $y=x+y'$. However replacing those expressions into the equation, I got stuck with replacing $x'$ and $y'$ for $x$ and $y$. The only thing I see is that: $x' + y'=2$. How can I use this technique properly?

And what about the inequality? How to deal with $x + y + z \leq 13$? Thanx in advance!

$\endgroup$
  • $\begingroup$ Are $x,y,z$ non-negative integers? $\endgroup$ – user26486 Feb 22 '15 at 8:47
  • 3
    $\begingroup$ We deal with the inequality part only, in order to mention useful trick. The number of solutions in non-negative integers of $x_1+\cdots +x_n\le k$ is equal to the number of solutions in non-negative integers of $x_1+\cdots +x_n+x_{n+1}=k$. $\endgroup$ – André Nicolas Feb 22 '15 at 8:48
  • $\begingroup$ Yes of course! I forgot to mention this, sorry. $\endgroup$ – iJup Feb 22 '15 at 8:50
4
$\begingroup$

As you say, the inequalities are essentially just saying that $y=x+y', x+2=y+x', z=x+z'$ for some non-negative integers $x',y',z'\in\mathbb Z_{\ge 0}$. Then:

$$3x+y'+z'\le 13\iff 3x+y'+z'+A=13$$

for some non-negative integer $A$.

But we still haven't used $x+2=y+x'\iff x'+y'=2$ (we used $y=x+y'$), which is just saying that $y'\in[0;2]$.

Thus the generating function we need is:

$$(1+x^3+x^6+x^9+x^{12})(1+x+x^2)(\sum_{i=0}^{13} x^i)(\sum_{i=0}^{13} x^i)$$

The coefficient of $x^{13}$ will be our answer. It is 105.
For a way of finding the coefficient of generating functions see this answer.

Since $(1+x^3+x^6+x^9+x^{12})(1+x+x^2)=(1+x+x^2+\cdots+x^{14})$, we can simply write our generating function as:

$$\left[\left(\sum_{i=0}^\infty x^i\right)^3\right]_{x^{13}}=\left[\frac{1}{(1-x)^3}\right]_{x^{13}}=\binom{13+3-1}{13}=\binom{15}{13}=\binom{15}{2}=\frac{15\cdot 14}{2}=15\cdot 7=105$$

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