Does the sum over the non-negative integers,
$$ \sum\limits_{ {i_1, \ldots i_k \geq 0:\\\ i_1+\ldots i_k=L }} 1 $$ have a closed expression, where $L$ and $k$ are some integers?
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ You're looking at partitions of $L$ into $k$ parts, which is well-studied. Well, it's slightly different, since you're also allowing zero, but it's not too hard to reduce your situation to the usual case. $\endgroup$– MathematicsStudent1122Commented Dec 28, 2021 at 20:24
-
$\begingroup$ @MathematicsStudent1122 Allowing zero is the usual case and the answer is $\binom{L+k-1}L$. $\endgroup$– Parcly TaxelCommented Dec 28, 2021 at 20:26
-
$\begingroup$ @ParclyTaxel Thank you for the clarification. $\endgroup$– MathematicsStudent1122Commented Dec 28, 2021 at 20:30
-
$\begingroup$ where can I find a proof of this formula? $\endgroup$– QuantumLogarithmCommented Dec 28, 2021 at 20:55
-
$\begingroup$ you are looking for the (weak) Compositions of L into k parts. Partitions would appear instead if there was the further restriction $i_1 \le i_2 \le \cdots$ $\endgroup$– G CabCommented Dec 28, 2021 at 22:31
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
Let $ n,k\in\mathbb{N}^{*}\left(=\mathbb{N}\setminus\left\lbrace 0\right\rbrace\right) $.
If $ \left(a_{i_{1},\cdots,i_{k}}\right)_{i_{1},\cdots,i_{k}\geq 0}\in\mathbb{R}^{\mathbb{N}^{k}} $, then : \begin{aligned}\large\sum_{i_{1}+\cdots +i_{k}=n}{a_{i_{1},\cdots,i_{k}}}=\sum_{0\leq i_{1}\leq\cdots\leq i_{k-1}\leq n}{a_{n-i_{1},i_{1}-i_{2},\cdots ,i_{k-2}-i_{k-1},i_{k-1}}}\end{aligned}
Thus : $$ \sum_{i_{1}+\cdots +i_{k}=n}{1}=\sum_{0\leq i_{1}\leq\cdots\leq i_{k-1}\leq n}{1}=\binom{n+k-1}{k-1} $$
$\textbf{Note :}$ You can prove by induction on $ k $, that $ \sum\limits_{0\leq i_{1}\leq\cdots\leq i_{k}\leq n}{1}=\binom{n+k}{k} $, denoting $ u_{n,k}=\sum\limits_{0\leq i_{1}\leq\cdots\leq i_{k}\leq n}{1} $, we have : $$ u_{n,k}=\sum_{i=0}^{n}{u_{i,k-1}} $$
