# Combination to find integers satisfying a condition

Let $$n$$ and $$k$$ be positive integers such that $$n\ge\frac{k(k+1)}{2}$$. The number of solutions $$(x_1,x_2,\dots,x_{k})$$, with $$x_1\ge1$$, $$x_2\ge2$$,..., $$x_{k}\ge k$$ for all integers satisfying $$x_1+x_2+\dots+x_{k}=n$$ is?

I substituted the last equation in the first inequality. $$x_1+x_2+\dots+x_{k}\ge\frac{k(k+1)}{2}.$$ Took $$x_1$$ as $$1+ t_1$$, $$x_2$$ as $$2+t_2$$...where $$t_i\ge 0$$. On simplifying by using sum of k numbers, I end with with $$t_1+t_2+\dots+t_{k} \ge0$$. Since $$x_1,x_2$$... are in increasing order, and sum of all $$t$$ values is $$0$$, I conclude that this is only possible when $$t=0$$. Therefore only one solution is possible when $$LHS = RHS$$. The inequality is not valid.

But the answer is $$\frac{1}{2}(2n-k^2+k-2)$$. What am I missing here?

• Could you please check the given answer? In my opinion is the one given in my answer below. Jul 25, 2020 at 14:38
• @RobertZ hey i just saw the answer as my net was down. the answer given is 1/2 (2n-(k^2)+k-2) and the answer you have given doesn't simplify to it. The method given in the book uses the sum of coefficients of t^n in (t + t^2 +t^3 ...)(t^2 + t^3 +....)(t^k + t^(k-1)+...). If this is helpful in answering as i didnt understand what happening here. Jul 30, 2020 at 13:00
• What is the title of the book? Jul 30, 2020 at 13:11
• it is a book of past IIT-JEE questions Jul 30, 2020 at 13:12
• I edited my answer (which is correct). Please take a look at the P.S. Jul 30, 2020 at 13:51

No, the sequence $$x_1,x_2,\dots,x_{k}$$ is not necessarily increasing, so your conclusion is not correct.
Let $$t_k=x_k-k\geq 0$$, then we have to count the number of non-negative integer solutions of $$t_1+t_2+\dots+t_k=n-\frac{k(k+1)}{2}$$ which is, by Stars-and-Bars, given by $$\binom{n-\frac{k(k+1)}{2}+k-1}{k-1}=\binom{\frac{2n-k^2+k-2}{2}}{k-1}.$$
P.S. My answer is correct. Probably there is a typo in your book. The integer $$\binom{\frac{2n-k^2+k-2}{2}}{k-1}$$ is precisely the coefficient of $$t^n$$ in $$(t + t^2 +t^3+ \dots)(t^2 + t^3 +t^4+\dots)\dots (t^k + t^{k+1}+t^{k+2}+\dots),$$ that is $$[t^n]\prod_{j=1}^k\frac{t^j}{1-t}=[t^{n-\frac{k(k+1)}{2}}](1-t)^{-k} =(-1)^{{n-\frac{k(k+1)}{2}}}\binom{-k}{n-\frac{k(k+1)}{2}}=\binom{n-\frac{k(k+1)}{2}+k-1}{k-1}.$$ Numerical example. Take $$n=8$$ and $$k=3$$, then it is easy to see that $$(t + t^2 +t^3+ \dots)(t^2 + t^3+ t^4 +\dots)(t^3 + t^{4}+t^{5}+\dots) =t^6+3t^7+6t^8+\dots$$ and the coefficient of $$t^8$$ is $$6$$: $$\binom{\frac{16-9+3-2}{2}}{3-1}=\binom{4}{2}=6.$$
• No. Take $n=12$ and $k=3$, then $x_1=5\geq 1$, $x_2=4\geq 2$ and $x_3=3\geq 2$ satisfy the given conditions, but they are not increasing. Jul 31, 2020 at 13:22