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].
Liczba ciągów rosnących
- oldj
- Użytkownik
- Posty: 133
- Rejestracja: 5 wrz 2012, o 14:55
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 2 razy
- Pomógł: 37 razy
Liczba ciągów rosnących
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]}\).
-
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Liczba ciągów rosnących
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}\)
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}\)