Sum over integer compositions

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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