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 #
Multiset.antidiagonal_coe_sublists': the splits of a list are itssublists'.revzip.Multiset.filter_card_fst_eq_antidiagonal: the splits whose first part haskelements are indexed bypowersetCard k.Multiset.count_antidiagonal_eq_count_powerset: the multiplicity of a split is that of its second part in the powerset.
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.