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 #
Multiset.powersetCard_eq_filter:powersetCard nis then-element slice ofpowerset.Multiset.bind_revzip_sublists'_swap,Multiset.bind_revzip_sublists'_assoc: the splits of a list are symmetric, and nested splits reassociate.Multiset.count_powerset_of_le: fors ≤ t,t.powerset.count s = ∏ x ∈ t.toFinset, (t.count x).choose (s.count x).
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.
powersetCard n s is the slice of powerset s with n elements
(Finset.powersetCard_eq_filter analogue).
Sums over sublists'.revzip #
Swapping the two buckets of every split enumerates the same splits.
Nested splits reassociate. Splitting the second bucket of every split enumerates the same ordered triples as splitting the first bucket.
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.