The powerset of a multiset

powerset

def Multiset.powersetAux {α : Type u_1} (l : List α) : List (Multiset α)

A helper function for the powerset of a multiset. Given a list l, returns a list of sublists of l as multisets.

Equations

• Multiset.powersetAux l = List.map Multiset.ofList l.sublists

theorem Multiset.powersetAux_eq_map_coe {α : Type u_1} {l : List α} : powersetAux l = List.map ofList l.sublists

@[simp]

theorem Multiset.mem_powersetAux {α : Type u_1} {l : List α} {s : Multiset α} : s ∈ powersetAux l ↔ s ≤ ↑l

def Multiset.powersetAux' {α : Type u_1} (l : List α) : List (Multiset α)

Helper function for the powerset of a multiset. Given a list l, returns a list of sublists of l (using sublists'), as multisets.

Equations

• Multiset.powersetAux' l = List.map Multiset.ofList l.sublists'

theorem Multiset.powersetAux_perm_powersetAux' {α : Type u_1} {l : List α} : (powersetAux l).Perm (powersetAux' l)

@[simp]

theorem Multiset.powersetAux'_nil {α : Type u_1} : powersetAux' [] = [0]

@[simp]

theorem Multiset.powersetAux'_cons {α : Type u_1} (a : α) (l : List α) : powersetAux' (a :: l) = powersetAux' l ++ List.map (cons a) (powersetAux' l)

theorem Multiset.powerset_aux'_perm {α : Type u_1} {l₁ l₂ : List α} (p : l₁.Perm l₂) : (powersetAux' l₁).Perm (powersetAux' l₂)

theorem Multiset.powersetAux_perm {α : Type u_1} {l₁ l₂ : List α} (p : l₁.Perm l₂) : (powersetAux l₁).Perm (powersetAux l₂)

def Multiset.powerset {α : Type u_1} (s : Multiset α) : Multiset (Multiset α)

The power set of a multiset.

Equations

• s.powerset = Quot.liftOn s (fun (l : List α) => ↑(Multiset.powersetAux l)) ⋯

theorem Multiset.powerset_coe {α : Type u_1} (l : List α) : (↑l).powerset = ↑(List.map ofList l.sublists)

@[simp]

theorem Multiset.powerset_coe' {α : Type u_1} (l : List α) : (↑l).powerset = ↑(List.map ofList l.sublists')

@[simp]

theorem Multiset.powerset_zero {α : Type u_1} : powerset 0 = {0}

@[simp]

theorem Multiset.powerset_cons {α : Type u_1} (a : α) (s : Multiset α) : (a ::ₘ s).powerset = s.powerset + map (cons a) s.powerset

@[simp]

theorem Multiset.mem_powerset {α : Type u_1} {s t : Multiset α} : s ∈ t.powerset ↔ s ≤ t

theorem Multiset.map_single_le_powerset {α : Type u_1} (s : Multiset α) : map singleton s ≤ s.powerset

theorem Multiset.zero_mem_powerset {α : Type u_1} (s : Multiset α) : 0 ∈ s.powerset

theorem Multiset.self_mem_powerset {α : Type u_1} (s : Multiset α) : s ∈ s.powerset

@[simp]

theorem Multiset.card_powerset {α : Type u_1} (s : Multiset α) : s.powerset.card = 2 ^ s.card

@[simp]

theorem Multiset.powerset_eq_singleton_zero_iff {α : Type u_1} (s : Multiset α) : s.powerset = {0} ↔ s = 0

theorem Multiset.revzip_powersetAux {α : Type u_1} {l : List α} ⦃x : Multiset α × Multiset α⦄ (h : x ∈ (powersetAux l).revzip) : x.1 + x.2 = ↑l

theorem Multiset.revzip_powersetAux' {α : Type u_1} {l : List α} ⦃x : Multiset α × Multiset α⦄ (h : x ∈ (powersetAux' l).revzip) : x.1 + x.2 = ↑l

theorem Multiset.revzip_powersetAux_lemma {α : Type u_2} [DecidableEq α] (l : List α) {l' : List (Multiset α)} (H : ∀ ⦃x : Multiset α × Multiset α⦄, x ∈ l'.revzip → x.1 + x.2 = ↑l) : l'.revzip = List.map (fun (x : Multiset α) => (x, ↑l - x)) l'

theorem Multiset.revzip_powersetAux_perm_aux' {α : Type u_1} {l : List α} : (powersetAux l).revzip.Perm (powersetAux' l).revzip

theorem Multiset.revzip_powersetAux_perm {α : Type u_1} {l₁ l₂ : List α} (p : l₁.Perm l₂) : (powersetAux l₁).revzip.Perm (powersetAux l₂).revzip

@[simp]

theorem Multiset.powerset_le_powerset_iff_le {α : Type u_1} {s t : Multiset α} : s.powerset ≤ t.powerset ↔ s ≤ t

theorem Multiset.powerset_injective {α : Type u_1} : Function.Injective powerset

theorem Multiset.powerset_strictMono {α : Type u_1} : StrictMono powerset

theorem Multiset.powerset_mono {α : Type u_1} : Monotone powerset

powersetCard

def Multiset.powersetCardAux {α : Type u_1} (n : ℕ) (l : List α) : List (Multiset α)

Helper function for powersetCard. Given a list l, powersetCardAux n l is the list of sublists of length n, as multisets.

Equations

• Multiset.powersetCardAux n l = List.sublistsLenAux n l Multiset.ofList []

theorem Multiset.powersetCardAux_eq_map_coe {α : Type u_1} {n : ℕ} {l : List α} : powersetCardAux n l = List.map ofList (List.sublistsLen n l)

@[simp]

theorem Multiset.mem_powersetCardAux {α : Type u_1} {n : ℕ} {l : List α} {s : Multiset α} : s ∈ powersetCardAux n l ↔ s ≤ ↑l ∧ s.card = n

@[simp]

theorem Multiset.powersetCardAux_zero {α : Type u_1} (l : List α) : powersetCardAux 0 l = [0]

@[simp]

theorem Multiset.powersetCardAux_nil {α : Type u_1} (n : ℕ) : powersetCardAux (n + 1) [] = []

@[simp]

theorem Multiset.powersetCardAux_cons {α : Type u_1} (n : ℕ) (a : α) (l : List α) : powersetCardAux (n + 1) (a :: l) = powersetCardAux (n + 1) l ++ List.map (cons a) (powersetCardAux n l)

theorem Multiset.powersetCardAux_perm {α : Type u_1} {n : ℕ} {l₁ l₂ : List α} (p : l₁.Perm l₂) : (powersetCardAux n l₁).Perm (powersetCardAux n l₂)

def Multiset.powersetCard {α : Type u_1} (n : ℕ) (s : Multiset α) : Multiset (Multiset α)

powersetCard n s is the multiset of all submultisets of s of length n.

Equations

• Multiset.powersetCard n s = Quot.liftOn s (fun (l : List α) => ↑(Multiset.powersetCardAux n l)) ⋯

theorem Multiset.powersetCard_coe' {α : Type u_1} (n : ℕ) (l : List α) : powersetCard n ↑l = ↑(powersetCardAux n l)

theorem Multiset.powersetCard_coe {α : Type u_1} (n : ℕ) (l : List α) : powersetCard n ↑l = ↑(List.map ofList (List.sublistsLen n l))

@[simp]

theorem Multiset.powersetCard_zero_left {α : Type u_1} (s : Multiset α) : powersetCard 0 s = {0}

theorem Multiset.powersetCard_zero_right {α : Type u_1} (n : ℕ) : powersetCard (n + 1) 0 = 0

@[simp]

theorem Multiset.powersetCard_cons {α : Type u_1} (n : ℕ) (a : α) (s : Multiset α) : powersetCard (n + 1) (a ::ₘ s) = powersetCard (n + 1) s + map (cons a) (powersetCard n s)

theorem Multiset.powersetCard_one {α : Type u_1} (s : Multiset α) : powersetCard 1 s = map singleton s

@[simp]

theorem Multiset.mem_powersetCard {α : Type u_1} {n : ℕ} {s t : Multiset α} : s ∈ powersetCard n t ↔ s ≤ t ∧ s.card = n

@[simp]

theorem Multiset.card_powersetCard {α : Type u_1} (n : ℕ) (s : Multiset α) : (powersetCard n s).card = s.card.choose n

theorem Multiset.powersetCard_le_powerset {α : Type u_1} (n : ℕ) (s : Multiset α) : powersetCard n s ≤ s.powerset

theorem Multiset.powersetCard_mono {α : Type u_1} (n : ℕ) {s t : Multiset α} (h : s ≤ t) : powersetCard n s ≤ powersetCard n t

@[simp]

theorem Multiset.powersetCard_eq_empty {α : Type u_2} (n : ℕ) {s : Multiset α} (h : s.card < n) : powersetCard n s = 0

theorem Multiset.powersetCard_card_add {α : Type u_1} (s : Multiset α) {i : ℕ} (hi : 0 < i) : powersetCard (s.card + i) s = 0

@[simp]

theorem Multiset.powersetCard_self {α : Type u_1} (s : Multiset α) : powersetCard s.card s = {s}

theorem Multiset.powersetCard_map {α : Type u_1} {β : Type u_2} (f : α → β) (n : ℕ) (s : Multiset α) : powersetCard n (map f s) = map (map f) (powersetCard n s)

theorem Disjoint.powersetCard_powersetCard_multiset {α : Type u_1} {s t : Multiset α} (h : Disjoint s t) {n m : ℕ} (hn : n ≠ 0 ∨ m ≠ 0) : Disjoint (Multiset.powersetCard n s) (Multiset.powersetCard m t)

theorem Multiset.disjoint_powersetCard_of_ne {α : Type u_1} {m n : ℕ} (h : m ≠ n) (s t : Multiset α) : Disjoint (powersetCard m s) (powersetCard n t)

theorem Multiset.pairwise_disjoint_powersetCard {α : Type u_1} (s : Multiset α) : _root_.Pairwise fun (i j : ℕ) => Disjoint (powersetCard i s) (powersetCard j s)

theorem Multiset.bind_powerset_len {α : Type u_2} (S : Multiset α) : ((range (S.card + 1)).bind fun (k : ℕ) => powersetCard k S) = S.powerset

@[simp]

theorem Multiset.nodup_powerset {α : Type u_1} {s : Multiset α} : s.powerset.Nodup ↔ s.Nodup

theorem Multiset.Nodup.powerset {α : Type u_1} {s : Multiset α} : s.Nodup → s.powerset.Nodup

Alias of the reverse direction of Multiset.nodup_powerset.

theorem Multiset.Nodup.ofPowerset {α : Type u_1} {s : Multiset α} : s.powerset.Nodup → s.Nodup

Alias of the forward direction of Multiset.nodup_powerset.

theorem Multiset.Nodup.powersetCard {α : Type u_1} {n : ℕ} {s : Multiset α} (h : s.Nodup) : (powersetCard n s).Nodup