# Sum over integer compositions

Sorry if the question is trivial - are there closed form expressions or good approximations for the sum of a symmetric function taken over all integer compositions (into given number of parts) of a number?

More precisely, I'm interested in: $$S(n,k) = \sum_{a1+ \cdots +a_k = n, \ \ a_i \geq 1} \phi_k(a_1,\dots,a_k)$$

where $\phi_k = \prod_i a_i^p$, e.g. for $p=-2$, but I'm curious even about $p=1$

I realize that I can bound this (using AM-GM ineq.) by replacing all terms by the most (un)balanced composition, but this seems quite weak as a bound.

EDITED: partition composition

• You say "partitions" but your summation notation indicates "compositions". Which is it? – Brendan McKay Sep 19 '13 at 14:09
• You are right, I need compositions. I'll change the question. – László Kozma Sep 19 '13 at 14:27

Since the question is about compositions, there is a generating function approach when $\phi(a_1,\ldots,a_n)=\prod_i f(a_1)$ for some function $f$. Namely, $S(n,k)$ is the coefficient of $x^n$ in $\left(\sum_{i\ge 1} f(i)x^i\right)^k$. For example if $f(i)=i$ then $\sum_{i\ge 1} f(i)x^i=x/(x-1)^2$ so $S(k,n)$ is the coefficient of $x^n$ in $x^k/(1-x)^{2k}$, which is $$\binom{n+k-1}{2k-1}$$ if I got it right. Other small powers can be done the same way. More complicated $f$ are likely to be able to be handled asymptotically by standard analytic methods.

• Thanks, this is very useful! For p=-2 the exact expression seems to be hard to get, but probably a good estimate can be obtained this way. – László Kozma Sep 19 '13 at 15:46

I assume that $k$ is fixed, while $n$ tends to $\infty$. I claim that for $p=2$ the sum in question is asymptotically equal to $k\zeta(2)^{k-1}n^{-2}$. First consider those partitions, which contain precisely one term $\geq\sqrt{n}$. The position of this large term can be chosen in $k$ ways, without loss assume that this position is at the end. Then we have \begin{eqnarray*} \sum\nolimits^*\phi(a_1, \ldots, a_k) & = & k\sum_{1\leq a_1\leq\sqrt{n}}\frac{1}{a_1^2}\dots\sum_{1\leq a_{k-1}\leq\sqrt{n}}\frac{1}{a_{k-1}^2}\cdot\frac{1}{(n-a_1-a_2-\dots-a_{k-1})^2}\\ & = & k\zeta(2)^{k-1}n^{-2}+\mathcal{O}(n^{-5/2}), \end{eqnarray*} where $\sum\nolimits^*$ denotes summation over the subset with only one large term.

Now consider all partiotions which contain at least two parts $\geq\sqrt{n}$. Decomposing the sum as above and using the fact that the largest part is $\geq n/k$ we see that these terms contribute $\mathcal{O}(n^{5/2})$. Hence for $p=2$ we obtain $S(n,k)=k\zeta(2)^{k-1}n^{-2}+\mathcal{O}(n^{-5/2})$. Note that the error terms depends heavily on $k$.

Clearly the same argument works for any $p<-1$. For larger values of $p$ there is a qualitative change in the asymptotic.

• Very nice analysis - unfortunately I need to approximate this for the whole range of k. – László Kozma Sep 19 '13 at 15:45

Yes, there are closed-form expressions. The number $S(n,k)$ you are looking for is the number of weighted integer compositions with weighting function $f(a)=a^p$. Many recursions and other representations for this number exist.

For example, the number $S(n,k)$ from above is precisely the number $d_{S,f}(n,k)$ defined in Eger (2013), Restricted weighted integer compositions and extended binomial coefficients (for $S=\{1,2,3,…,\}$ and $f(a)=a^p$). This paper says that $S(n,k)$ is an extended binomial coefficient, and gives various representations of the extended binomial coefficients. Other relevant literature would be Fahssi (2012), The polynomial triangles revisited, and Shapcott (2013), C-color compositions and palindromes. More relevant literature can be found in the references of these works. Other work of C. Shapcott also addresses part-products of integer compositions, which is related to your case $p=1$.

• Yes, of course. For example, the number $S(n,k)$ from above is precisely the number $d_{S,f}(n,k)$ defined in Eger (2013), Restricted weighted integer compositions and extended binomial coefficients (for $S=\{1,2,3,\ldots,\}$ and $f(a)=a^p$). This paper says that $S(n,k)$ is an extended binomial coefficient, and gives various representations of the extended binomial coefficients. Other relevant literature would be Fahssi (2012), The polynomial triangles revisited, and Shapcott (2013), C-color compositions and palindromes. More relevant literature can be found in the references of these works. – mathse Mar 6 '14 at 22:39