Liczba ciągów rosnących

[sins12]

Witam, prosiłbym o przedstawienie sposobu jak rozwiązać poniższe zadanie.

Znajdź liczbę ciągów ściśle rosnących długości k o wyrazach ze zbioru [n].

[brzoskwinka1]

\(\displaystyle{ n\choose k}\)

[oldj]

równoważnie szukamy liczby funkcji ściśle rosnących ze zbioru \(\displaystyle{ [k]}\) w zbiór \(\displaystyle{ [n]}\). Szukana liczba to \(\displaystyle{ {n \choose k}}\) - łatwo pokazać bijekcję między zbiorem funkcji ściśle rosnących ze zbioru \(\displaystyle{ [k]}\) w zbiór \(\displaystyle{ [n]}\) a zbiorem wszystkich k-elementowych podzbiorów zbioru \(\displaystyle{ [n]}\).

[bakala12]

To ja może powiem to samo, ale nieco inaczej:
Wybieramy dowolny \(\displaystyle{ k}\)-elementowy podzbiór zbioru \(\displaystyle{ n}\)-elementowego i ustawiamy jego elementy w ciąg rosnący (można to zrobić na jeden sposób).
Zatem odpowiedź to oczywiście:
\(\displaystyle{ n \choose k}\)