1
$\begingroup$

Let $k>0$ and $(l_1,\ldots,l_n)$ be given with $l_i>0$ (and the l_i's need not be distinct). How do I count the number of distinct tuples $(a_1,\ldots,a_r)$ where $a_1+\ldots+a_r=k$ and each $a_i$ is some $l_j$. There will typically be a different length $r$ for each such tuple.

If there is not a reasonably simple expression, is there some known asymptotic behavior as a function of $k$?

1 Answers 1

0

The generation function for $P_d(n)$, where no part appears more than $d$ times is given by $ \prod_{k=1}^\infty \frac{1-x^{(d+1)k}}{1-x^k} = \sum_{n=0}^\infty P_d(n)x^n. $ In your case $d=1$ and the product simplifies to $ \prod_{k=1}^\infty (1+x^k)= 1+x+x^2+2 x^3+2 x^4+3 x^5+4 x^6+5 x^7+6 x^8+8 x^9+10 x^{10}+12 x^{11}+\cdots $

See here(eqn. 47) or at OEIS. Interestlingly the number of partitions of $n$ into distinct parts matches the number of partitions of $n$ into odd parts. Something that was asked/answered here and is known as Euler identity: $ \prod_{k=1}^\infty (1+x^k) = \prod_{k=1}^\infty (1-x^{2k-1})^{-1} $