4
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – László Kozma Sep 19 '13 at 15:46
4
$\begingroup$

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.

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

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.