Documentation

Mathlib.Combinatorics.Young.YoungDiagram

Young diagrams #

A Young diagram is a finite set of up-left justified boxes:

□□□□□
□□□
□□□
□

This Young diagram corresponds to the [5, 3, 3, 1] partition of 12.

We represent it as a lower set in ℕ × ℕ in the product partial order. We write (i, j) ∈ μ to say that (i, j) (in matrix coordinates) is in the Young diagram μ.

Main definitions #

YoungDiagram : Young diagrams
YoungDiagram.card : the number of cells in a Young diagram (its cardinality)
YoungDiagram.instDistribLatticeYoungDiagram : a distributive lattice instance for Young diagrams ordered by containment, with (⊥ : YoungDiagram) the empty diagram.
YoungDiagram.row and YoungDiagram.rowLen: rows of a Young diagram and their lengths
YoungDiagram.col and YoungDiagram.colLen: columns of a Young diagram and their lengths

Notation #

In "English notation", a Young diagram is drawn so that (i1, j1) ≤ (i2, j2) means (i1, j1) is weakly up-and-left of (i2, j2). This terminology is used below, e.g. in YoungDiagram.up_left_mem.

Tags #

Young diagram

References #

https://en.wikipedia.org/wiki/Young_tableau

structure YoungDiagram :

A Young diagram is a finite collection of cells on the ℕ × ℕ grid such that whenever a cell is present, so are all the ones above and to the left of it. Like matrices, an (i, j) cell is a cell in row i and column j, where rows are enumerated downward and columns rightward.

Young diagrams are modeled as finite sets in ℕ × ℕ that are lower sets with respect to the standard order on products.

cells : Finset (ℕ × ℕ)
A finite set which represents a finite collection of cells on the ℕ × ℕ grid.
isLowerSet : IsLowerSet ↑self.cells
Cells are up-left justified, witnessed by the fact that cells is a lower set in ℕ × ℕ.

theorem YoungDiagram.ext {x y : YoungDiagram} (cells : x.cells = y.cells) :

instance YoungDiagram.instSetLikeProdNat :

SetLike YoungDiagram (ℕ × ℕ)

Equations

YoungDiagram.instSetLikeProdNat = { coe := fun (y : YoungDiagram) => ↑y.cells, coe_injective' := YoungDiagram.instSetLikeProdNat.proof_1 }

@[simp]

theorem YoungDiagram.mem_cells {μ : YoungDiagram} (c : ℕ × ℕ) :

c ∈ μ.cells ↔ c ∈ μ

@[simp]

theorem YoungDiagram.mem_mk (c : ℕ × ℕ) (cells : Finset (ℕ × ℕ)) (isLowerSet : IsLowerSet ↑cells) :

c ∈ { cells := cells, isLowerSet := isLowerSet } ↔ c ∈ cells

instance YoungDiagram.decidableMem (μ : YoungDiagram) :

DecidablePred fun (x : ℕ × ℕ) => x ∈ μ

Equations

μ.decidableMem = inferInstanceAs (DecidablePred fun (x : ℕ × ℕ) => x ∈ μ.cells)

theorem YoungDiagram.up_left_mem (μ : YoungDiagram) {i1 i2 j1 j2 : ℕ} (hi : i1 ≤ i2) (hj : j1 ≤ j2) (hcell : (i2, j2) ∈ μ) :

(i1, j1) ∈ μ

In "English notation", a Young diagram is drawn so that (i1, j1) ≤ (i2, j2) means (i1, j1) is weakly up-and-left of (i2, j2).

@[simp]

theorem YoungDiagram.cells_subset_iff {μ ν : YoungDiagram} :

μ.cells ⊆ ν.cells ↔ μ ≤ ν

@[simp]

theorem YoungDiagram.cells_ssubset_iff {μ ν : YoungDiagram} :

μ.cells ⊂ ν.cells ↔ μ < ν

instance YoungDiagram.instMax :

Max YoungDiagram

Equations

YoungDiagram.instMax = { max := fun (μ ν : YoungDiagram) => { cells := μ.cells ∪ ν.cells, isLowerSet := ⋯ } }

@[simp]

theorem YoungDiagram.cells_sup (μ ν : YoungDiagram) :

(μ ⊔ ν).cells = μ.cells ∪ ν.cells

@[simp]

theorem YoungDiagram.coe_sup (μ ν : YoungDiagram) :

↑(μ ⊔ ν) = ↑μ ∪ ↑ν

@[simp]

theorem YoungDiagram.mem_sup {μ ν : YoungDiagram} {x : ℕ × ℕ} :

x ∈ μ ⊔ ν ↔ x ∈ μ ∨ x ∈ ν

instance YoungDiagram.instMin :

Min YoungDiagram

Equations

YoungDiagram.instMin = { min := fun (μ ν : YoungDiagram) => { cells := μ.cells ∩ ν.cells, isLowerSet := ⋯ } }

@[simp]

theorem YoungDiagram.cells_inf (μ ν : YoungDiagram) :

(μ ⊓ ν).cells = μ.cells ∩ ν.cells

@[simp]

theorem YoungDiagram.coe_inf (μ ν : YoungDiagram) :

↑(μ ⊓ ν) = ↑μ ∩ ↑ν

@[simp]

theorem YoungDiagram.mem_inf {μ ν : YoungDiagram} {x : ℕ × ℕ} :

x ∈ μ ⊓ ν ↔ x ∈ μ ∧ x ∈ ν

instance YoungDiagram.instOrderBot :

OrderBot YoungDiagram

The empty Young diagram is (⊥ : young_diagram).

Equations

YoungDiagram.instOrderBot = OrderBot.mk YoungDiagram.instOrderBot.proof_2

@[simp]

theorem YoungDiagram.cells_bot :

⊥.cells = ∅

@[simp]

theorem YoungDiagram.not_mem_bot (x : ℕ × ℕ) :

x ∉ ⊥

theorem YoungDiagram.coe_bot :

instance YoungDiagram.instInhabited :

Inhabited YoungDiagram

Equations

YoungDiagram.instInhabited = { default := ⊥ }

instance YoungDiagram.instDistribLattice :

DistribLattice YoungDiagram

Equations

One or more equations did not get rendered due to their size.

@[reducible, inline]

abbrev YoungDiagram.card (μ : YoungDiagram) :

Cardinality of a Young diagram

Equations

μ.card = μ.cells.card

def YoungDiagram.transpose (μ : YoungDiagram) :

The transpose of a Young diagram is obtained by swapping i's with j's.

Equations

μ.transpose = { cells := (Equiv.prodComm ℕ ℕ).finsetCongr μ.cells, isLowerSet := ⋯ }

@[simp]

theorem YoungDiagram.mem_transpose {μ : YoungDiagram} {c : ℕ × ℕ} :

c ∈ μ.transpose ↔ c.swap ∈ μ

@[simp]

theorem YoungDiagram.transpose_transpose (μ : YoungDiagram) :

μ.transpose.transpose = μ

theorem YoungDiagram.transpose_eq_iff_eq_transpose {μ ν : YoungDiagram} :

μ.transpose = ν ↔ μ = ν.transpose

@[simp]

theorem YoungDiagram.transpose_eq_iff {μ ν : YoungDiagram} :

μ.transpose = ν.transpose ↔ μ = ν

theorem YoungDiagram.le_of_transpose_le {μ ν : YoungDiagram} (h_le : μ.transpose ≤ ν) :

μ ≤ ν.transpose

@[simp]

theorem YoungDiagram.transpose_le_iff {μ ν : YoungDiagram} :

μ.transpose ≤ ν.transpose ↔ μ ≤ ν

theorem YoungDiagram.transpose_mono {μ ν : YoungDiagram} (h_le : μ ≤ ν) :

μ.transpose ≤ ν.transpose

def YoungDiagram.transposeOrderIso :

YoungDiagram ≃o YoungDiagram

Transposing Young diagrams is an OrderIso.

Equations

One or more equations did not get rendered due to their size.

@[simp]

theorem YoungDiagram.transposeOrderIso_symm_apply (μ : YoungDiagram) :

(RelIso.symm transposeOrderIso) μ = μ.transpose

@[simp]

theorem YoungDiagram.transposeOrderIso_apply (μ : YoungDiagram) :

transposeOrderIso μ = μ.transpose

Rows and row lengths of Young diagrams. #

This section defines μ.row and μ.rowLen, with the following API: 1. (i, j) ∈ μ ↔ j < μ.rowLen i 2. μ.row i = {i} ×ˢ (Finset.range (μ.rowLen i)) 3. μ.rowLen i = (μ.row i).card 4. ∀ {i1 i2}, i1 ≤ i2 → μ.rowLen i2 ≤ μ.rowLen i1

Note: #3 is not convenient for defining μ.rowLen; instead, μ.rowLen is defined as the smallest j such that (i, j) ∉ μ.

def YoungDiagram.row (μ : YoungDiagram) (i : ℕ) :

Finset (ℕ × ℕ)

The i-th row of a Young diagram consists of the cells whose first coordinate is i.

Equations

μ.row i = Finset.filter (fun (c : ℕ × ℕ) => c.1 = i) μ.cells

theorem YoungDiagram.mem_row_iff {μ : YoungDiagram} {i : ℕ} {c : ℕ × ℕ} :

c ∈ μ.row i ↔ c ∈ μ ∧ c.1 = i

theorem YoungDiagram.mk_mem_row_iff {μ : YoungDiagram} {i j : ℕ} :

(i, j) ∈ μ.row i ↔ (i, j) ∈ μ

theorem YoungDiagram.exists_not_mem_row (μ : YoungDiagram) (i : ℕ) :

∃ (j : ℕ), (i, j) ∉ μ

def YoungDiagram.rowLen (μ : YoungDiagram) (i : ℕ) :

Length of a row of a Young diagram

Equations

μ.rowLen i = Nat.find ⋯

theorem YoungDiagram.mem_iff_lt_rowLen {μ : YoungDiagram} {i j : ℕ} :

(i, j) ∈ μ ↔ j < μ.rowLen i

theorem YoungDiagram.row_eq_prod {μ : YoungDiagram} {i : ℕ} :

μ.row i = {i} ×ˢ Finset.range (μ.rowLen i)

theorem YoungDiagram.rowLen_eq_card (μ : YoungDiagram) {i : ℕ} :

μ.rowLen i = (μ.row i).card

theorem YoungDiagram.rowLen_anti (μ : YoungDiagram) (i1 i2 : ℕ) (hi : i1 ≤ i2) :

μ.rowLen i2 ≤ μ.rowLen i1

Columns and column lengths of Young diagrams. #

This section has an identical API to the rows section.

def YoungDiagram.col (μ : YoungDiagram) (j : ℕ) :

Finset (ℕ × ℕ)

The j-th column of a Young diagram consists of the cells whose second coordinate is j.

Equations

μ.col j = Finset.filter (fun (c : ℕ × ℕ) => c.2 = j) μ.cells

theorem YoungDiagram.mem_col_iff {μ : YoungDiagram} {j : ℕ} {c : ℕ × ℕ} :

c ∈ μ.col j ↔ c ∈ μ ∧ c.2 = j

theorem YoungDiagram.mk_mem_col_iff {μ : YoungDiagram} {i j : ℕ} :

(i, j) ∈ μ.col j ↔ (i, j) ∈ μ

theorem YoungDiagram.exists_not_mem_col (μ : YoungDiagram) (j : ℕ) :

∃ (i : ℕ), (i, j) ∉ μ.cells

def YoungDiagram.colLen (μ : YoungDiagram) (j : ℕ) :

Length of a column of a Young diagram

Equations

μ.colLen j = Nat.find ⋯

@[simp]

theorem YoungDiagram.colLen_transpose (μ : YoungDiagram) (j : ℕ) :

μ.transpose.colLen j = μ.rowLen j

@[simp]

theorem YoungDiagram.rowLen_transpose (μ : YoungDiagram) (i : ℕ) :

μ.transpose.rowLen i = μ.colLen i

theorem YoungDiagram.mem_iff_lt_colLen {μ : YoungDiagram} {i j : ℕ} :

(i, j) ∈ μ ↔ i < μ.colLen j

theorem YoungDiagram.col_eq_prod {μ : YoungDiagram} {j : ℕ} :

μ.col j = Finset.range (μ.colLen j) ×ˢ {j}

theorem YoungDiagram.colLen_eq_card (μ : YoungDiagram) {j : ℕ} :

μ.colLen j = (μ.col j).card

theorem YoungDiagram.colLen_anti (μ : YoungDiagram) (j1 j2 : ℕ) (hj : j1 ≤ j2) :

μ.colLen j2 ≤ μ.colLen j1

The list of row lengths of a Young diagram #

This section defines μ.rowLens : List ℕ, the list of row lengths of a Young diagram μ.

YoungDiagram.rowLens_sorted : It is weakly decreasing (List.Sorted (· ≥ ·)).
YoungDiagram.rowLens_pos : It is strictly positive.

def YoungDiagram.rowLens (μ : YoungDiagram) :

List of row lengths of a Young diagram

Equations

μ.rowLens = List.map μ.rowLen (List.range (μ.colLen 0))

@[simp]

theorem YoungDiagram.get_rowLens {μ : YoungDiagram} {i : ℕ} {h : i < μ.rowLens.length} :

μ.rowLens [i] = μ.rowLen i

@[simp]

theorem YoungDiagram.length_rowLens {μ : YoungDiagram} :

μ.rowLens.length = μ.colLen 0

theorem YoungDiagram.rowLens_sorted (μ : YoungDiagram) :

List.Sorted (fun (x1 x2 : ℕ) => x1 ≥ x2) μ.rowLens

theorem YoungDiagram.pos_of_mem_rowLens (μ : YoungDiagram) (x : ℕ) (hx : x ∈ μ.rowLens) :

Equivalence between Young diagrams and lists of natural numbers #

This section defines the equivalence between Young diagrams μ and weakly decreasing lists w of positive natural numbers, corresponding to row lengths of the diagram: YoungDiagram.equivListRowLens : YoungDiagram ≃ {w : List ℕ // w.Sorted (· ≥ ·) ∧ ∀ x ∈ w, 0 < x}

The two directions are YoungDiagram.rowLens (defined above) and YoungDiagram.ofRowLens.

def YoungDiagram.cellsOfRowLens :

List ℕ → Finset (ℕ × ℕ)

The cells making up a YoungDiagram from a list of row lengths

Equations

One or more equations did not get rendered due to their size.
YoungDiagram.cellsOfRowLens [] = ∅

theorem YoungDiagram.mem_cellsOfRowLens {w : List ℕ} {c : ℕ × ℕ} :

c ∈ YoungDiagram.cellsOfRowLens w ↔ ∃ (h : c.1 < w.length), c.2 < w [c.1]

def YoungDiagram.ofRowLens (w : List ℕ) (hw : List.Sorted (fun (x1 x2 : ℕ) => x1 ≥ x2) w) :

Young diagram from a sorted list

Equations

YoungDiagram.ofRowLens w hw = { cells := YoungDiagram.cellsOfRowLens w, isLowerSet := ⋯ }

theorem YoungDiagram.mem_ofRowLens {w : List ℕ} {hw : List.Sorted (fun (x1 x2 : ℕ) => x1 ≥ x2) w} {c : ℕ × ℕ} :

c ∈ ofRowLens w hw ↔ ∃ (h : c.1 < w.length), c.2 < w [c.1]

theorem YoungDiagram.rowLens_length_ofRowLens {w : List ℕ} {hw : List.Sorted (fun (x1 x2 : ℕ) => x1 ≥ x2) w} (hpos : ∀ x ∈ w, 0 < x) :

(ofRowLens w hw).rowLens.length = w.length

The number of rows in ofRowLens w hw is the length of w

theorem YoungDiagram.rowLen_ofRowLens {w : List ℕ} {hw : List.Sorted (fun (x1 x2 : ℕ) => x1 ≥ x2) w} (i : Fin w.length) :

(ofRowLens w hw).rowLen ↑i = w [i]

The length of the ith row in ofRowLens w hw is the ith entry of w

theorem YoungDiagram.ofRowLens_to_rowLens_eq_self {μ : YoungDiagram} :

ofRowLens μ.rowLens ⋯ = μ

The left_inv direction of the equivalence

theorem YoungDiagram.rowLens_ofRowLens_eq_self {w : List ℕ} {hw : List.Sorted (fun (x1 x2 : ℕ) => x1 ≥ x2) w} (hpos : ∀ x ∈ w, 0 < x) :

(ofRowLens w hw).rowLens = w

The right_inv direction of the equivalence

def YoungDiagram.equivListRowLens :

YoungDiagram ≃ { w : List ℕ // List.Sorted (fun (x1 x2 : ℕ) => x1 ≥ x2) w ∧ ∀ x ∈ w, 0 < x }

Equivalence between Young diagrams and weakly decreasing lists of positive natural numbers. A Young diagram μ is equivalent to a list of row lengths.

Equations

One or more equations did not get rendered due to their size.

@[simp]

theorem YoungDiagram.equivListRowLens_apply_coe (μ : YoungDiagram) :

↑(equivListRowLens μ) = μ.rowLens

@[simp]

theorem YoungDiagram.equivListRowLens_symm_apply (ww : { w : List ℕ // List.Sorted (fun (x1 x2 : ℕ) => x1 ≥ x2) w ∧ ∀ x ∈ w, 0 < x }) :

equivListRowLens.symm ww = ofRowLens ↑ww ⋯