Run Distribution Over Flattened Partitions

Olivia Nabawanda^{1} Department of Mathematics

Makerere University P. O. Box 7062 Kampala Uganda

 onabawanda@must.ac.ug

Fanja Rakotondrajao

Département de Mathématiques et Informatique

Université d’Antananarivo Antananarivo Madagascar

   frakoton@yahoo.fr

Alex Samuel Bamunoba Department of Mathematics

Makerere University P. O. Box 7062 Kampala Uganda

 bamunoba@cns.mak.ac.ug

Abstract

The study of flattened partitions is an active area of current research. In this paper, our study unexpectedly leads us to the OEIS sequence \underline{A124324}. We provide a new combinatorial interpretation of these numbers. A combinatorial bijection between flattened partitions over [n + 1] and the partitions of [n] is also given in a separate section. We introduce the numbers f_{n,k} which count the number of flattened partitions over [n] having k runs. We give recurrence relations defining them, as well as their exponential generating function in differential form. It should be appreciated if its closed form is established. We extend the results to flattened partitions where the first s integers belong to different runs. Combinatorial proofs are given.

1Corresponding author.

1 Introduction and preliminaries

The study of the different statistics of permutations such as descents, ascents, excedances and runs has a long history and has been an area of intensive research in the past years. A lot of work is available in the literature [6, 11, 14, 17, 18]. These statistics play an important role in combinatorics and mathematics as a whole.

For a given positive integer n, we denote the set {1, 2, …, n} by [n]. A permutation σ over [n] is represented as a word σ(1)σ(2) ⋯ σ(n). We say that σ has an ascent (descent) at position i if σ(i) < σ(i + 1) (σ(i) > σ(i + 1)), where i ∈ [n]. A run in a permutation σ is a subword σ(i)σ(i + 1) ⋯ σ(i + p)σ(i + p + 1) where i, i + 1, …, i + p are consecutive ascents. In this case, i − 1 (if it does exist) and i + p + 1 are non ascents, where i ∈ [n]. For example, in σ = 526134, we have ascents at positions 2, 4 and 5. It also has descents at positions 1 and 3. The last element 4 of σ at position 6 is neither an ascent nor a descent. A right to left minimum of a permutation σ is an element σ(i) such that σ(i) < σ(j) for all j > i. For example, in σ = 1246357, the right to left minima are {1, 2, 3, 5, 7}.

Counting permutations according to the number of runs has been studied from various perspectives in enumerative combinatorics. Canfield and Wilf [4] considered a run as a subsequence of a permutation σ, whose values either increase on the interval (run up) or decrease on the interval (run down). More related work on permutation runs can also be found in articles [2, 9, 10, 20]. A permutation π is said to be a flattened partition if it consists of runs arranged from left to right such that their first entries are in increasing order. It is clear that the first run always starts with 1, and so all flattened partitions start with the integer 1. For example, consider a permutation σ = 139278456. This is a flattened partition with three runs namely: 139, 278, 456 whose first entries 1, 2, 4 are in increasing order. However, the permutation σ = 139456287 is not a flattened partition since the first entries 1, 4, 2, 7, of the runs 139, 456, 28, 7 are not in increasing order. Given a non-empty finite subset S of positive integers, a set partition P of S is a collection of disjoint non-empty subsets B_{1}, B_{2}, …, B_{k} of S (called blocks) such that ∪_{i=1}^{k}B_{i} = S [12, 16]. We shall maintain the name and notion of “flattened partition” introduced by Callan [3]. Callan borrowed the notion “flatten” from Mathematica programming language, where it acts by taking lists of sets arranged in increasing order, removes their parentheses, and writes them as a single list [19]. Mansour et al. [13] also used the same notion. To generate flattened partitions, the elements of each block are written as increasing subsequences, and blocks arranged from left to right in increasing order of their first entries. Carlitz [5] also applied the notion “flatten” to permutations expressed in cycle notation.

We let F_{n} denote the set of all flattened partitions over [n], F_{n,k} the set consisting of all flattened partitions over [n] having k runs, f_{n,k} the cardinality of the set F_{n,k}. In Table 1, we give the first few values of the numbers f_{n,k}.

[figure: n; k] 1 2 3 4 5
1  1
2  1
3  1 1
4  1 4 0
5  1 11 3 0
6  1 26 25 0 0

Table 1: The numbers f_{n,k}

We notice that the terms in the column for k = 2 of Table 1 correspond to the Eulerian numbers. Foata and Schützenberger [7] gave the fundamental work on these numbers. Mantaci and Rakotondrajao [15] gave a new combinatorial interpretation to the same. Many other references concerning Eulerian numbers can be found on the OEIS \underline{A000295}. In Section 2, we establish different recurrence relations of the numbers f_{n,k} and give their combinatorial proofs. We also define the exponential generating function F (x, u) of the numbers f_{n,k} which is defined by

F (x, u) = ∑_{n≥0} ∑_{k≥0} f_{n,k}x^{k} \frac{u^{n}}{n!} = ∑_{n≥0} ∑_{σ∈F_{n}} x^{run(σ)} \frac{u^{n}}{n!} ,

where run(σ) is the number of runs in a flattened partition σ. In Section 3, we generalize the results in Section 2 to flattened partitions over [n] whose first s integers belong to different runs . We let f_{n,k}^{(s)} denote the number of flattened partitions over [n] whose first s integers belong to different runs, and F^{[s]}(x, u) the exponential generating function for the numbers f_{n,k}^{(s)}. The first few values of f_{n,k}^{(s)} for s = 2 and s = 3 are shown in Table 2 and 3:

Table 2: The numbers f_{n,k}^{(2)}
Table 3: The numbers f_{n,k}^{(3)}

[figure: n; k] 2 3 4 5

2  0 3  1 0 4  3 0 5  7 3 0 6  15 22 0 7  31 105 15 0

[figure: n; k] 3  4 5

4  0 5 2 0 6  12 0 7  50 12 0 8  180 140 0

Mansour et al. [13] gave a recursive formula for the number of flattened partitions over [n], and also mention that the number of distinct permutations that can be obtained as flattened partitions over [n] is the Bell number B_{n−1}. Let P_{n} denote the collection of partitions of [n]. Our study led us to the OEIS \underline{A124324} which counts the number of partitions of [n] having k blocks of size greater than 1.

The authors of the present paper were introduced to the OEIS \underline{A124324} by Heinz [8] who gave a maple program for computing the terms of this sequence recursively. The first maple program which computes this sequence using the exponential generating function was given by Emeric Deutsch. A combinatorial bijection between elements of P_{n} having (k − 1) blocks of size greater than 1 and F_{n+1,k} will be given in Section 4.

2 Flattened partitions and their behaviours on runs

2.1 Recurrence relations

We have f_{n,1} = 1 for all n ≥ 1 and f_{n,k} = 0 for all k ≥ n ≥ 2. It is not possible to have a flattened partition over [n] whose number of runs k is greater or equal to its length.

Theorem 1. For all integers n and k such that 2 ≤ k < n, the numbers f_{n,k} of flattened partitions over [n] with k runs satisfy the recurrence relation

f_{n,k} = ∑_{m=1}^{n−2} (\binom{n − 1}{m} − 1) f_{m,k−1}.  (1)

Proof. To construct a flattened partition π over [n] having k runs, we consider a flattened partition τ over [m] having k − 1 runs, for an integer m < n. Since all flattened partitions start with element 1, we insert the word of length n − m starting with 1, before a flattened partition τ to obtain 1 \underbrace{…}_{n−m−1} \underbrace{τ}_{m}, and then re-order the elements of τ making sure the

number of runs increase by one. The n−m−1 elements between 1 and τ can be chosen from the set \{2, 3, 4, …, n\} of (n − 1) terms in \binom{n − 1}{n−m−1} ways. In order to increase the number of runs by one, we avoid choosing the subset {2, 3, …, n − m − 1} of consecutive elements.

We thus have (\binom{n − 1}{n − m − 1} − 1) possible subsets to be inserted after 1. The minimum

number of elements in the first run is 2, implying that the maximum length of τ is n − 2. Since n ≥ 3, then the minimum length of τ is 1. Thus we have that 1 ≤ m ≤ n − 2. Thus summing up over 1 ≤ m ≤ n − 2 gives the recurrence relation in Equation (1).

Example 2. Let us construct flattened partitions over [6] having 3 runs from a flattened partition τ over [3] having 2 runs. We have τ = 132. The favorable subsets of two terms from the set {2, 3, 4, 5, 6} are: {2, 4}, {2, 5}, {2, 6}, {3, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {5, 6}. Consider the pair ({3, 4}, τ), we get π = 134265. For the pair ({4, 6}, τ), we get π = 146253.

Let a_{n} denote the maximum number of runs k in a flattened partition of [n]. From Table 1 above, we see that the maximum number of runs, a_{n} results into a sequence 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, …, for n ≥ 1.

Proposition 3. The maximal number a_{n} of runs in a flattened partition over [n] satisfies the relation

a_{n} = a_{n−2} + 1,

for all n ≥ 2, with initial conditions a_{0} = 0, a_{1} = 1.

Proof. Let n be an integer such that n ≥ 2. Consider a flattened partition τ over [n−2] having maximal number of runs. Using the construction in Theorem 1, inserting two elements 1x where x = {3, 4, …, n} before τ and re-ordering the elements of τ can only add a maximum of 1 run. Hence we have a_{n} ≥ a_{n−2} + 1. On the other hand, inserting n − 2 elements between 1 and the identity τ = 1 from the construction in the same theorem, we have 1 \underbrace{⋯}_{n−2} 1 and

then re-ordering the elements of τ. This means the subsets between 1 and τ can be chosen from the set {3, 4, …, n} of n − 2 elements whose maximum number of runs is a_{n−2}. Hence we have a_{n} ≤ a_{n−2} + 1. These two inequalities, together with a_{0} = 0 and a_{1} = 1, yield a_{n} = a_{n−2} + 1.

As an obvious conclusion, we have the following corollary:

Corollary 4. The maximal number of runs a_{n} in a flattened partition over [n] has the

closed form \frac{1}{4}(2n + (−1)^{n+1} + 1) and its generating function Y (x) = ∑_{n=0}^{∞} a_{n}x^{n} is given by

\frac{x}{(1 − x)^{2}(1 + x)}.

If a is a starting point of a run in a flattened partition π and x is an integer such that x < a, then π^{−1}(x) < π^{−1}(a). In other words, all integers smaller than a are on its left. By contradiction, suppose there exists an x < a on the right of a. Then x is an element of another run. This makes the starting points of the runs of π not to be in increasing order, which contradicts π being a flattened partition. Hence x should be on the left of a.

Let C_{n,k} denote the set of flattened partitions over [n] of the form 1X2 ⋯, having k runs, where X ∈ {3, 4, 5, …, n}. More precisely, each partition in C_{n,k} has only two elements in the first run. For example, we have C_{5,2} = {13245, 14235, 15234}.

From the construction in Theorem 1, we have the following corollary:

Corollary 5. For all integers n and k such that 1 ≤ k < n, the cardinality of the set C_{n,k} is (n − 2)f_{n−2,k−1}.

Let K_{n,k} denote the set of flattened partitions over [n] having k runs and containing either the subword 2n1 or the integer n at the end. In other words, deleting the integer n does not affect the number of runs. Let L_{n,k} denote the set of flattened partitions over [n] having k runs and containing the subword 1n2, the set where deleting the integer n reduces the number of runs by 1. For example, we have L_{5,2} = {12354, 12534, 15234} and K_{5,2} = {14523, 14235, 13524, 13452, 13425, 13245, 12453, 12435}.

Remark 6. The sets K_{n,k} and L_{n,k} are mutually exclusive, i.e., K_{n,k} ∩ L_{n,k} = ∅ and form a partition of the set F_{n,k}, i.e., F_{n,k} = K_{n,k} ∪ L_{n,k}.

For all integers n and k such that 1 ≤ k < n, the cardinalities of the sets C_{n,k} and L_{n,k} are equal. We use a variation of the bijection defined by Beyene and Mantaci [1, p. 5] to construct a combinatorial bijection between the two sets.

Let us consider the map f : C_{n,k} → L_{n,k} defined as follows: for each π ∈ C_{n,k}, delete the subword 1X and let τ be the standardized form of the remaining elements. Insert the subword n(X − 1) after the smallest rightmost element to (X − 1) in τ and reorder to get σ = f(π) ∈ L_{n,k}.

Example 7. Let us illustrate the map f with n = 5 and k = 2. We have C_{5,2} = {13245, 14235, 15234}. For π = 13245, then τ = 123 and σ = 15234 i.e., f(13245) = 15234. Similarly, f(14235) = 12534, f(15234) = 12354.

Proposition 8. The map f : C_{n,k} → L_{n,k} is a bijection.

Proof. We will prove that f is surjective and injective.

(i) Surjectivity. Let g : L_{n,k} → C_{n,k} be defined as follows: for each σ ∈ L_{n,k}, delete the subword nX and let τ be the standardized form of the remaining. Insert the subword 1(X + 1) before τ and re-order to get π ∈ C_{n,k}. It is obvious that g is the inverse map of f.

(ii) Injectivity. Let π_{1} and π_{2} be two elements in C_{n,k} such that f(π_{1}) = f(π_{2}). Necessarily, τ_{1} = τ_{2} and hence π_{1} = π_{2}.

Let us illustrate the map f^{−1} with n = 5 and k = 2.

We have L_{n,k} = {12354, 12534, 15234}. For σ = 12354, then τ = 123 and π = 15234 i.e., f^{−1}(12354) = 15234. Similarly, f^{−1}(12534) = 14235, f^{−1}(15234) = 13245.

Theorem 9. For all integers n and k such that 1 ≤ k < n, the cardinality of the set K_{n,k} is kf_{n−1,k}.

Proof. Let us construct the elements of K_{n,k}. Let π ∈ F_{n−1,k}. Inserting n at the end of a run of π does not change the number of runs. There are k possibilities of such insertions. This generates k flattened partitions in the set K_{n,k}. Thus |K_{n,k}| = kf_{n−1,k}.

Theorem 10. For all integers n and k such that 1 ≤ k < n, f_{n,k} = kf_{n−1,k} +(n−2)f_{n−2,k−1}.

Proof. From Remark 6, we have that |F_{n,k}| = |K_{n,k}| + |L_{n,k}|. Using Theorem 9, Proposition 8 and Corollary 5, we then have that

f_{n,k} = kf_{n−1,k} + (n − 2)f_{n−2,k−1}.  (2)

Corollary 11. For all integers n and k such that 1 ≤ k < n, we have

kf_{n,k} = ∑_{m=1}^{n−2} (\binom{n}{m} − 1)f_{m,k−1}.

Proof. Considering Equation (1) and Equation (2), we deduce the result.

We still do not have a direct combinatorial proof of Corollary 11, and it remains an open problem worth investigating. Theorem 12. For all integers n and k such that 1 ≤ k ≤ n, the numbers f_{n+2,k} of flattened partitions over [n + 2] having k runs satisfy the recurrence relation

f_{n+2,k} = f_{n+1,k} + ∑_{i=1}^{n} \binom{n}{i}f_{n+1−i,k−1}.  (3)

Proof. To construct a flattened partition π over [n + 2] for all n ≥ 0 having k runs, we use the property that the first two terms 1 and 2 of π are either in the same run or in different runs. We consider these two possibilities to enumerate f_{n+2,k}.

1. If 1 and 2 are in the same run, by the construction in Theorem 1, π is of the form π = 1 \underbrace{τ}_{n+1}, where τ is a subword of length n + 1 whose starting integer is 2. Deleting

1 of π and reducing each of the remaining terms by 1 gives a flattened partition of length n + 1, with the same number of runs k i.e., f_{n+1,k}.

2. If 1 and 2 are in different runs, suppose the first run has (i + 1) terms including the first term 1. Using Theorem 1, the remaining (i + 1) − 1 = i terms in the first run can be chosen from the set {3, 4, …, n + 2} of (n + 2) − 2 = n terms. This is because

the positions of 1 and 2 in π are already known. There are \binom{n}{i} ways to do this. The

remaining k −1 runs have length (n+2)−(i+1) = n+1−i. Hence we have f_{n+1−i,k−1} flattened partitions over [n + 1 − i] with k − 1 runs. Since the length of the first run including 1 varies between 2 and n + 1, the number of flattened partitions over [n + 2]

with 1 and 2 in different runs is given by ∑_{i=1}^{n} \binom{n}{i}f_{n+1−i,k−1}.

Adding these two cases together gives

f_{n+2,k} = f_{n+1,k} + ∑_{i=1}^{n} \binom{n}{i}f_{n+1−i,k−1}.

2.2 Generating function

Theorem 13. The exponential generating function F (x, u) of the run distribution over flattened partitions has the closed differential form

\frac{∂F (x, u)}{∂u} = x exp(x(exp(u) − 1) + u(1 − x)),  (4)

with initial condition \frac{∂F (x, 0)}{∂u} = x. Proof. We have

F (x, u) = ∑_{n≥1} ∑_{k≥1} f_{n,k}x^{k} \frac{u^{n}}{n!} = ∑_{n≥1} f_{n}(x)\frac{u^{n}}{n!} .

where f_{n}(x) is the polynomial defined by ∑_{k≥1} f_{n,k}x^{k} = f_{n}(x).

From Equation (3), multiplying by x^{k} \frac{u^{n}}{n!} and summing over k and n gives

∑_{n≥1} ∑_{k≥1} f_{n+2,k}x^{k} \frac{u^{n}}{n!} = ∑_{n≥1} ∑_{k≥1} (f_{n+1,k} + ∑_{i=1}^{n} \binom{n}{i}f_{n+1−i,k−1})x^{k} \frac{u^{n}}{n!} .  (5)

Equation (5) can be rewritten as A = B + C, where

A = ∑_{n≥1} ∑_{k≥1} f_{n+2,k}x^{k} \frac{u^{n}}{n!} ,

B = ∑_{n≥1} ∑_{k≥1} f_{n+1,k}x^{k} \frac{u^{n}}{n!} ,

and

C = ∑_{n≥1} ∑_{k≥1} ( ∑_{i=1}^{n} \binom{n}{i}f_{n+1−i,k−1}x^{k} \frac{u^{n}}{n!} ).

We have

A = \frac{∂^{2}F}{∂u^{2}} , B = \frac{∂F}{∂u} .  (6)

Fixing i and summing over k in C gives

C = ∑_{n≥1} ∑_{i=1}^{n} \binom{n}{i}( ∑_{k≥1} f_{n+1−i,k−1}x^{k})\frac{u^{n}}{n!} .  (7)

Equation (7) can be re-written as

C = x ∑_{n≥1} ∑_{i=1}^{n} \binom{n}{i}( ∑_{k≥1} f_{n+1−i,k−1}x^{k−1})\frac{u^{n}}{n!} .  (8)

Expanding the binomial coefficient \binom{n}{i} in Equation (8) and simplifying gives

C = x ∑_{n≥1} ∑_{i=1}^{n} \frac{u^{i}}{i!} ( ∑_{k≥1} f_{(n−i)+1,k−1}x^{k−1} \frac{u^{(n−i)}}{(n − i)!})

= x ∑_{i=1}^{∞} \frac{u^{i}}{i!} ( ∑_{n≥i} ∑_{k≥1} f_{(n−i)+1,k−1}x^{k−1} \frac{u^{(n−i)}}{(n − i)!})

= x ∑_{i=1}^{∞} \frac{u^{i}}{i!} ( ∑_{n≥i} f_{(n−i)+1}(x)\frac{u^{n−i}}{(n − i)!}).

We have

C = x ∑_{i=1}^{∞} \frac{u^{i}}{i!} \frac{∂F (x, u)}{∂u}

= x(exp(u) − 1)\frac{∂F (x, u)}{∂u}.

Substituting Equation (6) and C = x(exp(u) − 1)\frac{∂F (x, u)}{∂u} into Equation (5) gives

\frac{∂^{2}F (x, u)}{∂u^{2}} = \frac{∂F (x, u)}{∂u} + x(exp(u) − 1)\frac{∂F (x, u)}{∂u}.  (9)

Let V = \frac{∂F (x, u)}{∂u}. Then

\frac{∂V}{∂u} = \frac{∂^{2}F (x, u)}{∂u^{2}}.

Substituting V into Equation (9) gives

\frac{∂V}{∂u} = V (x(exp(u) − 1) + 1)  (10)

with initial condition V (x, 0) = x. Solving for V in Equation (10) gives

V = \frac{∂F (x, u)}{∂u} = x exp(−x) exp((x(exp(u) − u) + u)).

3 Flattened partitions with the first s terms in different runs

We recall that f_{n,k}^{(s)} and F^{[s]}(x, u) are the number of flattened partitions over [n] whose first s integers belong to different runs and the exponential generating function for the numbers f_{n,k}^{(s)} respectively.

Theorem 14. For all integers s, k and n such that 1 ≤ s < k < n, the numbers f_{n+s+1,k}^{(s+1)} satisfy the relation

f_{n+s+1,k}^{(s+1)} = ∑_{i_{1},i_{2},...,i_{s}≥1} \binom{n}{i_{1}}\binom{n − i_{1}}{i_{2}} ⋯ \binom{n − ∑_{j=1}^{s−1} i_{j}}{i_{s}}f_{n+1−∑_{j=1}^{s} i_{j},k−s}.  (11)

Proof. Let π be a flattened partition over [n + s + 1] having k runs. Let i_{1} + 1, i_{2} + 1, i_{3} + 1, …, i_{s} +1 be the lengths of the s first runs whose starting points are 1, 2, …, s respectively. Since the first run, including 1 has length i_{1} + 1, we have i_{1} terms to arrange out of the (n + s + 1) − s − 1 = n terms. There are \binom{n}{i_{1}} ways. For the second run, it remains to arrange

i_{2} terms out of n − i_{1} terms. There are \binom{n − i_{1}}{i_{2}} ways. Repeating the same process up to

the s^{th} run inductively gives \binom{n − i_{1} − i_{2} − ⋯ − i_{s−1}}{i_{s}} = \binom{n − ∑_{j=1}^{s−1} i_{j}}{i_{s}} possibilities. The

remaining k −s runs have length (n+s+1)−((i_{1} +1)+(i_{2} +1)+⋯ (i_{s} +1)) = n+1−∑_{j=1}^{s} i_{j}.

So we have \binom{n}{i_{1}}\binom{n − i_{1}}{i_{2}} ⋯ \binom{n − ∑_{j=1}^{s−1} i_{j}}{i_{s}}f_{n+1−∑_{j=1}^{s} i_{j},k−s}. Summing over all possibilities

of i_{1}, i_{2}, …, i_{s} ≥ 1 gives the result.

Theorem 15. The exponential generating function F^{[s]}(x, u) for the numbers f_{n+s,k}^{(s)} has the closed differential form

\frac{∂^{s+1}F^{[s+1]}(x, u)}{∂u^{s+1}} = x^{s}(exp(u) − 2)(exp(u) − 1)^{s−1} \frac{∂F (x, u)}{∂u}.  (12)

Proof. We have

\frac{∂^{s+1}F^{[s+1]}(x, u)}{∂u^{s+1}} = ∑_{n=1}^{∞} ∑_{k≥1} f_{n+s+1,k}^{(s+1)}x^{k} \frac{u^{n}}{n!} .

From Equation (11), multiplying by x^{k} \frac{u^{n}}{n!} and summing over k and n gives

∑_{n≥1} ∑_{k≥s} f_{n+s+1,k}^{(s+1)}x^{k} \frac{u^{n}}{n!} = ∑_{n≥1} ∑_{k≥s} ( ∑_{i_{1},i_{2},...,i_{s}≥1} \binom{n}{i_{1}} ⋯ \binom{n − ∑_{j=1}^{s−1} i_{j}}{i_{s}}f_{n+1−∑_{j=1}^{s} i_{j},k−s})x^{k} \frac{u^{n}}{n!}

(13)

Let

L = ∑_{n≥1} ∑_{k≥s} f_{n+s+1,k}^{(s+1)}x^{k} \frac{u^{n}}{n!} ,

and

M = ∑_{n≥1} ∑_{k≥s} ( ∑_{i_{1},i_{2},...,i_{s}≥1} \binom{n}{i_{1}}\binom{n − i_{1}}{i_{2}} ⋯ \binom{n − ∑_{j=1}^{s−1} i_{j}}{i_{s}}f_{n+1−∑_{j=1}^{s} i_{j},k−s})x^{k} \frac{u^{n}}{n!} .

We have

L = \frac{∂^{s+1}F^{[s+1]}(x, u)}{∂u^{s+1}}.  (14)

Fixing i and summing over k gives

M = ∑_{n≥1} ∑_{i_{1},i_{2},...,i_{s}≥1} ( ∑_{k} x^{s}\binom{n}{i_{1}}\binom{n − i_{1}}{i_{2}} ⋯ \binom{n − ∑_{j=1}^{s−1} i_{j}}{i_{s}}f_{n+1−∑_{j=1}^{s} i_{j},k−s}x^{k−s})\frac{u^{n}}{n!}

= x^{s} ∑_{i_{1},i_{2},...,i_{s}=1}^{∞} ∑_{n≥i_{1},i_{2},...,i_{s}} \binom{n}{i_{1}}\binom{n − i_{1}}{i_{2}} ⋯ \binom{n − ∑_{j=1}^{s−1} i_{j}}{i_{s}}( ∑_{k≥s} f_{n+1−∑_{j=1}^{s} i_{j},k−s}x^{k−s} \frac{u^{n}}{n!} )

= x^{s} ∑_{i_{1},i_{2},...,i_{s}=1}^{∞} ∑_{n≥i_{1},i_{2},...,i_{s}} \frac{n!}{(n − i_{1})!i_{1}!} ⋯ \frac{(n − ∑_{j=1}^{s−1} i_{j})!}{(n − ∑_{j=1}^{s} i_{j})!i_{s}!}( ∑_{k≥s} f_{n+1−∑_{j=1}^{s} i_{j},k−s}x^{k−s} \frac{u^{n}}{n!} )

= x^{s} ∑_{i_{1},i_{2},...,i_{s}=1}^{∞} \frac{u^{i_{1}}}{i_{1}!} \frac{u^{i_{2}}}{i_{2}!} ⋯ \frac{u^{i_{s}}}{i_{s}!} ( ∑_{n≥i_{1},i_{2},...,i_{s}} ∑_{k≥s} f_{n+1−∑_{j=1}^{s} i_{j},k−s}x^{k−s} \frac{u^{n−∑_{j=1}^{s} i_{j}}}{(n − ∑_{j=1}^{s} i_{j})!})

= (x(exp(u) − 1))^{s} \frac{∂F (x, u)}{∂u}.

Substituting Equation (14) and (x(exp(u)−1))^{s} \frac{∂F (x, u)}{∂u} into Equation (13) gives the result.

4 Bijection between flattened partitions over [n+1] and partitions of [n]

Let P ∈ P_{n} be a partition of [n], written as P = B_{1}|B_{2}| ⋯ |B_{k} where the elements in each block B_{i} are written in increasing order. We write P as P′ in such a way that in each block, the smallest element appears at the end but still maintaining the remaining elements. We construct a word P_{+} from P′ by deleting the marks “|” enclosing the different blocks of P′ and then increasing all the terms by 1.

Let f : P_{n} → F_{n+1} be a map which associates a partition P of [n] with a flattened partition defined by f(P) = σ = 1P_{+}. The map f is well defined since if P_{1} and P_{2} are two set partitions over [n] and assume that P_{1} = P_{2}, then f(P_{1}) = 1P_{1+} = 1P_{2+} = f(P_{2}).

Proposition 16. The map f : P_{n} → F_{n+1} is a bijection.

Proof. Since both P_{n} and F_{n+1} are finite with the same size B_{n}, it suffices to prove that f is injective. Let P_{1} and P_{2} be two partitions of [n]. Assume that f(P_{1}) = f(P_{2}). Then by definition, 1P_{1+} = 1P_{2+}. Since the map f is well defined, the strings P_{1+} and P_{2+} are equal after deleting 1 from the front. Thus P_{1} = P_{2}.

Example 17. Consider a partition P = 12|3|45 of [5]. Re-ordering P such that in each block, the smallest entry appears at the end of the partition gives P′ = 21|3|54. Then P_{+} = 32465. And thus σ = 1P_{+} = 132465.

Let σ ∈ F_{n+1} having k runs. Let us define P = f^{−1}(σ) as follows: Insert the mark “|” at the end of each right to left minimum of σ. Delete element 1. Re-order to get the blocks of the partition P.

Example 18. Consider a flattened partition σ = 132465 over [6]. Inserting the mark “|” at the end of each right to left minimum 1|32|4|65|. Deleting 1 and re-ordering the remaining gives the partition P = 12|3|45.

We now give a property of our bijection. This bijection preserves the number of blocks of size greater than 1 in a partition and the number of runs of its corresponding flattened partition.

Theorem 19. For any integer n ≥ 0, if P is a partition over [n] and σ its corresponding flattened partition over [n + 1], then the following assertions are equivalent:

(i) the number of blocks of size greater than 1 of the partition P is k − 1,

(ii) the number of runs of the flattened partition σ is equal to k.

Proof. For n = 0, 1 is the only flattened partition corresponding to the empty set. Consider a partition P of [n] having (k − 1) blocks of size greater than 1. Using the construction of the map f, we write each of the blocks in such a way that the smallest elements of each block appear at the end. Thus the smallest elements become the starting points for a run in a flattened partition σ = f(P) if the block has at least two elements as well as integer 1. The element of singleton blocks becomes a right to left minimum in σ and is not a starting point of a run. So σ has k runs.

Conversely, consider a flattened partition σ having k runs. Placing a mark “|” after the right to left minima forms a partition of [n + 1]. Since a starting point of a run is preceded by a greater element, except the integer 1, the blocks with two or more elements consist of those containing a starting point. Deleting the integer 1 and re-ordering the remaining blocks gives (k − 1) blocks of size greater than 1.

In Example 17, the partition P has 2 blocks of size greater than 1 and the corresponding flattened partition, σ has 3 runs.

5 Acknowledgment

We would like to thank the editor and the anonymous referee for their comments and useful suggestions. This work was financially supported by the Swedish Sida bilateral program with Makerere University, 2015-2020, project 316 “Capacity building in Mathematics and its applications”. The first author would like to thank in a special way Prof. Paul Vaderlind (Stockholm University), Prof. Roberto Mantaci (University Paris Diderot 7) and the Département de Mathématiques et Informatique, Université d’Antananarivo for hosting her during research visits.

References

[1] F. Beyene and R. Mantaci, Exhaustive generation algorithm for flattened set partitions, preprint, 2020. Available at https://cutt.ly/xorkr2M.

[2] M. Bóna and R. Ehrenborg, A combinatorial proof of the log-concavity of the number of permutations with k runs, J. Combin. Theory Ser. A 90 (2000), 293–303.

[3] D. Callan, Pattern avoidance in “flattened” partitions, Discrete Math. 309 (2009), 4187– 4191.

[4] E. R. Canfield and H.S. Wilf, Counting permutations by their alternating runs, J. Combin. Theory Ser. A 115 (2008), 213–225.

[5] L. Carlitz, Generalized Stirling numbers, Combinatorial Analysis Notes, Duke University (1968), 8–15.

[6] R. Ehrenborg and E. Steingrimsson, The excedance set of a permutation, Adv. Appl. Math. 24 (2000), 284–299.

[7] D. Foata and M. P. Schützenberger, Théorie Géométrique des Polynômes Eulériens, Springer, 2006.

[8] A. Heinz, Personal communication to the second author.

[9] S. Ma, An explicit formula for the number of permutations with a given number of alternating runs, J. Combin. Theory Ser. A 119 (2012), 1660–1664.

[10] S. Ma, Enumeration of permutations by number of alternating runs, Discrete Math. 313 (2013), 1816–1822.

[11] P. A. MacMahon, Combinatorial Analysis, Academic Press, 1960.

[12] T. Mansour, Combinatorics of Set Partitions, CRC Press, 2012.

[13] T. Mansour, M. Shattuck, and S. Wagner, Counting subwords in flattened partitions of sets, Discrete Math. 338 (2015), 1989–2005.

[14] R. Mantaci and F. Rakotondrajao, Exceedingly deranging!, Adv. Appl. Math. 30 (2003), 177–188.

[15] R. Mantaci and F. Rakotondrajao, A permutation representation that knows what Eulerian means, Discrete Math. Theor. Comput. Sci. 4 (2001), 101–108.

[16] G. Rota, The number of partitions of a set, Amer. Math. Monthly 71 (1964), 498–504.

[17] N. J. A. Sloane et al., The on-line encyclopedia of integer sequences, Available at

    https://oeis.org, 2019.

[18] J. Steinhardt, Permutations with ascending and descending blocks, Electron. J. Combin. 17 (2010), #R14.

[19] S. Wolfram, The Mathematica Book, Cambridge University Press, 2000.

[20] Y. Zhuang, Counting permutations by runs, J. Combin. Theory Ser. A 142 (2016), 147–176.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A10, 05A15, 05A18. Keywords: flattened partition, generating function, recurrence relation, run, set partition.

(Concerned with sequence \underline{A000295} and \underline{A124324}.)

Received February 10 2020; revised versions received July 1 2020; August 5 2020; October 15 2020. Published in Journal of Integer Sequences, October 15 2020.

Return to Journal of Integer Sequences home page.