DisMat UE 05

5.2

Show the following formulas by means of a combinatorial argument:

a)

s (n, n - 2) = \frac{3 n - 1}{4} (3 n), for n \geq 3

Es gibt zwei Wege wie eine Permutation von $[n]$ $n - 2$ Kreise hat.

Es gibt einen 3er Kreis dieser reduziert die Menge an Kreisen um 2.
Oder zwei 2er Kreise die jewails die Menge an Kreisen um einen reduzieren.

Nun zählen wir beide Fälle:

Einen 3er Kreis:
Mann kann die 3 Elemente auf $(3 n)$ Wege wählen.
Mit diesen 3 Elementen gibt es zwei einzigartige 3er Kreise bilden
denn $(3 - 1)! = 2$ bzw:
(a, b, c)
(a, c, b)
Zwei 2er Kreise:
Mann kann die 4 Elemente auf $(4 n)$ Wege wählen.
Dazu gibt es 3 Möglichkeiten 4 Elemente in zwei geordnete Paare zu sortieren.
Dies ist das perfekt matching Problem auf einem vollverbunden Graph.

M (n) = \frac{( 2 k )!}{2 ^{k} k !} n = 2 k

Da wir diese jedoch nie in der Vorlesung hatten gebe ich hier jetzt einfach alle Möglichkeiten an:
(a, b) (c, d)
(a, c) (b, d)
(a, d) (c, b)

Also zählen wir

s (n, n - 2) = 2 (3 n) + 3 (4 n) = 2 (3 n) + 3 (\frac{n - 3}{4} (3 n)) = (2 + \frac{3 ( n - 3 )}{4}) (3 n) = (\frac{8}{4} + \frac{3 n - 9}{4}) (3 n) = \frac{3 n - 1}{4} (3 n)

Gilt für $n = 3$ denn:
Es gibt nur 3 Elemente die nur 3er Kreise bilden können und es gibt zwei Möglichkeiten dafür.

\frac{3 \cdot 3 - 1}{4} (3 3) = \frac{8}{4} = 2

ab $n = 4$ gibt es beide Fälle.

s (n, n - 3) = (2 n) (4 n), for n \geq 4

Es gibt drei Wege wie eine Permutation von $[n]$ $n - 3$ Kreise hat.

Es gibt einen 4er Kreis dieser reduziert die Menge an Kreisen um 3.
Ein 3er Kreis und ein 2er Kreise die Menge um 2 und 1 reduzieren.
Oder drei 2er Kreise die jewails um 1 reduzieren.

Nun zählen wir die drei Fälle:

Ein 4er Kreis
Mann kann die 4 Elemente auf $(4 n)$ Wege wählen.
Mit diesen 4 Elementen kann man 6 einzigartige 3er Kreise bilden
denn $(4 - 1)! = 6$
Ein 3er Kreis und ein 2er Kreis
Mann kann die 5 Elemente auf $(5 n)$ Wege wählen.
Von den 5 wählen wir 3 mit in $(3 5) = 10$ Wegen für den ersten Kreis.
Wie in a) gezeigt könne gibt es zwei Mögliche 3er Kreise.
So gibt es hier $2 \cdot 10 \cdot (5 n)$ Möglichkeiten
Drei 2er Kreise
Mann kann die 6 Elemente auf $(6 n)$ Wege wählen.
Auf den gleichen Weg wie a) kann man hier 15 einzigartige Paare bilden, denn das perfekte matching auf einem voll verbunden Graph von 6 ist 15.
Die Möglichkeiten sind:

{(A,B), (C,D), (E,F)}
{(A,B), (C,E), (D,F)}
{(A,B), (C,F), (D,E)}
{(A,C), (B,D), (E,F)}
{(A,C), (B,E), (D,F)}
{(A,C), (B,F), (D,E)}
{(A,D), (B,C), (E,F)}
{(A,D), (B,E), (C,F)}
{(A,D), (B,F), (C,E)}
{(A,E), (B,C), (D,F)}
{(A,E), (B,D), (C,F)}
{(A,E), (B,F), (C,D)}
{(A,F), (B,C), (D,E)}
{(A,F), (B,D), (C,E)}
{(A,F), (B,E), (C,D)}

Also zählen wir

s (n, n - 2) = 6 (4 n) + 20 (5 n) + 15 (6 n) = (6 + 20 \frac{( 5 n )}{( 4 n )} + 15 \frac{( 6 n )}{( 4 n )}) (4 n)

nun vereinfache

\frac{( 5 n )}{( 4 n )} = \frac{\frac{n !}{( n - 5 )! 5 !}}{\frac{n !}{( n - 4 )! 4 !}} = \frac{n ! ( n - 4 )! 4 !}{n ! ( n - 5 )! 5 !} = \frac{4 !}{5 !} (n - 4) = \frac{4 !}{5 \cdot 4 !} (n - 4) = \frac{n - 4}{5}

20 \frac{n - 4}{5} = 4 (n - 4) = 4 n - 16

und

\frac{( 6 n )}{( 4 n )} = \frac{\frac{n !}{( n - 6 )! 6 !}}{\frac{n !}{( n - 4 )! 4 !}} = \frac{n ! ( n - 4 )! 4 !}{n ! ( n - 6 )! 6 !} = \frac{4 !}{6 !} (n - 4) (n - 5) = \frac{4 !}{6 \cdot 5 \cdot 4 !} (n - 4) (n - 5) = \frac{( n - 4 ) ( n - 5 )}{30}

15 \frac{( n - 4 ) ( n - 5 )}{30} = \frac{1}{2} (n - 4) (n - 5)

Wenn wir nun einsetzten bekommt man:

6 + 20 \frac{( 5 n )}{( 4 n )} + 15 \frac{( 6 n )}{( 4 n )} = 6 + 4 n - 16 + \frac{1}{2} (n - 4) (n - 5) = - 10 + 4 n + \frac{1}{2} (n^{2} - 9 n + 20) = - 10 + 4 n + \frac{1}{2} n^{2} - \frac{9}{2} n + 10 = \frac{1}{2} n^{2} - \frac{1}{2} n = \frac{1}{2} n (n - 1) = (2 n)

somit ist

s (n, n - 2) = 6 (4 n) + 20 (5 n) + 15 (6 n) = (2 n) (4 n)

Gilt auch für $n = 4$ denn:
Es gibt nur 4 Elemente die nur ein 4er Kreise bilden können und es gibt 6 Möglichkeiten dafür.

(2 4) (4 4) = 6 \cdot 1 = 6

Gilt auch für $n = 5$ denn:
Mann kann nur ein ein 4er Kreise oder oder ein 3er Kreis und ein 2er Kreis bilden.
Dafür gibt es

6 (4 5) + 20 (5 5) = 6 \cdot 5 + 20 = 50

Möglichkeiten.

(2 5) (4 5) = 10 \cdot 5 = 50

ab $n = 4$ gibt es alle drei Fälle.

5.4

Let $n \geq 1$ . A permutation $π = π_{1} ... π_{n}$ of the set $[n]$ is called 213-avoiding if there are no $1 \leq i < j < k \leq n$ such that $π_{j} < π_{i} < π_{k}$ .
Show that the Catalan number $C_{n}$ is equal to the number of 213-avoiding permutations of the set $[n]$ .

Uns ist aufgefallen dass,

Das Kompliment (231-avoiding) hat die gleich Menge:

\overline{π} := n + 1 - π

da diese Abbildung eine Bijektion ist.

Nun gilt $π_{j} < π_{k} < π_{i}$ für $1 \leq i < j < k \leq n$ .
Das macht es leichter da nun das maximale Element in der Mitte liegt.

Beweis per Rekursion

Sei $\overline{π}$ eine 231-avoiding Permutation von $[n]$ .
Steht das Maximum $n$ an Position $k$ , dann hat $π$ die Form

L n R

mit $∣ L ∣ = k - 1$ und $∣ R ∣ = n - k$ .

$L$ und $R$ sind selbst 231-vermeidend.
Alle Werte in $L$ sind kleiner als alle Werte in $R$ . Deswegen nutzen wir 231-avoiding.
Denn gäbe es $x \in L$ und $y \in R$ mit $x > y$ , entstünde ein 231-Muster.

Damit bestehen die Werte in $L$ genau aus den $k - 1$ kleinsten Zahlen und die in $R$ aus den $n - k$ größten.
$L$ und $R$ können unabhängig als 231-avoiding Permutationen angeordnet werden.
Daher gibt es

b_{k - 1} \cdot b_{n - k}

Permutationen mit $n$ an Position $k$ .
Summiert man über alle $k = 1, \dots, n$ , erhält man

b_{n} = = = k = 1 \sum n b_{k - 1} b_{n - k}, k = 0 \sum n - 1 b_{k} b_{n - k - 1} C_{n} b_{0} = 1

Dies ist genau die Catalan-Rekursion aus der Vorlesung.

Quartz 4

Explorer

DisMat UE 05

5.2

a)

5.4

Uns ist aufgefallen dass,

Beweis per Rekursion

Graph View

Table of Contents

Backlinks