Combinatorics

Question 1

Permutation

Answer 1

A permutation of the set {1,2,…,n} is a sequence of length n in which each of the numbers appears exactly once

Question 2

sequences of length k formed from n elts without repetition

Answer 2

n!/(n-k)!

Question 3

ways to choose a subset of k objects from set of size n (0 ≤ k ≤ n)

Answer 3

(n k) = n!/k!(n-k)!

Question 4

Binomial theorem

Answer 4

(𝑥 + 𝑦)ⁿ = ∑_{k=0, n} (n k)𝑥ⁿ⁻ᵏ𝑦ᵏ

Question 5

Inductive property of binom coefficients

Answer 5

For all integers n ≥ 0 and k,

n k) = ([n-1] [k-1]) + ([n-1] k

Question 6

Orthogonality for binom coefficients

Answer 6

If r < n are nonnegative integers, then

∑_{k=0, n} (n k)(-1)ᵏkʳ = 0.

Question 7

Mean Value Theorem for divided differences

Answer 7

If f is n times diffble on an open interval including [0,n] then for some t, 0 ≤ t ≤ n,
∑_{k=0, n}(n k)(-1)ᵏf(k) = (-1)ⁿf⁽ⁿ⁾(t).

Question 8

Multiset

Answer 8

An unordered collection of elts in which repetition is allowed.

Question 9

Multiset formula

Answer 9

The number of multisets of size d with elts from a set of size m is
([d+m-1] [m-1]) = ([d+m-1] d).

Question 10

Dimension of spaces of polynomials

Answer 10

The space of homogeneous polynomials of degree d in m variables has dimension
([d+m-1] [m-1]).
The space of polynomials of degree at most d in m variables has dimension
([d+m] m).

Question 11

Multinomial theorem

Answer 11

(𝑥 + 𝑦 + 𝑧)ⁿ =

∑_{k,j,𝓁≥0, k+j+𝓁=n} (n!/k!j!𝓁!) 𝑥ʲ𝑦ᵏ𝑧ˡ

Question 12

Inclusion-Exclusion formula

Answer 12

Let A₁, A₂, …, Aₙ be subsets of a set Ω. Then
|Ω(A₁ ∪ A₂ ∪ … ∪ Aₙ)|
= |Ω| - ∑ᵢ |Aᵢ| + ∑_{i

Question 13

Stirling approximation

Answer 13

n! ~ sqrt(2𝜋n)(n/e)ⁿ

Question 14

Binet Theorem (Fibonacci formula)

Answer 14

Let 𝜑 = (1+√5)/2,
𝜓 = (1-√5)/2,
then for n ≥ 0 the nth Fibonacci number is
Fₙ = (𝜑ⁿ - 𝜓ⁿ)/(𝜑 - 𝜓).

Question 15

Golden Ratio

Answer 15

Fₙ₊₁/Fₙ = (𝜑ⁿ⁺¹ - 𝜓ⁿ⁺¹)/(𝜑ⁿ - 𝜓ⁿ) → 𝜑, so we call 𝜑 the golden ratio.

Question 16

Fibonacci matrix theorem

Answer 16

Let Q = (1, 1; 1, 0).
Then the powers of Q generate the Fibonacci numbers as follows,
Qⁿ = (Fₙ₊₁, Fₙ; Fₙ, Fₙ₋₁).

Question 17

Divisibility of Fibonacci numbers

Answer 17

If n = km, then Fₘ|Fₙ.

Proof uses induction on k and matrix theorem

Question 18

Generating function

Answer 18

Given a sequence 𝑝₀, 𝑝₁, 𝑝₂,… the function

g(𝑥) = ∑_{k=0, ∞}𝑝ₖ𝑥ᵏ with positive radius of convergence is the generating function of the sequence.

Question 19

Catalan recurrence

Answer 19

The nᵗʰ Catalan number satisfies

Cₙ =