Combinatorics theorems

Question 1

pigeonhole principle

Answer 1

let n∈ℕ. If at least n+1 pigeons are placed in n pigeonholes, then some pigeonhole contains at least two pigeons

Question 2

pigeonhole principle - general form

Answer 2

let n,k∈ℕ. If at least n pigeons are placed in k pigeonholes, the some pigeonhole contains atleast ⌈n/k⌉ pigeons

Question 3

axiom of extension

Answer 3

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

Question 4

composition of injections

Answer 4

Let f:A-> Band g:B->C be functions. If f and g are both injective, the g∘f is injective

Question 5

composition of surjections

Answer 5

Let f:A-> Band g:B->C be functions. If f and g are both surjective, the g∘f is surjective

Question 6

composition of Bijections

Answer 6

Let f:A-> Band g:B->C be functions. If f and g are both bijective, the g∘f is bijective

Question 7

injection of sets

Answer 7

Let X and Y be finite sets. Then |X|≤|Y| iff there exists an injection f:X->Y

Question 8

pairing principle

Answer 8

Let X and Y be finite sets. Then |X|=|Y| iff there exists an bijection f:X->Y

Question 9

sum rule

Answer 9

If C and D are disjoint finite sets then |C∪D| = |C|+|D|

Question 10

inclusion exclusion for two sets

Answer 10

Suppose that A and B are finite sets. Then, |A∪B| = |A|+|B|- |A∩B|

Question 11

Inclusion exclusion for three sets

Answer 11

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|

Question 12

general inclusion exclusion

Answer 12

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

Question 13

product rule for two sets

Answer 13

if A and B are finite sets, then |AxB| = |A||B|

Question 14

product rule for r sets

Answer 14

for any r∈ℕ and any finite sets A₁,A₂,..,Aᵣ we have |A₁xA₂x…xAᵣ|=|A₁||A₂|…|Aᵣ|

Question 15

size of power set

Answer 15

If A is a set with |A|=n, then |P(A)|= 2ⁿ. Equivilently a set with n elements has 2ⁿ subsets

Question 16

choose r choices from n elements where order matters and repition is allowed

Answer 16

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ʳ

Question 17

choose r choices from n elements where order matters and repition is not allowed (r≤n)

Answer 17

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!

Question 18

choose r choices from n elements where order doesn’t matter and repition is not allowed (n≤r)

Answer 18

For r>n it is not possible to make r successive choices from S if reption is forbidden

Question 19

number of permutations

Answer 19

A set S of n elements has n! permutations

Question 20

choose r choices from n elements where order doesn’t matter and repition is forbidden

Answer 20

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

Question 21

choose r choices from n elements where order doesnt matter and repition is allowed

Answer 21

there are n+r-1 choose r possible ways to make r successive choices from S

Question 22

solutions to an equation of n unknowns equal to r

Answer 22

For natural numbers r and n, the number of non-negative integer solutions of x₁+x₂+…+xₙ=r is n+r-1 choose r

Question 23

pascals triangle and binomial coeficiants

Answer 23

For any Integers r and n with 0≤r

Question 24

Binomial Theorem

Answer 24

For any integer n≥0 and any a,b∈ℝ we have

(a+b)ⁿ = Σⁿᵢ₌₀ (n i) aᶦbⁿ⁻ᶦ

Question 25

sum of all binomial coeficiants

Answer 25

For any integer n≥0 we have Σⁿᵢ₌₀(n i) = 2ⁿ

Question 26

sum of swapping parities binomial coeficiants

Answer 26

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

Question 27

Same number of odd subsets and even subsets

Answer 27

Let S be a set of size n≥1. Then S has 2ⁿ⁻¹ subsets of even size and 2ⁿ⁻¹ subsets of odd size