Combinatorics Flashcards
How many ways are there to place k labelled balls into n labelled boxes?
The number of ways to place k labelled balls into n labelled boxes is nk.
What is the Multinomial Theorem?
Let n be a positive integer. Then
(a1 + · · · + ar)n = ∑k1+···+kr=n (nCk1, . . . , kr) * a1k1 · · · arkr.
How many ways are there to distribute n balls into n labelled boxes, with k1 balls coloured c1, . . . , kr balls coloured cr?
Suppose we have n labelled boxes, and n balls — k1 labelled with colour c1, k2 labelled with colour c2, and so on up to kr labelled with colour cr, where k1 + k2 + · · · + kr = n. Then the number of distinct ways of distributing the balls among the boxes is n!/k1!k2!···kr!
What is the set [n]?
For brevity, rather than writing {1, . . . , n} and {1, . . . , k} all the time, we will write [n] and [k]. This is reasonably standard. Note that zero is not included, and that [0] is the empty set ∅.
What is the Inclusion-Exclusion Theorem?
Let A1, . . . , Ar be sets. Then
|A1 ∪ · · · ∪ Ar| = ∑I⊆{1,…,r},I=∅ (−1)|I|−1 |∩i∈I Ai|
How many surjections are there from [k] to [n]?
Surj(k,n) = ∑m=0n (−1)m(n − m)k nCm.
What are the Stirling Numbers (of the second kind)?
What if we count surjections, but with unlabelled boxes? This has a nice interpretation, namely counting the ways of dividing [k] into n nonempty pieces.
These numbers S(k, n) are called the Stirling numbers of the second kind.
What is the formula for the Stirling Numbers.
S(k,n) = 1/n! * Surj(k,n)
What are the Bell Numbers?
For k ≥ 0, define the Bell numbers Bk = ∑n=0k S(k, n). That is, Bk is the number of ways to partition [k] into any number of parts.
How can we use Stars and Bars?
Where k unlabelled objects have to be shared among n labelled boxes, we can consider the ‘joint sequence’ of stars and bars, distributing the objects between the bars. Then we see that we have to choose where to place k objects among (n+k-1) places, giving
(n+k-1)Ck = (n+k-1)C(n-1) ways to distribute.
What is a Generating function of a sequence?
Let (an)n≥0 be a sequence of numbers. The formal power series
∑n=0,∞ an * x^n
is called the ordinary generating function of (an)n≥0, and the formal power series
∑n=0,∞ an * (x^n/n!)
is called the exponential generating function of (an)n≥0.
How are generating functions useful?
We use generating function to come up with a simple formula for a sequence.
Given a sequence that relies on some sort of recursion (e.g. the Fibonacci sequence), we can find a formula for the next term in the sequence, depending on n only.
Basically there will be some identity with the generating function of a sequence and that can be used to find individual terms from the coefficients of the series.
When choosing which type of generating function to use, use the one that has similar growth as to the sequence at hand. ie. use the exponential one if the sequence grows exponentially-ish.
What is p(n) and pk(n)?
These are the number of integer partitions into any number of boxes and the partitions into k boxes.
What is the useful way of drawing integer partitions, a Ferrer diagram?
Given a partition of n, in order of size. So n = a1 + a2 + … + ar where a1>=a2>=…>=ar.
Then the diagram consists of r bars drawn horizontally, one of top of another and the bars are made up of ai squares.
What is the conjugate of an integer partition?
Let λ be a partition of n. The conjugate partition λT of λ is the partition corresponding to the reflection of the Ferrers diagram of λ over the (upper-left-to-lower-right) diagonal
How are integer partitions related between amount of parts and size of parts?
The number of partitions of n into at most k parts is equal to the number of partitions of n into parts of size at most k.
We can relate the two by conjugation of their respective diagram.
How is the number of integer partitions into odd parts and distinct parts related?
The number of partitions of n into odd parts is equal to the number of partitions of n into distinct parts.
What is a triangulation?
A triangulation of a regular n-gon is a collection of non-crossing diagonals that divide the n-gon into triangles.
What are the Catalan numbers?
The nth Catalan number Cn is the number of triangulations of a regular (n + 2)-gon.
What is a Graph?
Definition 2.1. A graph (or simple graph) G = (V, E) is
* a set V , whose elements are called the vertices of G, and
* a set E of unordered pairs of distinct vertices, whose elements are called the edges of G.
What is the terminology for graphs?
Let G = (V, E) be a graph.
* If e ∈ E contains v, we say e is incident to v, or v is an endpoint of e.
* If v1, v2 ∈ V are vertices such that {v1, v2} ∈ E, we say v1 and v2 are adjacent (or are neighbors).
* For v ∈ V, the number of edges incident to v is called the degree deg(v) or valence val(v) of v.
What is a regular graph?
A graph is called k-regular if every vertex has degree k. (Or just regular if it is k-regular for some k.)
What is the degree-sum fromula?
Let G = (V, E) be a graph. Then
∑v∈V deg(v) = 2*|E|.
In particular, the number of odd-degree vertices of G is even.
When are graphs isomorphic?
Two (simple) graphs G = (V, E) and G′ = (V′,E′) are isomorphic if there exists a bijection ϕ : V → V′such that {v1, v2} ∈ E
if and only if {ϕ(v1), ϕ(v2)} ∈ E′. (That is, if they differ only in the naming of the vertices).
What are subgraphs? And spanning subgraphs, and induced subgraphs?
- Let G = (V, E) and H = (V′, E′) be simple graphs, where V′ ⊆ V . We say H is a subgraph of G if for all edges {v1, v2} ∈ E′, we have {v1, v2} ∈ E
- Let G = (V, E) be a connected graph, and let H = (V′, E′) be a subgraph (so V′ ⊆ V ). We say H is a spanning subgraph (or H spans G) if V′ = V.
- For a graph G = (V, E) and a subset V′ ⊆ V, the subgraph of G induced by V′ is the subgraph with vertex set V′ and edge set E′ = {e ∈ E : e ⊆ V′}. That is, the set of all edges between vertices in V′.
When does a graph contain another?
Let G and G′ be graphs. We say G′
contains G if G is isomorphic to a subgraph of G′.
