Combinatorics Flashcards Preview

Second Year > Combinatorics > Flashcards

Flashcards in Combinatorics Deck (19)
Loading flashcards...
1
Q

Permutation

A

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

2
Q

sequences of length k formed from n elts without repetition

A

n!/(n-k)!

3
Q

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

A

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

4
Q

Binomial theorem

A

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

5
Q

Inductive property of binom coefficients

A

For all integers n ≥ 0 and k,

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

6
Q

Orthogonality for binom coefficients

A

If r < n are nonnegative integers, then

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

7
Q

Mean Value Theorem for divided differences

A

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).

8
Q

Multiset

A

An unordered collection of elts in which repetition is allowed.

9
Q

Multiset formula

A

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).

10
Q

Dimension of spaces of polynomials

A

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).

11
Q

Multinomial theorem

A

(𝑥 + 𝑦 + 𝑧)ⁿ =

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

12
Q

Inclusion-Exclusion formula

A

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

13
Q

Stirling approximation

A

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

14
Q

Binet Theorem (Fibonacci formula)

A

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

15
Q

Golden Ratio

A

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

16
Q

Fibonacci matrix theorem

A

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

17
Q

Divisibility of Fibonacci numbers

A

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

Proof uses induction on k and matrix theorem

18
Q

Generating function

A

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

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

19
Q

Catalan recurrence

A

The nᵗʰ Catalan number satisfies

Cₙ =