Nierówność i permutacja

[mol_ksiazkowy]

Ile jest permutacji \(\displaystyle{ f}\) zbioru \(\displaystyle{ \{1,..., n \}}\) takich, że istnieje tylko jedno \(\displaystyle{ j \in \{1,..., n-1\} }\) takie, że \(\displaystyle{ f(j)> f(j+1)}\) ?

[kerajs]

Ile jest permutacji \(\displaystyle{ f}\) zbioru \(\displaystyle{ \{1,..., n \}}\) takich, że istnieje tylko jedno \(\displaystyle{ j \in \{1,..., n-1\} }\) takie, że \(\displaystyle{ f(j)> f(j+1)}\) ?

Dla ustalonego miejsca \(\displaystyle{ j}\) takich ciągów jest \(\displaystyle{ {n \choose j} -1 }\). Wybranych \(\displaystyle{ j}\) liczb ustawia się w ciąg rosnący tylko na jeden sposób, podobnie jak \(\displaystyle{ n-j}\) pozostałych liczb. Wyjątkiem jest wybór liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ j}\) i stąd odjemnik.
Szukaną liczbą permutacji jest \(\displaystyle{ \sum_{j=1}^{n-1}( {n \choose j}-1)=2^n-n-1}\)