TU Wien:Mathematik 1 UE (diverse)/Übungen WS08/Beispiel 137

Wieviele Permutationen $\pi$ von [1,2,...,n] gibt es mit $\pi (k)\leq k+1$ für alle $i\leq k\leq n-1$?

also am Bsp von einer Menge {1,2,...,6} erkennt man, dass es 2^6 => 2^n sein müssen:

$\pi$(1)<=2, $\pi$(2)<=3, $\pi$(3)<=4, $\pi$(4)<=5, $\pi$(5)<=6

die oberen werte können also wie folgt permutieren:

1	2	3	4	5	6
_	_	_	_	_	_
1	2	3	4	5	6
2	2	2	2	2	2
-	3	3	3	3	3
-	-	4	4	4	4
-	-	-	5	5	5
-	-	-	-	6	6

wenn 1--> jetzt auf 1 oder 2 permutiert, dann bleiben nur noch 2 Elemente (3 Elemente - 1 Element) übrig gegen die 2 Permutieren kann, 2 permutiert also gegen 1 oder 3 (wenn 1 gegen 2 permutiert ist) bzw. gegen 2 oder 3 (wenn 1 gegen 1 permutiert ist), also bleiben für das 3. Element 3 auch nur noch 2 Werte übrig, usw., das letzte permutiert nur noch gegen den verbliebenen Wert => für alle (bis auf den letzten) Werte gibt es 2 Werte gegen die sie permutieren können also 2^(6-1) = 32 mögliche Permutationen...

allgemein: 2^(n-1) Permuationen

-- yoki