Patterns in Set Partitions

Bruce E. Sagan Department of Mathematics Michigan State University East Lansing, MI 48824-1027 sagan@math.msu.edu www.math.msu.edu/˜ sagan

1. The First Definition

2. Enumeration

3. The Stanley-Wilf Conjecture

4. The Noonan-Zeilberger Conjecture

5. The Second Definition

6. More Open Problems 1. The First Definition

Given sets S, T and a function f : S → T, apply f element-wise to objects built from S

Ex. 1. If p = a_{1}a_{2} … a_{m} is a word over S, possibly with repetitions, then f(p) = f(a_{1})f(a_{2}) … f(a_{m}).

2. If B ⊆ S then f(B) = {f(a) | a ∈ B}.

Given two positive integers m, n ∈ ℙ, we will let [m, n] = {m, m + 1, …, n} and [n] = [1, n].

Now if S ⊆ ℙ has cardinality #S = n then the reduction map is the unique order-preserving bijection r_{S} : S → [n].

Ex. If S = {2, 5, 7, 8} then

r_{S}(2) = 1, r_{S}(5) = 2, r_{S}(7) = 3, r_{S}(8) = 4.

Ordinary pattern containment can be defined: Let q ∈ 𝔖_{m}, then p = a_{1}a_{2} … a_{n} ∈ 𝔖_{n} contains q if there is a subword p′ = a_{i_{1}}a_{i_{2}} … a_{i_{m}} of p such that

r_{S}(p′) = q

where S = {a_{i_{1}}, a_{i_{2}}, …, a_{i_{m}}}.

A partition π of a set S is a family of nonempty sets B_{1}, B_{2}, …, B_{k} such that ⊎_{i}B_{i} = S. The B_{i} are called the blocks of π and the number of blocks is the length of π, l(π). We write π = B_{1}/B_{2}/ … /B_{k} ⊢ S, e.g., 137/28/456/9 ⊢ [9]. Let

Π_{n} = {π ⊢ [n]} and Π = _{n≥1}^{⨄} Π_{n}.

We say σ is contained in π, σ ⊆ π, if each block of σ is contained in some block of π.

Ex. 28/3/46 ⊆ 137/28/456/9 because 28 ⊆ 28, 3 ⊆ 137, and 46 ⊆ 456.

Now π contains the pattern σ, π ⊒ σ, if there is a partition π′ ⊆ π with

r_{S}(π′) = σ

where π′ ⊢ S.

Ex. If σ = 13/2 then π = 14/236/5 contains six copies of σ: 14/2, 14/3, 26/4, 26/5, 36/4, 36/5.

We say π avoids σ if π ⋣ σ and let

Π_{n}(σ) = {π ∈ Π_{n} | π ⋣ σ} and Π(σ) = _{n≥1}^{⨄} Π_{n}(σ).

2. Enumeration Sequence (a_{n})_{n≥0} has egf F (x) = _{n≥0}^{∑} a_{n}\frac{x^{n}}{n!}.

Subset J ⊆ ℙ has egf F_{J}(x) = _{j∈J}^{∑} \frac{x^{j}}{j!}. Theorem 1 Let a_{n,k}^{J} = #{π ∈ Π_{n} | l(π) = k and block sizes in J }. Then

_{n≥0}^{∑} a_{n,k}^{J}\frac{x^{n}}{n!} = \frac{F_{J}(x)^{k}}{k!} .

Let

exp (x) = ∞ ; ∑ ; n=0 \frac{x^{n}}{n!}  exp (x) = ∞ ; ∑ ; n=1 \frac{x^{n}}{n!}
exp_{m}(x) = m ; ∑ ; n=0 \frac{x^{n}}{n!}  exp_{m}(x) = m ; ∑ ; n=1 \frac{x^{n}}{n!}

and

C_{n}F (x) = the coefficient of x^{n}/n! in F (x).

Theorem 2 (S) We have

Π(1/2/ … /m) = {π | l(π) < m},  (1)
#Π_{n}(1/2/ … /m)  = C_{n} exp_{m−1}(exp x).  (2)
Π(12 … m) = {π | #B < m ∀B ∈ π}, (3)
#Π_{n}(12 … m)  = C_{n} exp (exp_{m−1}x).  (4)

Proof for σ = 12 … m. First, π ⊒ σ iff there is a block B of π with #B ≥ m proving (?? ). Also

#Π_{n}(12 … m) = _{k≥0}^{∑} a_{n,k}^{J} where J = [m − 1].

So by Theorem ??

_{n≥0}^{∑} #Π_{n}(12 … m) \frac{x^{n}}{n!} = _{k≥0}^{∑} _{n≥0}^{∑} a_{n,k}^{[m−1]} \frac{x^{n}}{n!}

= _{k≥0}^{∑} \frac{(exp_{m−1}x)^{k}}{k!} = exp (exp_{m−1}x).

Call σ and involution if all B ∈ σ have #B = 1 or 2.

Corollary 3 (Klazar, S) We have

Π(1/2/3) = {π | π has at most 2 blocks },
#Π_{n}(1/2/3)  = 2^{n−1}.
Π(123) = {π | π is an involution },
#Π_{n}(123)  = _{i≥0}^{∑} \binom{n}{2i}(2i)!!

Partition π is layered if it is of the form

π = [1, i]/[i + 1, j]/ … /[k + 1, n].

Theorem 4 (S) We have

Π(13/2) = {π | π is layered },
#Π_{n}(13/2)  = 2^{n−1}.
Π(12/3) = {π = B_{1}/ … /B_{k} | min B_{i} = i ∀i

and ∃i with [k + 1, n] ⊆ B_{i} },

#Π_{n}(12/3)  = \binom{n}{2} + 1.

Given σ = C_{1}/ … /C_{l} ⊢ [m] we let

σ′ = C′_{1}/ … /C′_{l} where C′_{i} = {m + 1 − a | a ∈ C_{i}} ∀i. Ex. σ = 135/24/6 implies σ′ = 642/53/1.

Proposition 5 (S) We have

Π(σ′) = {π′ | π ∈ Π(σ)}, and
#Π_{n}(σ′) = #Π_{n}(σ) for n ≥ 1 .

Since (12/3)′ = 1/23, this completes the enumeration of partitions avoiding a single pattern of length at most three. Sets of patterns and refinements by parity can also be enumerated.

3. The Stanley-Wilf Conjecture Conjecture 6 (Stanley-Wilf) For every permutation pattern q the limit

lim_{n→∞} #𝔖_{n}(q)^{1/n}

exists and is finite. This is not always true of the limit

lim_{n→∞} #Π_{n}(σ)^{1/n}.  (5)

Theorem 7 (K) If σ = 123 or 12/34, then (?? ) is infinite. Proof for σ = 123. By Corollary ?? and Stirling

#Π_{n}(123)^{1/n} ≥ n!!^{1/n} ≥ C√n

for some constant C and large n. Since τ ⊒ σ implies Π_{n}(τ) ⊇ Π_{n}(σ), we have Corollary 8 (K) The limit (?? ) is infinite if σ ⊒ 123 or σ ⊒ 12/34. So the patterns for which we have not yet determined (?? ) are exactly those in Π(123, 12/34)

Another description of the σ ∈ Π(123, 12/34): Since σ avoids 123, it is an involution. To include the other restriction, given a permutation p = a_{1}a_{2} … a_{n} we have a corresponding permutation partition

σ_{p} = 1(a_{1} + n)/2(a_{2} + n)/ … /n(a_{n} + n).

Ex. If p = 2431 then σ_{p} = 16/28/37/45.

An inflated permutation partition is σ = τ ⊎ ρ such that τ consists of only singleton blocks and r_{S}(ρ) is a permutation partition where ρ ⊢ S.

Theorem 9 (K) 1. The inflated permutation partitions are precisely those in Π(123, 12/34).

2. If for each permutation partition there is a constant c with Π_{n}(σ_{p}) ≤ c^{n} for all large n, then the same is true of inflated permutation partitions.

Theorem 10 (S) The limit (?? ) exists and is finite for σ = 1/2/ … /m and for all partitions with at most 3 elements except σ = 123.

A limit either exists and is finite, exists and is infinite, or does not exist. Also #Π_{n}(σ) ≤ c^{n} for all large n implies the limit is finite or does not exist.

Define σ ⊢ [m] to be reducible if there is j with 0 < j < m such that σ = τ ⊎ ρ with

τ ⊢ [j] and ρ ⊢ [j + 1, m].

Using Fekete’s Lemma one can prove

Theorem 11 (S) For σ irreducible, the limit (?? ) exisits (and may be infinite).

Since permutation patterns are irreducible, this Theorem implies Arratia’s result that the corresponding limit exists for all permutations.

Putting all the evidence together, we conjecture

Conjecture 12 (K,S) For all σ, the limit (?? ) exists. It is finite precisely for σ ∈ Π_{n}(123, 12/34).

Notes: 1. Since p ∈ 𝔖_{n}(q) implies σ_{p} ∈ Π_{n}(σ_{q}) we have #Π_{n}(σ_{q}) ≥ #𝔖_{n}(q). So the previous conjecture implies the Stanley-Wilf conjecture.

2. Klazar has shown that for σ ∈ Π_{n}(123, 12/34) we have #Π_{n}(σ) ≤ ω(n)^{n} where ω(n) grows slowly.

4. The Noonan-Zeilberger Conjecture

A sequence (a_{n})_{n≥0} is P-recursive if there are polynomials P_{0}(n), P_{1}(n), …, P_{k}(n) (not all zero) such that for all n ∈ ℙ

P_{0}(n)a_{n} + P_{1}(n)a_{n+1} + ⋯ + P_{k}(n)a_{n+k} = 0.

Ex. a_{n} = n! is P-recursive: (n + 1)a_{n} − a_{n+1} = 0.

Conjecture 13 (Noonan-Zeilberger) For any permutation q, the sequence a_{n} = #𝔖_{n}(q) is P-recursive.

A series f(x) ∈ ℂ[[x]] is D-finite if there are polynomials p_{0}(x), p_{1}(x), …, p_{k}(x) (not all zero) such that

p_{0}(x)f(x) + p_{1}(x)f′(x) + ⋯ + p_{k}(x)f^{(k)}(x) = 0.

Sequence (a_{n})_{n≥0} has ogf f(x) = _{n≥0}^{∑} a_{n}x^{n}.

Theorem 14 (Jungen,Stanley) 1. (a_{n})_{n≥0} is P-recursive iff its ogf f(x) is D-finite.

2. If (a_{n})_{n≥0} and (b_{n})_{n≥0} are P-recursive then so is (a_{n}b_{n})_{n≥0}.

Corollary 15 (S) (a_{n})_{n≥0} is P-recursive iff its egf F (x) is D-finite.

A series f(x) ∈ ℂ[[x]] is algebraic if there are polynomials q_{0}(x), q_{1}(x), …, q_{k}(x) (not all zero) such that

q_{0}(x)f(x) + q_{1}(x)f(x)^{2} + ⋯ + q_{k}(x)f(x)^{k} = 0.

Theorem 16 (Stanley) If f(x) is D-finite and g(x) is algebraic then f(g(x)) is D-finite.

Theorem 17 (S) If σ is a pattern with at most 3 elements or σ = 1/2/ … /m or σ = 12 … m then the sequence a_{n} = #Π_{n}(σ) is P-recursive.

Proof for σ = 12 … m. We showed that

_{n≥0}^{∑} #Π_{n}(12 … m)\frac{x^{n}}{n!} = exp (exp_{m−1}x).

Now exp_{m−1}(x) is a polynomial and so algebraic. Furthermore, f(x) = exp (x) is D-finite since we have f(x) − f′(x) = 0. So we are done by the previous Theorem and Corollary.

Conjecture 18 (S) For any partition σ, we have that the sequence a_{n} = #Π_{n}(σ) is P-recursive.

5. The Second Definition

A sequence r = a_{1}a_{2} … a_{n} of positive integers is a restricted growth function (RGF) of length n if

a_{1} = 1 and a_{i} ≤ 1 + max_{j<i} a_{j} for i ≥ 2.

Let R_{n} be the set of such functions and R = ⊎_{n≥1}R_{n}. To connect with partitions, all π = B_{1}/B_{2}/ … /B_{k} in this section will be ordered, i.e., indexed so that

min B_{1} < min B_{2} < … < min B_{k}.  (6)

Given π ⊢ [n] we construct a sequence r_{π} = a_{1}a_{2} … a_{n} by letting a_{i} = j iff i ∈ B_{j}.

Ex. If π = 137/28/456/9 then r_{π} = 121333124.

Condition (?? ) forces r_{π} to be an RGF and this map is a bijection Π_{n} ⟷ R_{n}.

Now r ∈ R contains the pattern s, r ⪰ s, if there is a subword r′ = a_{i_{1}}a_{i_{2}} … a_{i_{m}} of r such that

r_{S}(r′) = s

where S = {a_{i_{1}}, a_{i_{2}}, …, a_{i_{m}}}.

In terms of partitions, π ⪰ σ if the elements reducing to the jth block of σ come from B_{i_{j}} in π with

i_{1} < i_{2} < … < i_{l}.

Ex. If σ = 13/2 then π = 14/236/5 ⪰ σ in four ways: 14/2, 14/3, 26/5, 36/5.

We say π RGF-avoids σ if π ⪰̸ σ and let

R_{n}(σ) = {π ∈ Π_{n} | π ⪰̸ σ} and R(σ) = _{n≥1}^{⨄} R_{n}(σ).

Note that π ⪰ σ implies π ⊒ σ so R_{n}(σ) ⊇ Π_{n}(σ).

Many of the results for ⊒ have analogues for ⪰.

Theorem 19 (S) If σ ⊢ [3] then

#R_{n}(σ) = 2^{n−1}

except for σ = 123 when

R_{n}(123) = Π_{n}(123).

Conjecture 20 (S) The analogues of the Stanley-Wilf and Noonan-Zeilberger conjectures obtained by replacing ⊒ with ⪰ everywhere are also true.

6. More Open Problems

a. Associated with any ordered partition π we have a permutation p_{π} obtained by concatenating the blocks where each block is written in decreasing order.

Ex. If π = 14/236/5 then p_{π} = 416325.

Note that if π is layered then so is p_{π} and any layered permutation is p_{π} for a unique π. Also, if σ, π are layered then σ ⊑ π iff σ ⪰ π. These observations lead to the following analogue of a result of Stromquist.

Theorem 21 (S) Let σ be layered. Among all elements of Π_{n} which contain the maximum number of copies of σ (using either ⊑ or ⪰) there is always one which is layered.

What can be said about packing densities of partition patterns, especially layered ones?

b. One can define generalized RGF-pattern containment by insisting that certain adjacent elements of the pattern RGF must be adjacent in the containing RGF à la Babson and Steingrímsson. What can be said about the concepts we have addressed in this context?

c. A poset is well partially ordered (WPO) if it contains neither an infinite descending chain nor an infinite antichain. We have the following weak analogue of a theorem of Atkinson, Murphy, and Ruškuc.

Theorem 22 (S) The poset (Π(σ), ⪯) is WPO if σ has at most three elements with the exception of (Π(123), ⪯) which is not WPO.

AMR actually give a characterization of the permutations q such that 𝔖(q) is WPO. It would be interesting to do the same for partitions.