— — Permutace a faktoriál

Permutace a faktoriál

Permutace konečné množiny X: Libovolná bijekce π: X ⟷^{1–1} X.

Příklad:

Mějme množinu X = {a, b, c, d}, definujme permutaci π(a) = b, π(b) = d, π(c) = c, π(d) = a. Matice permutace pak je

( \begin{matrix}a & b & c & d \\ b & d & c & a \end{matrix} ) ,

permutace tvoří uspořádání

(b, d, c, a)

a dá se vyjádřit na grafu jako

a * ---¿ * b ˙ — —“ — “ v

c *¡-“ * d “-/

n faktoriál: n! = 1 · 2 · 3 ⋯ n, 0! = 1

Tvrzení:

Počet permutací n-prvkové množiny je n!.

DŮKAZ:

n možností, kam se zobrazí první prvek. n − 1 možností, kam se zobrazí druhý prvek. …

VĚTA ():

|X| = n, |Y | = k. Pak existuje:

• k^{n} zobrazení X → Y.

• k(k − 1)(k − 2) … (k − n + 1) prostých zobrazení X → Y.

• k! = n! bijekcí X ⟷^{1–1} Y, pokud k = n.

• 0 bijekcí X ⟷^{1–1} Y, pokud k ≠ n.

Kombinační čísla

Definice:

Kombinační číslo (neboli binomický koeficient):

\binom{n}{k} = \frac{n!}{k!(n − k)!} = \frac{n(n − 1) … (n − k + 1)}{k(k − 1) … 1} n, k ∈ ℕ_{0}, n ≥ k

Alternativní definice:

\binom{n}{k} je počet k-prvkových podmnožin n-prvkové množiny.

— — Kombinační čísla

Tvrzení:

Obě definice jsou ekvivalentní. DŮKAZ:

Nechť |X| = n. Pak počet uspořádaných k-tic různých prvků z X je kombinatorickou úvahou

n(n − 1)(n − 2) … (n − k + 1) = \frac{n!}{(n − k)!}.

Zároveň však tento počet můžeme spočítat přes kombinační čísla jako (počet k-prvkových podmnožin X)(počet možných uspořádání) = \binom{|X|}{k}k! = \frac{n!}{(n − k)!} .

Q.E.D.

Značení:

Buď X množina. Pak \binom{X}{k} je množina všech k-prvkových podmnožin množiny X. Navíc

|\binom{X}{k}| = \binom{|X|}{k}.

Platí:

(i) Symetrie:

\binom{n}{k} = \binom{n}{n − k} n ≥ k ≥ 0

DŮKAZ:

Z definice kombinačního čísla (algebraicky nebo doplňky).

(ii) Sousední čísla:

\binom{n}{k} = \binom{n − 1}{k − 1} + \binom{n − 1}{k}

DŮKAZ:

Z množinové definice kombinačního čísla:

|\binom{X}{k}| = \underbrace{|\binom{X \ \{x_{n}\}}{k − 1}|}_{počet k-prvkových podm. množiny X obs. x_{n}} + \underbrace{|\binom{X \ \{x_{n}\}}{k}|}_{počet k-prvkových podm. množiny X neobs. x_{n}}

Q.E.D.

Pascalův trojúhelník

Ve vrcholu △ je 1, okraje jsou lemovány nulami, každý prvek je součtem dvou prvků nad ním.

1

1 1
1 2 1
1 3 3 1
1 4 6 4 1

/L:1 2 — — Kombinační čísla

Pohled přes kombinační čísla:

\binom{0}{0}
\binom{1}{0}  \binom{1}{1}
\binom{2}{0}  \binom{2}{1}  \binom{2}{2}
\binom{3}{0}  \binom{3}{1}  \binom{3}{2}  \binom{3}{3}
\binom{4}{0}  \binom{4}{1}  \binom{4}{2}  \binom{4}{3}  \binom{4}{4}

neboť \binom{n}{k} = \binom{n − 1}{k − 1} + \binom{n − 1}{k} .

Binomická věta

Víme:

(x + y)^{2} = x^{2} + 2xy + y^{2} (x + y)^{3} = x^{3} + 3x^{2}y + 3xy^{2} + y^{3}

(x + y)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{k}y^{n−k} n ∈ ℕ_{0}, x, y ∈ ℝ

DŮKAZ:

Indukcí podle n:

(1) n = 0, n = 1

\begin{aligned}(x + y)^{0} & = \binom{0}{0}x^{0}y^{0} = 1 \\ (x + y)^{1} & = \binom{1}{0}x^{0}y^{1} + \binom{1}{1}x^{1}y^{0} \end{aligned}

(2) n ⇒ n + 1

(x + y)^{n+1} = (x + y)^{n}(x + y) = (x + y) (\binom{n}{0}x^{0}y^{n} + ⋯ + \binom{n}{n}x^{n}y^{0}) =

= \binom{n}{0}x^{1}y^{n} + ⋯ + \binom{n}{n}x^{n+1} y^{0} + \binom{n}{0}x^{0}y^{n+1} + ⋯ + \binom{n}{n}x^{n}y^{1} =

= \binom{n + 1}{0}x^{0}y^{n+1} + \binom{n + 1}{1}x^{1}y^{n} + ⋯ + \binom{n + 1}{n}x^{n}y^{1} + \binom{n + 1}{n + 1}x^{n+1} y^{0} =

= ∑_{k=0}^{n+1} \binom{n + 1}{k}x^{k}y^{(n+1)−k}

Důsledek:

(1 + x)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{k}