Recurrence Relations and Two-Dimensional Set Partitions

Toufik Mansour Department of Mathematics University of Haifa 31905 Haifa, Israel

                toufik@math.haifa.ac.il

Augustine Munagi

John Knopfmacher Centre for Applicable Analysis and Number Theory

School of Mathematics University of the Witwatersrand Johannesburg, South Africa

              Augustine.Munagi@wits.ac.za

Mark Shattuck Department of Mathematics University of Tennessee Knoxville, TN 37996 USA

                 shattuck@math.utk.edu

Abstract

In this paper, we consider a two-dimensional model for finite set partitions which arises in conjunction with a special case of a general non-linear recurrence. We investigate properties of some of the related counting sequences, including recurrences and generating functions. In particular, we obtain, by combinatorial arguments, some formulas relating these sequences to the Stirling numbers of the first kind. Specializing these arguments yields bijective proofs of some recent identities of Gould and Quaintance involving the Bell numbers, which were established using algebraic methods.

1 Introduction

In this paper, we consider a combinatorial model which explains a special case of the general non-linear recurrence

T_{n} = ∑_{j=0}^{n−1} \binom{n − 1}{j}a_{j}T_{n−j−1},  (1)

with the initial conditions T_{0} = 1 and T_{n} = 0 for n < 0, where a_{n} is any given sequence. In particular, we investigate a concept of two-dimensional set partition and derive properties of some of the associated counting sequences. See [2, 5, 13] and [1, Chap. 11] for comparable considerations involving higher dimensional analogues of integer partitions. See also the related paper [12] on “hierarchical orderings”.

We remark that the recurrence relation (1) may be solved analytically, using generating functions, as follows. Let A(x) = ∑_{n≥0} \frac{a_{n}}{n!} x^{n} and T (x) = ∑_{n≥0} \frac{T_{n}}{n!} x^{n}. Then rewriting (1) gives

\frac{T_{n}}{(n − 1)!} = ∑_{j=0}^{n−1} \frac{a_{j}}{j!} \frac{T_{n−j−1}}{(n − j − 1)!}.

Multiplying by x^{n−1} and summing over all n ≥ 1, we obtain \frac{d}{dx}T (x) = A(x)T (x), which implies T (x) = e^{∫_{0}^{x} A(t)dt+c}. Noting the initial value T_{0} = T (0) = 1, we obtain the following result:

T (x) = e^{∫_{0}^{x} A(t)dt}.  (2)

Example 1. If a_{n} = 1 for all n, then A(x) = e^{x} and hence T (x) = e^{e^{x}−1}, in which case T_{n} is the n-th Bell number. For another example, suppose a_{n} = 1 + δ_{n,0} for all n. Then A(x) = e^{x} + 1 and hence T (x) = e^{e^{x}+x−1} = \frac{d}{dx}e^{e^{x}−1}, which implies that T_{n} is the (n + 1)-st Bell number.

Example 2. If a_{n} = B_{n+1} for all n, then A(x) = e^{e^{x}+x−1} and hence T (x) = e^{e^{e^{x}−1}−1}.

In the next section, we investigate a concept of a two-dimensional (2D) partition which arises in conjunction with the special case a_{n} = B_{n+1} above. We then exhibit several properties of 2D set partitions, some of which are higher-dimensional analogues of properties for standard set partitions. The final section is devoted to the proofs of higher dimensional versions of recent identities of Gould and Quaintance [7] relating Bell numbers to the Stirling numbers of the first kind. The proofs we give for our relations are combinatorial in nature and specialize to the identities occurring in [7] which were proven there using algebraic methods. We also obtain, as a consequence, bijective proofs of simple relations which express the Bell and Stirling numbers in terms of sequences which count 2D partitions.

Recall that a partition of the set [n] = {1, 2, …, n} is any collection of nonempty, disjoint subsets, called blocks, whose union is [n]. A partition B having k blocks (called a k-partition) is often denoted by B = B_{1}/B_{2}/ ⋯ /B_{k}, where the blocks of B are arranged in the standard order: min(B_{1}) < ⋯ < min(B_{k}). The partition B will be said to be in standard form. For example, the partitions of [3] in standard form are given by 123, 1/23, 12/3, 13/2 and 1/2/3. We denote the set of all partitions of [n] having exactly k blocks by B(n, k) and the set of all partitions of [n] by B(n). Recall that |B(n, k)| = S_{n,k}, the classical Stirling number of the second kind, and |B(n)| = B_{n}, the n-th Bell number (see, e.g., [14] or [16]). Throughout, empty sums will take the value 0 and empty products the value 1, with 0^{0} := 1.

2 Combinatorial Interpretation via 2D Set Partitions

We give a combinatorial solution of the recurrence relation (1) for the specialization a_{n} = B_{n+1}. We first consider a class of shapes in the plane which will be used to define our combinatorial object.

Definition 3. Consider the two dimensional (2D) grid G of unit squares whose vertices are the lattice points and any finite subset S of G having left-justified rows with no restriction on the row lengths. We will call such configurations 2D shapes.

See Figure 1 below for some examples of 2D shapes. Clearly, our 2D shapes are more general than the classical Ferrers shapes (see, e.g., [1]). The individual unit squares of a 2D shape will be called cells.

Figure 1: Examples of 2D-shapes with 5 rows and at most 5 columns.

We now give our definition for two-dimension set partitions.

Definition 4. A two-dimensional partition of [n] is a distribution of the elements of [n] among the cells of a 2D shape according to the following rules:

(1) If a row consists of i non-empty cells, then the first i cells, from left to right, are nonempty (gap-free row condition);

(2) If the first column consists of i non-empty cells, then the first i cells, from top to bottom, are non-empty (first column gap-free condition);

(3) In each row, and in the first column, the cells appear in order of their increasing smallest elements.

A non-empty cell of a 2D partition will also be called a block of the partition. Thus “a 2D partition with r blocks” will be taken to mean “a partition in which the 2D shape consists of r non-empty cells.” To illustrate, the following are 2D partitions of [13]:

\begin{matrix}1, 2 & 10 \\ 3, 11 \\ 4 & 5 & 12 \\ 6, 7, 13 & 8, 9 \end{matrix} , \begin{matrix}1, 2 \\ 3, 11 & 10 \\ 4 & 6, 7, 13 & 8, 9 \\ 5 & 12 \end{matrix} , \begin{matrix}1, 2 & 10 \\ 3, 11 \\ 4 & 5 & 6, 7, 13 & 8, 9 \\ 12 \end{matrix} .

A 2D partition may also be viewed as the target of a mapping of the set of blocks of a standard set partition into the cells of a 2D shape in accordance with the aforementioned rules. Thus each of the partitions in the previous example corresponds to a single standard partition of [13], namely, 1, 2/3, 11/4/5/6, 7, 13/8, 9/10/12, up to rearrangements. We also say that the latter is the support of each 2D partition.

Denote the set of 2D partitions of [n] by P P_{n}, and the subset of P P_{n} with r rows by P P_{n,r}. Let the respective cardinalities of the sets be P_{n} and P_{n,r}. For example, P P_{3} contains the twelve partitions shown below:

\begin{matrix}1, 2, 3 , & 1, 2 3 , & 1, 3 2 , & 1 2, 3 , & 1 2 3 , & \begin{matrix}1, 2 \\ 3 \end{matrix} , \\ 1 2 3 , & \begin{matrix}1, 3 \\ 2 \end{matrix} , & 1 3 2 , & \begin{matrix}1 \\ 2, 3 \end{matrix} , & 1 2 3 , & 1 2 3 . \end{matrix}

A standard partition of [n] will also be referred to as a 1D partition of [n]. We now provide a combinatorial explanation of (1) in the case when a_{j} = B_{j+1}.

Theorem 5. The number P_{n,r} of 2D partitions of [n] with r rows satisfies the recurrence,

P_{n,r} = ∑_{j=0}^{n−1} \binom{n − 1}{j}B_{j+1}P_{n−j−1,r−1},  n ≥ 1,  (3)

where P_{n,0} = δ_{n,0}. The number P_{n} of 2D partitions of [n] satisfies the recurrence,

P_{n} = ∑_{j=0}^{n−1} \binom{n − 1}{j}B_{j+1}P_{n−j−1},  n ≥ 1,  (4)

where P_{0} = 1.

Proof. We construct a partition A ∈ P P_{n,r}. Select j elements from [n] − \{1\}, in \binom{n−1}{j} ways, and form the first row of A, using a 1D partition of the j + 1 elements (including 1), in B_{j+1} ways, and then distribute the remaining n − j − 1 elements so as to form the other r − 1 rows of A, in P_{n−j−1,r−1} ways. Summing over j yields (3) which we sum over r to get (4). The initial values are clear. For example, the partition π ∈ P P_{5,3} given by

π = \begin{matrix}1 & 4 \\ 2, 3 \\ 5 \end{matrix}

is formed from α = 1/2 ∈ B(2) and β ∈ P P_{3,2} given by

β = \begin{matrix}1, 2 \\ 3 \end{matrix} ,

upon selecting {4} ⊆ [5] − {1}.

Corollary 6. We have

∑_{n=0}^{∞} P_{n} \frac{x^{n}}{n!} = e^{e^{e^{x}−1}−1} and ∑_{n=0}^{∞} P_{n,r} \frac{x^{n}}{n!} = \frac{(e^{e^{x}−1} − 1)^{r}}{r!} .  (5)

Proof. Let P_{n}(y) := ∑_{r=0}^{n} P_{n,r}y^{r}. Theorem 5 gives P_{n}(y) = y ∑_{j=0}^{n−1} \binom{n−1}{j}B_{j+1}P_{n−j−1}(y). Pro-

ceeding as in Example 2 above implies P (x, y) := ∑_{n=0}^{∞} P_{n}(y)\frac{x^{n}}{n!} = e^{y(e^{e^{x}−1}−1)}. Thus, the

generating function ∑_{n=0}^{∞} P_{n} \frac{x^{n}}{n!} is P (x, 1) = e^{e^{e^{x}−1}−1}, and the generating function ∑_{n=0}^{∞} P_{n,r} \frac{x^{n}}{n!} is

the coefficient of y^{r} in P (x, y), which is \frac{(e^{e^{x}−1}−1)^{r}}{r!} .

Remark 7. For further analytic information on the function g(x) = e^{e^{e^{x}−1}−1}, see p. 571 of [6]. See also A000258 of [11] for further information concerning the number P_{n}, which is defined there as the coefficient of \frac{x^{n}}{n!} in the Taylor series expansion of g(x). Example 5.2.4 of [15] supplies a k-fold generalization of g(x).

The following explicit formula may be established by extracting the coefficients of x^{n}/n! from both sides of the first equation in (5), but we supply a direct combinatorial proof.

Corollary 8. If n ≥ 0, then

P_{n} = ∑_{k=0}^{n} S_{n,k}B_{k}.  (6)

Proof. Let B = B_{1}/B_{2}/ ⋯ /B_{k} denote a member of B(n, k) in standard form. Regard the blocks of B as single elements and group these elements together according to any λ ∈ B(k). Within each block of λ, assume that the B_{i} are written in increasing order of their indices and that the blocks of λ themselves are arranged in increasing order according to the index of the first element. Now take the first block of λ, say λ_{1} = {B_{t_{1}}, B_{t_{2}}, …, B_{t_{i}}}, and insert the members of block B_{t_{j}} in the j-th cell of the first row for each j ∈ [i]. Repeat this for the remaining blocks of λ and the subsequent rows to obtain a 2D shape having k cells altogether (each labelled by a block of B). Allowing B to vary over B(n, k), we obtain all members of P P_{n} which have k blocks. Summing over all possible k completes the proof.

Similarly, the solution of the recurrence (3) can be explicitly given as follows.

Corollary 9. If n, r ≥ 0, then

P_{n,r} = ∑_{k=r}^{n} S_{n,k}S_{k,r}.  (7)

Proof. The general summand counts the members of P P_{n,r} according to the number of blocks k, r ≤ k ≤ n, by the reasoning used in the proof of the preceding corollary. Place the blocks of a member of B(n, k) in r rows so that no row is left empty and the blocks within any row and within the first column are arranged by increasing smallest elements.

Remark 10. Note that transforms (6) and (7) are special cases, respectively, of the Sheffer polynomial transforms (31) and (27) found in [10]. It would be interesting to see if our combinatorial explanations of (6) and (7) could be extended to explain some of the more general Stirling transforms in [10].

It does not appear that the P_{n,r} satisfy a simple two-term recurrence like the S_{n,k}. The following recurrence though for P_{n,r} furnishes a higher dimensional analogue of the Stirling number recurrence (6.28) found in [8].

Proposition 11. If ℓ, m, n ≥ 0, then

\binom{ℓ + m}{ℓ}P_{n,ℓ+m} = ∑_{k=ℓ}^{n−m} \binom{n}{k}P_{k,ℓ}P_{n−k,m}.  (8)

Proof. We may assume n ≥ ℓ + m, for otherwise both sides of (8) are zero, by convention. Consider circling ℓ of the ℓ+m rows within members of P P_{n,ℓ+m}, noting that there are clearly \binom{ℓ+m}{ℓ}P_{n,ℓ+m} possibilities. We may also obtain such partitions by designating k members of [n] and arranging them to go in the ℓ circled rows in \binom{n}{k}P_{k,ℓ} ways and then arranging the remaining n − k members of [n] in m rows (which are not to be circled) in P_{n−k,m} ways, where ℓ ≤ k ≤ n − m. Finally, order the ℓ + m rows so obtained from top to bottom in increasing order according to the size of the smallest element in a given row.

Table 1 below shows some small values of P_{n,r}. Note that P_{n} = ∑_{r} P_{n,r}.

n\r 1  2  3  4  5  6  7 8 P_{n}
1  1  1
2  2  1  3
3  5  6  1  12
4  15 32  12  1  60
5  52 175 110 20  1  358
6  203 1012 945 280 30  1  2471
7  877 6230 8092 3465 595 42 1  19302
8  4140 40819 70756 40992 10010 1120 56 1 167894

Table 1: Number P_{n,r} of 2D partitions of [n] with r rows, 1 ≤ r ≤ n ≤ 8.

3 Some Properties of 2D Set Partitions

In the next section, we exhibit some further basic properties of 2D set partitions.

3.1 Specification by Number of Blocks and Number of Rows

The 2D partitions of [n] may be generated recursively from those of [n − 1] by extending the familiar 1D procedure. Let P P_{n,k,r} denote the set of 2D partitions having k blocks and r rows and let P_{n,k,r} = |P P_{n,k,r}|.

Theorem 12. Let n, k, r ≥ 0. Then

P_{n,k,r} = P_{n−1,k−1,r−1} + rP_{n−1,k−1,r} + kP_{n−1,k,r},  n, k, r ≥ 1,  (9)

where P_{0,0,0} = 1 and P_{n,k,r} = 0 if nkr = 0, with n, k, r not all zero.

Proof. We construct a partition A ∈ P P_{n,k,r}, recursively, as follows:

1. Insert the singleton block {n} at the end of the first column of a member of P P_{n−1,k−1,r−1} or insert {n} at the end of each row of a member of P P_{n−1,k−1,r}. The number of partitions A so obtained is P_{n−1,k−1,r−1} + rP_{n−1,k−1,r}.

2. Insert n into each block of a member of P P_{n−1,k,r} to get a total of kP_{n−1,k,r} partitions A. Adding these two contributions yields (9). The initial values are clear.

Now we solve algebraically the recurrence in the statement of Theorem 12. Let P_{k,r}(x) := ∑_{n≥k} P_{n,k,r}x^{n}. Then Theorem 12 gives

P_{k,r}(x) = xP_{k−1,r−1}(x) + rxP_{k−1,r}(x) + kxP_{k,r}(x),

which is equivalent to

P_{k,r}(x) = \frac{x}{1 − kx}P_{k−1,r−1}(x) + \frac{rx}{1 − kx}P_{k−1,r}(x).

Let Q_{k,r}(x) be defined by \frac{x^{k}}{(1−x)···(1−kx)}Q_{k,r}(x) = P_{k,r}(x). Then the last recurrence implies

Q_{k,r}(x) = Q_{k−1,r−1}(x) + rQ_{k−1,r}(x), Q_{r,r}(x) = 1.

Let Q_{r}(x, y) := ∑_{k≥r} Q_{k,r}(x)y^{k}. We then have

Q_{r}(x, y) = yQ_{r−1}(x, y) + ryQ_{r}(x, y),

which implies

Q_{r}(x, y) = \frac{y}{1 − ry} Q_{r−1}(x, y),

with Q_{0}(x, y) = 1. By induction on r, we have Q_{r}(x, y) = \frac{y^{r}}{(1−y)···(1−ry)}, and using the fact \frac{y^{r}}{(1−y)···(1−ry)} = ∑_{j≥r} S_{j,r}y^{j}, we obtain Q_{k,r}(x) = S_{k,r}. By the definitions, we can state

P_{k,r}(x) = \frac{S_{k,r}x^{k}}{(1 − x) ⋯ (1 − kx)},

which implies the following result.

Theorem 13. If n, k, r ≥ 0, then

P_{n,k,r} = S_{n,k}S_{k,r}.  (10)

One can also give a combinatorial proof for (10) similar to that given above for (7). The following Stirling number relation is a consequence of Theorem 13.

Corollary 14. If n, k, r ≥ 1 with k ≥ r, then

S_{n+r+1,k}S_{k,r} = ∑_{i=1}^{r}(2i + k − r)S_{n+i,i+k−r}S_{i+k−r,i}.  (11)

Proof. By (10), relation (11) is equivalent to

P_{n+r+1,k,r} = ∑_{i=1}^{r}(2i + k − r)P_{n+i,i+k−r,i}.

To show this, we argue that the right-hand side counts the members of P P_{n+r+1,k,r} according to the largest index i, 1 ≤ i ≤ r, such that the element n + i + 1 does not occupy a row by itself (note that there must be at least one such index i, for otherwise there would be no rows in which to place the elements 1, 2, …, n + 1). Then there are P_{n+i,i+k−r,i} ways to place the elements of [n + i] and (i + k − r) + i = 2i + k − r choices regarding the placement of the element n + i + 1, since it can either go in a block with at least one member of [n + i] or occur as a singleton block at the end of one of the first i rows. The elements n + i + 2, n + i + 3, …, n + r + 1 are then all placed as singleton blocks within their own rows.

The next identity relates P_{n,r} with P_{n,k,r}.

Proposition 15. If n, m, r ≥ 0, then

P_{n+m+1,r+1} = ∑_{i=r}^{n+m} ∑_{j=r}^{i} ∑_{k=0}^{n+m−i} \binom{n + m − i}{k}(j + r)^{n+m−i−k}B_{k+1}P_{i,j,r}.  (12)

Proof. We may assume r ≤ n + m, for otherwise both sides of (12) are clearly zero. We argue that the right-hand side of (12) counts the members of P P_{n+m+1,r+1} according to the smallest element, i + 1, in the (r + 1)-st row. Note that if i + 1 is the smallest element in the (r + 1)-st row, then the elements of [i] would constitute a member of P P_{i,j,r} for some j, r ≤ j ≤ i. Select k of the n + m − i elements of [n + m + 1] − [i + 1] and form a partition together with i + 1 in \binom{n+m−i}{k}B_{k+1} ways, writing the blocks in the (r + 1)-st row. Finally, place the remaining n + m − i − k elements of [n + m + 1] − [i + 1] in the first r rows in (j + r)^{n+m−i−k} ways.

3.2 On 2D Partitions with 2 Rows

Taking r = 2 in (3), and recalling P_{n,1} = B_{n}, implies that the number of 2D partitions of [n] with 2 rows is given by

P_{n,2} = ∑_{j=0}^{n−2} \binom{n − 1}{j}B_{j+1}B_{n−j−1}.

On the other hand, the explicit formula in Corollary 9 gives

P_{n,2} = ∑_{k=2}^{n} S_{n,k}S_{k,2} = ∑_{k=2}^{n}(2^{k−1} − 1)S_{n,k} = ∑_{k=1}^{n} 2^{k−1}S_{n,k} − B_{n}.

Combining the two expressions for P_{n,2} yields the following formula for the Bell numbers.

Proposition 16. If n ≥ 1, then

B_{n} = ∑_{k=1}^{n} 2^{k−1}S_{n,k} − ∑_{j=1}^{n−1} \binom{n − 1}{j − 1}B_{j}B_{n−j}.  (13)

Proof. We may provide a combinatorial proof of formula (13) as follows. If n ≥ 1, then the first sum on the right-hand side of (13) counts all the partitions of [n] in which one is allowed to circle any block not containing the element 1 (which we’ll call circled partitions) according to the number of blocks k; note that there are 2^{k−1}S_{n,k} circled partitions containing k blocks. Alternatively, one may specify beforehand the number of elements j of [n] to occupy the uncircled blocks. There are \binom{n−1}{j−1}B_{j} ways to select j − 1 members of [n] − \{1\} and to arrange them in uncircled blocks together with the element 1. Then place the remaining n − j elements of [n] in circled blocks in B_{n−j} ways. The second sum on the right-hand side of (13) then counts all the circled partitions of [n] in which there is at least one circled block and subtracting this from the first gives all circled partitions of [n] in which there are no circled blocks, which clearly number B_{n}.

Let h_{n,2} denote the number of 2D partitions of [n] with 2 rows such that the number of blocks in the second row does not exceed the number in the first row.

Proposition 17. If n ≥ 2, then

h_{n,2} = ∑_{j=0}^{n−1} ∑_{r=1}^{j+1} ∑_{t=1}^{r} \binom{n − 1}{j}S_{j+1,r}S_{n−j−1,t}.  (14)

Proof. We construct an enumerated partition A. Select j elements from [n] − \{1\}, in \binom{n−1}{j} ways, 0 ≤ j ≤ n − 1, and form the first row of A with a standard r-partition of the j + 1 elements (including 1), in S_{j+1,r} ways, 1 ≤ r ≤ j + 1. The second row is then formed with a standard t-partition of the remaining n − j − 1 elements, 1 ≤ t ≤ r, in S_{n−j−1,t} ways. Thus the total number of possibilities for A is

h_{n,2} = ∑_{j=0}^{n−1} \binom{n − 1}{j} ∑_{r=1}^{j+1} S_{j+1,r} ∑_{t=1}^{r} S_{n−j−1,t}.

4 A 2D Analogue of a Bell Number Formula of Gould and Quaintance

Gould and Quaintance [7] have recently proven the following Bell number formula by combining the binomial and Stirling inversion principles:

B_{n} = ∑_{k=0}^{n}(−p)^{n−k}\binom{n}{k} ∑_{m=0}^{p} B_{k+m}s_{p,m},  n, p ≥ 0,  (15)

where s_{p,m} is the Stirling number of the first kind. Recall that c_{p,m} := (−1)^{p−m}s_{p,m} (called the signless Stirling number of the first kind) counts all of the permutations of [p] containing exactly m cycles (see, e.g., [14]). One may then rewrite (15) slightly as

(−1)^{n+p}B_{n} = ∑_{k=0}^{n} p^{n−k}\binom{n}{k} ∑_{m=0}^{p}(−1)^{k+m}B_{k+m}c_{p,m},  n, p ≥ 0.  (16)

We establish below the following analogue of (16) involving c_{p,m} and the numbers P_{n} and P_{n,r}.

Theorem 18. If n, p ≥ 0, then

(−1)^{n+p} ∑_{i=0}^{n} P_{n,i} ∑_{j=0}^{p} \binom{p}{j}i^{p−j}B_{j} = ∑_{k=0}^{n} p^{n−k}\binom{n}{k} ∑_{m=0}^{p}(−1)^{k+m}P_{k+m}c_{p,m}.  (17)

Taking n = 0 in (17) yields the following simple relation.

Corollary 19. If p ≥ 0, then

B_{p} = ∑_{m=0}^{p} P_{m}s_{p,m}.  (18)

We prove (17) using a combinatorial argument in the sense of [3] and [4] by defining a signchanging involution whose set of survivors has cardinality given by the absolute value of the left-hand side. By allowing objects to occupy only a single row, our involution particularizes to provide a direct bijective proof of (16) and hence of (15). We have not been able to find such proofs of formulas (15) or (16) in the literature.

4.1 An Involution for (16) and (17)

We first prove (17), where we may clearly assume p ≥ 1 (note that both sides reduce to (−1)^{n}P_{n} when p = 0). We will also assume n ≥ 1, for it will be apparent what adjustments must be made to handle the n = 0 case, which is simpler. We first provide a combinatorial interpretation of the right-hand side of (17) as a signed sum over a set of configurations A. To do so, consider a collection of 4-tuples (S, λ, α, β), where S, λ, α and β are given as follows. First select any subset S of [n] of cardinality k, 0 ≤ k ≤ n, and any permutation λ of [p] having exactly m cycles, 0 ≤ m ≤ p. Let α be any function from [n]−S to [p] and let β be any 2D partition having k + m elements comprising the k members of S and the m cycles of λ. (Cycles of λ are considered as distinct objects and are written so that the smallest element is first and are to be ordered according to the size of first elements; any member of S will be considered less any cycle of λ.) Let A denote the collection of all possible 4-tuples (S, λ, α, β) as k and m vary.

Define the sign of (S, λ, α, β) ∈ A as (−1)^{k+m}, where k denotes the cardinality of S and m denotes the number of cycles of λ. For example, let n = 8, p = 6, k = 6, m = 3, S = {1, 4, 5, 6, 7, 8} ⊆ [8], and λ = (1, 4, 3), (2), (5, 6), with α : {2, 3} ↦ [6] given by α(2) = 3, α(3) = 1. Let β be the 2D partition having two rows and comprising nine elements (the six members of S and the three cycles of λ) given by

β ={1, 4, (1, 4, 3)}, {5, 8};
{6, 7}, {(2), (5, 6)}.

Then the 4-tuple c = (S, λ, α, β) would have sign (−1)^{6+3} = −1. Given k and m, note that there are p^{n−k}\binom{n}{k} choices for S and α and P_{k+m}c(p, m) choices for λ and β. Thus, the right-hand side of (17) above gives the signed sum over all possible configurations in A.

For the remainder of the proof, we will express members of A in the following manner. First assume that given a configuration (S, λ, α, β), the blocks of β are expressed canonically as follows: (i) any members of S occurring within a block of β are written in increasing order prior to any cycles of λ; (ii) any cycles of λ occurring within a block of β are arranged from left-to-right by increasing order of first (= smallest) elements; (iii) blocks are arranged from left-to-right by increasing smallest elements within a row (recall any cycle of λ is considered greater than any member of S), and (iv) rows are ordered from top to bottom according to the size of the first (= smallest) element in the first block. Note that the blocks of β in the configuration c given above are expressed canonically.

We now observe that we are able to pair up, with opposite signs, almost all of the configurations of A except a certain subset C, the details of which are given below. Hence, counting A is the same as counting the remainder set C. The set C consists of those members of A with S = [n] and λ = ι_{d} and whose 2D partition β completely isolates the 1-cycles of λ in individual cells. Note that every member of C has sign (−1)^{n+p}. If n = 5 and p = 6, then c = ([5], ι_{d}, ∅, β) is a member of C, where β is the 2D partition with three rows given by

β ={1, 3}, {(2)}, {(5)};
{2, 5}, {4}, {(3)}, {(6)};
{(1)}, {(4)}.

Furthermore, the sum on the left-hand side of (17) above gives the cardinality of C according to the number of rows i occupied by the elements of S = [n]. For once the elements of S are arranged in i rows in one of P_{n,i} ways within β, there are ∑_{j=0}^{p} \binom{p}{j}i^{p−j}B_{j} ways to arrange the p 1-cycles of λ = ι_{d}. To see this, first pick p − j of the cycles and place them one-by-one in the first i rows of c in \binom{p}{j}i^{p−j} ways (note that they must be written at the end of these rows in their own blocks in increasing order after the elements of S occurring in a row). Then arrange the remaining j cycles in additional rows (following the first i rows) according to a member of B(j) (where two cycles belonging to the same row here is considered as equivalent to two members of [j] belonging to the same block in some member of B(j)). Now sum over all possible values of j.

We now define an involution of A. Given a configuration x = (S, λ, α, β), suppose that within β, there is a block on some row containing two or more members of [p] within the cycles of λ lying in that block. Identify the lowest numbered row containing such a block and within that row, identify the left-most such block, which we will denote by M. Let a < b be the two smallest elements of [p] lying within cycles in M. If a and b belong to the same cycle (a, …, b, …), then split that cycle at b to obtain the two smaller cycles (a, …), (b, …), both belonging to M, and conversely, merge the two cycles at b if a and b belong to different cycles (recall that within a block of β, the cycles are arranged by increasing smallest [= first] elements and are written following any elements of S occurring in the block). If x′ denotes the resulting configuration, then it may be verified that the mapping x ↦ x′ is a sign-reversing involution on the set A − B, where B denotes the set consisting of those configurations (S, λ, α, β) such that λ = ι_{d} and no block of β contains two or more 1-cycles of λ. Note that neither S nor α is changed by the mapping x ↦ x′. We illustrate it in Figure 2 below; note that M = {5, (2, 4, 3, 5), (6, 8)}, a = 2 and b = 3 in this example.

Configuration u = (S, λ, α, β)  Configuration u′ = (S, λ′, α, β′)
S = {1, 4, 5, 6, 7, 8, 9, 10, 12}  S = {1, 4, 5, 6, 7, 8, 9, 10, 12}
λ = (1), (2, 4, 3, 5), (6, 8), (7)  λ′ = (1), (2, 4), (3, 5), (6, 8), (7)
α : {2, 3, 11} ↦ [8],  α : {2, 3, 11} ↦ [8],
α(2) = 3, α(3) = 1, α(11) = 5 ⟶  α(2) = 3, α(3) = 1, α(11) = 5
β = {1, 6}, {4, 9, (7)}, {(1)};  β′ = {1, 6}, {4, 9, (7)}, {(1)};
{5, (2, 4, 3, 5), (6, 8)}, {7, 10};  {5, (2, 4), (3, 5), (6, 8)}, {7, 10};
{8, 12}  {8, 12}

Figure 2: An example of the mapping x ↦ x′ when n = 12, p = 8, k = 9 and m = 4.

To complete the proof, we define an involution on B. Suppose y = (S, λ = ι_{d}, α, β) ∈ B satisfies one of the following two conditions:

(i) S ≠ [n], or (ii) S = [n] and a block in some row of β contains both a 1-cycle of λ and a member of S.

Given y, let ℓ_{o} denote the smallest index ℓ, 1 ≤ ℓ ≤ p, such that at least one of the following holds:

(i) At least one member of [n] − S maps to ℓ under α, or (ii) The cycle (ℓ) lies within a block in some row of β containing at least one member of S.

Once ℓ_{o} is identified, then let j_{o} denote the smallest index j, 1 ≤ j ≤ n, such that one of the following holds:

(i) j ∈ [n] − S and α(j) = ℓ_{o}, or (ii) j ∈ S and j lies in the same block as (ℓ_{o}) within β.

Switch j_{o} to the other option with regard to (i) and (ii). It may be verified that switching options concerning j_{o} defines a sign-changing involution x ↦ x̂ on the set B − C, where C consists of those pairs (S, λ = ι_{d}, α, β) in B such that S = [n] (whence α is the empty function) and no block of β contains both a cycle of λ and a member of S. Note that S, α, and β all change under the mapping x ↦ x̂. We illustrate it in Figure 3 below; note that ℓ_{o} = 3 and j_{o} = 4 in this example. Combining this mapping with the one above yields the required sign-changing involution of A − C. This completes the proof of (17).

Configuration v = (S, ι_{d}, α, β)  Configuration v̂ = (Ŝ, ι_{d}, α̂, β̂)
S = {1, 2, 3, 4, 5, 8} Ŝ = {1, 2, 3, 5, 8}
λ = (1)(2)(3)(4)(5)  λ = (1)(2)(3)(4)(5)
α : {6, 7} ↦ [5],  α̂ : {4, 6, 7} ↦ [5],
α(6) = 3, α(7) = 4  ⟶  α̂(4) = 3, α̂(6) = 3, α̂(7) = 4
β = {1, 2}, {3, 8}, {5}, {(1)};  β̂ = {1, 2}, {3, 8}, {5}, {(1)};
{4, (3)}, {(4)}, {(5)};  {(2)};
{(2)}  {(3)}, {(4)}, {(5)}

Figure 3: An example of the mapping x ↦ x̂ when n = 8, p = 5, k = 6 and m = 5.

The same argument also applies to (16), upon requiring members of β to have only one row. The following adjustments to the above argument must be made. Throughout, replace 2D partition by partition. The signed weight of all possible 4-tuples (S, λ, α, β) in A is now given by the sum on the right-hand side of (16). The involution is defined the same way, and the set B now consists of those configurations (S, λ, α, β) such that λ = ι_{d} with no block of β containing two or more cycles of λ (note that β is now a one-dimensional partition whose elements are the members of S and the cycles of λ). The set C then consists of those configurations (S, ι_{d}, α, β) in B such that S = [n] and no block of β contains both a cycle of λ and a member of S. Every member of C has sign (−1)^{n+p} and there are B_{n} in all, since each 1-cycle of λ comprises its own block within β and since the elements of S = [n] themselves may comprise any partition. This yields the left-hand side of (16).

4.2 Other Identities

In this section, we discuss some other identities which follow from modifying in various ways the proof above. First, if we require that the 2D partition β contain a fixed number r of rows in the proof above for (17), then we obtain an analogous relation for P_{n,r} since the involution is seen to preserve the number of rows.

Theorem 20. If n, p, r ≥ 0, then

(−1)^{n+p} ∑_{i=0}^{r} P_{n,i} ∑_{j=r−i}^{p} \binom{p}{j}i^{p−j}S_{j,r−i} = ∑_{k=0}^{n} p^{n−k}\binom{n}{k} ∑_{m=0}^{p}(−1)^{k+m}P_{k+m,r}c_{p,m}. (19)

Taking n = 0 in (19) yields the following simple relation.

Corollary 21. If p, r ≥ 0, then

S_{p,r} = ∑_{m=0}^{p} P_{m,r}s_{p,m}.  (20)

Similarly, by requiring the 1D partition β to contain a fixed number j of blocks in the proof of (16) above, then we obtain the following Stirling number identity analogous to (15) which does not seem to have been previously noted.

Theorem 22. If n, p, j ≥ 0 with j ≥ p, then

S_{n,j−p} = ∑_{k=0}^{n}(−p)^{n−k}\binom{n}{k} ∑_{m=0}^{p} S_{k+m,j}s_{p,m}.  (21)

If we require further that the 2D partition β contain a fixed number t of blocks and a fixed number r of rows in the proof of (17) above, then we obtain the following relation for P_{n,t,r} since the involution is seen to preserve both the number of blocks and the number of rows.

Theorem 23. If n, p, r, t ≥ 0 with t ≥ max{r, p}, then

(−1)^{n+p} ∑_{i=0}^{r} P_{n,t−p,i} ∑_{j=r−i}^{p} \binom{p}{j}i^{p−j}S_{j,r−i} = ∑_{k=0}^{n} p^{n−k}\binom{n}{k} ∑_{m=0}^{p}(−1)^{k+m}P_{k+m,t,r}c_{p,m}. (22)

We note the following special case.

Corollary 24. If n, p ≥ 0, then

δ_{n,0} = ∑_{k=0}^{n}(−p)^{n−k}\binom{n}{k} ∑_{m=0}^{p} S_{k+m,p}s_{p,m}.  (23)

Proof. Taking t = p in (22) yields the following identity:

δ_{n,0} · S_{p,r} = ∑_{k=0}^{n}(−p)^{n−k}\binom{n}{k} ∑_{m=0}^{p} P_{k+m,p,r}s_{p,m},

where n, p, r ≥ 0 with p ≥ r. This relation is equivalent to (23), since P_{k+m,p,r} = S_{k+m,p}S_{p,r}, by (10). Note that (23) also follows from setting j = p in (21).

Other identities involving the Bell numbers can be given combinatorial proofs using the involution above.

Remark 25. The following identity occurs as Lemma 1 in [7]:

∑_{k=0}^{n} \binom{n}{k}B_{n−k}p^{k} = ∑_{m=0}^{p} B_{n+m}s_{p,m},  n, p ≥ 0,  (24)

which may be rewritten as

(−1)^{p} ∑_{k=0}^{n} \binom{n}{k}B_{n−k}p^{k} = ∑_{m=0}^{n}(−1)^{m}B_{n+m}c_{p,m},  n, p ≥ 0.  (25)

The argument above for (16) applies. To see this, restrict the involution of A−B used in the proof of (16) to the subset of A consisting of the configurations (S, λ, α, β) for which S = [n] (whence α is the empty function). The survivors of this involution are the configurations of the form ([n], ι_{d}, ∅, β) in which the cycles of λ = ι_{d} all belong to different blocks of β. The sum on the left-hand side of (25) then counts these survivors (each has sign (−1)^{n+p}) according to the number, k, of elements of [n] sharing a block of β with a cycle of λ. Note that we have cancelled factors of (−1)^{n} from both sides in (25). Remark 26. Consider the n-th Bell polynomial ϕ_{n}(t) given by

ϕ_{n}(t) = ∑_{k=0}^{n} S_{n,k}t^{k},

which reduces to B_{n} when t = 1. It satisfies the relations

t^{p}ϕ_{n}(t) = ∑_{k=0}^{n}(−p)^{n−k}\binom{n}{k} ∑_{m=0}^{p} ϕ_{k+m}(t)s_{p,m},  n, p ≥ 0,  (26)

and

t^{p} ∑_{k=0}^{n} \binom{n}{k}ϕ_{n−k}(t)p^{k} = ∑_{m=0}^{p} ϕ_{n+m}(t)s_{p,m},  n, p ≥ 0,  (27)

which reduce to (15) and (24), respectively, when t = 1. See identities (17) and (16) in [7]. The involution used to show (16) above also applies to (26) and (27) since it preserves the number of blocks.

5 Final Remarks

It is well known that the multiset of block sizes of a 1D partition of [n] is a standard partition of the integer n. However, there is no such clear relation between 2D partitions and classical plane partitions in general. Rather the block sizes of 2D partitions form a more general type of splitting of a positive integer into summands that lie in the cells of a 2D shape.

Let us denote a 2D partition A, with r rows and k blocks, in the one-line form:

A = A_{11}, …, A_{1k_{1}}//A_{21}, …, A_{2k_{2}}// ⋯ //A_{k1}, …, A_{rk_{r}},  (28)

where A_{i1}, …, A_{ik_{i}} is the sequence of blocks in the i-th row, i ∈ [r], and k_{1} + ⋯ + k_{r} = k.

Definition 27. Consider the 2D partition A of [n] given by (28) above and denote the cardinality of a block A_{ij} by a_{ij}, where n ≥ 1. Let cc(A) denote the distribution of integers in a 2D shape obtained by replacing each A_{ij} with a_{ij}. That is,

cc(A) = a_{11}, …, a_{1k_{1}}//a_{21}, …, a_{2k_{2}}// ⋯ //a_{k1}, …, a_{rk_{r}},  (29)

where ∑_{i} ∑_{j} a_{ij} = n. We call cc(A) a plane-type (PT) composition of n. We call a PT composition of n in which the entries of each row are non-increasing a plane-type (PT) partition of n, which we denote by cp(n).

If we restrict the 2D shapes in Definition 27 to Ferrers shapes, then the resulting subset of the PT compositions are synonymous with the plane compositions studied in [9]. The same restriction applied to the PT partitions of an integer n yields the classical plane partitions of n studied in [2].

Clearly, a given PT composition cc(n) (or PT partition cp(n)) with r entries can correspond to several members A of P P_{n,r}, upon replacing each block in A with its cardinality. We will say that cc(n) generates A. The set of all PT compositions of n clearly generates all of P P_{n}. The subset of all PT compositions of n consisting of those members for which a_{i,j} = 1 for each i and j (note that they are in 1 − 1 correspondence with the set of all 2D shapes) generates a subset of P P_{n} having cardinality B_{n}, upon writing (in increasing order) the elements of the i-th block of a partition of [n] (expressed in standard form) in the i-th row of a 2D-shape. The further subset of these compositions whose members have exactly r rows generates a subset of P P_{n,r} containing S_{n,r} elements. In other cases, it is unclear as to the subset of P P_{n} generated.

Question 1: How many 2D partitions of [n] are generated by the set of PT partitions of n? by the set of plane compositions of n studied in [9]?

Question 2: Given an arbitrary PT composition or partition, is it possible to specify the subset of 2D partitions it generates?

One might also consider placing various restrictions on 2D partitions. For example, one could place restrictions on the size of and/or on the members contained within a particular block or row. A non-crossing 2D partition of [n] might be one in which each row is itself a non-crossing 1D partition or one in which, in addition, no two blocks in distinct rows are allowed to form a crossing either. Similar definitions could be made for non-nesting 2D partitions of [n]. Furthermore, perhaps some of the statistics on 1D partitions of [n] could be extended to yield interesting q-generalizations of P_{n} or P_{n,r}.

References

[1] G. E. Andrews, The Theory of Partitions, Cambridge University Press, 1984.

[2] G. E. Andrews and P. Paule, MacMahon’s partition analysis, XII: Plane partitions, J. Lond. Math. Soc. (2) 76 (2007), 647–666.

[3] A. T. Benjamin and J. J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, Mathematical Association of America, 2003.

[4] A. T. Benjamin and J. J. Quinn, An alternate approach to alternating sums: a method to die for, College Math. J. 39 (2008), 191–201.

[5] D. Bressoud, Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture, Cambridge University Press, 1999.

[6] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[7] H. W. Gould and J. Quaintance, Implications of Spivey’s Bell number formula, J. Integer Seq. 11 (2008), Article 8.3.7.

[8] R. Graham, D. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994.

[9] A. Knopfmacher, T. Mansour and A. O. Munagi, Recurrence relations with two indices and plane compositions, J. Difference Equ. Appl. 17, (2011), 115–127.

[10] K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, Hierarchical Dobinski-type relations via substitution and the moment problem, J. Phys. A 37 (2004), 3475–3487.

[11] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[12] N. J. A. Sloane and T. Wieder, The number of hierarchical orderings, Order 21 (2004), 83–89.

[13] R. P. Stanley, Theory and application of plane partitions, Parts 1 and 2, Stud. Appl. Math. 50 (1971), 167–188; 259–279.

[14] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 1996.

[15] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[16] D. Stanton and D. White, Constructive Combinatorics, Springer-Verlag, 1986.

2010 Mathematics Subject Classification: 05A18, 05A19, 05A15 Keywords: set partition, generating function, recurrence relation, combinatorial proof.

(Concerned with sequence \underline{A000110}, \underline{A000258}, \underline{A008275}, and \underline{A008277}.)

Received November 4 2010; revised version received March 14 2011. Published in Journal of Integer Sequences, March 26 2011.

Return to Journal of Integer Sequences home page.