combi 89

Laat de verzameling $A_k$, voor $1 \leq k \leq n$, de verzameling zijn met de permutaties van $\{1,2,...,2n \}$ zodat het element $k$ grenst aan het element $k+n$. Dan is $\left | \bigcup_{n}^{i=1} A_i \right |$ het aantal permutaties die P bezitten. We bewijzen eerst volgende twee lemma's:

Lemma 1: $\left | \bigcap^{q}_{i=1} A_{y_i} \right |=2^i (2n-i)!$, waar $y_1, y_2, ..., y_i$ disjuncte, natuurlijke getallen tussen één en $n$ zijn.

Bewijs: Beschouw een willekeurige permutatie van de verzameling van $2n-i$ elementen zonder $y_1,y_2,...,y_i$. Vervolgens kan elke $y_k$ ($1\le k \le i$) net voor of net na $y_k+n$ geplaatst worden. Elke permutatie uit $\bigcap^{q}_{i=1} A_{y_i} $ is zo op een unieke manier gevormd.
Dus zijn er $2^i (2n-i)!$ permutaties van $\{1,2,...,2n \}$ waarbij elk van de elementen $y_k$ grenst aan $y_k+n$. Dus $\left | \bigcap^{q}_{i=1} A_{y_i} \right |=2^i (2n-i)!$.

Lemma 2: Voor positieve $i,n$ geldt dat $2^i {n \choose i} (2n-i)! > {n\choose i+1} 2^{i+1} (2n-i-1)!$.

Bewijs: $2^i {n \choose i} (2n-i)! > {n\choose i+1} 2^{i+1} (2n-i-1)! $
$\Leftrightarrow (2n-i)(n-i-1)!(i+1)!>2(n-i)!i! \Leftrightarrow (2n-i)(i+1)>(2n-2i)$. De laatste ongelijkheid is triviaal.

Volgens PIE en lemma 1 en 2 geldt nu dat $\left | \bigcup_{n}^{i=1} A_i \right |=\sum_{i=1}^{n}{ (-1)^{i+1} 2^i {n\choose i} (2n-i)!}\geq (2n)!-4{n\choose 2} (2n-2)!$. We claimen dat het laatste altijd groter is dan $\frac 12 (2n)!$. Inderdaad, $(2n)!-4{n \choose 2} (2n-2)!> \frac 12 (2n)! \Leftrightarrow (2n)!>8 {n\choose 2} (2n-2)! \Leftrightarrow (2n)(2n-1)>4n(n-1)$
$ \Leftrightarrow 2n-1>2n-2$. Het laatste is duidelijk altijd waar. Q.E.D.