Protected Cells in Compositions

Abstract

Compositions (ordered partitions) of n are finite sequences of positive integers that sum to n. We represent a composition of n as a bargraph with area n such that the height of the i-th column of the bargraph equals the size of the i-th part of the composition. We consider the concept of protected cells and protected columns in the bargraph representation of the composition. An r-protected cell is a cell in which the shortest path to the outside has at least $r+1$ steps (up, down, left or right). We obtain the average number of r-protected cells and protected columns. Finally we study the total protection number of a composition and compute the mean of this quantity over all compositions of n. We define the total protection number of a composition $\pi$ to be the sum of the protection numbers of each individual cell in that composition.

1 Introduction

Compositions of n are finite sequences of positive integers $(\sigma _i)_{i=1}^k$ such that

$$\begin{aligned} \sigma _1+\sigma _2+\cdots +\sigma _k=n, \end{aligned}$$

where the $\sigma _i$’s are called parts. Compositions of n can be represented as bargraphs of area n. Bargraphs are drawn on a regular planar lattice grid and are made up of square cells. A composition is uniquely defined by the size of each part. The height of the i-th column of the representing bargraph matches the size of the i-th part. The size of the composition is the total number of cells in the representing bargraph. A comprehensive study of compositions appears in the book [6]. The concept of protected nodes in trees is studied in various papers such as [2,3,4,5, 7, 8]. We define an analogous notion of protected cells in bargraphs. This is a model of the protection of cells in biological systems where the notion of protection indicates that the cell is insulated from outside attackers such as viruses or bacteria. Protection, here, means that the cell is not adjacent to the boundary. A different definition of protected cells in bargraphs was given by Mansour et al. in [10]. Their version takes into account just left and right protection of a cell; not also vertical protection. In addition we consider the more general case of r-protection, whereas Mansour’s left-right protection corresponds to the case $r=1$.

Assume we move through the bargraph starting at a particular cell using only vertical or horizontal steps from one cell to the next. An r-protected cell is a cell in which the shortest path to the outside has at least $r+1$ steps (up, down, left or right). We also define the protection number of a cell to be r in the case that the cell is r-protected but not $r+1$-protected. In addition we define the total protection number of a composition $\pi$ to be the sum of the protection numbers of each individual cell in that composition. In Fig. 1, we illustrate the nine 2-protected cells in the composition 335677658.

Fig. 1

The composition 335677658 of 50 with nine 2-protected cells

As the value of r increases the number of r-protected cells decreases, Fig. 2 shows there is only one 3-protected cell for the same composition.

Fig. 2

The composition 335677658 of 50 with one 3-protected cell

We illustrate the total protection number for this composition in Fig. 4 of Section 4.

2 Protected Cells

In this section we compute the average number of r-protected cells. From the definition of an r-protected cell, it follows that all cells are 0-protected. For $r=1$ the smallest value of n that will yield a 1-protected cell is 7, given by the composition 232. Also, the smallest value of n that will yield a 2-protected cell is 19, given by the composition 34543. Let $C_r(n)$ be the total number of r-protected cells over all compositions of n. Our method is to obtain a recursion for $C_r(n+1)$ in terms of $C_r(n)$. We construct all compositions of $n+1$ from compositions of n and observe the change in the number of protected cells. For each composition of n, we create two distinct compositions of $n+1$ by using each of the two steps in the following procedure. Every composition of $n+1$ is produced uniquely by this process.

• Process one: prepend a part of size one in front of the old composition.

• Process two: add a cell to the first part of the old composition. Thus if the first part of the composition of n is a then the first part of the new composition of $n+1$ will be $a+1$.

In process one prepending a part of size one does not change the number of r-protected cells for $r \ge 1$, thus $C_r(n)$ is preserved and it doesn’t contribute new protected cells to $C_r(n+1)$. For process two, let $e_r(n)$ be the number of extra r-protected cells that are produced when an extra cell is added to the first part. Thus after process two the total number of r-protected cells is $C_r(n)+e_r(n)$. We shall use the notation $a^+$ to denote a part of size at least a (similarly $n^+$ will denote a composition of size at least n). We indicate this in Fig. 3 by a vertical arrow pointing up.

Example 1

For example, in Fig. 3, when $r=2$, we illustrate the process two on the composition $2\,\,4^+5^+4^+3^+$ as shown by the addition of the shaded cell. This yields an extra 2-protected cell as shown by $\bullet$, below.

The parts $2\,\,4^+5^+4^+3^+$ have generating function $\frac{x^{18}}{(1-x)^4}$ but these parts can be followed by any composition with generating function $\frac{1-x}{1-2x}$. Thus for this particular example ($2\,\,4^+5^+4^+3^+$), the number of extra 2-protected cells is

$$\begin{aligned}{}[x^n]\frac{x^{18}}{(1-x)^4}\,\frac{1-x}{1-2x}. \end{aligned}$$

Fig. 3

The composition $2\,\,4^+5^+4^+3^+$ of $18^+$ changed to $\,3\,\,4^+5^+4^+3^+$ of $19^+$ using process two

Note that in general process two produces the number of extra 2-protected cells ($e_2(n)$) across all compositions of n, where this whole structure may be lifted by any number of rows. I.e.,

$$\begin{aligned} e_2(n) = [x^n]\frac{x^{18}}{(1-x)^4(1-x^5)}\,\frac{1-x}{1-2x}. \end{aligned}$$

(2.1)

We obtain the recursion, for $n\ge 18$

$$\begin{aligned} C_2(n+1)=2C_2(n)+e_2(n), \end{aligned}$$

with $C_2(18)=0$ and $e_2(18)=1$.

Now we generalise the concept given above and consider cells that are r-protected for general $r \ge 1$. Process one is still as before and $C_r(n)$ is preserved. For process two, the minimal shape which will produce an additional r-protected cell after adding one to the first part is

$$\begin{aligned} r(r+2)^+(r+3)^+ \cdots (2r)^+(2r+1)^+(2r)^+ \cdots (r+1)^+. \end{aligned}$$

(2.2)

It may as before be followed by any composition. The generating function is thus

$$\begin{aligned} \sum _{n\ge 0} e_r(n)\,x^n&=\frac{x^r x^{(\sum _{j=r+1}^{2r+1}j+\sum _{j=r+2}^{2r}j)}}{(1-x)^{2r}(1-x^{2r+1})}\,\frac{1-x}{1-2x} =\frac{x^{3r^2+3r}}{(1-x)^{2r-1}(1-x^{2r+1})(1-2x)}. \end{aligned}$$

The first part of size r is captured by $x^r$. The generating function for the remaining parts in (2.2) is given by $\frac{x^{(\sum _{j=r+1}^{2r+1}j+\sum _{j=r+2}^{2r}j)}}{(1-x)^{2r}}$ where the denominator accounts for the fact that they can be bigger than the minimal size. The term $1-x^{2r+1}$ in the denominator indicates that the minimal shape (of all $2r+1$ parts) can be shifted upwards. The $\frac{1-x}{1-2x}$ represents the generating function of the (possibly empty) composition that follows the first $2r+1$ columns. The general recursion is

$$\begin{aligned} C_r(n+1)=2C_r(n)+e_r(n), \end{aligned}$$

(2.3)

where we define $C_r(0):=0$.

We now define $C_r(x):=\sum _{n\ge 0} C_r(n)x^n$. Thus multiplying (2.3) by $x^{n+1}$, summing over all $n\ge 0$ we have

$$\begin{aligned} \sum _{n \ge 0} C_r(n+1)x^{n+1}=2x\sum _{n \ge 0} C_r(n)x^n+x\sum _{n \ge 0} e_r(n)x^{n}. \end{aligned}$$

This simplifies to

$$\begin{aligned} C_r(x)=2xC_r(x)+\frac{x^{3r^2+3r+1}}{(1-x)^{2r-1}(1-x^{2r+1})(1-2x)}. \end{aligned}$$

Thus the solution to this equation is

$$\begin{aligned} C_r(x)=\frac{x^{3r(r+1)+1}}{(1-2x)^2(1-x)^{2r-1}(1-x^{2r+1})}. \end{aligned}$$

(2.4)

Let us first return to our original example when $r=2$. We have

$$\begin{aligned} C_2(x)=\frac{x^{19}}{(1-2x)^2(1-x)^{3}(1-x^{5})}. \end{aligned}$$

Using partial fractions we have

$$\begin{aligned} \frac{C_2(x)}{x^{19}}=&\frac{1}{(1-2x)^2(1-x)^{3}(1-x^{5})} =\frac{13}{1-x}+\frac{22}{5(1-x)^2}+\frac{6}{5(1-x)^3}\\&\quad +\frac{1}{5(1-x)^4}-\frac{25088}{961(1-2x)}+\frac{256}{31(1-2x)^2} +\frac{231+135x-212x^2-255x^3}{4805(1+x+x^2+x^3+x^4)}. \end{aligned}$$

For asymptotic purposes, we ignore the first and last terms in the partial fractions above as their contributions are O(1). Extracting the coefficient of $x^n$, we obtain

$$\begin{aligned}{}[x^n]C_2(x)=\frac{2^{n-11}}{31}n-\frac{41}{961}2^{n-7}-\frac{1}{30}n^3+\frac{23}{10}n^2-\frac{682}{15}n+O(1). \end{aligned}$$

Dividing by $2^{n-1}$yields the average number of2 -protected cells in all compositions of $n\ge 19$:

$$\begin{aligned} \frac{2^{-10}}{31}n-\frac{41}{961}2^{-6}+O\left( \frac{n^3}{2^n}\right) . \end{aligned}$$

Coming back to the general r case, we proceed with (2.4) by expanding $\frac{1}{(1-2x)^2(1-x)^{2r-1}(1-x^{2r+1})}$ as partial fractions

$$\begin{aligned} \frac{A_r}{1-2x}+\frac{B_r}{(1-2x)^2}+\sum _{j=1}^{2r-1}\frac{C_{r,j}}{(1-x)^j}+\frac{D_r}{1-x^{2r+1}}. \end{aligned}$$

For purposes of estimating the average, we will ignore the terms $\sum _{j=1}^{2r-1}\frac{C_{r,j}}{(1-x)^j}$ and $\frac{D_r}{1-x^{2r+1}}$ whose contributions are $o(2^n)$. We will incorporate $x^{3r(r+1)+1}$ from the numerator later when we consider the coefficient of $x^{n-(3r(r+1)+1)}$. We obtain

$$\begin{aligned} A_r=\frac{2^{1+4r}(1-2^{2r}+2^{1+2r}r)}{1-2^{1+2r}} \text {\quad and \quad } B_r=\frac{2^{4r}}{2^{1+2r}-1}. \end{aligned}$$

Thus extracting the required coefficients,

$$\begin{aligned}{}[&x^{n-(3r(r+1)+1)}]\left( \frac{2^{1+4r}(2^{1+2r}r-2^{2r}+1)}{(1-2^{1+2r})(1-2x)}-\frac{2^{4r}}{(1-2^{1+2r})(1-2x)^2}\right) \\&=\frac{2^{-1+n+r-3r^2}}{2^{1+2r}-1}n+\frac{2^{-1+n+r-3r^2}}{(2^{1+2r}-1)^2} \left( 2(4^r-1)+(3-5\cdot 2^{1+2r})r+3(1-2^{1+2r})r^2 \right) . \end{aligned}$$

Dividing by $2^{n-1}$ and bounding the contributions of the $C_{r,j}$ and $D_r$ terms we obtain

Theorem 1

The average number of r-protected cells in all compositions of n is

$$\begin{aligned} \frac{2^{r-3r^2}}{2^{1+2r}-1}n+\frac{2^{r-3r^2}}{(2^{1+2r}-1)^2} \left( 2(4^r-1)+(3-5\cdot 2^{1+2r})r+3(1-2^{1+2r})r^2 \right) +O\left( \frac{n^{2r-1}}{2^n}\right) . \end{aligned}$$

Recall, the protection number of a cell is r in the case that the cell is r-protected but not $r+1$-protected. Thus, in order to obtain the number of protected cells with protection number r, we perform the subtraction $C_r(n)-C_{r+1}(n)$ and obtain

Theorem 2

The average number of protected cells with a protection number r in all compositions of n is

$$\begin{aligned} n \left( \frac{2^{r-3r^2}}{2^{1+2r}-1}-\frac{2^{1+r-3(1+r)^2}}{2^{3+2r}-1}\right) +O(1). \end{aligned}$$

Let us call the constant in the brackets X(r). Below we collect the value of the constant X(r) for $r=0$ to 5; so the average proportion of cells with a protection number r is given in the Table 1.

Table 1 Average proportion of cells with protection number r

Remark 1

The special case $r=0$, that is, cells that are 0-protected but not 1-protected make up the inner site-perimeter of compositions which has been studied in [1, 9]. In particular we see that approximately $96.4\%$ of the cells have protection number 0.

3 Protected Columns

We define a protected column to be a column in the bargraph representation of the composition with at least one protected cell. In Fig. 1 the composition has four protected columns. Using the same procedure as that required for protected cells, the number of extra protected columns when the first part in the composition of n is increased by one cell is

$$\begin{aligned} ec_r(n)=[x^n] \frac{x^r\,x^{(\sum _{j=r+1}^{2r+1} j +\sum _{j=r+2}^{2r} j)}}{(1-x)^{2r}}\, \frac{1-x}{1-2x} =[x^{n-3r(r+2)}]\frac{1}{(1-2x)(1-x)^{2r-1}}. \end{aligned}$$

The explanation is as for protected cells except we omit the factor $1-x^{2r+1}$ in the denominator since the new protected cell must be the first to occur in that column.

Define $D_r(n)$ to be the total number of r-protected columns over all compositions of n. The recursion therefore is $D_r(n+1)=2D_r(n)+ec_r(n)$. Solving this as before gives

$$\begin{aligned} D_r(x)=\frac{x^{3r(r+1)+1}}{(1-2x)^2(1-x)^{2r-1}}. \end{aligned}$$

Using partial fractions

$$\begin{aligned} \frac{1}{(1-2x)^2(1-x)^{2r-1}}=\frac{\hat{A}_r}{1-2x}+\frac{\hat{B}_r}{(1-2x)^2}+\sum _j\frac{\hat{C}_{r,j}}{(1-x)^j}, \end{aligned}$$

where $\hat{A}_r=2^{n-1+2r}(1-2r)$ and $\hat{B}_r=2^{n-1+2r}(n+1)$.

This gives the coefficient of $x^{n-(3r(r+1)+1}$ to be

$$\begin{aligned} 2^{-2+n-r-3r^2}(1+n-5r-3r^2)+O\left( n^{2r-2}\right) , \end{aligned}$$

where the $\hat{C}_{r,j}$ terms are in the Big-O term.

Dividing by $2^{n-1}$ gives

Theorem 3

The average number of r-protected columns in all compositions of n is

$$\begin{aligned} 2^{-1-r-3r^2}(n+1-5r-3r^2)+O\left( \frac{n^{2r-2}}{2^n}\right) . \end{aligned}$$

Table 2 shows the values for the coefficient of n, for $r=0$ to 5.

Table 2 Coefficient of n for $r=0 \ldots 5$

4 Total Protection Number of a Composition

In the introduction we have already defined the protection number of a cell and the total protection number of a composition $\pi$. So for example, for the composition 335677658 below, each cell has its protection number shown in it. The total protection number for that particular composition is 34 (Fig. 4).

Fig. 4

The composition 335677658 of 50 with total protection number 34

In order to compute the total protection number of a composition $\pi$, we sum the number of r-protected cells in $\pi$ over all r. This is because an r-protected cell is also a $1, 2, \ldots , (r-1)$ -protected cell and hence each cell with a protection number r is counted in this sum precisely r times.

From (2.4), the generating function for the total protection number over all the compositions is given by

$$\begin{aligned} \sum _{r \ge 1} C_r(x)=\frac{x}{(1-2x)^2} \sum _{r \ge 1} \frac{x^{3r(r+1)}}{(1-x)^{2r-1}(1-x^{2r+1})}. \end{aligned}$$

As a series expansion it is

$$\begin{aligned}&x^7+5x^8+17x^9+50x^{10}+134x^{11}+338x^{12}+819x^{13}+1927x^{14}+4435x^{15}+10036x^{16}\\&+22408x^{17}+49492x^{18}+108342x^{19}+235408x^{20}+O(x^{21}). \end{aligned}$$

Summing the expression in Theorem 1 over r we obtain

Theorem 4

The mean total protection number over all compositions of n is asymptotically equal to

$$\begin{aligned} \sum _{r \ge 1} \left( \frac{2^{r-3r^2}}{2^{1+2r}-1}n+\frac{2^{r-3r^2}}{(2^{1+2r}-1)^2} \left( 2(4^r-1)+(3-5\cdot 2^{1+2r})r+3(1-2^{1+2r})r^2 \right) \right) +o(1), \end{aligned}$$

where in the sum only the terms where $3r(r+1)+1 \le n$ are included.

This expression is of the form $Xn+Y$ where the numerical values of the constants X and Y are

$$\begin{aligned}X=0.035745788199742769401, \qquad \text {and} \qquad Y=-0.26597276502635296044.\end{aligned}$$