Documentation

Linglib.Core.Data.Multiset.Antidiagonal

Splits in Multiset.antidiagonal #

Multiset.antidiagonal w enumerates the ordered splits w = p.1 + p.2 with multiplicities. This file reads it off a list's sublists', slices it by the size of the first part, and counts a split through Multiset.powerset.

Main results #

theorem Multiset.antidiagonal_coe_sublists' {α : Type u_1} (l : List α) :
(↑l).antidiagonal = ↑(List.map (fun (p : List α × List α) => (↑p.1, ↑p.2)) l.sublists'.revzip)

antidiagonal of a coerced list enumerates sublists'.revzip.

theorem Multiset.filter_card_fst_eq_antidiagonal {α : Type u_1} [DecidableEq α] (s : Multiset α) (k : ℕ) :
filter (fun (p : Multiset α × Multiset α) => p.1.card = k) s.antidiagonal = map (fun (t : Multiset α) => (t, s - t)) (powersetCard k s)

The splits of s whose first part has k elements are the k-element sub-multisets of s paired with their complements (Finset.HasAntidiagonal.filter_fst_eq_antidiagonal analogue).

theorem Multiset.count_antidiagonal_eq_count_powerset {α : Type u_1} [DecidableEq α] (s t : Multiset α) :
count (s, t) (s + t).antidiagonal = count t (s + t).powerset

The multiplicity of (s, t) in antidiagonal (s + t) is the number of ways to select the sub-multiset t from s + t.