Proof of an asymptotic formula by Tricomi

Question

Firs of all I ask my question, then I explain how this question arises in my mind and lastly what I tried to solve it.

QUESTION:

Let $P_{n,N}(k)$ be the number of composition of an integer $k$ in $n$ parts bounded by $N.$ Prove that, if $n$ and $N$ are sufficiently large, $$P_{n,N}(k)\sim N^{n-1}\sqrt{\dfrac{6}{\pi n}}\exp{\left[-\frac{3}{2n}\left(\frac{nN+n-2k}{N}\right)^{2}\right]}.$$

PROLOGUE:

Following a suggestion given by Daniele Tampieri in his answer to this question (I acknowledge Daniele for this inspiring advice), I read the autobiographical work of F. Tricomi [1] where the author describes, together with some autobiographical facts, some of his works. In particular he speaks about his paper [2]. Tricomi says that, in this paper, he considers the number $P_{n,N}(k)$ of composition of an integer $k$ in $n$ parts bounded above by $N$ (I retained the same notations used by Tricomi) and that he proves that, asymptotically, if $n$ and $N$ are sufficiently large, the above estimate holds. That formula reminds me the Hardy-Ramanujan-Rademacher formula for the number of partitions of an integer.

I found the description of this paper a little bit surprising because Tricomi is best known for his work on ordinary differential equations and special function, not for works on number theory/combinatorics.

Since I am not able to find a copy of the original paper of Tricomi, my question is how to prove his asymptotic formula.

WHAT I TRIED TO DO:

I write down the generating function $$\sum_k P_{n,N}(k)x^k$$ which is trivially $$\left(\frac{x-x^{N+1}}{1-x}\right)^{n}$$ from which one can find the explicit expression $$P_{n,N}(k)=\sum_{j}(-1)^j\binom{n}{j}\binom{k-1-Nj}{n-1}.$$ Then I tried to apply the classical result for the asymptotic estimates in analytic combinatorics (see e.g. [3]) without success.

Perhaps some asymptotic for large binomial coefficient of which I am not aware is necessary?

REFERENCES

[1] Tricomi, Francesco; La mia vita di matematico attraverso la cronistoria dei miei lavori. (Bibliografia commentata 1916–1967), Padova: CEDAM – Casa Editrice Dottor Antonio Milani, pp. XII+172 (1967), MR0274255, Zbl 0199.28603.

[2] Tricomi, Francesco; Su di una variabile casuale connessa con un notevole tipo di partizioni di un intero. Giornale dell'Istituto Italiano degli Attuari, 2, 455-468 (1931), JFM 57.0614.02, Zbl 0003.01703.

[3] Flajolet, Philippe; Sedgewick, Robert; Analytic combinatorics. Cambridge University Press, Cambridge, 2009. xiv+810 pp., MR2483235, Zbl 1165.05001.

Answer 1

$\newcommand{\si}{\sigma} \newcommand{\Z}{\mathbb Z}$As noted in Pietro Majer's comment, the meaning of $\sim$ in the claim that, if $n$ and $N$ are sufficiently large, then \begin{equation*} P_{n,N}(k)\sim N^{n-1}\sqrt{\frac6{\pi n}} \exp\Big(-\frac3{2n}\Big(\frac{nN+n-2k}N\Big)^2\Big) \tag{1}\label{1} \end{equation*} should be clarified. Looking at the constant factor $\sqrt{\frac6\pi}$ on the right-hand side of \eqref{1}, one should apparently assume that $A\sim B$ is supposed to mean here that $A/B\to1$ (as it is common). So, then the claim is that \eqref{1} holds uniformly in $k$ (or at least for each feasible value of $k$) as $n,N\to\infty$.

Then \eqref{1} will of course be false. For instance, if $k=n$, then $P_{n,N}(k)=1$, whereas the right-hand side of \eqref{1} goes to $\infty$ (super-exponentially fast).

Below we will see for what values of $k$ the asymptotic relation \eqref{1} holds. We will also see that a slight modification of \eqref{1} holds for finite $N\ge2$ and such values of $k$.

---

The proper setting for statements like \eqref{1} is the so-called local (central) limit theorems (LLT's) of probability theory. Indeed, let \begin{equation*} S_{n,N}:=X_{1,N}+\dots+X_{n,N}, \end{equation*} where for each $N$ we have that $X_{1,N},\dots,X_{n,N}$ are independent random variables (r.v.'s) each uniformly distributed on the set $[N]:=\{1,\dots,N\}$. Then \begin{equation*} P_{n,N}(k)=N^n P(S_{n,N}=k). \tag{2}\label{2} \end{equation*} Moreover, one has the following LLT:
\begin{equation*} P(S_{n,N}=k)=\frac1{\si_N\sqrt{2\pi n}} e^{-z_k^2/2} +o\Big(\frac1{\si_N\sqrt n}\Big) \tag{3}\label{3} \end{equation*} uniformly in $k\in\Z$, where $z_k:=z_{k;n,N}:=\dfrac{k-n\mu_N}{\si_N\,\sqrt n}$, $\mu_N:=EX_{1,N}=(N+1)/2$, and $\si_N:=\sqrt{Var\,X_{1,N}}=\sqrt{(N^2-1)/12}$. (The condition $N\to\infty$ is not needed. One may also note that the case $N=2$ of \eqref{3} is also the case $p=q$ of the de Moivre–Laplace theorem.)

It follows immediately from \eqref{2} and \eqref{3} that \eqref{1} holds as $n,N\to\infty$ uniformly in all values $k$ that are in the normal deviation zone from the mean $n\mu_N$ of $S_{n,N}$ -- that is, uniformly in $k$ such that $|z_k|=O(1)$. Moreover, the slight modification of \eqref{1} for finite $N\ge2$ -- with $N^{n-1}$ replaced by $N^n/\sqrt{N^2-1}$ and $\dfrac{nN+n-2k}N$ replaced by $\dfrac{nN+n-2k}{\sqrt{N^2-1}}$ -- holds, again uniformly in $k$ such that $|z_k|=O(1)$.

The proof of \eqref{3} is similar to the proof of, say, Theorem 1 in Ch. VII of Petrov's book. That theorem is stated for a sequence $(X_j)$ of (lattice-valued) r.v.'s, whereas in our case we have to deal with a double-index array $(X_{j,N})$. However, the $X_{j,N}$'s have the specific and easy to deal with uniform distribution on the set $[N]$, which makes the proof of \eqref{3} significantly easier overall than the proof of the mentioned theorem. Indeed, in view of (say) Lemma 2 of Gamkrelidze, we can deal with the most difficult integral $I_3$ in the proof of the mentioned theorem the same way as with the easy integrals $I_2$ and $I_4$ (the four integrals $I_1,\dots,I_4$ are defined at the bottom of p. 190 of Petrov's book).

Answer 2

This is not a new answer but more properly a complement to the question itself and the Iosif Pinelis's answer above.
Thanks to my librarian, I found a digital copy of the paper by Tricomi in the second volume of the "Giornale dell'Istituto Italiano degli Attuari" (ID of the first page of the paper: 15969108) held by the Journal Library of the National Central library in Rome.

Brief survey of the paper (mainly translation of the paper abstract...)

Tricomi ([2], §1 p. 455, I refer to the work listed in the "Reference" section of the question) writes that the article stems from his former results on the random variable $$ y = x_1 +x_2+\ldots+x_n $$ where $x_1, x_2, \ldots, x_n$ are continuous constant probability random variables whose range of values is $(a, b)$. He was able to prove that the probability density of $y$, $p(y)$ has in this case the expression $$ p(y)=\frac{1}{(b-a)(n-1)!} B_s^{n-1}(\theta)\qquad na\le y\le nb $$ where

• $s=\left[\frac{y -na}{b-a}\right]$ where $[\cdot]:\Bbb R_{>0}\to \Bbb N$ is the floor function,
• $\theta=\frac{y -na}{b-a}-s$ is the fractional part of $\frac{y -na}{b-a}$, and
• $B_s^{n-1}(\theta)=\sum_{k=1}^n (-1)^i\binom{n}{k} (s-k+\theta)^{n-1}$ are "...certain kind of polynomials in the theory of Bernoulli numbers" (loc. cit.).

He wants to study what happens when the random variables $x_1, x_2, \ldots, x_n$ are discrete and can only assume integer values between $1$ and $N$ with constant probability $1/N$. Let $\overline{y}$ be the value of the sum random variable in this case and let $P_{k,N}(\overline{y})$ the number of partitions of $\overline{y}$ in $k$ integers with $k\le N$: from his previous work [B1] he knows that $$ p(\overline{y})\triangleq p_\overline{y} = \frac{P_{k,N}(\overline{y})}{N^n} $$ Then he uses this relation in order to find the above asymptotic expression of $P_{n,N}(y)$ as $N\to\infty$ (improving a coarser one naively deduced in the previous paper [B1]).

Bibliography

[B1] Francesco Tricomi, "Sul numero delle partizioni di un intero dato [On the number of partitions of a given integer]" (Italian), Bollettino della Unione Matematica Italiana 7, 243-245 (1928), JFM 54.0180.01.