Margaret Archibald
email: margaret.archibald@wits.ac.za

Aubrey Blecher
email: aubrey.blecher@wits.ac.za

Charlotte Brennan
email: charlotte.brennan@wits.ac.za

Arnold Knopfmacher
email: arnold.knopfmacher@wits.ac.za

Toufik Mansour
email: tmansour@univ.haifa.ac.il

Two by two squares in set partitions

Keywords: Set partitions, restricted growth functions, generating functions, Bell numbers

come

Introduction

A partition π of a set S is a collection B 1 , B 2 , . . . , B k of non-empty disjoint subsets of S such that k i=1 B i = S (see for example [START_REF] Mansour | Combinatorics of Set Partitions, Discrete Mathematics and its applications[END_REF]). The B i 's are called blocks, and the size |B| of a block B is the number of elements in B. We assume that B 1 , B 2 , . . . , B k are listed in increasing order of their minimal elements, that is, min B 1 < min B 2 < • • • < min B k . This is known as the canonical representation. The collection of all set partitions of S is denoted by P (S). We define [n] to be the set {1, 2, . . . , n}. For example, the canonical representations of the five partitions of [START_REF] Mansour | Combinatorics of Set Partitions, Discrete Mathematics and its applications[END_REF] are {1, 2, 3}; {1, 2}, {3}; {1, 3}, {2}; {1}, {2, 3} and {1}, {2}, {3}.

Let A be a (totally ordered) alphabet of k letters. A word w of size n over the alphabet A is an element of A n . In the case A = [k], an element of A n is called k-ary word of size n. For example, the 2-ary words of size 3 are 111, 112, 121, 122, 211, 212, 221, and 222. In the word form of the set partition canonical representation, we indicate for each integer the block in which it occurs. Thus a partition into k blocks would be represented by a word π = π 1 π 2 • • • π n , where for 1 ≤ j ≤ n, π j ∈ [k] and n i=1 {π i } = [k], and π j indicates that j ∈ B π j . For example, the above set partitions of [START_REF] Mansour | Combinatorics of Set Partitions, Discrete Mathematics and its applications[END_REF]

n = 0, 1, 2, • • • (see [4, Section 1.4], A000110 in [1]).
It is a fact (see [START_REF] Mansour | Combinatorics of Set Partitions, Discrete Mathematics and its applications[END_REF]) that the canonical representations of all set partitions of [n] are precisely the words π = π 1 π 2 • • • π n such that π 1 = 1, and if i < j then the first occurrence of the letter i precedes the first occurrence of j. Such words are known as restricted growth functions.

Set partitions (or restricted growth functions) have been extensively studied in the literature, see [START_REF] Mansour | Combinatorics of Set Partitions, Discrete Mathematics and its applications[END_REF] and references therein. The exponential generating function for set partitions is given by e e x -1 = ∑ ∞ n=0 B n

x n n! , and the Bell numbers B n satisfy the binomial recurrence

B n+1 = ∑ n k=0 n k B k with B 0 = 1.
In this paper we wish to find the number of squares of side two in the canonical representation or growth restriction function of set partitions of [n]. These squares can overlap and their bases are not necessarily on the x-axis.

For example the set partition {14}{23}{5}{6} has restricted growth function 122134. Our example has a total of three 2 × 2 squares. We illustrate one of these squares below. 1 2 2 1 3 4

Fig. 1: An example of a two by two square in the restricted growth function 122134

Generating function

Let P k (x, q) be the generating function for the number of set partitions of [n] with exactly k blocks, according to the number of squares of size 2 (2 by 2 squares). The number of parts is counted by x and the number of 2 by 2 squares by q. We introduce P k (x, q|a), the generating function for partitions that end with the letter a and similarly P k (x, q|ba) for those that end in ba (column b followed by column a).

Thus for set partitions ending in a we have

P k (x, q|a) = k ∑ b=1 P k (x, q|ba) = a-1 ∑ b=1 P k (x, q|ba) + k ∑ b=a P k (x, q|ba) = x a-1 ∑ b=1 q b-1 P k (x, q|b) + xq a-1 k ∑ b=a P k (x, q|b). (1)
For set partitions ending with the letter k, we have

P k (x, q|k) = k-1 ∑ b=1 P k (x, q|bk) + P k (x, q|kk) = x k-1 ∑ b=1 q b-1 [P k (x, q|b) + P k-1 (x, q|b)] + xq k-1 P k (x, q|k). (2)
The term P k-1 (x, q|b) corresponds to the case where the k-th block contains only one element.

To simplify the notation, we shall omit the variables x and q and write P k (a) for P k (x, q|a). Thus we have two cases depending on the size of a:

Case I: For 1 ≤ a ≤ k -1 P k (a) = x a-1 ∑ b=1 q b-1 P k (b) + q a-1 x k ∑ b=a P k (b), (3)
from equation [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF].

Case II: For a = k

P k (k) = x k ∑ b=1 q b-1 P k (b) + x k-1 ∑ b=1 q b-1 P k-1 (b) = xP k (x, q; q) + xP k-1 (x, q; q), (4)
from equation ( 2), where we define

P k (x, q; v) := k ∑ a=1 P k (a)v a-1 . (5)
We proceed with equation (3), multiply it by v a-1 and sum over all values of a for 1 ≤ a ≤ k -1 and obtain P k (x, q; v)

-P k (k)v k-1 = xA + xB -xq k-1 v k-1 P k (k), (6)
where

A = q 0 P k (1)v 1 + q 0 P k (1) + qP k (2)v 2 + • • • + q 0 P k (1)v k-2 + q 1 P k (2)v k-2 + • • • + q k-3 P k (k -2)v k-2
and

B =q 0 v 0 P k (1) + q 0 v 0 P k (2) + • • • + q 0 v 0 P k (k) + q 1 v 1 P k (2) + • • • + q 1 v 1 P k (k) + • • • + q k-2 v k-2 P k-1 (k -1) + q k-2 v k-2 P k-1 (k) + q k-1 v k-1 P k (k).
Now using equation ( 4) in ( 6) we have

P k (x, q; v) -x[P k (x, q; q) + P k-1 (x, q; q)]v k-1 = x q 0 P k (1) v -v k-1 1 -v + qP k (2) v 2 -v k-1 1 -v + • • • + q k-3 P k (k -2) v k-2 -v k-1 1 -v + q k-2 P k (k -1) v k-1 -v k-1 1 -v + x 1 -qv 1 -qv P k (1) + 1 -(qv) 2 1 -qv P k (2) + • • • + 1 -(qv) k 1 -qv P k (k) -x(qv) k-1 P k (k).
This implies that for k ≥ 2

P k (x, q; v) -x [P k (x, q; q) + P k-1 (x, q; q)] v k-1 = xv 1 -v P k (x, q; qv) -P k (k)(qv) k-1 - xv k-1 1 -v P k (x, q; q) -P k (k)(q) k-1 + x 1 -qv P k (x, q; 1) - xqv 1 -qv P k (x, q; qv) -x(qv) k-1 [P k (x, q; q) + P k-1 (x, q; q)] so that P k (x, q; v) = xv 1 -v P k (x, q; qv) - xv k-1 1 -v P k (x, q; q) + x 1 -qv P k (x, q; 1) - xqv 1 -qv P k (x, q; qv) + xP k (k)v k-1 .
We define P 0 (x, q; v) = 1 and P 1 (x, q; v) = x 1-x . Thus, if we introduce the variable y that counts the number of blocks, which is k in P(x, y, q; v) = ∑ k≥0 P k (x, q; v)y k we have

P(x, y, q; v) - xy 1 -x -1 = xv(1 -q) (1 -v)(1 -qv) P(x, y, q; qv) - xy 1 -x -1 - x 1 -v P(x, yv, q; q) - xvy 1 -x -1 + x 1 -qv P(x, y, q; 1) - xy 1 -x -1 + xy [P(x, yv, q; q) -1].
This simplifies to the following result.

Theorem 2.1. We have

P(x, y, q; v) = xv(1 -q) (1 -v)(1 -qv)
P(x, y, q; qv) + xy -x 1v P(x, yv, q; q) + x 1qv P(x, y, q; 1) + 1.

The series expansion starts 1 + xy + x 2 (y + vy 2 ) + x 3 (y + y 2 + vy 2 + qvy 2 + qv 2 y 3 ) + x 4 (y + 2y 2 + qy 2 + 2vy 2 + qvy 2 + vq 2 y 2 + qy 3 + q 2 vy 3 + v 2 y 3 + qv 2 y 3 + q 2 v 2 y 3 + q 3 v 2 y 3 + q 3 v 3 y 4 ). We illustrate the coefficient of x 4 i.e., the 15 set partitions with 4 parts in Figure 2. Recall v counts m -1 where m is the size of the last letter and y counts the number of blocks. Below each drawing is the number of two by two squares. It is well known that the generating function for the number of set partitions of [n] with exactly k blocks is given by P(x, y,

1 1 1 1 y 1 1 2 1 y 2 1 2 1 1 y 2 1 2 2 1 qy 2 1 2 1 2 vy 2 1 1 1 2 vy 2 1 1 2 2 qvy 2 1 2 2 2 q 2 vy 2 1 2 3 1 qy 3 1 2 3 2 q 2 vy 3 1 2 1 3 v 2 y 3 1 1 2 3 qv 2 y 3 1 2 2 3 q 2 v 2 y 3 1 2 3 3 q 3 v 2 y 3 1 2 3 4 q 3 v 3 y 4
1; 1) = ∑ k≥0 x k y k ∏ k j=1 (1-jx) .
On the other hand, Theorem 2.1 for q = 1 gives

P(x, y, 1; v) = xy - x 1 -v P(x, yv, 1; 1) + x 1 -v P(x, y, 1; 1) + 1.
Hence, the generating function for the number of set partitions of [n] with exactly k blocks according to which block the element n appears in is given by

P(x, y, 1; v) = 1 + ∑ k≥1 x k y k-1 (1 + v + • • • + v k-2 + v k-1 y) ∏ k-1 j=0 (1 -jx)
.

Theorem 2.1 with q = 0, we have

P(x, y, 0; v) = xv 1 -v P(x, y, 0; 0) + xy - x 1 -v P(x, yv, 0; 0) + xP(x, y, 0; 1) + 1,
which implies that P(x, y, 0; 0) = (xyx) + xP(x, y, 0; 1) + 1. Thus,

P(x, y, 0; v) = xv + 1 -v 1 -v P(x, y, 0; 0) + xy - x 1 -v P(x, yv, 0; 0) + x -xy. ( 7
)
Lemma 2.2. The generating function f k (x) for the number of words over alphabet [k] of length n with no squares of size 2 is given by 1+(k-1)x 1-x-(k-1)x 2 . Moreover, the generating function for the number of words aπ over alphabet [k] of length n with no squares of size 2 is given by

x 1-x-(k-1)x 2 .
Proof. Let f k (x|a) be the generating function for the number of words aπ over alphabet [k] of length n with no squares of size 2. Each word aπ with a ≥ 2 and π is not empty word, we have the first letter of π is 1, otherwise aπ has a square of size 2. Thus,

f k (x|a) = x + x 2 f k (x), for all a = 2, 3, . . . , k. Note that f k (x|1) = x f k (x). Therefore, by the fact that f k (x) = 1 + ∑ k a=1 f k (x|a), we obtain f k (x) = 1 + (k -1)x 1 -x -(k -1)x 2 . Moreover, f k (x|a) = x 1-x-(k-1)
x 2 , which completes the proof.

Each set partition π1 with exactly k blocks with no squares of size 2 can be written as

π (1) 12π (2) 13π (3) • • • 1kπ (k) 1,
where π ( j) is a word over alphabet [ j] such that jπ ( j) has no squares of size 2. Hence, by Lemma 2.2, we have

P(x, y, 0; 0) = 1 + ∑ k≥1 xy k 1 -x k ∏ i=2 x 2 1 -x -(i -1)x 2 = 1 + ∑ k≥1 x 2k-1 y k ∏ k-1 i=0 (1 -x -ix 2 )
.

Hence, by (7), we obtain

P(x, y, 0; v) = 1 + ∑ k≥1 x 2k-1 y k ∏ k-1 i=0 (1 -x -ix 2 ) + ∑ k≥1 x 2k y k (v + v 2 + • • • + v k-1 ) ∏ k-1 i=0 (1 -x -ix 2 ) + xy ∑ k≥1 x 2k-1 v k y k ∏ k-1 i=0 (1 -x -ix 2 )
, which implies the following result.

Theorem 2.3. We have P(x, y, 0; 1)

= 1 + ∑ k≥1 x 2k-1 y k (1 + (k -1)x + xy) ∏ k-1 i=0 (1 -x -ix 2 )
.

Although we did not succeed to solve the functional equation in Theorem 2.1, we have come with a new technique to study the generating function P(x, y, q; 1). In order to do that, we define the following notation. Let W k (x) be the generating function for the words over alphabet [k] of length n according to the number of squares of size 2. Theorem 2.4. Fix 1 ≤ a ≤ k. Let W k (x|a) be the generating function for the words aπ over alphabet [k] of length n according to the number of squares of size 2. Then

W k (x) = 1 + ∑ k i=1 x i ∑ k-1≥ j 1 > j 2 >•••> j i ≥0 (1 -q j i ) ∏ i m=2 (q j m -q j m-1 ) 1 -∑ k i=1 x i ∑ k-1≥ j 1 > j 2 >•••> j i ≥0 q j i ∏ i m=2 (q j m -q j m-1 )
.

Moreover, W k (x|a) = M a (x; q)W k (x) + L a (x; q), where

M a (x; q) = a ∑ i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 q j i i ∏ m=2 (q j m -q j m-1 ), L a (x; q) = a ∑ i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 (1 -q j i ) i ∏ m=2
(q j mq j m-1 ).

Proof. By the definitions

W k (x|a) = x + x a-1 ∑ j=1 q j-1 W k (x| j) + xq a-1 k ∑ j=a W k (x| j), which, by W k (x) = 1 + ∑ k a=1 W k (x|a), is equivalent to W k (x|a) = x(1 -q a-1 ) + xq a-1 W k (x) + x a-1 ∑ j=1 (q j-1 -q a-1 )W k (x| j).
Assume that W k (x|a) = M a (x; q)W k (x) + L a (x; q). Then M a (x; q) = xq a-1 + x a-1 ∑ j=1 (q j-1q a-1 )M j (x; q). and L a (x; q) = x(1q a-1 ) + x a-1 ∑ j=1 (q j-1q a-1 )L j (x; q). By induction on a, we have

M a (x; q) = a ∑ i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 q j i i ∏ m=2 (q j m -q j m-1 ), L a (x; q) = a ∑ i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 (1 -q j i ) i ∏ m=2
(q j mq j m-1 ).

Thus,

a ∑ j=1 M j (x; q) = a ∑ i=1 x i ∑ a-1≥ j 1 > j 2 >•••> j i ≥0 q j i i ∏ m=2 (q j m -q j m-1 ), a ∑ j=1 L j (x; q) = a ∑ i=1 x i ∑ a-1≥ j 1 > j 2 >•••> j i ≥0 (1 -q j i ) i ∏ m=2
(q j mq j m-1 ).

Hence, the generating function W k (x) is given by

W k (x) = 1 + ∑ k j=1 L j (x; q) 1 -∑ k j=1 M j (x; q)
, and the generating function W k (x|a) is given by W k (x|a) = M a (x; q)W k (x) + L a (x; q), as required.

Example 2.5. Theorem 2.

4 for k = 1, 2, 3 gives W 1 (x) = 1 1-x , W 2 (x) = 1+(1-q)x 1-(1+q)x-(1-q)x 2 and W 3 (x) = 1+x(2-q-q 2 )+x 2 q(1-q) 2 1-x(1+q+q 2 )-x 2 (2-q-q 3 )-x 3 q(1-q) 2 .
In the next result, we study a particular case, namely, the generating function W * k (x) for the number of words π over alphabet [k] of length n according to the number of squares of size 2 in π(k + 1). More generally, Let W * k (x|a) be the generating function for the number of words aπ over alphabet [k] of length n according to the number of squares of size 2 in aπ(k + 1).

Theorem 2.6. We have

W * k (x) = 1 1 -∑ k i=1 x i ∑ k-1≥ j 1 > j 2 >•••> j i ≥0 q j i ∏ i m=2 (q j m -q j m-1 )
.

Moreover, for all a = 1, 2, . . . , k,

W * k (x|a) = ∑ a i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 q j i ∏ i m=2 (q j m -q j m-1 ) 1 -∑ k i=1 x i ∑ k-1≥ j 1 > j 2 >•••> j i ≥0 q j i ∏ i m=2 (q j m -q j m-1 )
.

Proof. By the definitions

W * k (x|a) = xq a-1 + x a-1 ∑ j=1 q j-1 W * k (x| j) + xq a-1 k ∑ j=a W * k (x| j).
As usual by

W * k (x) = 1 + ∑ k a=1 W * k (x|a). Hence W * k (x|a) = xq a-1 W * k (x) + x a-1 ∑ j=1 (q j-1 -q a-1 )W * k (x| j).
Thus, by induction on a, we obtain

W * k (x|a) = W * k (x) a ∑ i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 q j i i ∏ m=2 (q j m -q j m-1 ). Hence, by W * k (x) = 1 + ∑ k a=1 W * k (x|a), we have W * k (x) = 1 1 -∑ k i=1 x i ∑ k-1≥ j 1 > j 2 >•••> j i ≥0 q j i ∏ i m=2 (q j m -q j m-1 )
, as required.

Theorem 2.7. The generating function P(x, y, q, 1) for the number of set partitions of [n] with exactly k blocks according to the number of squares of size 2 is given by P(x, y, q, 1)

= 1 + ∑ k≥1 y k M k (x; q) 1 + ∑ k i=1 L i (x; q) 1 -∑ k i=1 M i (x; q) + L k (x; q) k-1 ∏ ℓ=1 M ℓ (x; q) 1 -∑ ℓ i=1 M ℓ (x; q)
, where

M a (x; q) = a ∑ i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 q j i i ∏ m=2 (q j m -q j m-1 ), L a (x; q) = a ∑ i=1 x i ∑ a-1= j 1 > j 2 >•••> j i ≥0 (1 -q j i ) i ∏ m=2
(q j mq j m-1 ).

Proof. Fix k. Note that each set partition with exactly k blocks can be presented as 1π (1) 2π (2) • • • kπ (k) , where π ( j) is a word over alphabet [ j]. By using Theorem 2.4 and Theorem 2.6, we obtain that the generating function for the number of set partitions of [n] with exactly k blocks according to the number of squares of size 2 is given by

W * 1 (x|1)W * 2 (x|2) • • •W * k-1 (x|k -1)W k (x|k),
as claimed.

Example 2.8. Let us consider Theorem 2.7 when q = 1. For q = 1, M a (x) | q=1 = x and L a (x) | q=1 = 0. Thus, P(x, y, 1, 1)

= 1 + ∑ k≥1 xy k 1 -kx k-1 ∏ ℓ=1 x 1 -ℓx = ∑ k≥0 x k y k (1 -x)(1 -2x) • • •(1 -kx) ,
as is well known.

Example 2.9. Here, we focus on the case q = 0, namely, set partitions with no squares of size 2. Theorem 2.7 with q = 0 gives that M 1 (x) | q=0 = x, L 1 (x) = 0, and M a (x) | q=0 = xL a (x) | q=0 = x 2 for a = 2, 3, . . . , k, i.e., L a (x)| q=0 = x. Hence, P(x, y, 0, 1)

= 1 + xy 1 -x + ∑ k≥2 y k x 2k ∏ k ℓ=1 (1 -x -(ℓ -1)x 2 )
.

Average

According to the definitions in Theorem 2.7, we have

M a (x; 1) = x, L a (x; 1) = 0, d dq M a (x; q)| q=1 = (a -1)x - a 2 x 2 , d dq L a (x)| q=1 = -(a -1)x.
Thus, by Theorem 2.7, we obtain Corollary 3.1. The generating function d dq P(x, y, q, 1)| q=1 for the total number of squares of size 2 in all set partitions of [n] with exactly k blocks is given by d dq P(x, y, q, 1)

q=1 = 1 6 ∑ k≥1 y k k ∏ ℓ=1 x 1 -ℓx k(k -1)(3 -x -kx)x 1 -kx + k-1 ∑ ℓ=1 (ℓ -1)(6 -6ℓx -ℓ(1 -2ℓ)x 2 ) 1 -ℓx .
In order to study the generating function d dq P(x, y, q, 1)| q=1 , we will find an exponential generating function E(x, y) for the total number of squares of size 2 in all set partitions of [n] with exactly k blocks. This can be done by extending the coefficient of x n in d dq P(x, y, q, 1)| q=1 and then replacing x n by x n /n!. At first, we write d dq P(x, y, q, 1)

q=1 = 1 6 ∑ k≥1 y k k ∏ ℓ=1 x 1 -ℓx - 2k x + 2k 2 -7k + 6 - x 6 (4k 3 -21k 2 + 17k) + k ∑ ℓ=1 2/x 1 -ℓx + k ∑ ℓ=1 x -3 1 -ℓx .
The ordinary and exponential generating functions for the number of set partitions of [n] with k blocks are given by ∑ k≥1 y k ∏ k ℓ=1 x 1-ℓx and e y(e x -1) -1 respectively. We obtain that the exponential generating function that corresponding to the ordinary generating function By collecting all theses terms together, we obtain that E(x, y) = e y(e x -1) -1 -ye y(e x -1) 3 1 + y + 7 2 (e x -1) + y 6 e x+y(e x -1) (2x + 2xye x ) -y 9

x 0 (e t -1)e y(e t -1) (y(e t -1) + (1 + y(e t -1)) 2 )dt + 7y 12

x 0 (e t -1)e y(e t -1) (1 + y(e t -1))dt -17y 36

x 0 ((e t -1)e y(e t -1) dt + y 6

x 0 te t e y(e t -1) dt.

At y = 1, we have that

  in canonical representation are respectively 111, 112, 121, 122 and 123. We denote the set of all partitions of [n] by P ([n]), and the number of all set partitions of [n] by B n = |P ([n])|, with B 0 = 1 for the empty set. The B n are known as the Bell numbers. Their sequence starts with 1, 1, 2, 5, 15, 52, 203, 877, • • • for

Fig. 2 :

 2 Fig. 2: Two by two squares in the 15 set partitions with 4 parts

  Note that F(x) = ∑ n≥0 a n x n = ∑ k x n = ∑ k≥1 y k ∑ n≥k nS n,k x n-1 ,where S n,k is the Stirling number of the second kind. Therefore, the corresponding exponential generating function is given by ∑

- 1 .

 1 Let B(x) = e e x -1 = ∑ n≥0 B n x n n! be the exponential generating function for the number of set partitions of [n].

This material is based upon work supported by the National Research Foundation under grant numbers 89147 This material is based upon work supported by the National Research Foundation under grant numbers 86329 This material is based upon work supported by the National Research Foundation under grant numbers 81021

Hence, the coefficient of x n n! in d dx E(x, 1) is given by Kasraoui [START_REF] Kasraoui | Average values of some z-parameters in a random set partition[END_REF] showed

) . Hence, asymptotically, the mean of the number of squares of size 2 over all set partitions of [n] is given by n 2 3 log n .