Multiset

A multiset, or bag, is an unordered collection of elements where each element can have multiple instances. The number of instances an element has in a multiset is its multiplicity. Multisets are defined both by what elements they contain and their multiplicities. To visually distinguish them from sets, multisets are notated with square brackets.

To be concise, a multiset is like a set where repetitions matter. For example, $\set{0, 1, 2}$ and $\set{0, 1, 1, 2}$ are the same set, but not the same multiset: $[0, 1, 2] \neq [0, 1, 1, 2].$ Also, since multisets are unordered, $[0, 1, 1, 2] = [1, 2, 0, 1].$ Equal multisets not only have the same elements, but also the same number of each of them.

Contents

Cardinality

The cardinality of a finite multiset is the sum of the multiplicities of all its elements.

Counting multisets

Multisets appear in situations where elements are varied, and it is possible to have multiple instances of each. For example, imagine a customer wants to buy a dozen $(12)$ donuts from a well-stocked bakery. The donuts come in $3$ varieties: glazed $(G)$, pink-frosted $(P)$, and Boston cream $(B).$ For our purposes, each donut is indistinguishable from all other donuts of the same variety. One possible purchase is the multiset $[G, G, G, P, P, P, P, P, B, B, B, B]$ if the customer selects $3$ glazed, $5$ pink-frosted, and $4$ Boston cream donuts.

To count the number of ways to select $12$ donuts from $3$ varieties, we'll need to define a bijection to a set of easy-to-count codewords, which in this case will be binary strings that uniquely identify each purchase. You can unambiguously equate each purchase of donuts to a decision of where to place $2$ separators between $12$ objects to create $3$ groups. So, in each binary string, let $1$'s be our separators and let $0$'s be our objects. In the context of this problem, have the first group represent the glazed variety, the second group represent the pink-frosted variety, and the third group represent the Boston cream variety. The groups must always be ordered that way in every binary string. Then, $00010000010000$ would correspond a purchase of $3$ glazed, $5$ pink-frosted, and $4$ Boston cream donuts. See where we're going with this?

The number of bits in each binary string is exactly the number of donuts the customer wants to buy, plus the number of varieties minus $1$ (which is the number of separators). This totals to $12 + 3 - 1 = 14$ bits. To determine how many ways there are of placing these $2$ separators, we must ask: how many $14$-bit binary strings have exactly $2$ $1$'s? With a healthy understanding of combinations, one can quickly give an answer of $\binom{14}{2}.$ By the bijection rule, that's the same as the number of ways to select $12$ donuts from $3$ varieties. A general formula for answering questions like this is given below:

The number of multisets of cardinality $n$ that can be made from $m$ varieties of elements is: $$\binom{n + m - 1}{m - 1}$$ This is the number of ways there are of selecting $n$ elements from $m$ varieties, where elements of the same variety are indistinguishable and there is a limitless number of elements of each variety.

How many ways are there of selecting $12$ donuts from $3$ varieties? How many non-negative solutions are there to the equation $x + y + z = 12$? Believe it or not, the answer is the same for both questions. It helps to view $x$, $y$, and $z$ as the number of donuts you buy of the first, second, and third variety respectively.

⚠ Please do not brush aside the detail that only non-negative solutions are being counted. This is critical because the multiplicity of an element in a multiset can never be less than $0.$

How many ways are there of placing $12$ indistinguishable balls into $3$ distinguishable bins? The answer is still the same as before, but now this is getting pretty abstract. Hear me out. You can think of each distinct bin as a variety of donut and each identical ball as an "intention to buy $1$". Then, let the act of placing a ball into a bin represent the intention of buying $1$ donut of the bin's corresponding variety of donut. Hopefully, this is enough to make the bijection a bit more understandable, with each valid placement identifying a unique purchase, and vice versa.

How many ways can $12$ identical candy bars be distributed among $3$ different kids? Same answer as before, of course. But what if you wanted to be nice and guarantee each kid gets at least $1$ candy bar? There's a quick fix for that! First, give $1$ candy bar to each kid. Then, the question becomes: how many ways can $9$ identical candy bars be distributed among $3$ different kids? From what we know about multisets, the answer is $\binom{11}{2}.$ As a rule, whenever there is a specific constraint such as this, try to take care of it first, and then start counting.

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort