3
$\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

Improve this question
$\endgroup$
1
  • 1
    $\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$
    – Fedor Petrov
    Dec 12 '20 at 9:18
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."

Improve this answer
$\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 '20 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$
    – Brian Hopkins
    Mar 20 '20 at 1:54

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.