Combinatorics Flashcards Preview

Second Year > Combinatorics > Flashcards

Flashcards in Combinatorics Deck (19):
1

Permutation

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

2

# sequences of length k formed from n elts without repetition

n!/(n-k)!

3

# ways to choose a subset of k objects from set of size n (0 โ‰ค k โ‰ค n)

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

4

Binomial theorem

(๐‘ฅ + ๐‘ฆ)โฟ = โˆ‘_{k=0, n} (n k)๐‘ฅโฟโปแต๐‘ฆแต

5

Inductive property of binom coefficients

For all integers n โ‰ฅ 0 and k,
(n k) = ([n-1] [k-1]) + ([n-1] k).

6

Orthogonality for binom coefficients

If r < n are nonnegative integers, then
โˆ‘_{k=0, n} (n k)(-1)แตkสณ = 0.

7

Mean Value Theorem for divided differences

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

Multiset

An unordered collection of elts in which repetition is allowed.

9

Multiset formula

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

Dimension of spaces of polynomials

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

Multinomial theorem

(๐‘ฅ + ๐‘ฆ + ๐‘ง)โฟ =
โˆ‘_{k,j,๐“โ‰ฅ0, k+j+๐“=n} (n!/k!j!๐“!) ๐‘ฅสฒ๐‘ฆแต๐‘งหก

12

Inclusion-Exclusion formula

Let Aโ‚, Aโ‚‚, ..., Aโ‚™ be subsets of a set ฮฉ. Then
|ฮฉ\(Aโ‚ โˆช Aโ‚‚ โˆช ... โˆช Aโ‚™)|
= |ฮฉ| - โˆ‘แตข |Aแตข| + โˆ‘_{i

13

Stirling approximation

n! ~ sqrt(2๐œ‹n)(n/e)โฟ

14

Binet Theorem (Fibonacci formula)

Let ๐œ‘ = (1+โˆš5)/2,
๐œ“ = (1-โˆš5)/2,
then for n โ‰ฅ 0 the nth Fibonacci number is
Fโ‚™ = (๐œ‘โฟ - ๐œ“โฟ)/(๐œ‘ - ๐œ“).

15

Golden Ratio

Fโ‚™โ‚Šโ‚/Fโ‚™ = (๐œ‘โฟโบยน - ๐œ“โฟโบยน)/(๐œ‘โฟ - ๐œ“โฟ) โ†’ ๐œ‘, so we call ๐œ‘ the golden ratio.

16

Fibonacci matrix theorem

Let Q = (1, 1; 1, 0).
Then the powers of Q generate the Fibonacci numbers as follows,
Qโฟ = (Fโ‚™โ‚Šโ‚, Fโ‚™; Fโ‚™, Fโ‚™โ‚‹โ‚).

17

Divisibility of Fibonacci numbers

If n = km, then Fโ‚˜|Fโ‚™.
(Proof uses induction on k and matrix theorem)

18

Generating function

Given a sequence ๐‘โ‚€, ๐‘โ‚, ๐‘โ‚‚,... the function
g(๐‘ฅ) = โˆ‘_{k=0, โˆž}๐‘โ‚–๐‘ฅแต with positive radius of convergence is the generating function of the sequence.

19

Catalan recurrence

The nแต—สฐ Catalan number satisfies
Cโ‚™ =