Documentation

Linglib.Core.Data.Multiset.Powerset

Slicing, splitting and counting Multiset.powerset #

powersetCard n as a slice of powerset, sums over the splits l.sublists'.revzip of a list, and the multiplicity of s in t.powerset as a product of binomial coefficients: a sub-multiset picks s.count x of the t.count x copies of each distinct x. (This product of binomials is not Nat.multinomial, which is the quotient (∑ᵢ kᵢ)! / ∏ᵢ kᵢ!.)

Main results #

Implementation notes #

The count is proved over a fixed ambient Finset containing both supports (count_powerset_subset), so the index set stays constant through the induction.

theorem Multiset.powersetCard_eq_filter {α : Type u_1} {n : ℕ} {s : Multiset α} :
powersetCard n s = filter (fun (t : Multiset α) => t.card = n) s.powerset

powersetCard n s is the slice of powerset s with n elements (Finset.powersetCard_eq_filter analogue).

Sums over sublists'.revzip #

theorem Multiset.bind_revzip_sublists'_swap {α : Type u_1} {β : Type u_2} (l : List α) (F : List α → List α → Multiset β) :
((↑l.sublists'.revzip).bind fun (p : List α × List α) => F p.1 p.2) = (↑l.sublists'.revzip).bind fun (p : List α × List α) => F p.2 p.1

Swapping the two buckets of every split enumerates the same splits.

theorem Multiset.bind_revzip_sublists'_assoc {α : Type u_1} {β : Type u_2} (l : List α) (K : List α → List α → List α → Multiset β) :
((↑l.sublists'.revzip).bind fun (p : List α × List α) => (↑p.2.sublists'.revzip).bind fun (q : List α × List α) => K p.1 q.1 q.2) = (↑l.sublists'.revzip).bind fun (p : List α × List α) => (↑p.1.sublists'.revzip).bind fun (q : List α × List α) => K q.1 q.2 p.2

Nested splits reassociate. Splitting the second bucket of every split enumerates the same ordered triples as splitting the first bucket.

theorem Multiset.bind_bind_bind_comm {α : Type u_1} {β : Type u_2} {γ : Type u_3} {δ : Type u_4} (m : Multiset α) (n : α → Multiset β) (o : Multiset γ) (f : α → β → γ → Multiset δ) :
(m.bind fun (a : α) => (n a).bind fun (b : β) => o.bind fun (c : γ) => f a b c) = o.bind fun (c : γ) => m.bind fun (a : α) => (n a).bind fun (b : β) => f a b c
theorem Multiset.bind_revzip_sublists'_bind_assoc {α : Type u_1} {β : Type u_2} {γ : Type u_3} (l : List α) (S : List α → Multiset β) (F : β → List α → List α → Multiset γ) :
((↑l.sublists'.revzip).bind fun (p : List α × List α) => (S p.1).bind fun (a : β) => (↑p.2.sublists'.revzip).bind fun (q : List α × List α) => F a q.1 q.2) = (↑l.sublists'.revzip).bind fun (q : List α × List α) => (↑q.2.sublists'.revzip).bind fun (q' : List α × List α) => (S q'.1).bind fun (a : β) => F a q.1 q'.2
theorem Multiset.bind_revzip_sublists'_bind_assoc' {α : Type u_1} {β : Type u_2} {γ : Type u_3} (l : List α) (S : List α → Multiset β) (F : β → List α → List α → Multiset γ) :
((↑l.sublists'.revzip).bind fun (p : List α × List α) => (S p.1).bind fun (a : β) => (↑p.2.sublists'.revzip).bind fun (q : List α × List α) => F a q.1 q.2) = (↑l.sublists'.revzip).bind fun (q : List α × List α) => (↑q.1.sublists'.revzip).bind fun (q' : List α × List α) => (S q'.1).bind fun (a : β) => F a q'.2 q.2
theorem Multiset.count_powerset_of_le {α : Type u_1} [DecidableEq α] {s t : Multiset α} (h : s ≤ t) :
count s t.powerset = ∏ x ∈ t.toFinset, (count x t).choose (count x s)

Count of a sub-multiset s ≤ t among the sub-multisets of t: for each distinct x, choose s.count x of the t.count x copies.

@[simp]
theorem Multiset.count_zero_powerset {α : Type u_1} [DecidableEq α] (t : Multiset α) :
count 0 t.powerset = 1
@[simp]
theorem Multiset.count_powerset_self {α : Type u_1} [DecidableEq α] (t : Multiset α) :
count t t.powerset = 1