# 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? Sep 19, 2013 at 14:09
• You are right, I need compositions. I'll change the question. Sep 19, 2013 at 14:27

## 4 Answers

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. Sep 19, 2013 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. Sep 19, 2013 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$.

• Dear @mathse, can you please add some details and/or references to your answer? That would probably be very helpful. Thank you. Mar 6, 2014 at 10:58
• 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. Mar 6, 2014 at 22:39
• Dear @mathse, thank you. I think it would be helpful if you could add the content of your comment to your answer above. Mar 6, 2014 at 23:06
• Dear @Ricardo Andrade, thanks for your feedback. As you suggested, I added the references. Mar 7, 2014 at 8:23

Your case p=1 seems to be http://oeis.org/A078812, just binomial(n+k-1, 2*k-1). See also the references to http://oeis.org/A078812. The case p=-1 seems to be a variant of http://oeis.org/A048594, more specifically k!/n! S1(n,k) with S1 the unsigned Stirling numbers of the first kind.
Forgive me for including a line of obtruse Mathematica 9.0 code:

Table[ Apply[Times,Map[#^p&,temp=IntegerPartitions[n,{k}],{2}],1] . (Apply[Multinomial,Length/@ Split[#]]&/@ temp),{n,8},{k,n}] /. p-> -1 is, as Brendan McKay pointed out, equivalent to Table[SeriesCoefficient [PolyLog[-p, x]^k, {x, 0, n}], {n, 8}, {k, n}] /. p-> -1