# Number of solutions of $x_1+2x_2+\cdots+kx_k=n$?

Suppose $$n$$ be a given positive integer. Then the Diophantine equation $$x=n$$ has only $$1$$ solution. Just by inspection, I found that the Diophantine equation $$x+2y=n$$ has $$\left\lfloor \dfrac{n}{2}+1\right\rfloor$$ non-negative solutions for $$(x,y).$$
Also, according to this post the Diophantine equation $$x+2y+3z=n$$ has $$\left\lfloor \dfrac{n^2}{12}+\dfrac{n}{2}+1 \right\rfloor$$ non-negative solutions for $$(x,y).$$

Is there any closed form for the number of non-negative integer solutions for $$(x_1,x_2,\cdots,x_k)$$ of $$x_1+2x_2+3x_3+\cdots+kx_k=n$$ for a given $$k\in\Bbb{N}$$?

How can I prove these formulas rigorously?

EDIT
After a very tedious calculation I found that the equation $$w+2x+3y+4z=n$$ has $$\left\lfloor \dfrac{n^3}{144}+\dfrac{5n^2}{48}+\dfrac{(15+(-1)^n)n}{32}+1 \right\rfloor$$ solutions.
This solution completely agree with the approximation given by Rus May.
However still I believe that we can do something more than this.
Thank you for your valuable attention.

• You are asking for the number of partitions of $n$ into parts of sizes $\leq k$. Don't think there is a closed formula holding for all $n, k$. But for each fixed $k$, the number can be computed as the $t^n$-coefficient of the formal power series $\dfrac{1}{\left(1-t\right)\left(1-t^2\right) \cdots\left(1-t^k\right)}$, which should fall prey to some standard methods (it satisfies a linear recurrence, if I remember correctly?). – darij grinberg Dec 11 '16 at 2:50
• It can be proved that the multinomial of $x_i$, $1\leq i \leq k$ is equal the $n$th term of generalized Fibonacci numbers, as shown $$\sum_{(x_1,x_2,\cdots,x_k)} \left( \begin{array}{c} x_1+\cdots+x_k \\ x_1,\cdots , x_k \end{array} \right)=f_n\, .$$ where the summation is over non-negative integers satisfying $$x_1+2\, x_2+3\, x_3+\cdots + k\, x_k=n \, .$$ and $f_n$ is the generalized Fibonacci numbers, as follows $$f_n=\sum_{i=1}^k f_{n-i} \quad , \quad (f_0,\cdots,f_{k-2},f_{k-1})=(0,\cdots,0,1) \, .$$ – Amin235 Dec 15 '16 at 15:40
• References are generalized Fibonacci sequence and Combinatorial method. – Amin235 Dec 15 '16 at 15:41

The singularities of the generating function $\frac1{(1-t)(1-t^2)\cdots(1-t^k)}$ all lie on the unit circle in the complex plane. The partial fractions decomposition of the generating function has terms of the form $\frac\alpha{(1-x/\omega)^{1+\ell}}$, where $\alpha$ is a constant, $\omega$ is a root of unity, and $\ell$ is a natural number less than $k$. The coefficient of such a term is $\alpha\binom{n+\ell}{\ell}/\omega^\ell$, so the term with the highest multiplicity makes the greatest contribution. In this case, it is the singularity at 1 with $\ell=k-1$. Then the coefficient of $t^n$ in the generating function is approximately \begin{eqnarray*} [t^n]\frac1{(1-t)\cdots(1-t^k)}&=&\alpha\binom{n+k-1}{k-1}+o(n^{k-1})\\ &=&\alpha\frac{n^{k-1}}{(k-1)!}+o(n^{k-1}). \end{eqnarray*} To evaluate the constant $\alpha$, just multiply the generating function and the partial fractions decomposition by $(1-t)^k$ and take the limit at 1, resulting in $\alpha=1/k!$. Then, Schur's approximation to the number of solutions of $x_1+2x_2+\cdots+kx_k=n$ is $$\frac{n^{k-1}}{(k-1)!\,k!} .$$
• If by "partition function" you mean partitions of integers, then your problem is a finite version of partitions of integers. The generating function that marks the number of partitions of an integer would be $\frac{1}{(1-t)(1-t^2)(1-t^3)\cdots}$. – Rus May Jan 11 '17 at 14:41
• If we substitute $x_k=y_1$, $x_k+x_{k-1}=y_2$ and finally $x_k+\cdots+x_2+x_1=y_k,$ then $n=y_1+y_2+\cdots+y_k,$ where $0\le y_1\le y_2\le \cdots\le y_k.$ Therefore actually we need is number of ways that $n$ can written as sum of $k$ non-negative integers without considering the order. Am I correct? Is there any way to do this without using generating functions? – Bumblebee Jan 12 '17 at 5:42