Number of positive integral solutions in the given inequality

660 Views Asked by At

Find the number of positive integral solutions of the inequality $$3x+y+z \leq 30$$

My attempt: Introducing a dummy variable '$a$' then the equation becomes $3x+y+z+a=30$, where $x,y,z \geq 1$ and $a\geq0$, then we have to find coefficient of $x^{30}$ in the expansion of $$(t^3 +t^6 +\cdots)\cdot(t^1+t^2+\cdots)^2\cdot(1+t+t^2+\cdots).$$

I am not sure this is the correct method. Also, I have doubts about the conditions of variables, i.e., whether they are correct or not.

2

There are 2 best solutions below

0
On BEST ANSWER

The method you have used is correct (by correct, I mean that the coefficient of $t^{30}$ does indeed correspond to the number of positive integral solutions of the inequality), but you still need a way to compute the coefficient. Since what we want is the coefficient of a term in the expansion, we first impose the restriction $|t| < 1$, and evaluate each multiplicands as an infinite geometric series.

This gives the product $$f(t) = (t^3 +t^6 +\cdots)\cdot(t^1+t^2+\cdots)^2\cdot(1+t+t^2+\cdots) = \frac{t^3}{1 - t^3} \left(\frac{t}{1 - t}\right)^2 \frac{1}{1 - t} = \frac{t^5}{(1 - t^3)(1 - t)^3} = \frac{t^5}{(1 - t)^4(1 + t + t^2)}$$ which can be expanded as a Taylor series at $t = 0$, with the coefficient of the term $t^{30}$ in the expansion giving the answer you desire. However, taking the 30th derivative of this rational to compute this coefficient is undesirable. As an improvement, you can take a partial fraction decomposition of the form: $$f(t) = \frac{t^5}{(1 - t)^4(1 + t + t^2)} = \frac{At + B}{1 + t + t^2} + \frac{C}{(1 - t)^4} + \frac{D}{(1 - t)^3} + \frac{E}{(1 - t)^2} + \frac{F}{1 - t}$$ and solve for the constants. It then turns out that the $n$-th derivatives of each of these fractions (edit: except the first one) has a concise closed form in terms of $n$, and hence you can efficiently solve for the coefficient of $t^{30}$ by letting $n = 30$.

Edit 2: Very late edit, but it turns out that $A = 0$, so the first fraction can be further decomposed using partial fractions such that $$\frac{1}{1 + t + t^2} = \frac{G}{e^{2 \pi i / 3} - t} + \frac{H}{e^{4 \pi i / 3} - t},$$ which gives $$f^{(n)}(t) = \frac{BGn!}{(e^{2 \pi i / 3} - t)^{n + 1}} + \frac{BHn!}{(e^{4 \pi i / 3} - t)^{n + 1}} + \frac{C(n + 3)!/3!}{(1 - t)^{n + 4}} + \frac{D(n + 2)!/2!}{(1 - t)^{n + 3}} + \frac{E(n + 1)!}{(1 - t)^{n + 2}} + \frac{Fn!}{1 - t}.$$ The $n$-the coefficient of the $n$-th term ($n \in \mathbb{N}$) in the Taylor expansion of $f$ about $t = 0$ is $$a_n = \frac{f^{(n)}(0)}{n!} = \frac{BG}{(e^{2 \pi i / 3})^{n + 1}} + \frac{BH}{(e^{4 \pi i / 3})^{n + 1}} + \frac{C(n + 3)(n + 2)(n + 1)}{6} + \frac{D(n + 2)(n + 1)}{2} + E(n + 1) + F,$$ which can be evaluated by hand. Since it has been over a month since this question was asked, I will reveal that $B = 1/9$, $C = 1/3$, $D = -4/3$, $E = 17/9$, $F = -1$, $G = (e^{-2 \pi i / 3})/(e^{2 \pi i / 3} - 1) = i/\sqrt{3}$, and $H = -G$. It is easily checked that $a_{30} = 1215$ using the expression above.

Remark: This final closed form solution can be used to achieve a solution to the problem, where the inequality has any non-negative integer on the right side. If the number on the right side is $n$, the number of solutions is $a_n$.

2
On

I would start by noting that the number of solutions to $y+z \le k$ is $\frac 12k(k-1)$ and that $k=30-3x$ can equal $3, 6, 9,\ldots 27$ so our total number of solutions is $$\sum_{i=1}^9\frac 12(3i)(3i-1)=\frac 12\sum_{i=1}^99i^2-3i=\frac 12\left(9\frac {9(9+1)(2\cdot 9+1)}6-3\cdot \frac 12\cdot 9(9+1)\right)=1215$$