Szczególne porządki

[mol_ksiazkowy]

Na ile sposobów można uporządkować liczby ze zbioru \(\displaystyle{ \{ 1, ..., n \}}\) tak aby każda z nich była większa, bądź mniejsza od wszystkich ją poprzedzających ?

np. \(\displaystyle{ 3, 2, 4, 5, 1}\)

[kerajs]

Niech pierwszą wybraną liczbą będzie \(\displaystyle{ k}\), a wtedy \(\displaystyle{ k-1}\) liczb od niej mniejszych pojawiać się będzie w porządku malejącym, a \(\displaystyle{ n-k}\) liczb od niej większych pojawiać się będzie w porządku rosnącym. Ilość szukanych ciągów zaczynających się od liczby \(\displaystyle{ k}\) jest równa \(\displaystyle{ \frac{(n-1)!}{(k-1)!(n-k)!}= {n-1 \choose k-1} }\), a ilość wszystkich to: \(\displaystyle{ \sum_{k=1}^{n} {n-1 \choose k-1} =2^{n-1}}\)

[Dasio11]

Inaczej: ostatnią liczbą musi być \(\displaystyle{ 1}\) lub \(\displaystyle{ n}\). Jeśli jest nią \(\displaystyle{ 1}\), to przedostatnią liczbą jest \(\displaystyle{ 2}\) lub \(\displaystyle{ n}\), jeśli zaś jest nią \(\displaystyle{ n}\), wówczas na przedostatniej pozycji musi stać \(\displaystyle{ 1}\) bądź \(\displaystyle{ n-1}\). Ogólnie: przy ustalonej końcówce ciągu zawsze są dwie możliwości obsadzenia ostatniej nieustalonej jeszcze pozycji, oczywiście z wyjątkiem sytuacji gdy jest nią pozycja pierwsza, bo wtedy wyboru nie ma. Stąd liczba takich ciągów to \(\displaystyle{ 2^{n-1}}\).