In the present paper, we are interested in the distribution of the elements lying along the Raab direction in the binomial coefficients triangle. More precisely, we prove that the sequence \(\{\binom{n-rk}{k}\}_{0\leq k \leq \lfloor n/(r+1)\rfloor}\) is asymptotically distributed according to a Gaussian law. We also provide some experimental evidences.
Let \(n\) and \(r\) be two non-negative integers. The sequence of binomial coefficients \(\{\binom{n-rk}{k}\}_{k}\), where \(0\leq k \leq \lfloor n/(r+1) \rfloor\) [9], appears in many combinatorial contexts. It represents the elements lying along all the parallel diagonals of direction \((1, r)\) in the binomial coefficients triangle [4]. Figures 1 and 2 illustrate two different directions \((1, 1)\) and \((1, 2)\) in the binomial coefficients triangle (BCT).
Raab in [9] established the recurrence relation for the sum of elements lying along the cited parallel diagonals. Let \(u_n\) be the general term of the sum of elements lying on the corresponding diagonal ray, for \(n \geq 0\) : \[u_{n+1}= \sum\limits_{k=0}^{\lfloor n/(1+r)\rfloor}\binom{n-rk}{k}x^{n-(r+1)k}y^k,\] with \(x\) and \(y\) are variables and \(u_0=0\). He proved that \(\{u_n\}_{n}\) satisfies the following recurrence relation \[u_{n+1}=xu_{n}+yu_{n-r},\] with \(u_0=0, u_k= x^{k-1}, k= 1,\ldots ,r-1.\) For more details see [2, 1].
Belbachir et al. [5, 4] generalized Raab’s work to any finite direction, or a transversal ray in the BCT, denoted by \((\theta , \alpha , r)\), where \(\theta\) is the starting position of the transversal ray in the BCT, with \(0 \leq \theta <\alpha\), \(\alpha \in \mathbb{N}\). Here, \(\alpha\) represent the number of horizontal steps, and \(r\) is the number of vertical steps, where \(r\in \mathbb{Z}\) with \(\alpha +r > 0\). This condition ensures that the direction is finite; otherwise, it will be infinite. They established the recurrence relation associated with the sum of elements lying along any finite direction.
Bender in \(1973\) established conditions for the nature of the bivariate generating function associated with a double indexed sequence of non-negative numbers \(a_{n, l}\) \((0\leq l \leq n)\) which implies asymptotic normality for the finite sequence \(\{a_{n, l}\}_l\) for fixed \(n\).
In the present paper, we use Bender’s approach [8] to prove that the sequence \(\{\binom{n-rk}{k}\}_k\) follows asymptotically a normal Gaussian distribution.
Set \(P_n(k)=\dfrac{\binom{n-rk}{ k}}{\sum\limits_j\binom{n-rj}{ j}}\). The main result of this paper is the following.
Theorem 1.1. The sequence \(\{\binom{n-rk}{k}\}_k\) is asymptotically normal with mean \(\mu_n\) and variance \(\sigma_n^2\) and we have \[\lim_{n\rightarrow \infty}\sup_x\left| \sum\limits_{k\leq \sigma_n x+\mu_n}P_n(k)-\dfrac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-\frac{t^2}{2}}dt\right| =0,\] with \[\mu_n = \dfrac{n(1- \beta)}{1+r-r\beta } \hspace{1cm} \text{and} \hspace{1cm} \sigma_n^2 = \dfrac{n\beta (1- \beta )}{(1+r-r\beta )^3},\] where \(\beta\) is a simple root of the equation \(1-z-z^{1+r}=0\), with \(|\beta|\) is the smallest one.
As specified by Bender in [8], there is only one root inside the circle of convergence (\(\beta\) is the specified simple root).
In order to prove Theorem 1.1, we define the bivariate generating function associated with \(\{\binom{n-rk}{k}\}_{n, k}\) and we prove that it satisfies Bender’s conditions hence satisfy the Central Limit Theorem (CLT).
We start by giving Bender’s result. For this, consider a double indexed sequence of non-negative numbers \(\{a_{n, l}\}_{0\leq l \leq n}\) and the corresponding normalized sequence \(P_n(l)=\dfrac{a_{n,l}}{\sum\limits_{l}a_{n,l}}\).
Theorem 2.1. [8] Let \(f(z,w)\) have a power series expansion \[f(z,w)=\sum\limits_{n,l\geq 0}a_{n,l}z^nw^l,\] where \(a_{n,l} \geq 0\), for all \(n\) and \(l\). Suppose there exists
\(\bullet\) an \(A(s)\) continuous and non-zero near \(0\),
\(\bullet\) an \(\beta(s)\) with bounded third derivative near \(0\),
\(\bullet\) a non-negative integer \(m\), and
\(\bullet\) \(\epsilon , \delta >0\) such that \[\label{1} (1-\frac{z}{\beta (s)})^mf(z,e^s)-\dfrac{A(s)}{1-z/\beta (s)}, \tag{1}\] is analytic and bounded for \[|s|< \epsilon \hspace{0.5cm} \text{and}\hspace{0.5cm} |z|<|\beta (0)|+\delta.\]
Define \[\label{2} \mu = -\dfrac{\beta ^{'}(0)}{\beta (0)} \hspace{0.5cm} \text{and}\hspace{0.5cm} \sigma^2=\mu^2-\dfrac{\beta ^{''}(0)}{\beta (0)}. \tag{2}\]
If \(\sigma \neq 0\), then \[\lim_{n\rightarrow \infty}\sup_x\left| \sum\limits_{l\leq \sigma_n x+\mu_n}P_n(l)-\dfrac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-\frac{t^2}{2}}dt\right| = 0,\] holds with \(\mu_n = n\mu\) and \(\sigma_n^2 = n \sigma^2\).
In [8], Bender discussed the case where the bivariate generating function associated with \(\{a_{n,l}\}_{n, l}\) is of the form \(\dfrac{Q(z, w)}{H(z, w)^{m+1}}\), where \(Q\) is an analytic function and \(H\) is a polynomial.
He established new conditions in order to ensure the asymptotic normality of the coefficients. Herein we quote the conditions.
Claim 1.[8] Suppose that \[f(z, w)= \dfrac{Q(z, w)}{H(z, w)^{m+1}},\] if \(H(z, w)\) is a polynomial in \(z\) with coefficients continuous in \(w\), \(H(z, 1)\) has a simple root at \(\beta\) and all other roots have larger absolute value, \(Q(z, w)\) is analytic for \(w\) near \(1\) and \(z< \beta +\epsilon ,\) \(Q(\beta , 1) \neq 0 .\)
Then the Theorem 2.1 is applicable.
Let \(\beta (\theta)\) be a root of \(H(z, e^{\theta})=0\). Differentiating we obtain \[\begin{aligned} \beta ^{'}\frac{\partial H}{\partial z} + e^{\theta}\frac{\partial H}{\partial w} & = 0, \\ \beta ^{''}\frac{\partial H}{\partial z} + (\beta ^{'})^2\frac{\partial^2 H}{\partial z^2}+2e^{\theta}r^{'}\frac{\partial H}{\partial z \partial w} + e^{\theta}\frac{\partial H}{\partial w} + e^{2\theta} \frac{\partial H}{\partial w^2} & = 0. \end{aligned}\]
When \(\theta =0\) we obtain \[\begin{aligned} \beta^{'} &= -\frac{\partial H}{\partial w}/\frac{\partial H}{\partial z},\\ \beta^{''} &= \dfrac{-1}{\frac{\partial H}{\partial z}}\left( \beta^{'2} \dfrac{\partial^{2} H}{\partial z^{2}}+ 2\beta^{'}\dfrac{\partial H}{\partial z \partial w} + \dfrac{\partial H}{\partial w} + \dfrac{\partial^{2} H}{ \partial w^{2}}\right). \end{aligned}\]
In order to prove Theorem 1.1, we need to define the bivariate generating function associated with \(\{\binom{n-rk}{k}\}_{n, k}\) given by Tanny and Zuker (see Lemma 2.2 below). We then prove that these sequences satisfy Bender’s special case conditions Claim 1.
Lemma 2.2. [10] The bivariate generating function associated with \(\{\binom{n-rk}{k}\}_{n,k}\) is given by \[\sum\limits_{n, k}\binom{n-rk}{k}z^nw^k= \dfrac{1}{1-z -wz^{r+1}}.\]
We need also the following lemma given by Wolfram in [11].
Lemma 2.3. [11] The characteristic polynomial \(p(x)=x^p-x^{p-1}-\cdots -1\) associated with the multibonacci sequence \(v_n=v_{n-1}+ \cdots + v_{n-p}\) admits only simple roots.
For more properties concerning this sequence see [3].
Proof of Theorem 1.1. Let consider the bivariate generating function associated with \(\{\binom{n-rk}{k}\}_{n,k}\), \[\sum\limits_{n, k}\binom{n-rk}{k}z^nw^k= \dfrac{1}{1-z -wz^{r+1}} = \dfrac{Q(z,w)}{H(z,w)},\] then, we have
\(\bullet\) \(H(z,w)= 1-z -wz^{r+1}\) is a polynomial in \(z\) where the coefficients are continuous function of \(w\).
\(\bullet\) By Lemma 2.3, the roots of \(H(z,1)\) are simple.
\(\bullet\) Let \(\beta\) be the root of \(H(z,1)\), with the smallest absolute value. The absolutely smallest root is less than \(1\) for \(w\) near \(1\), because \(\frac{\partial H}{\partial z}<0\) for \(z, w>0\) (see[8]).
\(\bullet\) \(Q(z,w) =1\) is trivially analytic and \(Q(\beta ,1)\neq 0\).
These conditions being checked, we can apply Bender’s result and conclude that the sequence \(\{\binom{n-rk}{k}\}_{n,k}\) is asymptotically normal with mean \(\mu_n\) and variance \(\sigma_n^2\).
We compute \(\mu\) and \(\sigma^2\) given by (2). Let \(\beta(\theta)\) be the root of \(H(z,e^\theta)\). We have \[\begin{aligned} \beta^{'}(\theta) &= -\frac{\partial H}{\partial w}/\frac{\partial H}{\partial z},\\ \beta^{''}(\theta) &= \dfrac{-1}{\frac{\partial H}{\partial z}}\left(\beta^{'2}\dfrac{\partial^{2} H}{\partial z^{2}} + 2\beta^{'}\dfrac{\partial H}{\partial z \partial w} + \dfrac{\partial H}{\partial w} + \dfrac{\partial^{2} H}{ \partial w^{2}}\right), \end{aligned}\] thus \[\begin{aligned} \mu = -\dfrac{\beta^{'}(0)}{\beta(0)} \hspace{1cm} & \text{and} & \hspace{1cm} \sigma^{2} = \mu^{2} – \dfrac{\beta^{''}(0)}{\beta(0)}.\\ \end{aligned}\]
Consequently, \[\mu=\dfrac{1- \beta }{(1+r)-r\beta } \hspace{1cm} \text{and} \hspace{1cm} \sigma^2= \dfrac{\beta (1- \beta )}{(1+r-r\beta)^3}.\] Then \(\{\binom{n-rk}{k}\}_{n,k}\) is asymptotically normal with mean \(\mu_n= n\mu\) and variance \(\sigma^2_n= n\sigma^2\). ◻
In what follows, we give some examples of \(\{ \binom{n-rk}{k} \}_k\) with different fixed values of \(r\).
| \((1, r)\) | \(\binom{n-rk}{k}\) | \(H(z,1)\) | \(\beta\) | \(\mu\) | \(\sigma^2\) |
|---|---|---|---|---|---|
| \((1,0)\) | \(\binom{n}{k}\) | \(1-2z\) | \(0.5\) | \(0.5\) | \(0.25\) |
| \((1,1)\) | \(\binom{n-k}{k}\) | \(1-z-z^2\) | \(0,62\) | \(0.28\) | \(0.09\) |
| \((1,2)\) | \(\binom{n-2k}{k}\) | \(1-z-z^3\) | \(0.68\) | \(0.20\) | \(0.05\) |
| \((1,3)\) | \(\binom{n-3k}{k}\) | \(1-z-z^4\) | \(0,72\) | \(0,15\) | \(0,03\) |
| \((1,4)\) | \(\binom{n-4k}{k}\) | \(1-z-z^5\) | \(0,75\) | \(0,125\) | \(0,02\) |
| \((1,5)\) | \(\binom{n-5k}{k}\) | \(1-z-z^6\) | \(0,78\) | \(0,10\) | \(0,02\) |
| \((1,6)\) | \(\binom{n-6k}{k}\) | \(1-z-z^7\) | \(0,8\) | \(0,09\) | \(0,02\) |
| \((1,7)\) | \(\binom{n-7k}{k}\) | \(1-z-z^8\) | \(0,81\) | \(0,08\) | \(0,01\) |
| \((1,8)\) | \(\binom{n-8k}{k}\) | \(1-z-z^9\) | \(0,82\) | \(0,07\) | \(0,01\) |
| \((1,9)\) | \(\binom{n-9k}{k}\) | \(1-z-z^{10}\) | \(0,84\) | \(0,07\) | \(9\cdot 10^{-3}\) |
Figures 3, 4 and 5 represent the distribution of the binomial coefficients associated with different directions and for different values of \(n.\)
A positive real sequence \(\{a_l\}_{0\leq l \leq n}\) is said to be unimodal if there exists integers \(l_{0}\) and \(l_{1},\) \(0\leq l_{0} \leq l_{1} \leq n\) such that \[a_0\leq a_1\leq \cdots \leq a_{l_0-1}<a_{l_0}= \cdots = a_{l_1}>a_{l_1+1}\geq \cdots a_{n}.\]
The integers \(m\), with \(l_0\leq m \leq l_1,\) are called the modes of \(\{a_l\}_{0\leq l \leq n}\). If \(l_0 = l_1\), we talk about a peak, otherwise, the set of modes is called a plateau. It is well known that if \(n\) is even, then the \(n^{th}\) row of the BCT has a peak at \(n/2\), otherwise (when \(n\) is odd) there is a plateau with two elements \(\lfloor n/2\rfloor\) and \(\lceil n/2 \rceil\). Also some extensions, for the direction \((1, 1)\) were studied in [9, 3, 7, 6]. It was proved by Tanny and Zuker[10] that the sequence \(\{\binom{n-rk}{k}\}_k\) is unimodal more over it is log-concave, also they derived a general formula for \(k_{n,r}\) the least integer at which the maximum of \(\{\binom{n-rk}{k}\}_k\) occurs. Here we can consider that the peaks of \(\{\binom{n-rk}{k}\}_k\) is the nearest non-negative integer close to the mean \(\mu_n\)( \(\lfloor \mu_n \rfloor\) or \(\lceil \mu_n \rceil\)), for a larger \(n\), where \(\mu_n = n(1- \beta)/(1+r-r\beta)\). Hence we obtain the same result given by Tanny and Zuker in [10].
The following Tables 2 and 3 give the comparative values between the peaks of \(\{\binom{n-k}{k}\}_{k}\) and \(\{\binom{n-2k}{k}\}_{k}\) and the corresponding mean \(\mu_n\).
| \(n\) | \(\mu_{n}\) | \(k_0\) | \(|\mu_n-k_{0}|\) | \(\binom{n-k_0}{k_0}\) | \(n\) | \(\mu_{n}\) | \(k_0\) | \(|\mu_n-k_{0}|\) | \(\binom{n-k_0}{k_0}\) | |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0.28 | 0 | 0.28 | 1 | 26 | 7.28 | 7 | 0.28 | 50388 | |
| 2 | 0.56 | 0 | 0.56 | 1 | 27 | 7.56 | 7 | 0.56 | 77520 | |
| 3 | 0.84 | 1 | 0.16 | 2 | 28 | 7.84 | 8 | 0.16 | 125970 | |
| 4 | 1.12 | 1 | 0.12 | 3 | 29 | 8.12 | 8 | 0.12 | 203490 | |
| 5 | 1.4 | 1 | 0.4 | 4 | 30 | 8.4 | 8 | 0.4 | 319770 | |
| 6 | 1.68 | 2 | 0.32 | 6 | 31 | 8.68 | 9 | 0.32 | 497420 | |
| 7 | 1.96 | 2 | 0.04 | 10 | 32 | 8.96 | 9 | 0.04 | 817190 | |
| 8 | 2.24 | 2 | 0.24 | 15 | 33 | 9.24 | 9 | 0.24 | 1307504 | |
| 9 | 2.52 | 2 | 0.52 | 21 | 34 | 9.52 | 9 | 0.52 | 2042975 | |
| 10 | 2.80 | 3 | 0.2 | 35 | 35 | 9.8 | 10 | 0.2 | 3268760 | |
| 11 | 3.08 | 3 | 0.08 | 56 | 36 | 10.08 | 10 | 0.08 | 5311735 | |
| 12 | 3.36 | 3 | 0.36 | 84 | 37 | 10.36 | 10 | 0.36 | 8436285 | |
| 13 | 3.64 | 4 | 0.36 | 126 | 38 | 10.64 | 10 | 0.64 | 13123110 | |
| 14 | 3.92 | 4 | 0.08 | 210 | 39 | 10.92 | 11 | 0.08 | 21474180 | |
| 15 | 4.2 | 4 | 0.2 | 330 | 40 | 11.20 | 11 | 0.2 | 34597290 | |
| 16 | 4.48 | 4 | 0.48 | 495 | 41 | 11.48 | 11 | 0.48 | 54627300 | |
| 17 | 4.76 | 5 | 0.24 | 792 | 42 | 11.76 | 12 | 0.24 | 86493225 | |
| 18 | 5.04 | 5 | 0.04 | 1287 | 43 | 12.04 | 12 | 0.04 | 141120525 | |
| 19 | 5.32 | 5 | 0.32 | 2002 | 44 | 12.32 | 12 | 0.32 | 225792840 | |
| 20 | 5.60 | 5 | 0.6 | 3003 | 45 | 12.60 | 12 | 0.6 | 354817320 | |
| 21 | 5.88 | 6 | 0.12 | 5005 | 46 | 12.88 | 13 | 0.12 | 573166440 | |
| 22 | 6.16 | 6 | 0.16 | 8008 | 47 | 13.16 | 13 | 0.16 | 927983760 | |
| 23 | 6.44 | 6 | 0.44 | 12376 | 48 | 13.44 | 13 | 0.44 | 1476337800 | |
| 24 | 6.72 | 7 | 0.28 | 19448 | 49 | 13.72 | 14 | 0.28 | 2319959400 | |
| 25 | 7.00 | 7 | 0 | 31824 | 50 | 14.00 | 14 | 0 | 3796297200 |
| \(n\) | \(\mu_{n}\) | \(k_0\) | \(|\mu_n-k_{0}|\) | \(\binom{n-2k_0}{k_0}\) | \(n\) | \(\mu_{n}\) | \(k_0\) | \(|\mu_n-k_{0}|\) | \(\binom{n-2k_0}{k_0}\) | |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0.2 | 0 | 0.2 | 1 | 26 | 5.2 | 5 | 0.2 | 4368 | |
| 2 | 0.4 | 0 | 0.4 | 1 | 27 | 5.4 | 5 | 0.4 | 6188 | |
| 3 | 0.6 | 0 | 0.6 | 1 | 28 | 5.6 | 5 | 0.6 | 8568 | |
| 4 | 0.8 | 1 | 0.2 | 2 | 29 | 5.8 | 6 | 0.2 | 12376 | |
| 5 | 1.0 | 1 | 0 | 3 | 30 | 6 | 6 | 0 | 18564 | |
| 6 | 1.2 | 1 | 0.2 | 4 | 31 | 6.2 | 6 | 0.2 | 27132 | |
| 7 | 1.4 | 1 | 0.4 | 5 | 32 | 6.4 | 6 | 0.4 | 38760 | |
| 8 | 1.6 | 1 | 0.6 | 6 | 33 | 6.6 | 6 | 0.6 | 54264 | |
| 9 | 1.8 | 2 | 0.2 | 10 | 34 | 6.8 | 7 | 0.2 | 77520 | |
| 10 | 2.0 | 2 | 0 | 15 | 35 | 7 | 7 | 0 | 116280 | |
| 11 | 2.2 | 2 | 0.2 | 21 | 36 | 7.2 | 7 | 0.2 | 170544 | |
| 12 | 2.4 | 2 | 0.4 | 28 | 37 | 7.4 | 7 | 0.4 | 245157 | |
| 13 | 2.6 | 2 | 0.6 | 36 | 38 | 7.6 | 7 | 0.6 | 346104 | |
| 14 | 2.8 | 3 | 0.2 | 56 | 39 | 7.8 | 8 | 0.2 | 490314 | |
| 15 | 3.0 | 3 | 0 | 84 | 40 | 8 | 8 | 0 | 735471 | |
| 16 | 3.2 | 3 | 0.2 | 120 | 41 | 8.2 | 8 | 0.2 | 1081575 | |
| 17 | 3.4 | 3 | 0.4 | 165 | 42 | 8.4 | 8 | 0.4 | 1562275 | |
| 18 | 3.6 | 3 | 0.6 | 220 | 43 | 8.6 | 8 | 0.6 | 2220075 | |
| 19 | 3.8 | 4 | 0.2 | 330 | 44 | 8.8 | 9 | 0.2 | 3124550 | |
| 20 | 4.0 | 4 | 0 | 495 | 45 | 9 | 9 | 0 | 4686825 | |
| 21 | 4.2 | 4 | 0.2 | 715 | 46 | 9.2 | 9 | 0.2 | 6906900 | |
| 22 | 4.4 | 4 | 0.4 | 1001 | 47 | 9.4 | 9 | 0.4 | 10015005 | |
| 23 | 4.6 | 4 | 0.6 | 1365 | 48 | 9.6 | 9 | 0.6 | 14307150 | |
| 24 | 4.8 | 5 | 0.2 | 2002 | 49 | 9.8 | 9 | 0.2 | 20160075 | |
| 25 | 5.0 | 5 | 0 | 3003 | 50 | 10 | 10 | 0 | 30045015 |
