March26,2013 HenriM¨uhle CountingProperMergings

Motivation Characterization Enumeration

Counting Proper Mergings

Henri M¨uhle

Universit¨at Wien

March 26, 2013

Motivation Characterization Enumeration

Outline

1 Motivation

2 Characterization

3 Enumeration

Proper Mergings of Two Chains Proper Mergings of Two Antichains

Proper Mergings of an Antichain and a Chain

Motivation Characterization Enumeration

Outline

1 Motivation

2 Characterization

3 Enumeration

Proper Mergings of Two Chains Proper Mergings of Two Antichains

Proper Mergings of an Antichain and a Chain

Motivation Characterization Enumeration

Motivation

I let (P,≤_P) be a poset

I consider the elements of P as tasks

I for p,p⁰ ∈P, consider p <_P p⁰ as saying that the execution of p has to be finished before the execution of p⁰ can begin

I thus, (P,≤_P) can be seen as a schedule, or an execution plan, and≤_P can be seen as a set of restrictions

I let (Q,≤_Q) be another poset

I How many different schedules exist such that

I (P,≤P) and (Q,≤Q) are executed “in parallel”,

and

I no restrictions of (P,≤P) and (Q,≤Q) are violated or added

I no two tasks are executed at the same time?

I we call such a schedule a

Motivation Characterization Enumeration

Motivation

I let (P,≤_P) be a poset

I consider the elements of P as tasks

I for p,p⁰ ∈P, consider p <_P p⁰ as saying that the execution of p has to be finished before the execution of p⁰ can begin

I thus, (P,≤_P) can be seen as a schedule, or an execution plan, and≤_P can be seen as a set of restrictions

I let (Q,≤_Q) be another poset

I How many different schedules exist such that

I (P,≤P) and (Q,≤Q) are executed “in parallel”,

and

I no restrictions of (P,≤P) and (Q,≤Q) are violated or added

I no two tasks are executed at the same time?

I we call such a schedule a

Motivation Characterization Enumeration

Motivation

I let (P,≤_P) be a poset

I consider the elements of P as tasks

I for p,p⁰ ∈P, consider p <_P p⁰ as saying that the execution of p has to be finished before the execution of p⁰ can begin

I thus, (P,≤_P) can be seen as a schedule, or an execution plan, and≤_P can be seen as a set of restrictions

I let (Q,≤_Q) be another poset

I How many different schedules exist such that

I (P,≤P) and (Q,≤Q) are executed “in parallel”,

and

I no restrictions of (P,≤P) and (Q,≤Q) are violated or added

I no two tasks are executed at the same time?

I we call such a schedule a

Motivation Characterization Enumeration

Motivation

I let (P,≤_P) be a poset

I consider the elements of P as tasks

I for p,p⁰ ∈P, consider p <_P p⁰ as saying that the execution of p has to be finished before the execution of p⁰ can begin

I thus, (P,≤_P) can be seen as a schedule, or an execution plan, and≤_P can be seen as a set of restrictions

I let (Q,≤_Q) be another poset

I How many different schedules exist such that

I (P,≤P) and (Q,≤Q) are executed “in parallel”, and

I no restrictions of (P,≤P) and (Q,≤Q) are violated or added?

I no two tasks are executed at the same time?

I we call such a schedule a

Motivation Characterization Enumeration

Motivation

I let (P,≤_P) be a poset

I consider the elements of P as tasks

I for p,p⁰ ∈P, consider p <_P p⁰ as saying that the execution of p has to be finished before the execution of p⁰ can begin

I thus, (P,≤_P) can be seen as a schedule, or an execution plan, and≤_P can be seen as a set of restrictions

I let (Q,≤_Q) be another poset

I How many different schedules exist such that

I (P,≤P) and (Q,≤Q) are executed “in parallel”, and

I no restrictions of (P,≤P) and (Q,≤Q) are violated or added?

I no two tasks are executed at the same time?

I we call such a schedule amerging of (P,≤_P) and (Q,≤_Q)

Motivation Characterization Enumeration

Motivation

I let (P,≤_P) be a poset

I consider the elements of P as tasks

I for p,p⁰ ∈P, consider p <_P p⁰ as saying that the execution of p has to be finished before the execution of p⁰ can begin

I thus, (P,≤_P) can be seen as a schedule, or an execution plan, and≤_P can be seen as a set of restrictions

I let (Q,≤_Q) be another poset

I How many different schedules exist such that

I (P,≤P) and (Q,≤Q) are executed “in parallel”,

and

I no restrictions of (P,≤P) and (Q,≤Q) are violated or added,

I no two tasks are executed at the same time?

I we call such a schedule a proper merging of (P,≤_P) and (Q,≤_Q)

Motivation Characterization Enumeration

Example

p₁ p₂

p₃ p4

q₁ q₂

q₃ q₄

q₅ q₆

q1

q₂ p₂ p₁

q₄

q₅ q₆

p₄

Motivation Characterization Enumeration

Example

p₁ p₂

p₃ p4

q₁ q₂

q₃ q₄

q₅ q₆

q1

q₂ p₂ p₁

q₃ q₄

p₃

q₅ q₆

p₄

Motivation Characterization Enumeration

Example

p₁ p₂

p₃ p4

q₁ q₂

q₃ q₄

q₅ q₆

q1

q₂ p₂ p₁

q₃ q₄

p₃

q₅ q₆

p₄

Motivation Characterization Enumeration

Example

p₁ p₂

p₃ p4

q₁ q₂

q₃ q₄

q₅ q₆

q1

q₂ p₂ p₁

q₃ q₄

p₃

q₅ q₆

p₄

Motivation Characterization Enumeration

Example

p₁ p₂

p₃ p4

q₁ q₂

q₃ q₄

q₅ q₆

q1

q₂ p₂ p₁

q₃ q₄

p₃

q₅ q₆

p₄

Motivation Characterization Enumeration

Example

p₁ p₂

p₃ p4

q₁ q₂

q₃ q₄

q₅ q₆

q1

q₂ p₂ p₁

q₃ q₄

p₃

q₅ q₆

p₄

Motivation Characterization Enumeration

Example

p₁ p₂

p₃ p4

q₁ q₂

q₃ q₄

q₅ q₆

q1

q₂ p₂ p₁

q₃ p₃ q₄

q₅ q₆

p₄

Motivation Characterization Enumeration

Outline

1 Motivation

2 Characterization

3 Enumeration

Proper Mergings of Two Chains Proper Mergings of Two Antichains

Proper Mergings of an Antichain and a Chain

Motivation Characterization Enumeration

Characterization

I let G,G⁰,M,M⁰ be sets, and let I ⊆G ×M,I⁰⊆G⁰×M⁰ be two binary relations

I row of I: the setg^I =

m∈M |(g,m)∈I for g ∈G

I column of I: the set m^I =

g ∈G |(g,m)∈I for m∈M

I intent ofI: an intersection over a subset of the rows ofI

I extent of I: an intersection over a subset of the columns of I

I bond between I andI⁰: a binary relationR ⊆G ×M⁰ such that for all g ∈G, the rowg^R is an intent ofI⁰, and for all m∈M⁰, the column m^R is an extent of I

Motivation Characterization Enumeration

Example

p1 p2 p3 p4 q1 q2 q3 q4 q5 q6

p₁ × × ×

× × ×

p₂ × × ×

× × × ×

p₃ × ×

× × ×

p₄ ×

q₁ × × × × ×

q₂ × × ×

q₃ × × ×

q₄ × ×

q₅ ×

q₆ ×

p₁ p₂

p₃ p₄

q₁ q₂

q₃ q₄

q₅ q₆

Motivation Characterization Enumeration

Example

p1 p2 p3 p4 q1 q2 q3 q4 q5 q6

p₁ × × × × × ×

p₂ × × ×

×

×

×

×

p₃ × ×

× ×

×

p₄ ×

q₁ × × × × ×

q₂ × × ×

q₃ × × ×

q₄ × ×

q₅ ×

q₆ ×

p₁ p₂

p₃ p₄

q₁ q₂

q₃ q₄

q₅ q₆

Motivation Characterization Enumeration

Example

p1 p2 p3 p4 q1 q2 q3 q4 q5 q6

p₁ × × × × × ×

p₂ × × ×

×

×

×

×

p₃ × × ×

×

×

p₄ ×

q₁ × × × × ×

q₂ × × ×

q₃ × × ×

q₄ × ×

q₅ ×

q₆ ×

p₁ p₂

p₃ p₄

q₁ q₂

q₃ q₄

q₅ q₆

Motivation Characterization Enumeration

Example

p1 p2 p3 p4 q1 q2 q3 q4 q5 q6

p₁ × × × × × ×

p₂ × × × × × × ×

p₃ × × × × ×

p₄ ×

q₁ × × × × ×

q₂ × × ×

q₃ × × ×

q₄ × ×

q₅ ×

q₆ ×

p₁ p₂

p₃ p₄

q₁ q₂

q₃ q₄

q₅ q₆

Motivation Characterization Enumeration

Characterization

I let (P,≤_P) and (Q,≤_Q) be disjoint posets, and let R ⊆P×Q, andT ⊆Q×P

I for p,q ∈P∪Q, definep ←_R,T q if and only if p≤_P q orp≤_Q qor (p,q)∈Ror (p,q)∈T

I merging of (P,≤_P) and (Q,≤_Q): a pair (R,T) such that (P∪Q,←_R,T) is a quasi-ordered set

I proper merging of (P,≤_P) and (Q,≤_Q): a merging (R,T) such that R∩T⁻¹ =∅

Motivation Characterization Enumeration

Characterization

Proposition (Meschke, 2011)

Let(P,≤_P) and(Q,≤_Q) be disjoint posets, and let R⊆P ×Q and T ⊆Q×P. The relation ←_R,T is reflexive and transitive if and only if all of the following are satisfied:

1. R is a bond between 6≥_P and6≥_Q, 2. T is a bond between6≥_Q and 6≥_P, 3. R◦T is contained in≤_P,

4. T ◦R is contained in≤_Q.

Moreover,←_R,T is antisymmetric if and only if R∩T⁻¹ =∅.

I in other words, (P ∪Q,←_R,T) is a poset if and only if (R,T) is a proper merging of (P,≤_P) and (Q,≤_Q)

Motivation Characterization Enumeration

Characterization

Proposition (Meschke, 2011)

Let(P,≤_P) and(Q,≤_Q) be disjoint posets, and let R⊆P ×Q and T ⊆Q×P. The relation ←_R,T is reflexive and transitive if and only if all of the following are satisfied:

1. R is a bond between 6≥_P and6≥_Q, 2. T is a bond between6≥_Q and 6≥_P, 3. R◦T is contained in≤_P,

4. T ◦R is contained in≤_Q.

Moreover,←_R,T is antisymmetric if and only if R∩T⁻¹ =∅.

I in other words, (P ∪Q,←_R,T) is a poset if and only if (R,T) is a proper merging of (P,≤_P) and (Q,≤_Q)

Motivation Characterization Enumeration

A Lattice Structure

I let M_P,Q denote the set of

proper

mergings of (P,≤_P) and (Q,≤_Q)

I define a partial order via

(R,T)(R⁰,T⁰) if and only if R ⊆R⁰ andT ⊇T⁰,

Theorem (Meschke, 2011)

Let(P,≤_P) and(Q,≤_Q) be disjoint posets. The poset(M_P,Q,) is in fact a distributive lattice, where the least element is

(∅,P ×Q) and the greatest element is (P×Q,∅).

Moreover, the poset(M^•_P,Q,) is a distributive sublattice of the previous.

Motivation Characterization Enumeration

A Lattice Structure

I let M^•_P,Q denote the set of proper mergings of (P,≤_P) and (Q,≤_Q)

I define a partial order via

(R,T)(R⁰,T⁰) if and only if R ⊆R⁰ andT ⊇T⁰,

Theorem (Meschke, 2011)

Let(P,≤_P) and(Q,≤_Q) be disjoint posets. The poset(M_P,Q,) is in fact a distributive lattice, where the least element is

(∅,P ×Q) and the greatest element is (P×Q,∅).

Moreover, the poset(M^•_P,Q,) is a distributive sublattice of the previous.

Motivation Characterization Enumeration

A Lattice Structure

I let M^•_P,Q denote the set of proper mergings of (P,≤_P) and (Q,≤_Q)

I define a partial order via

(R,T)(R⁰,T⁰) if and only if R ⊆R⁰ andT ⊇T⁰,

Theorem (Meschke, 2011)

Let(P,≤_P) and(Q,≤_Q) be disjoint posets. The poset(M_P,Q,) is in fact a distributive lattice, where the least element is

(∅,P ×Q) and the greatest element is(P×Q,∅).

Moreover, the poset(M^•_P,Q,) is a distributive sublattice of the previous.

Motivation Characterization Enumeration

Outline

1 Motivation

2 Characterization

3 Enumeration

Proper Mergings of Two Chains Proper Mergings of Two Antichains

Proper Mergings of an Antichain and a Chain

Motivation Characterization Enumeration

Enumeration

I Is it easy to determine the number of (proper) mergings of two posets (P,≤_P) and (Q,≤_Q)?

In general, no!

I the number of (proper) mergings depends heavily on the structure of (P,≤_P) and (Q,≤_Q)

Motivation Characterization Enumeration

Enumeration

I Is it easy to determine the number of (proper) mergings of two posets (P,≤_P) and (Q,≤_Q)? In general, no!

I the number of (proper) mergings depends heavily on the structure of (P,≤_P) and (Q,≤_Q)

Motivation Characterization Enumeration

Enumeration

I Is it easy to determine the number of (proper) mergings of two posets (P,≤_P) and (Q,≤_Q)? In general, no!

I the number of (proper) mergings depends heavily on the structure of (P,≤_P) and (Q,≤_Q)

Motivation Characterization Enumeration

Enumeration

I Is it easy to determine the number of (proper) mergings of two posets (P,≤_P) and (Q,≤_Q)? In general, no!

I the number of (proper) mergings depends heavily on the structure of (P,≤_P) and (Q,≤_Q)

1 1

18 15

230 155

2676 1443

30386 12899

344748 113235

Motivation Characterization Enumeration

Enumeration

I Is it easy to determine the number of (proper) mergings of two posets (P,≤_P) and (Q,≤_Q)? In general, no!

I the number of (proper) mergings depends heavily on the structure of (P,≤_P) and (Q,≤_Q)

1 1

18 15

142 105

723 409

2782 1764

8796 5292

Motivation Characterization Enumeration

Enumeration

I Is it easy to determine the number of (proper) mergings of two posets (P,≤_P) and (Q,≤_Q)? In general, no!

I the number of (proper) mergings depends heavily on the structure of (P,≤_P) and (Q,≤_Q)

I we present the enumeration of three special cases:

1. proper mergings of two chains 2. proper mergings of two antichains

3. proper mergings of an antichain and a chain

Motivation Characterization Enumeration Proper Mergings of Two Chains

Outline

1 Motivation

2 Characterization

3 Enumeration

Proper Mergings of Two Chains Proper Mergings of Two Antichains

Proper Mergings of an Antichain and a Chain

Motivation Characterization Enumeration Proper Mergings of Two Chains

Preparation

I let C ={c₁,c₂, . . . ,c_n} be a set and define c_i ≤_cc_j if and only if i ≤j

c= (C,≤_c) is a chain

I we notice that c_i 6≥_cc_j if and only if i <j, or equivalently ci <ccj for all i,j ∈ {1,2, . . . ,n}

I thus, the extents of 6≥_c are of the form{c₁,c₂, . . . ,c_k}for somek ∈ {0,1, . . . ,n}and the intents are of the form {c_k,c_k+1, . . . ,cn}for somek ∈ {1,2, . . . ,n+ 1}

Motivation Characterization Enumeration Proper Mergings of Two Chains

Preparation

I let C ={c₁,c₂, . . . ,c_n} be a set and define c_i ≤_cc_j if and only if i ≤j c= (C,≤_c) is a chain

I we notice that c_i 6≥_cc_j if and only if i <j, or equivalently ci <ccj for all i,j ∈ {1,2, . . . ,n}

I thus, the extents of 6≥_c are of the form{c₁,c₂, . . . ,c_k}for somek ∈ {0,1, . . . ,n}and the intents are of the form {c_k,c_k+1, . . . ,cn}for somek ∈ {1,2, . . . ,n+ 1}

Motivation Characterization Enumeration Proper Mergings of Two Chains

Preparation

I let C ={c₁,c₂, . . . ,c_n} be a set and define c_i ≤_cc_j if and only if i ≤j c= (C,≤_c) is a chain

I we notice that c_i 6≥_cc_j if and only if i <j, or equivalently ci <ccj for all i,j ∈ {1,2, . . . ,n}

I thus, the extents of 6≥_c are of the form{c₁,c₂, . . . ,c_k}for somek ∈ {0,1, . . . ,n}and the intents are of the form {c_k,c_k+1, . . . ,cn}for somek ∈ {1,2, . . . ,n+ 1}

Motivation Characterization Enumeration Proper Mergings of Two Chains

Preparation

I let C ={c₁,c₂, . . . ,c_n} be a set and define c_i ≤_cc_j if and only if i ≤j c= (C,≤_c) is a chain

I we notice that c_i 6≥_cc_j if and only if i <j, or equivalently ci <ccj for all i,j ∈ {1,2, . . . ,n}

c₁ c₂ c₃ c₄

I thus, the extents of 6≥_c are of the form{c₁,c₂, . . . ,c_k}for somek ∈ {0,1, . . . ,n}and the intents are of the form {c_k,c_k+1, . . . ,cn}for somek ∈ {1,2, . . . ,n+ 1}

Motivation Characterization Enumeration Proper Mergings of Two Chains

Preparation

I let C ={c₁,c₂, . . . ,c_n} be a set and define c_i ≤_cc_j if and only if i ≤j c= (C,≤_c) is a chain

I we notice that c_i 6≥_cc_j if and only if i <j, or equivalently ci <ccj for all i,j ∈ {1,2, . . . ,n}

c₁ c₂ c₃ c₄

≤_c c₁ c₂ c₃ c₄

c₁ × × × ×

c2 × × ×

c3 × ×

c₄ ×

I thus, the extents of 6≥_c are of the form{c₁,c₂, . . . ,c_k}for somek ∈ {0,1, . . . ,n}and the intents are of the form {c_k,c_k+1, . . . ,cn}for somek ∈ {1,2, . . . ,n+ 1}

Motivation Characterization Enumeration Proper Mergings of Two Chains

Preparation

I let C ={c₁,c₂, . . . ,c_n} be a set and define c_i ≤_cc_j if and only if i ≤j c= (C,≤_c) is a chain

I we notice that c_i 6≥_cc_j if and only if i <j, or equivalently ci <ccj for all i,j ∈ {1,2, . . . ,n}

c₁ c₂ c₃ c₄

≤_c c₁ c₂ c₃ c₄

c₁ × × × ×

c2 × × ×

c3 × ×

c₄ ×

6≥_c c₁ c₂ c₃ c₄

c₁ × × ×

c2 × ×

c3 ×

c₄

I thus, the extents of 6≥_c are of the form{c₁,c₂, . . . ,c_k}for somek ∈ {0,1, . . . ,n}and the intents are of the form {c_k,c_k+1, . . . ,cn}for somek ∈ {1,2, . . . ,n+ 1}

Motivation Characterization Enumeration Proper Mergings of Two Chains

Preparation

I let C ={c₁,c₂, . . . ,c_n} be a set and define c_i ≤_cc_j if and only if i ≤j c= (C,≤_c) is a chain

I we notice that c_i 6≥_cc_j if and only if i <j, or equivalently ci <ccj for all i,j ∈ {1,2, . . . ,n}

c₁ c₂ c₃ c₄

≤_c c₁ c₂ c₃ c₄

c₁ × × × ×

c2 × × ×

c3 × ×

c₄ ×

6≥_c c₁ c₂ c₃ c₄

c₁ × × ×

c2 × ×

c3 ×

c₄

I thus, the extents of 6≥_c are of the form{c₁,c₂, . . . ,c_k}for somek ∈ {0,1, . . . ,n}and the intents are of the form {c_k,c_k+1, . . . ,cn}for somek ∈ {1,2, . . . ,n+ 1}

Motivation Characterization Enumeration Proper Mergings of Two Chains

The Idea

I let C ={c₁,c2, . . . ,cm) andC⁰ ={c₁⁰,c₂⁰, . . . ,c_n⁰}be sets and let c= (C,≤_c) andc⁰= (C⁰,≤_c⁰) be two chains

Motivation Characterization Enumeration Proper Mergings of Two Chains

The Idea

I let C ={c₁,c2, . . . ,cm) andC⁰ ={c₁⁰,c₂⁰, . . . ,c_n⁰}be sets and let c= (C,≤_c) andc⁰= (C⁰,≤_c⁰) be two chains

I if (R,T) is a merging of c andc⁰, thenR and T must be right-justified and top-justified

R

C⁰

C

T

C⁰ C

Motivation Characterization Enumeration Proper Mergings of Two Chains

The Idea

I let C ={c₁,c2, . . . ,cm) andC⁰ ={c₁⁰,c₂⁰, . . . ,c_n⁰}be sets and let c= (C,≤_c) andc⁰= (C⁰,≤_c⁰) be two chains

I if (R,T) is a proper merging of c andc⁰, thenR and T must

“fit together”

R

T

C⁰

C

Motivation Characterization Enumeration Proper Mergings of Two Chains

The Bijection

I plane partition π: a rectangular array which is weakly decreasing along rows and columns

I part of π: an entryπi,j in the array

I given a proper merging (R,T) of c andc⁰, define a plane partitionπ withm rows, n columns and largest part at most 2 as follows:

π_i,j =







2, if (c_i,c_n−j+1⁰ )∈R 0, if (c_n−j+1⁰ ,ci)∈T 1, otherwise

I this is in fact a bijection!

Motivation Characterization Enumeration Proper Mergings of Two Chains

The Bijection

I plane partition π: a rectangular array which is weakly decreasing along rows and columns

I part of π: an entryπi,j in the array

I given a proper merging (R,T) of c andc⁰, define a plane partitionπ withm rows, n columns and largest part at most 2 as follows:

π_i,j =







2, if (c_i,c_n−j+1⁰ )∈R 0, if (c_n−j+1⁰ ,ci)∈T 1, otherwise

I this is in fact a bijection!

Motivation Characterization Enumeration Proper Mergings of Two Chains

The Bijection

I plane partition π: a rectangular array which is weakly decreasing along rows and columns

I part of π: an entryπi,j in the array

I given a proper merging (R,T) of c andc⁰, define a plane partitionπ withm rows, n columns and largest part at most 2 as follows:

π_i,j =







2, if (c_i,c_n−j+1⁰ )∈R 0, if (c_n−j+1⁰ ,ci)∈T 1, otherwise

I this is in fact a bijection!

Motivation Characterization Enumeration Proper Mergings of Two Chains

The Enumeration

I the enumeration of plane partitions is classical Theorem (MacMahon)

The numberπ(m,n,l) of plane partitions with m rows, n columns and largest part at most l is given by

π(m,n,l) =

m

Y

i=1 n

Y

j=1 l

Y

k=1

i+j+k−1 i+j+k−2.

Motivation Characterization Enumeration Proper Mergings of Two Chains

The Enumeration

I in view of the bijection from before, we obtain the following result

Theorem

The number F_c(m,n) of proper mergings of an m-chain and an n-chain is given by

Fc(m,n) =π(m,n,2) = 1 m+n+ 1

m+n+ 1 m+ 1

m+n+ 1 m

.

I Fc(m,n) = Nar(m+n+ 1,m+ 1)

Motivation Characterization Enumeration Proper Mergings of Two Chains

The Enumeration

I in view of the bijection from before, we obtain the following result

Theorem

The number F_c(m,n) of proper mergings of an m-chain and an n-chain is given by

Fc(m,n) =π(m,n,2) = 1 m+n+ 1

m+n+ 1 m+ 1

m+n+ 1 m

.

I Fc(m,n) = Nar(m+n+ 1,m+ 1)

Motivation Characterization Enumeration Proper Mergings of Two Antichains

Outline

1 Motivation

2 Characterization

3 Enumeration

Proper Mergings of Two Chains Proper Mergings of Two Antichains

Proper Mergings of an Antichain and a Chain

Motivation Characterization Enumeration Proper Mergings of Two Antichains

Preparation

I let A={a₁,a₂, . . . ,a_n}be a set and define a_i =_aa_j if and only if i =j

a= (A,=a) is an antichain

I thus, the extents and intents of 6=_a are precisely the subsets of A

Motivation Characterization Enumeration Proper Mergings of Two Antichains

Preparation

I let A={a₁,a₂, . . . ,a_n}be a set and define a_i =_aa_j if and only if i =j a= (A,=a) is an antichain

I thus, the extents and intents of 6=_a are precisely the subsets of A

Motivation Characterization Enumeration Proper Mergings of Two Antichains

Preparation

I let A={a₁,a₂, . . . ,a_n}be a set and define a_i =_aa_j if and only if i =j a= (A,=a) is an antichain

a₁ a₂ a₃ a₄

I thus, the extents and intents of 6=_a are precisely the subsets of A

Motivation Characterization Enumeration Proper Mergings of Two Antichains

Preparation

I let A={a₁,a₂, . . . ,a_n}be a set and define a_i =_aa_j if and only if i =j a= (A,=a) is an antichain

a₁ a₂ a₃ a₄

=_a a₁ a₂ a₃ a₄

a₁ ×

a₂ ×

a₃ ×

a4 ×

I thus, the extents and intents of 6=_a are precisely the subsets of A

Motivation Characterization Enumeration Proper Mergings of Two Antichains

Preparation

I let A={a₁,a₂, . . . ,a_n}be a set and define a_i =_aa_j if and only if i =j a= (A,=a) is an antichain

a₁ a₂ a₃ a₄

=_a a₁ a₂ a₃ a₄

a₁ ×

a₂ ×

a₃ ×

a4 ×

6=_a a₁ a₂ a₃ a₄

a₁ × × ×

a₂ × × ×

a₃ × × ×

a4 × × ×

I thus, the extents and intents of 6=_a are precisely the subsets of A

Motivation Characterization Enumeration Proper Mergings of Two Antichains

Preparation

I let A={a₁,a₂, . . . ,a_n}be a set and define a_i =_aa_j if and only if i =j a= (A,=a) is an antichain

a₁ a₂ a₃ a₄

=_a a₁ a₂ a₃ a₄

a₁ ×

a₂ ×

a₃ ×

a4 ×

6=_a a₁ a₂ a₃ a₄

a₁ × × ×

a₂ × × ×

a₃ × × ×

a4 × × ×

I thus, the extents and intents of 6=_a are precisely the subsets of A

Motivation Characterization Enumeration Proper Mergings of Two Antichains

The Idea

I unfortunately, we have no idea of a bijection between proper mergings of two antichains and some other mathematical objects

I but, we have an idea for a generating function approach

I the Hasse diagram of a proper merging of two antichains can be considered as a bipartite graph

I every connected component of such a Hasse diagram can occur in two variations

, unless this component is just a single node

Motivation Characterization Enumeration Proper Mergings of Two Antichains

The Idea

I unfortunately, we have no idea of a bijection between proper mergings of two antichains and some other mathematical objects

I but, we have an idea for a generating function approach

I the Hasse diagram of a proper merging of two antichains can be considered as a bipartite graph

I every connected component of such a Hasse diagram can occur in two variations

, unless this component is just a single node

Motivation Characterization Enumeration Proper Mergings of Two Antichains

The Idea

I unfortunately, we have no idea of a bijection between proper mergings of two antichains and some other mathematical objects

I but, we have an idea for a generating function approach

I the Hasse diagram of a proper merging of two antichains can be considered as a bipartite graph

I every connected component of such a Hasse diagram can occur in two variations

, unless this component is just a single node

Motivation Characterization Enumeration Proper Mergings of Two Antichains

The Idea

I unfortunately, we have no idea of a bijection between proper mergings of two antichains and some other mathematical objects

I but, we have an idea for a generating function approach

I the Hasse diagram of a proper merging of two antichains can be considered as a bipartite graph

I every connected component of such a Hasse diagram can occur in two variations, unless this component is just a single node

Motivation Characterization Enumeration Proper Mergings of Two Antichains

The Generating Function

I let B(x,y) denote the bivariate exponential generating function for bipartite graphs, and let B_c(x,y) denote the bivariate exponential generating function for connected bipartite graphs

I we clearly have

B(x,y) =X

n≥0

X

m≥0

2^mnx^myⁿ m!n!

I since every bipartite graph can be considered as a collection of connected bipartite graphs, we obtain

B(x,y) = exp Bc(x,y)

Motivation Characterization Enumeration Proper Mergings of Two Antichains

The Generating Function

I let G(x,y) denote the bivariate exponential generating function for proper mergings of two antichains

I we obtain

G(x,y) = exp(2·Bc(x,y)−x−y)

= exp(2·logB(x,y)−x−y)

=B(x,y)²−exp(x)−exp(y)

=X

2^n1n2+m1m2(−1)^k1(−1)^k2

· x^n1+m1+k1

n₁!m₁!k₁! · y^n2+m2+k2 n₂!m₂!k₂!

Motivation Characterization Enumeration Proper Mergings of Two Antichains

The Enumeration

I the number of proper mergings of an m-antichain and an n-antichain is given by the coefficient of ^x_m!^my_n!ⁿ inG(x,y) Theorem

The number Fa(m,n) of proper mergings of an m-antichain and an n-antichain is given by

Fa(m,n) = X

k1+m1+n1=m

m k1,m1,n1

−1k1

2^m1+ 2ⁿ¹−1n

.

Motivation Characterization Enumeration Proper Mergings of an Antichain and a Chain

Outline

1 Motivation

2 Characterization

3 Enumeration

Proper Mergings of Two Chains Proper Mergings of Two Antichains

Proper Mergings of an Antichain and a Chain

Motivation Characterization Enumeration Proper Mergings of an Antichain and a Chain

The Idea

I let A={a₁,a₂, . . . ,a_m} andC ={c₁,c₂, . . . ,c_n}be sets, and let a= (A,=a) be anm-antichain and c= (C,≤_c) be an n-chain

I recall that the intents and extents of 6=_a are just subsets ofA, and the extents of6≥_c are of the form{c₁,c₂, . . . ,c_k} and the intents are of the form {c_k,c_k+1, . . . ,c_n}

Motivation Characterization Enumeration Proper Mergings of an Antichain and a Chain

The Idea

I let A={a₁,a₂, . . . ,a_m} andC ={c₁,c₂, . . . ,c_n}be sets, and let a= (A,=a) be anm-antichain and c= (C,≤_c) be an n-chain

I recall that the intents and extents of 6=_a are just subsets ofA, and the extents of6≥_c are of the form{c₁,c₂, . . . ,c_k} and the intents are of the form {c_k,c_k+1, . . . ,c_n}

I if (R,T) is a merging of a andc, then R must be right-justified and T must be top-justified

R

C

A

T

C A

Motivation Characterization Enumeration Proper Mergings of an Antichain and a Chain

The Idea

I let A={a₁,a₂, . . . ,a_m} andC ={c₁,c₂, . . . ,c_n}be sets, and let a= (A,=a) be anm-antichain and c= (C,≤_c) be an n-chain

I recall that the intents and extents of 6=_a are just subsets ofA, and the extents of6≥_c are of the form{c₁,c₂, . . . ,c_k} and the intents are of the form {c_k,c_k+1, . . . ,c_n}

I if (R,T) is a proper merging of a andc, then R andT must

“fit together”

R T

C

A

Motivation Characterization Enumeration Proper Mergings of an Antichain and a Chain

The Idea

I let A={a₁,a₂, . . . ,a_m} andC ={c₁,c₂, . . . ,c_n}be sets, and let a= (A,=a) be anm-antichain and c= (C,≤_c) be an n-chain

I recall that the intents and extents of 6=_a are just subsets ofA, and the extents of6≥_c are of the form{c₁,c₂, . . . ,c_k} and the intents are of the form {c_k,c_k+1, . . . ,c_n}

I if (R,T) is a proper merging of a andc, then R andT must

“fit together”

R T

C

A