6
$\begingroup$

For every set of natural numbers $A$ and for all positive integers $n$, $k$, let $c_k^A(n)$ be the number of compositions of $n$ into $k$ parts from $A$, that is, the number of $(a_1, \dots, a_k) \in A^k$ such that $a_1 + \cdots + a_k = n$.

I'm looking for asymptotic formulas for $c_k^A(n)$ as $n \to +\infty$ and $k \to +\infty$ (of course, in order to say anything interesting, some hypotheses on the relative grown of $n$ and $k$, and on the set $A$, are needed).

Where can I find such kind of results? I guess that something is surely known, but I keep finding only results with $A = \mathbb{N}$ and/or $k$ fixed.

Thank for any suggestion

$\endgroup$
3
  • 3
    $\begingroup$ That's the coefficient of $x^n$ in the polynomial $(\sum_{a\in A} x^a)^k$. Saddle point method is usually applied for asymptotics of such coefficients. $\endgroup$ Dec 12, 2020 at 9:18
  • $\begingroup$ Fedor's comment seems to answer the question as best as it can be answered in this very general formulation. For example, if the generating function $\sum_{a\in A} x^a$ of $A$ is rational, then you should be able to extract precise asymptotics. $\endgroup$ Apr 6, 2022 at 17:45
  • $\begingroup$ A nice video on restricted compositions from Robert Sedgewick Analytic Combinatorics is available at coursera.org/lecture/analytic-combinatorics/… It provide some particular generating functions for compositions and denumerations $\endgroup$ Apr 6, 2022 at 21:22

2 Answers 2

1
$\begingroup$

A partial answer with two simple cases first, followed by a more complex one, -a (weak) composition with bounded parts- that was asked several years ago and it did not get a complete answer. It is found here. I will apply a Mehler Heine-type method to get the dominant term asymptotics. (This is located towards the end of this post).

Compositions referred as counting multiset partitions into ordered multisets: A multiset (mset) is compound by a set of $k$ different objects mapped to a vector of integer multiplicities (repetitions) $[a_1,a_2,...,a_k]$ indicating that the multiset has a total of $n$ elements, all $a_1$ copies of the first object, $a_2$ of the second,... and $a_k$ of the last object, such that $a_1+a_2+...+a_k=n$. All permutations of this mset are partitioned in disjoint nonempty blocks, such that the union+ of these blocks is the multiset. The order of the elements inside these blocks is irrelevant and does not count while the order of all permuted blocks does matter.

$\left[a_1\right]=[n]$. There is just one object repeated $n$ times. This is elementary and it gives the classical definition of compositions. Partial and total number of compositions are$$c_k^A(n)=\binom{n-1}{k-1}\ \wedge\ \sum_{k=1}^n c_k^A(n)=2^{n-1}$$ enter image description here

Just 1 Object Repeated $n=3$ times, total of 4 compositions. $k$ = number of blocks. Number of compositions are the number of rows with $k$ blocks. With 1 block there is 1 row, with 2 blocks there are 2 rows, with 3 blocks there is 1 row.

$\left[a_1,a_2,...,a_n\right]=[1,1,...,1]$. There are $n$ different objects and mutiset has one of each. In this case, there is no a common name to enumerate these posets. Generalized compositions, chains, preferential arrangement or pattern of length $n$ have been used. Cardinality (total number of compositions. -See Note-) corresponds to Fubini's numbers, also known as ordered Bell Numbers, $\sum_{k=1}^n k!S(n,k)$ where $S(n,k)$ are Stirling numbers of 2nd kind. This gives sequence 1, 3, 13, 75, 541, 4683, 47293,... (OEIS A000670). Generating function is $g(z)=(2-e^z)^{-1}$. In this case from 5.2.8 in Wilf's Generatingfunctionology book (See reference below), partial and total number of compositions are respectively

$$c_k^A(n)=k!S(n,k)\ \wedge \ \sum_{k=1}^n c_k^A(n) \sim \frac{1}{2}n!\cdot (\log_2e)^{n+1}\ \ \mathrm{as}\ n\rightarrow\infty$$ Note: This corresponds to Exercise 4.16* in Combinatorics of compositions and words (Silvia Heubach, Toufik Mansour) Book. This case also corresponds to Stanley R. Enumerative Combinatorics (1986, Wadsworth) Ch.3 Posets. Examples 3.15.9 & 3.15.10 pg. 145-146 or (2012, Vol I. 2nd Ed. Cambridge), examples 3.18.9 & 3.18.10 pg. 326, where they are called chains (ordered partitions of $n$ into $k$ non-empty blocks).

enter image description here

$n=3$ different objects. Total of 13 compositions (chains). $k$ = number of blocks. Number of compositions or chains are the number of rows with $k$ blocks. With 1 block there is 1 row, with 2 blocks there are 6 rows, with 3 blocks there are 6 rows. Note that if $B=C=D$ compositions shrink to the former case.

There are other very interesting cases. For instance 2 objects repeated $[a_1,a_2]=[p,n-p]$ times $0<p<n$. Asymptotics for the total number of these generalized compositions, that is between the two previous cases, I guess it has been analyzed but I have not found it. I leave the example here

enter image description here

$n=3,\ p=2$. A total number of 8 = 1 + 4 + 3 generalized compositions.

Just to wrap up this section, there is a brief discussion in the comments that compositions are only about sets of integers and not other sets. I obviously agree about that since on the one hand, compositions, as they are defined, only refer to counting how a number breaks down into the sum of its parts (sets are implicit) and on the other hand, the enumeration of the posets shown in this answer, whatever they are named, are generalized compositions over the integers (in this case, mset multiplicities). I sincerely hope I have made this matter as clear as possible.


This section fits on a special case of the question made. It answers an old MO question for the asymptotics of a (weak) composition of a positive integer $n$ into $k$ parts (an ordered sequence of nonnegative integers $[a_1,a_2,…,a_k]$ such that $∑_{i=1}^k a_i =n$ with the parts conditioned by $a_i ∈ [0,1,…,j−1]$). The number of such compositions $\ c_{k,j}^A(n)=\kappa(n,j,k)$ satisfies, $$\kappa(n,j,k) = \sum_{\ell=0}^k (-1)^\ell {k \choose \ell} {k-j\ell+n-1 \choose k-1}$$

as it is pointed out in Stanley, Richard P. "Enumerative Combinatorics. Vol I". 2nd Printing. Cambridge 1998, Supplementary Problems Ch. 1 Exercise 3 pg. 307.

This is a terminating hypergeometric function. It corresponds to a polynomial of degree $k$ expressible as an scaled$\ _2\Psi_1^*$ Fox-Wright Function (evaluated at $z=-1$). We will use the method of Mehler-Heine to find the asymptotics for $n=k\,\lambda,\ 0<\lambda<j-1$ as $k\rightarrow\infty$ of this expression as it is indicated in Bracciali and Moreno-Balcazar report (Sect 2. pg 3). Note that asymptotics is respect the parameters of $\ _2\Psi_1^*$ and not the function variable $z$. For $\alpha=j-\lambda-1>0$ we have $$c_{k,j}^A(k\,\lambda) = \frac{(-1)^k}{\Gamma(k)}\cdot\sum_{\ell=0}^k \frac{(-k)_\ell}{\ell!}\cdot\frac{\Gamma(j\,\ell-k\,\alpha)}{\Gamma(j\,\ell-k\,(\alpha+1)+1)}$$ $(a)_b=\Gamma(a+b)/\Gamma(a)$ is the Pochhammer symbol. Therefore, $$c_{k,j}^A(k\,\lambda)=F(k,\alpha)\cdot S(k,\alpha)$$ $$S(k,\alpha)=\sum_{\ell=0}^k \frac{(-k)_\ell}{\ell!}\cdot\frac{(-k\,\alpha)_{j\,\ell}}{(-k\,(\alpha+1)+1)_{j\,\ell}}$$ $$F(k,\alpha)=\frac{(-1)^k}{\Gamma(k)}\cdot\frac{\Gamma(-k\,\alpha)}{\Gamma(-k\,(\alpha+1)+1)}$$ The approach is as follows (Mehler-Heine), for the sum $S$ apply Lebesgue's dominance to move the upper limit to $\infty$ and use $(\beta\,k+\gamma)_m\sim (\beta\,k+\gamma)^m\sim (\beta\,k)^m$ as $k\rightarrow\infty$. By doing this, the price we pay is that all asymptotic expansion of this sum is lost except the leading or dominant factor which is fully retained preserving uniform asymptotic convergence. This is enough to answer the original question. Therefore we get as $k\rightarrow\infty$ , $$S(k,\alpha)\sim\sum_{\ell=0}^\infty \frac{(-k)^\ell}{\ell!}\cdot\frac{(-k\,\alpha)^{j\,\ell}}{(-k\,(\alpha+1))^{j\,\ell}}=e^{-k\,\left[\frac{\alpha}{\alpha+1}\right]^j}$$ For the factor $F$ use reflection formula for the gammas and then Stirling's approximation. This gives $$F(k,\alpha)=\frac{\alpha+1}{\alpha}\cdot\frac{1}{\Gamma(k)}\cdot\frac{\Gamma(k\,(\alpha+1))}{\Gamma(k\,\alpha+1)}=\frac{1}{\alpha}\cdot\binom{k(\alpha+1)}{k}$$ $$F(k,\alpha)\sim\frac{1}{\sqrt{2\pi\,k}}\cdot\frac{(\alpha+1)^{k(\alpha+1)+\frac{1}{2}}}{\alpha^{k\,\alpha+\frac{3}{2}}}$$ Finally for $\alpha=j-\lambda-1$ we get as $k\rightarrow\infty$ $$c_{k,j}^A(\lambda\,k)=\kappa(\lambda\,k,j,k)\sim\frac{1}{\sqrt{2\pi\,k}}\cdot\frac{(\alpha+1)^{k(\alpha+1)+\frac{1}{2}}}{\alpha^{k\,\alpha+\frac{3}{2}}}\cdot e^{-k\,\left[\frac{\alpha}{\alpha+1}\right]^j}$$


Asymptotic for restricted compositions having the same number of parts is found here, also in ArXiv

Wilf, Herbert S., Generatingfunctionology., Boston, MA: Academic Press. x, 228 p. (1994). ZBL0831.05001.

Stanley, Richard P., Enumerative combinatorics. Vol. I, The Wadsworth & Brooks/Cole Mathematics Series. Monterey, California: Wadsworth & Brooks/Cole Advanced Books & Software. xi, 306 p. (1986). ZBL0608.05001.

Cleonice F. Bracciali, Juan Jose Moreno-Balcazar. Mehler-Heine Asymptotics of a Class of Generalized Hypergeometric Polynomials. Oberwolfach WP 2013 - 23. Mathematisches Forschungsinstitut Oberwolfach gGmbH. Oberwolfach Preprints (OWP) ISSN 1864-7596. (link here)


$\endgroup$
10
  • $\begingroup$ I am very confused by this answer. $\endgroup$ Apr 6, 2022 at 17:43
  • $\begingroup$ @Sam_Hopkins. I would appreciate if you can spread yourself, Thnks $\endgroup$ Apr 6, 2022 at 20:19
  • $\begingroup$ In particular, I don't get what is meant by ``$a_1=\cdots=a_k=1$'': in the terminology of the question-asker, the $a_i$ are the parts of the composition (whereas $A$ is the set of allowed parts). And $2^{n-1}$ is well-known to be the total number of compositions of $n$; but what happened to the parameter $k$, keeping track of the number of parts? If we really have $n=k$ then there is only one composition of $n$: $n=1+1+\ldots+1$. $\endgroup$ Apr 6, 2022 at 20:29
  • $\begingroup$ Ahhh, now I think I might see what's going on: you're talking about set partitions. But the question is just about compositions of an integer (into a certain number of parts, which come from some fixed set). $\endgroup$ Apr 6, 2022 at 20:30
  • $\begingroup$ @Sam_Hopkins. Multisets are 'sets' where repetitions of objects are allowed. Compositions arise from many sources. One of them is multiset partitions into ordered multisets. It is implemented in Sage doc.sagemath.org/html/en/reference/combinat/sage/combinat/… $\endgroup$ Apr 6, 2022 at 21:03
0
$\begingroup$

A great resource is the book Combinatorics of Compositions and Words, Silvia Heubach and Toufik Mansour, CRC Press, 2010. Chapter 8 is "Asymptotics for Compositions."

$\endgroup$
2
  • $\begingroup$ I agree that it is a great resource on compositions, but I checked that chapter and, unfortunately, there's no result about compositions with parts restricted to a set A. $\endgroup$
    – Nik
    Mar 19, 2020 at 8:26
  • $\begingroup$ Oops. They introduce restricted parts $A$ in $\S$3.3 and carefully prove things in that generality through chapter 5, but then most of chapter 8 is about unrestricted compositions or Carlitz compositions. Exceptions are Example 8.26 with $A=\{1,2\}$ and parts of $\S$8.4 which might be relevant, e.g., the asymptotics of the largest part in Theorem 8.39. $\endgroup$ Mar 20, 2020 at 1:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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