7
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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?). $\endgroup$ – darij grinberg Dec 11 '16 at 2:50
  • 1
    $\begingroup$ 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) \, . $$ $\endgroup$ – Amin235 Dec 15 '16 at 15:40
  • $\begingroup$ References are generalized Fibonacci sequence and Combinatorial method. $\endgroup$ – Amin235 Dec 15 '16 at 15:41
1
$\begingroup$

As Darij Grinberg says, there's not a nice closed formula for this. There is, however, a really neat approximation via Schur's theorem in combinatorics. It goes like this.

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is there any relationship between this equation and the partition function? If there any such relation, could you please explain it? $\endgroup$ – Bumblebee Jan 5 '17 at 17:42
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Rus May Jan 11 '17 at 14:41
  • $\begingroup$ 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? $\endgroup$ – Bumblebee Jan 12 '17 at 5:42

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.