Set Partitions and Other Bell Number Enumerated Objects

Fufa Beyene

Department of Mathematics, Addis Ababa University 1176 Addis Ababa, Ethiopia

           fufa.beyene@aau.edu.et

Jörgen Backelin

Department of Mathematics, Stockholm University

SE-106 91 Stockholm, Sweden

               joeb@math.su.se

Roberto Mantaci IRIF, Université de Paris 8 Place Aurélie Nemours F-75013 Paris, France

               mantaci@irif.fr

Samuel A. Fufa

Department of Mathematics, Addis Ababa University 1176 Addis Ababa, Ethiopia

           samuel.asefa@aau.edu.et

Abstract

In this paper, we study classes of subexcedant functions enumerated by the Bell numbers and present bijections on set partitions. We present a set of permutations whose transposition arrays are the restricted growth functions, thus defining Bell permutations of the second kind. We describe a bijection between Bell permutations of the first (introduced by Poneti and Vajnovzski) and the second kinds. We present two other Bell number enumerated classes of subexcedant functions. Further, we give bijections on set partitions, in particular, an involution that interchanges the sets of merging blocks and successions. We use the bijections to enumerate the distribution of these statistics over set partitions and give some structural and enumeration results.

1 Introduction

Let n be a fixed positive integer and let [n] := {1, 2, …, n}. A set partition of [n] is a collection of pairwise disjoint non-empty subsets of [n] such that their union forms the whole set [n].

For any set S, the function σ : [n] ⟶ S corresponds to the word σ(1)σ(2) ⋯ σ(n). In particular, a permutation is a word with distinct symbols.

Permutations and set partitions are among the classical objects in enumerative combinatorics. A fundamental reason for this truth is the wide variety of ways to represent a permutation and a set partition combinatorially. A second reason for their richness is the wide variety of interesting statistics. The Eulerian statistic is among the most classical statistics on permutations. The permutation statistics: descents, weak excedances, anti-excedances, and right-to-left minima (maxima) are examples of the Eulerian statistics. On the other hand, we recall the two most basic enumerations for set partitions: the total number of set partitions over [n] and the number of set partitions over [n] having k blocks are the Bell number, B(n) and the Stirling number of the second kind, S(n, k), respectively [?, ?, ?, ?].

Both permutations and set partitions can be coded by subexcedant functions, i.e., functions f : [n] ↦ [n] such that 1 ≤ f(i) ≤ i, ∀i ∈ [n] (in some contexts it is rather required that 0 ≤ f(i) ≤ i − 1).

Some permutation codes with subexcedant functions are very well known (Lehmer code or inversion table, Denert code, and so on) [?, ?, ?, ?]. On the other hand, a way to represent set partitions with subexcedant functions is given by Mansour’s definition of canonical form for a set partition P in the standard form, the elements in each block are arranged increasingly, and the blocks are arranged in increasing order of their minima [?]. In the canonical form, any integer i ∈ [n] is coded with the index of the block of P where it belongs, where P is in its standard form. The canonical forms of set partitions are restricted growth functions (RGF).

Several properties of permutations can easily be read from their corresponding codes, which allows one to prove some results elegantly by reasoning on the codes rather than the coded objects. See, for instance, the article of Baril and Vajnovszki [?] and the article of Foata and Zeilberger [?].

Mantaci and Rakotondrajao [?] studied the bijection ϕ associating a subexcedant function f with the permutation σ = ϕ(f) = (n, f_{n})(n − 1, f_{n−1}) ⋯ (1, f_{1}), where f_{i} = f(i), ∀i ∈ [n] and related the image values of f to the anti-excedances of σ. Later, Baril [?] independently studied a variation of the bijection ϕ, here denoted by χ, given by simply inverting the order of the product of transpositions in the definition of ϕ, and he called the subexcedant function associated with a permutation via this bijection the transposition array. Baril [?] also studied, in particular, the positions of weak excedances in a permutation using the corresponding subexcedant function.

Mansour and Munagi [?] studied set partitions according to the number of circular successions, i.e., the number of consecutive element pairs inside a block, assuming the elements arranged around a circle. Mansour and Shattuck [?] studied parity successions, pairs of adjacent elements a and b within some block such that a ≡ b (mod 2), in set partitions. Callan [?] proved that the number of singletons in all set partitions is equal to the number of circular successions by giving a bijection in terms of an algorithm that interchanges singletons and circular successions. Callan also proved that his bijection is an involution on set partitions and that it preserves the non-crossing partitions.

In this paper we study families of subexcedant functions enumerated by the Bell numbers. We present bijections between these classes and the set partitions. We enumerate these classes according to the distribution of some statistics. We also give an involution on set partitions and present some structural and enumeration results.

In Section 3, we study a class of permutations whose transposition arrays are the restricted growth functions. We will call this a class of Bell permutations of the second kind. We prove that the statistic of weak excedances is the Stirling number of the second kind. We enumerate such permutations according to the number of cycles and consider the joint distribution of these statistics. In Subsection ??, we describe a bijection between Bell permutations of the second kind and another Bell-counted class of permutations introduced by Poneti and Vajnovszki [?].

Section ?? presents two more families of subexcedant functions enumerated by the Bell numbers and bijections between these classes and set partitions.

Finally, in Section ??, we present bijections on set partitions. In particular, we give an involution that interchanges merging blocks and successions of a set partition. We use the bijections to present some structural and enumeration results. Also, we give the generating function for the joint distribution of these statistics.

2 Notation and preliminaries

2.1 Permutations

Recall that a permutation over [n] is a bijection σ : [n] ↦ [n]. Let 𝔖_{n} denote the set of all permutations over [n]. We write a permutation σ ∈ 𝔖_{n} as a word σ = σ(1)σ(2) ⋯ σ(n) (whence the σ(i) also are called letters), or in cycle notation as a product of disjoint cycles, where as usual a cycle in σ can be written as (j, σ(j), σ^{2}(j), …, σ^{t−1}(j)), where t, the length of the cycle, is the smallest positive integer such that σ^{t}(j) = j. Cycles of length one are fixed points. The cycle notation is σ = C_{1}C_{2} ⋯ C_{k}, where the C_{i}’s are disjoint cycles and the minima of the cycles form an increasing sequence. We let cyc(σ) denote the number of cycles of σ. A transposition is a permutation that swaps two integers and fixes all the others.

We say that a permutation σ over [n] has an excedance (resp., weak excedance, antiexcedance) in a position i if σ(i) > i (resp., σ(i) ≥ i, σ(i) ≤ i), where i ∈ [n]. We use the notation

Exc(σ) := {i : 1 ≤ i ≤ n, σ(i) > i},
Wex(σ) := {i : 1 ≤ i ≤ n, σ(i) ≥ i}, and
Ax(σ) := {i : 1 ≤ i ≤ n, σ(i) ≤ i}.

We also use the notation exc(σ) := | Exc(σ)|, wex(σ) := | Wex(σ)|, and ax(σ) := | Ax(σ)|.

The set of excedance letters, weak excedance letters, and anti-excedance letters of σ are defined as

ExcL(σ) := {σ(i) : i ∈ Exc(σ)},
WexL(σ) := {σ(i) : i ∈ Wex(σ)}, and
AxL(σ) := {σ(i) : i ∈ Ax(σ)}.

2.2 Subexcedant functions

A subexcedant function is a function f : [n] ↦ [n] such that 1 ≤ f(i) ≤ i, ∀i ∈ [n].

We let SF(n) denote the set of all subexcedant functions over [n]. For f = f_{1}f_{2} ⋯ f_{n} ∈ SF(n), we let Im(f) := f([n]), the image set of f, and im(f) := | Im(f)|. We say that f has a leftmost (rightmost) occurrence in a position i if f_{i} ∉ {f_{1}, …, f_{i−1}}, i.e., i = min(f^{−1}(f_{i})) (or f_{i} ∉ {f_{i+1}, …, f_{n}}, i.e., i = max(f^{−1}(f_{i})), respectively), where i ∈ [n]. If i is a leftmost (rightmost) occurrence in f, then we say that f_{i} is a leftmost (or rightmost) letter. The set of fixed points of f is given by

Fx(f) := {i : 1 ≤ i ≤ n, f_{i} = i}.

We let fx(f) := | Fx(f)|.

2.3 Set partitions

A set partition P of [n] is a collection B_{1}, …, B_{k} of nonempty disjoint subsets of [n] such that ⋃_{i=1}^{k} B_{i} = [n]. The subsets B_{i} will be referred to as blocks. The block representation P = B_{1}|B_{2}| ⋯ |B_{k} of a set partition P is said to be standard if the blocks B_{1}, …, B_{k} are sorted in such a way that min(B_{1}) < min(B_{2}) < ⋯ < min(B_{k}).

We consider set partitions only in their standard representation.

We let SP(n) denote the set of all set partitions over [n]. We also let bl(P) denote the number of blocks of a set partition P and SP(n, k) := {P ∈ SP(n) : bl(P) = k}.

Recall that | SP(n, k)| = S(n, k), where S(n, k) is the Stirling number of the second kind. For 2 ≤ i ≤ k, we say that block B_{i} is merging if max(B_{i−1}) < min(B_{i}). A set partition

without merging blocks is called merging-free.

If the integers (a − 1, a) are in the same block of P, then a is said to be a succession of P. In literature, “succession” is the first element of the pair, but we prefer to use it for the second element.

We let Mb(P), Suc(P), and Nmb(P) denote the set of the minimum elements of merging blocks of P, the set of successions of P, and the set of the minima of non-merging blocks of P, respectively. We use the notation mb(P) := | Mb(P)|, suc(P) := | Suc(P)|, and nmb(P) := | Nmb(P)|.

Remark 1. For any P ∈ SP(n), every element i of [n] is necessarily in one of the first i blocks of P.

The canonical form of a set partition P = B_{1}|B_{2}| ⋯ |B_{k} is an n-tuple f = f_{1}f_{2} ⋯ f_{n} indicating for each integer j the index of the block in which it occurs, i.e., B_{j} = f^{−1}(j), ∀j ∈ [k]. For instance, the canonical form of P = 1 5 7|2 4|3 8|6 ∈ SP(8) is f = 12321413.

Remark 2. The block B_{i} contains its index i if and only if i ∈ Fx(f).

Note that the canonical form of a set partition is a subexcedant function, but not all subexcedant functions are canonical forms of set partitions.

A restricted growth function (RGF) over [n] is a function f : [n] ↦ [n], where f = f_{1} ⋯ f_{n} such that f_{1} = 1 and f_{i} ≤ 1 + max{f_{1}, …, f_{i−1}} for 2 ≤ i ≤ n, or equivalently, such that the set {f_{1}, f_{2}, …, f_{i}} is an integer interval ∀i ∈ [n]. The canonical forms of set partitions are exactly the restricted growth functions (RGF) [?, p. 2]. We let RGF(n) denote the set of all restricted growth functions over [n].

3 Bell permutations of the second kind

In this section, we study the class of permutations associated with RGFs under χ, the bijection given by Baril [?]. Since this is a Bell enumerated set, we will call these objects “Bell permutations of the second kind” (Poneti and Vajnovszki [?] already introduced another Bell enumerated family of permutations that they called “Bell permutations”).

The bijection χ is given by χ : SF(n) ↦ 𝔖_{n}, where the permutation σ = χ(f) is defined by the product of transpositions:

σ = (1, f_{1})(2, f_{2}) ⋯ (n, f_{n}),

where the product is taken from right to left. The subexcedant function f = χ^{−1}(σ) is called the transposition array of σ. It is shown in [?] that Im(f) = Wex(σ). For instance, take f = 121132342 ∈ SF(9). Then

σ = χ(f) = (1, 1)(2, 2)(3, 1)(4, 1)(5, 3)(6, 2)(7, 3)(8, 4)(9, 2)
= 497812536,

and Im(f) = {1, 2, 3, 4} = Wex(σ).

Remark 3. [?] The rightmost occurrences of f are the weak excedance letters of χ(f).

Remark 4. Let f = f_{1}f_{2} ⋯ f_{n} and σ = χ(f). We have i ∈ Fx(f) if and only if i is the minimum element of some cycle of σ.

Beyene and Mantaci [?] essentially proved the following:

Lemma 5. Let σ = σ(1)σ(2) ⋯ σ(n) ∈ 𝔖_{n}. If f = χ^{−1}(σ) = f_{1}f_{2} ⋯ f_{n}, then f(i) = σ^{−t}(i) ≤ i, where t ≥ 1 is chosen as small as possible.

The following proposition presents an alternative algorithm to compute σ from f as a product of disjoint cycles.

Proposition 6. If f ∈ SF(n), then σ = χ(f) can be constructed as follows. For i = 1, 2, …, n:

• if f_{i} = i, then add a new singleton cycle: (i),

• if f_{i} < i, then insert i after f_{i} in its cycle.

Example 7. Take f = 1132532 ∈ SF(7). Then σ = χ(f) can be obtained as follows:

(1) (1, 2) (1, 2)(3) (1, 2, 4)(3) (1, 2, 4)(3)(5) (1, 2, 4)(3, 6)(5) (1, 2, 7, 4)(3, 6)(5) = σ.

The following lemma can easily be deduced from the above proposition and the definition of χ.

Lemma 8. Let f ∈ SF(n) and σ = χ(f) = C_{1}C_{2} ⋯ C_{ℓ}. If ∅ ≠ S ⊆ [n], then the following statements are equivalent.

1. f has the property

\begin{cases}f_{i} = min(S), & if i ∈ S; \\ f_{i} ∉ S, & otherwise. \end{cases}

2. The elements of S form some cycle C_{i} in σ, and the cycle can be written with its elements forming a decreasing sequence.

3. S is the underlying set of some cycle C_{i} with just one weak excedance.

Consider the bijection τ : SP(n) ↦ RGF(n) given by τ(P) = f, where f is the canonical form of P.

Definition 9. A Bell permutation of the second kind over [n] is a permutation σ obtained from f ∈ RGF(n) by applying χ to f, i.e., σ = χ(f).

Let BP_{2}(n) := χ(RGF(n)), the set of all Bell permutations of the second kind over [n], and BP_{2}(n, k) := {σ ∈ BP_{2}(n) : wex(σ) = k}.

The restriction of χ to RGF(n) is a bijection between RGF(n) and BP_{2}(n). Therefore, BP_{2}(n) is a Bell number enumerated set, i.e., | BP_{2}(n)| = B(n), the nth Bell number.

Since the composition of bijections is a bijection, the map λ = χ∘τ is a bijection between SP(n) and BP_{2}(n).

Proposition 10. Let P = B_{1}|B_{2}| ⋯ |B_{k} be a set partition, σ the permutation λ(P), and C_{1}C_{2} ⋯ C_{ℓ} the cycle decomposition in σ. Then

1. σ has k weak excedances,

2. the set of the weak excedances of σ is exactly the interval [k] = {1, 2, …, k}, and

3. the set of the minimal elements of the cycles of σ is exactly the interval [ℓ].

Proof. The first two items directly follow from Remark 3 and the fact that the number of blocks of P and the cardinality of the image set of its canonical form are equal.

Item 3. By Remark 4, any integer i ∈ [n] is fixed in f if and only if i = min(C_{j}) for some j. We show that if p is the maximum fixed point in f, then any q < p also is fixed. Suppose that there exist a non-fixed point smaller than p. Let t be the maximal of such non-fixed points, i.e., the elements of the interval [t + 1, p] are all fixed. So f_{t} < t and t ∉ {f_{1}, f_{2}, …, f_{t+1} = t + 1}. Thus f ∉ RGF(n), and this is a contradiction. Therefore, the set of fixed points of f is [p] and hence p = ℓ.

The above proposition implies that the distribution of the number of weak excedances on BP_{2}(n) is the same as the distribution of the number of blocks on SP(n) and also that the statistic of the number of cycles on BP_{2}(n) has the same distribution as the number of fixed points on RGF(n). Thus, we have the following.

Corollary 11.

1. | BP_{2}(n, k)| = S(n, k), the Stirling number of the second kind.

2. The number of set partitions having ℓ blocks containing their index element is the same as the number of Bell permutations of the second kind having ℓ cycles.

We consider the following lemma.

Lemma 12. Let f′ ∈ SF(n − 1), and let f ∈ SF(n) be obtained by concatenating some j ∈ [n] at the end of f′. Let σ′ = χ(f′) and σ = χ(f). If j ≠ n, then σ is obtained from σ′ by replacing the integer σ′(j) with n in σ′ and appending σ′(j) at the end. If j = n, then σ is obtained by simply appending n at the end of σ′.

The following lemma gives a recursive procedure to check if a permutation is a Bell Permutation of the second kind.

Lemma 13. A permutation σ = σ(1)σ(2) ⋯ σ(n) ∈ 𝔖_{n} whose set of weak excedances is an integer interval [k] is in BP_{2}(n) if and only if the permutation σ′ ∈ 𝔖_{n−1} obtained from σ by replacing the integer n with σ(n) in σ|_{[n−1]} is in BP_{2}(n − 1).

Proof. According to Lemma 12, for all permutations σ, if f = f_{1} ⋯ f_{n} = χ^{−1}(σ) and σ′ ∈ 𝔖_{n−1} is the permutation obtained from σ by replacing the integer n by σ(n), then the transposition array associated with σ′ is f′ = f_{1}f_{2} ⋯ f_{n−1}. Under the hypothesis that Wex(σ) = Im(f) is an integer interval [k], the following two conditions are trivially equivalent:

1. for 1 ≤ i ≤ n, the set {f_{1}, f_{2}, …, f_{i}} is an integer interval with minimum value 1.

2. for 1 ≤ i ≤ n − 1, the set {f_{1}, f_{2}, …, f_{i}} is an integer interval with minimum value 1.

That is, σ is Bell if and only if σ′ is Bell.

For instance, let σ = 7245613. We have Wex(σ) = [5], so σ may be a Bell permutation of the second kind. We apply Lemma 13: 7245613 → 324561 → 32451 → 3241 → 321. Since 321 ∈ BP_{2}(3), we can conclude that σ and those permutations obtained in the process are Bell permutations of the second kind. But 32541 ∉ BP_{2}(5), because 32541 → 3214 and 3214 ∉ BP_{2}(4).

We give new proof of the fact that | BP_{2}(n, k)| = S(n, k) by showing that the numbers | BP_{2}(n, k)| satisfy the recurrence relation of the Stirling number of the second kind.

Proposition 14. For all positive integers n, k, n ≥ 1, 1 ≤ k ≤ n, the number | BP_{2}(n, k)| satisfies the recurrence relation

| BP_{2}(n, k)| = k| BP_{2}(n − 1, k)| + | BP_{2}(n − 1, k − 1)|, | BP_{2}(0, 0)| = 1.  (1)

Proof. We use Lemma 13 to prove the assertion. Any Bell permutation of the second kind σ ∈ BP_{2}(n, k) can be uniquely obtained either from a permutation σ′ ∈ BP_{2}(n − 1, k) and an integer i ∈ [k] or from a permutation σ′ ∈ BP_{2}(n − 1, k − 1). More precisely: if σ′ ∈ BP_{2}(n − 1, k) and i ∈ [k], then σ is obtained from σ′ by replacing σ′(i) with n and then appending σ′(i) at the end, i.e., σ = σ′(i, n). In this case, σ ∈ BP_{2}(n, k), and there are | BP_{2}(n − 1, k)| possible choices for σ′ and k possibilities for i. Hence this contributes k| BP_{2}(n − 1, k)| to | BP_{2}(n, k)|. If σ′ ∈ BP_{2}(n − 1, k − 1), then σ is obtained from σ′ by replacing σ′(k) by n and then appending σ′(k) at the end, i.e., σ = σ′(k, n). In this case, σ ∈ BP_{2}(n, k), and σ has | BP_{2}(n − 1, k − 1)| possibilities. By combining the two cases, we have (1).

Let P ∈ SP(n, k) and Mx(P) = {max(B_{i}) : 1 ≤ i ≤ k}. By the above proposition, Remark 3, and the fact that the maximum elements of the blocks of P are the rightmost occurrences in τ(P) we have the following corollaries.

Corollary 15. We have Mx(P) = WexL(σ), where σ = λ(P).

Corollary 16. The bistatistics (bl, fx) on the set partitions has the same distribution as (wex, cyc) on the Bell permutations of the second kind.

Remark 17. The cardinality of the set BP_{2}(n, n − 1) is equal to the number S(n, n − 1) of set partitions over [n] having n − 1 blocks, which, as is well known, is equal to \binom{n}{2}.

OEIS entry number \underline{A259691} presents the sequence of the numbers T (n − 1, ℓ), counting set partitions over [n] where exactly ℓ blocks contain their index element. These numbers satisfy the relation:

T (n − 1, ℓ) = ∑_{i=0}^{n−ℓ} \binom{n − ℓ}{i}ℓ^{i+1}B(n − ℓ − i),  (2)

where T (n−1, n) = 1. Thus, by Corollary 11, the number of Bell permutations of the second kind over [n] having exactly ℓ cycles is also equal to T (n − 1, ℓ).

We now refine (2) by adding a parameter counting the number of weak excedances of the permutation. Consider a permutation σ′ ∈ BP_{2}(n − 1, k), an integer i ∈ [k + 1] representing a weak excedance, and the permutation σ = σ′(i, n), the product of σ′ and the transposition (i, n). Then, by Proposition 6, the numbers of cycles of σ and σ′ are equal, except when i = k + 1 = n (i.e., both σ′ and σ are the identity permutations) and i = k + 1, in which case cyc(σ) = cyc(σ′) + 1. Thus, the number T (n − 1, k, ℓ) of Bell permutations of the second kind over [n] having exactly k weak excedances and ℓ cycles satisfies:

T (n − 1, k, ℓ) = \begin{cases}δ_{k,n}, & if ℓ = n; \\ ∑_{i=0}^{n−ℓ} \binom{n−ℓ}{i}ℓ^{i+1}S(n − ℓ − i, k − ℓ), & otherwise. \end{cases}  (3)

Here, δ_{∗,∗} is the Kronecker delta function. Therefore, we have the following.

Proposition 18. For n ≥ 1, we have

∑_{σ∈BP_{2}(n)} x^{wex(σ)}y^{cyc(σ)} = ∑_{k=1}^{n} ∑_{ℓ=1}^{k} T (n − 1, k, ℓ)x^{k}y^{ℓ}.  (4)

Corollary 19. The number of Bell permutations of the second kind over [n] having exactly 1 cycle equals B(n − 1), n ≥ 1.

Proof. Let ℓ = 1 in (3) and take the sum over all 1 ≤ k ≤ n.