Combinatorics theorems Flashcards
pigeonhole principle
let n∈ℕ. If at least n+1 pigeons are placed in n pigeonholes, then some pigeonhole contains at least two pigeons
pigeonhole principle - general form
let n,k∈ℕ. If at least n pigeons are placed in k pigeonholes, the some pigeonhole contains atleast ⌈n/k⌉ pigeons
axiom of extension
two sets are equal if and only if they have the same elements i.e. ∀x∈A we have x∈B and ∀x∈B we have x∈A
composition of injections
Let f:A-> Band g:B->C be functions. If f and g are both injective, the g∘f is injective
composition of surjections
Let f:A-> Band g:B->C be functions. If f and g are both surjective, the g∘f is surjective
composition of Bijections
Let f:A-> Band g:B->C be functions. If f and g are both bijective, the g∘f is bijective
injection of sets
Let X and Y be finite sets. Then |X|≤|Y| iff there exists an injection f:X->Y
pairing principle
Let X and Y be finite sets. Then |X|=|Y| iff there exists an bijection f:X->Y
sum rule
If C and D are disjoint finite sets then |C∪D| = |C|+|D|
inclusion exclusion for two sets
Suppose that A and B are finite sets. Then, |A∪B| = |A|+|B|- |A∩B|
Inclusion exclusion for three sets
Suppose that A,B and C are finite sets. Then, |A∪B∪C| = |A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
general inclusion exclusion
Suppose that A₁, A₂, …,Aᵣ are finite sets. Then,
|A₁∪A₂∪…∪Aᵣ| =
1. add size of individual sets
2. subtract size of pairwise intersection
3. add three way intersections size
….
r. +- the r way intersection size
product rule for two sets
if A and B are finite sets, then |AxB| = |A||B|
product rule for r sets
for any r∈ℕ and any finite sets A₁,A₂,..,Aᵣ we have |A₁xA₂x…xAᵣ|=|A₁||A₂|…|Aᵣ|
size of power set
If A is a set with |A|=n, then |P(A)|= 2ⁿ. Equivilently a set with n elements has 2ⁿ subsets
choose r choices from n elements where order matters and repition is allowed
nʳ ways to choose r elements
moreover, if each choice from S is made uniformly at random and independently of all previous choices, then each of these outcomes has equal probability 1/nʳ
choose r choices from n elements where order matters and repition is not allowed (r≤n)
n!/(n-r)! possible ways to make r successive choices from S
if each choice from S is made uniformly at random from not previously chosen elements of S then each of these outcomes has equal probability (n-r)!/n!
choose r choices from n elements where order doesn’t matter and repition is not allowed (n≤r)
For r>n it is not possible to make r successive choices from S if reption is forbidden
number of permutations
A set S of n elements has n! permutations
choose r choices from n elements where order doesn’t matter and repition is forbidden
there are n choose r ways to select r elements. (i.e. there are n choose r subsets of size r).
moreover if each choice from S is made uniformly at random then each of these outcomes has equal probability 1/ n choose r
choose r choices from n elements where order doesnt matter and repition is allowed
there are n+r-1 choose r possible ways to make r successive choices from S
solutions to an equation of n unknowns equal to r
For natural numbers r and n, the number of non-negative integer solutions of x₁+x₂+…+xₙ=r is n+r-1 choose r
pascals triangle and binomial coeficiants
For any Integers r and n with 0≤r
Binomial Theorem
For any integer n≥0 and any a,b∈ℝ we have
(a+b)ⁿ = Σⁿᵢ₌₀ (n i) aᶦbⁿ⁻ᶦ
sum of all binomial coeficiants
For any integer n≥0 we have Σⁿᵢ₌₀(n i) = 2ⁿ
sum of swapping parities binomial coeficiants
For any n≥1 we have (n 0) - (n 1) + (n 2) - (n 3) + … ± (n n) = - where the ± is + if n is even and - if n is odd
Same number of odd subsets and even subsets
Let S be a set of size n≥1. Then S has 2ⁿ⁻¹ subsets of even size and 2ⁿ⁻¹ subsets of odd size
