MA416 - Things to Remember

count number of ways to partition a set of n elements into k non-empty unlabeled subsets, S(n, k)

Stirling Numbers of the Second Kind definition

1/(1-rx)

sequence a_n = r^n

1 (all elements in a single group)

S(n, 1)

1 (each element is in its own subset)

S(n, n)

S(n, k) = k * S(n-1, k) + S(n-1, k-1)

S(n, k) formula

f(k)

what is at location k

f^-1(k)

where k is

groups of n, from a range of numbers from 1-k, REPEATS ALLOWED

F_n,k

groups of n, from a range of numbers from 1-k, NO REPEATS

Q_n,k

k^n

o(F_n,k)

k!/(k-n)!

o(Q_n,k)

all numbers are used

onto

no repeated numbers

one-to-one

S(m, n)

m labeled balls, n unlabeled urns, NO empty urns

(nMi=1) S(n, i)

m labeled balls, n unlabeled urns, empty urns are OK

n^m

m labeled balls, n labeled urns, empty urns are OK

n!S(m, n)

m labeled balls, n labeled urns, NO empty urns

n!S(m, n)

the number of surjective (onto) functions in F_n,k

reflexive, symmetric, transitive

Equivalence relation

reflexive

everything is related to itself

symmetric

if “a is like b” then “b is like a”

transitive

If “a is like b” and “b is like c” then “a is like c”

C(m+n-1, m)

m unlabeled balls distributed among n labeled urns, empty is OK

C(m-1, n-1)

m unlabeled balls distributed among n labeled urns, NO empty urns

total number of set partitions of [m] (total equivalence relations)

bell number (B_m)

p_n(m)

m unlabeled balls and n unlabeled urns, NO empty urns

p1(m) + p2(m) + … +pn(m)

m unlabeled balls and n unlabeled urns, empty urns are OK

|A U B| = |A| + |B| - |A n B|

principle of inclusion and exclusion

a permutation with no fixed points, n!/e (nothing stays in it’s original place)

derangement

number of derangements of n items

D(n)

n!/k!(n-k)!

C(n, k)

n!/(n-k)!

P(n, k)

number of ways to take n labeled items and arrange them into k cycles, s(n, k)

stirling number of the first kind

s(m, n) = s(m-1, n-1) + (m-1)*s(m-1, n)

s(m, n) formula

1/(1-x)

a_n = 1

x/(1-x-x²)

fibonacci F_n generating function

1/1+x

a_n = (-1)^n

1/(1-x)²

a_n = n+1

x/(1-x)²

a_n = n

-x/(1+x)²

a_n = (-1)^n * n

isomorphic variants

edges, vertices, degree sequence

isomorphism

same shape, different numbers, bijection

subgraph

take away some vertices and edges from G(V, E)

induced subgraph

take away some vertices and that forces you to take away some edges

complete graph

a graph such that every pair of distinct vertices is connected by an edge

Clique

an induced subgraph that is complete, any subset of a ___ is a ____

smallest number n such that in any group of n people, you will always find either s people who all know each other or t people none of whom know each other.

Ramsey number N(s, t)

N(s, t) ≤ N(s-1, t) + N(s, t-1)

Ramsey number formula

sum of the degrees of all vertices in a graph equals twice the number of edges

handshake theorem

(pi k>1) (1/1-x^k)

closed form for the generating function where p_A(n) counts the number of partitions of n