Restricted partitions and convex topologies

1.   Introduction

Let $X_{n}$ be an $n$–element set. A partition $\pi =$ $\left(A_{1}, \ A_{2}, ..., A_{l} \right)$ of the set $X_{n}$ is a collection of non-empty subsets ($A_{i})_{i = 1}^{l}$ of $X_{n}$ such that $A_{i}\bigcap A_{j} = \phi \; \mathrm{for}\; i\neq j,$ and $X = \bigcup\limits_{i = 1}^{l}A_{i}.$ The $A_{i}$ are called blocks or parts of the partition. From now on, $X_{n}$ $= \left\{ 1, \; 2, \; ..., \; n\right\}$. A partition is called consecutive if each part consists of consecutive numbers in $X_{n}.$ A partition is an order-consecutive sequence if the parts $\left(A_{i}\right) _{i = 1}^{l}$ can be labelled $B_{1}, \; B_{2}, \; ..., \; B_{l}$ such that $\cup_{i = 1}^{l}B_{i}$ is a set of consecutive integers for each $i = 1, 2, ..., l.$ Partitions are ubiquitous in the field of operations research; due to their effectiveness in solving many problems linked to scheduling, factoring, and other practical questions. The total set of partitions has an exponential cardinality (Bell numbers, denoted $B_{n}$). For this and due to the cost, it is imperative to select just a subset of partitions and focus on its study to find optimal ones. Many types of partitions are considered in the literature, among them, the consecutive, the ordered consecutive, and the nested partitions, and the ordered consecutive sequences. The number of such partitions were studied by Hwang and Mallows in ^[1]. The following formulas for these sequences are as follows (see ^[1] for details):

$N_{c}(n, k) = \binom{n-1}{k-1},$ the number of consecutive partitions of $X_{n}$ in $k$ parts.

$N_{N}(n, k) = \frac{1}{n}\binom{n}{k-1}\binom{n}{k},$ the number of nested partitions of $X_{n}$ into $k$ parts.

$N_{oc}(n, k) = \sum\limits_{j = 0}^{k-1}\binom{n-1}{2k-j-2}\binom{ 2k-j-2}{j},$ the number of order consecutive partitions of $X_{n}$ into $k$ parts.

$T(n, k) = \sum\limits_{j = 0}^{k-1}(-1)^{k-1-j}\binom{k-1}{j} \binom{n+2j-1}{2j},$ the number of order consecutive partition sequences of $X_{n}$ into $k$ parts; this is also the number of convex topologies defined on the chain $X = \left\{ 1, \; 2, \; ..., \; n\right\}$ having $k$ non empty nested open sets $\phi \neq U_{1}\subsetneqq U_{2}\subsetneqq...\subsetneqq U_{k} = X$, see ^[2].

The sequence $T(n, k)$ appeared recently in ^[3], as coefficients of some homogeneous polynomials. Many combinatorial significations are supplied in Strehl's paper.

The sequences $N_{c}(n, k), N_{N}(n, k)$ and $N_{oc}(n, k)$ were extended to graphs see ^[4]. The numbers $N_{N}(n, k)$ are well known and named after Narayana. Also, they are extensively studied and linked to the famous Catalan numbers $C_{n}$, since $C_{n} =$ $\sum\limits_{k = 1}^{n}N_{N}(n, k).$ Curiously, and despite their importance in operation research and combinatorics, the other remaining sequences are not well investigated. The sequences $T(n, k)$ and $\ Tc(n) = \sum\limits_{k = 1}^{n}T(n, k)$ have a certain analogy with the Stirling numbers of the second kind and the Bell numbers, yet they are not as well studied (algebraically) as the Stirling's and the Bell's. In this paper, we show that all these sequences are log-concave, in fact, we will show that the generating polynomials associated with the sequences $T(n, k)$ and $N_{oc}(n, k)$ have only real zeros. Unlike the results in ^[5], the zeros of the considered polynomials in this paper are given explicitly. Although all the results apply for the sequence $N_{oc}(n, k)$ too, we will focus on the sequence $T(n, k)$. Using a version of a Lindeberg's Theorem, we prove that $T(n, k)$ (as well as $N_{oc}(n, k))$) is asymptotically normal.

2.   Preliminaries

In this section, we recall some definitions and facts about polynomials and unimodal sequences.

From now on, unless the mention of the contrary, all sequences considered in this paper are real and positive. A sequence $(a_{j})_{j = 0}^{n}$ is said to be unimodal, if there exist integers $k_{0}, \; k_{1}, \; (k_{0}\leq k_{1})$ such that

The integers $k_{0}\leq j\leq k_{1}$ where the maximum is reached are the modes of the sequence $(a_{j})_{j = 0}^{n}$.

The sequence $(a_{j})_{j = 0}^{n}$ is log-concave if

A real sequence $(a_{j})_{j = 0}^{n}$ is said to be with no internal zeros (NIZ for short), if $i < j, a_{i}\neq 0, \; a_{j}\neq 0\; \mathrm{then}\; a_{l}\neq 0$ for every $l, i\leq l\leq j$. A NIZ log-concave sequence is obviously unimodal, but the converse is not true. The sequence 1, 1, 4, 5, 4, 2, 1 is unimodal but not log-concave. Note the importance of the NIZ property: the sequence 0, 1, 0, 0, 2, 1 is log-concave but not unimodal. A real polynomial is unimodal (log-concave, symmetric, respectively) provided that the sequence of its coefficients is unimodal (log-concave, symmetric, respectively).

If inequalities in the log-concavity definition are strict, then the sequence is called strictly log-concave (SLC for short), and in this case, it has at most two consecutive modes. The following result may be helpful in proving unimodality:

Theorem 2.1. (Newton) If the polynomial $\sum\limits_{j = 0}^{n}a_jx^j$ associated with the real sequence $(a_j)_{j = 0}^{n}$ (not necessarily positive) has only real zeros, then

If the sequence $(a_{j})_{j = 0}^{n}$ in the previous theorem is positive, then it is SLC, and then it has at most two consecutive modes. Also, in this case a theorem of Darroch ^[6] determines the modes up to unity:

Theorem 2.2. If the polynomial $\sum\limits_{j = 0}^{n}a_{j}x^{j}$ associated with the positive sequence $(a_{j})_{j = 0}^{n}$ has only real zeros then every mode $k_{0}$ of the sequence $(a_{j})_{j = 0}^{n}$ satisfies

For a proof of this theorem, see ^[6].

3.   The real rootedness of the polynomials

In this section, we prove that the polynomial $Q_{n}(x) = \sum\limits_{k = 1}^{n}a(n, k)x^{k-1}$ has only real zeros, where $a(n, k)$ is $T(n, k)$ or $N_{oc}(n, k)$.

Theorem 3.1. The polynomial $Q_{n}(x) = \sum\limits_{k = 1}^{n}T(n, k)x^{k-1}$ has only real zeros. Also, all the roots are in $[-1, 0].$ More precisely, we have

Proof. Let

and consider

Let us evaluate

We have

Using the well known formula

we obtain

The roots $z_1, \; z_2$ of the quadratic equation $1-2(x+1)z+(1+x)z^{2}$ are given by

So, we have the decomposition

Expand the right-hand side about $z = 0$ to get

The coefficients of $z^{n-1}$, $Q_n(x)$ is given by

This is the wanted expression of $Q_n$. This means that $Q_{n}$ has $-1$ as a zero of multiplicity $^{\left\lfloor \frac{n-1}{2}\right\rfloor }.$ For the remaining zeros of $Q_{n}$, we solve the equation $Q_{n}(x) = 0,$ with $x\neq -1$:

this is equivalent to

or

Now, the previous relation may be written

Solving this last equation, we obtain

This proves that $Q_{n}$ has $(n-1)$ real zeros and are inside $[-1, 0]$.□

Here are some corollaries from the previous theorem:

Corollary 3.2. For $n \geq 2$, we have

with $Q_{1}(x) = 1, \; Q_{2}(x) = 2x+1.$

The following result may be deduced from the previous one.

Lemma 3.3. The sequence $T(n, k)$ satisfies $T(n, k) = 2T(n-1, k)+2T(n-1, k-1)-T(n-2, k)-T(n-2, k-1)$, with $T(2, 1) = 1, \ T(2, 2) = 2$ and $T(n, k) = 0,$ if $n\leq 0$ or $k > n.$

In the following result, we give the explicit value of the polynomial $H_n(x)$.

Theorem 3.4. The polynomial $H_{n}(x) = \sum\limits_{k = 0}^{n}N_{oc}(n+1, k+1)x^{k}$ has only real zeros, namely, we have

Proof. Let

then

Put

To find the explicit form of the polynomial $H_n(x)$, we compute the generating function

Substitute $b(n, l)$ by its values, we get

So,

and

Now

So,

So,

Obviously $H_n$ has only real zeros, and the theorem is proved. □

The following result follows directly from the previous theorem.

Corollary 3.5. For every $n\geq 1,$ we have

From the previous corollary, we deduce

Corollary 3.6. The sequence $N_{oc}(n, k)$ satisfies the recursion

With $N_{oc}(2, 1) =$ $N_{oc}(2, 2) = 1,$ and $N_{oc}(n, k) = 0,$ if $n\leq 0$ or $k > n.$

Proof. Use the recursion in the previous corollary. □

Another immediate result, by setting $x = 1$ in $H_n(x)$ is

Corollary 3.7. The total number of ordered consecutive partitions is given by

As a consequence of Theorem 3.1, the sequence $T(n, k)$ is log-concave and thus unimodal, with a peak or a plateau with at most 2 elements. These modes are determined up to unity in

Theorem 3.8. Every mode $k_{0}$ of the sequence $T(n, k)$ satisfies

Proof. Let us evaluate

For this, we have:

and

So,

and

This yields

Let $a = .414213$..., then

Finally we get

This means that every mode $k_{0}$ of the sequence $T(n, k)$ satisfies

This completes the proof. □

Remark 3.9. The mode must be shifted by 1 if we follow ^[3] and make the convention $T(0, 0) = 1$.

4.   Some identities and congruence relations

The coefficients of $Q_{n}(x)$ are combinatorial sums. For small values of $k$, computations are straightforward, for example, $T(n, 2) = \frac{ n(n+1)}{2}-1$. The following formulas are not easy to see without the explicit form of $Q_{n}(x),$ or a bit of effort to transform these sums to special values of hypergeometric functions.

Corollary 4.1. The following formulas hold for every $n\geq 3$

$1)\sum\limits_{j = 0}^{n-1}(-1)^{n-1-j}\binom{n-1}{j}\binom{n+2j-1}{2j} = 2^{n-1},$

$2)\sum\limits_{j = 0}^{n-2}(-1)^{n-2-j}\binom{n-2}{j}\binom{n+2j-1}{2j} = 2^{n-3}(3n-4),$

$3)\sum\limits_{j = 0}^{n-3}(-1)^{n-3-j}\binom{n-3}{j}\binom{n+2j-1}{2j} = 2^{n-6}(9n^{2}-35n+32)$.

Proof. We have

Note that sums 1–3 are just $T(n, k)$ for $n-2\leq k\leq n.$ So, these values are just the three first values of the coefficients of polynomial

Now,

The second and third summations are respectively $Q_{n}^{r}{^{\prime }}(0)$ and $\frac{Q_{n}^{r}{^{\prime \prime }}(0)}{2}.$ □

For the sake of completeness, we give the exponential generating functions of the sequences $(Q_n)_n$ and $(H_n)_n$.

Theorem 4.2. The exponential generating functions of the sequences $Q_n$ and $H_n$ are given by

with the convention $Q_0(x) = 1$.

Before giving another result connecting $T(n, k)$ and the sequences of Fibonacci, Lucas Pell, and Pell-Lucas, let us recall some definitions.

Definition 4.3. The Fibonacci and Lucas polynomials $F_{n}(x), \; L_n(x)$ are given by

The definitions of Fibonacci, Lucas, Pell and Pell-Lucas sequences, as well as their explicit formulas are given below

Definition 4.4.

Pell and Pell-Lucas sequences are defined by

The explicit formulas of these numbers are given by

The Pell and Pell-Lucas are given by

Now, let us write the polynomial $Q_n(x)$ as a function of $F_n(x)$ or $L_n(x)$:

Furthermore

Also, we can deduce

The appearance of the Fibonacci sequence $F_n$ in the context of convex topologies was already noted in ^[2]; in fact, the cardinal of a basis of convex open sets is a Fibonacci number.

In the following theorem, we give many identities connecting the numbers $T(n, k)$ and Fibonacci, Lucas, Pell, and Pell-Lucas numbers.

Theorem 4.5. We have the following identities

$1)\sum\limits_{j = 1}^{n}T(n, j) = \left\{ \begin{array}{c} 2^{l-1}q_{2l}\; {\rm if }\; n = 2l, \\ \\ 2^{l}P_{2l+1}\; {\rm if }\; n = 2l+1, \end{array} \right.$

$2)\sum\limits_{j = 1}^{n}T(n, j)4^{j-1} = \left\{ \begin{array}{c} \frac{5_{{}}^{l}F_{6l+3}}{2} \; {\rm if}\; n = 2l+1, \\ \\ \frac{5^{l-1}L_{6l}}{2} \; {\rm if }\; n = 2l, \end{array} \right.$

$3)\sum\limits_{j = 1}^{n}T(n, j)4^{-j+1} = \left\{ \begin{array}{c} \left (\frac{5}{4} \right)^{l} F_{2l+1} \; {\rm if}\; n = 2l+1, \\ \frac{1}{2} \left (\frac{5}{4} \right)^{l-1} L_{2l}\; {\rm if }\; n = 2l, \end{array} \right.$

$4)\sum\limits_{j = 1}^{n}T(n, j)(-1)^{n-j}2^{j-1} = q_{n}$,

$5)\sum\limits_{j = 1}^{n}T(n, j)8^{j-1} = 3^{n-2}q_{2n}$,

$6)\sum\limits_{j = 1}^{n}T(n, j)80^{j-1} = \frac{9^{n-2}}{2} L_{6n}$,

$7)\sum\limits_{j = 1}^{n}T(n, j)(-81)^{j-1} = \left\{ \begin{array}{c} (-1)^{n-1}2^{2n-5}5_{{}}^{\frac{n-2}{2}}L_{6k}\; {\rm if }\; n = 2k, \\ \\ \\ 2^{2n-5}5_{{}}^{\frac{n-1}{2}}F_{6n}\; {\rm if }\; n = 2k+1, \end{array} \right.$

$8)\sum \limits_{j = 1}^{n}T(n, n-j+1)4^{j-1} = \left\{ \begin{array}{c} 2^{n}5_{{}}^{\frac{n-2}{2}}L_{n}\; {\rm if }\; n = 2k, \\ \\ 2^{n-1}5_{{}}^{\frac{n-1}{2}}F_{n}\; {\rm if }\; n = 2k+1, \end{array} \right.$

$9)\sum\limits_{j = 1}^{n}T(n, j)(-5)^{j-1} = (-1)^{n-1} 2^{n-3}L_{3n}.$

Proof. For the first relation let $x = 1$ in $Q_n(x)$. For the second relation, letting $x = 4,$ and noting that $(2\pm\sqrt 5) = \left (\frac{1\pm \sqrt5}{2} \right)^3$ we get

The result follows by examining the two cases $n = 2l$ and $n = 2l+1$. The other results are obtained similarly. □

Remark 4.6. The values

mean that the $-\frac{1}{2}, \; -\frac{1}{4}$ are respectively zeros of the polynomial $Q_n$ for $n = 6k+3, \; 4k+2$, meanwhile $-\frac{1}{4}$ is never a zero for the polynomial $Q_n$.

In ^[7], many identities involving Fibonacci and Lucas numbers are proved combinatorially. It would be nice to do the same with the relations in the previous theorem.

At the end of this section, we give some congruence relations satisfied by the considered sequences.

Theorem 4.7. Let $p$ be an odd prime number. We have the following congruences

a) $N_{oc}(p, k)\equiv 0\mod(p), \ $ for $2\leq k\leq \frac{p+1}{2}$.

b) $N_{oc}\left(p, \frac{p+1}{2}\right) \equiv 1\mod(p)$.

c) $N_{oc}(p+1, k)\equiv 0\mod(p), \ $ for $2\leq k\leq \frac{p+1}{2}$.

d) $N_{oc}(p)\equiv 1\mod(p).$

e) $N_{oc}(p+1)\equiv 2\mod(p).$

Proof. Use the explicit formulas of $N_{oc}(p, k)$ and $N_{oc}(p)$. □

Theorem 4.8. Let $p$ be an odd prime. We have the following congruences

$T(p, k)\equiv (-1)^{k-1}\mod(p), \ $ for $1\leq k\leq p.$

$T(p-1, k)\equiv (-1)^{k-1}\mod(p), \ $ for $1\leq k\leq \frac{p+1}{2 }.$

$T\left(p-1, \frac{p+3}{2}\right) \equiv 0\mod(p); \ p\geq 7.$

$T(p+1, k)\equiv 0\mod(p), \ $ for $2\leq k\leq \frac{p+1}{2}.$

$T(p)\equiv 1\mod(p).$

Proof. Use the explicit formula of $T(n, k),$ and the fact that $p\mid \binom{p}{j}, \; 1\leq j\leq p-1$. □

5.   Asymptotic normality of the sequence $T(n, k)$

A positive real sequence $a(n, k)_{k = 0}^{n},$ with $A_{n} = \sum \limits_{k = 0}^{n}a(n, k)\neq 0,$ is said to satisfy a central limit theorem (or is asymptotically normal) with mean $\mu _{n}$ and variance $\sigma _{n}^{2}$ if

The sequence satisfies a local limit theorem on $B\subseteq \mathbb{R}$; with mean $\mu _{n}$ and variance $\sigma _{n}^{2}$ if

Recall the following result (see Bender ^[8]).

Theorem 5.1. Let $(g_n)_{n\geq 1}$ be a sequence of real polynomials; with only real negative zeros. The sequence of the coefficients of the $(g_n)_{n\geq 1}$ satisfies a central limit theorem; with $\mu _n = \frac{ g_n^{^{\prime }}(1)}{g_n(1)}$ and $\sigma _n^2 = \left(\frac{ g_{n}^{^{\prime \prime }}(1)}{g_n(1)}+ \frac{g_n^{^{\prime }}(1)}{g_n(1)} -\left(\frac{g_n^{^{\prime }}(1)}{g_n(1)}\right) ^2\right)$ provided that $\lim\limits_{n\longrightarrow +\infty }\sigma _n^2 = +\infty.$ If, in addition, the sequence of the coefficients of each $g_n$ is with no internal zeros; then the sequence of the coefficients satisfies a local limit theorem on $\mathbb{R}$.

Generally speaking, a central limit theorem for a sequence of random variables gives (5.1). Relation (5.2) is then deduced under the condition that the sequence has no internal zeros (see ^[8]). Relation (5.1) is nothing than simple (or pointwise) convergence. We have the following result

Theorem 5.2. The sequence $T(n, k)$ satisfies a central limit and a local limit theorem on $\mathbb{R}$, with mean

and variance

Proof. In order to prove that the sequence $T(n, k)$ is asymptotically normal, let us evaluate

Since

then $Q_{n}^{^{\prime \prime}}$, is given by

After simplification, we get

Now set

This yields

For the remaining, we have

Furthermore

Now, let us evaluate $\sigma_n^2$:

For $n$ large enough, we see that $\sigma _{n}^{2} \longrightarrow +\infty$, and this proves the theorem.□

By Theorem 5.1, and because all the $T(n, k)$ are non-zero, we have a local limit theorem, from which we deduce the

Corollary 5.3. Let $T_{k_{0}} = \max\limits_{1\leq k\leq n}\left\{ T(n, k)\right\}$. Then we have the approximation of the maximum element of $T(n, k)$

Remark 5.4. The same remarks apply for the sequence $N_{oc}(n, k),$ by the same approach, we can obtain a limit and a local theorem for $N_{oc}(n, k)$.

6.   Conclusions

In this paper, we proved that the generating polynomials associated with two sequences of restricted partitions have only real zeros. Our focus was essentially on the number of order consecutive partition sequences. The explicit form of the polynomials and the real- rooted property allow us to prove a probabilistic limit theorem, as well as some identities relating the elements of these sequences with some famous combinatorial sequences, such as Fibonacci and Lucas numbers.

Use of Generative-AI tools declaration

The author declares he has not used Artificial Intelligence (AI) tools in the creation of this article.

Funding

This work was supported and funded by the Deanship of Scientific Research at Imam Mohammad Ibn Saud Islamic University (IMSIU) (grant number IMSIU-RG23137).

Acknowledgments

The author thanks anonymous reviewers for their careful reading, corrections, and remarks which highly improved the paper in form as well as in substance.

Conflict of interest

The author has no conflicts of interest to declare.