Liczba ciągów rosnących

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
sins12
Użytkownik
Użytkownik
Posty: 19
Rejestracja: 8 lut 2011, o 16:36
Płeć: Mężczyzna
Lokalizacja: polska

Liczba ciągów rosnących

Post autor: sins12 » 22 wrz 2013, o 18:30

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

Liczba ciągów rosnących

Post autor: brzoskwinka1 » 22 wrz 2013, o 18:46

\(n\choose k\)

Awatar użytkownika
oldj
Użytkownik
Użytkownik
Posty: 133
Rejestracja: 5 wrz 2012, o 14:55
Płeć: Mężczyzna
Lokalizacja: Wrocław

Liczba ciągów rosnących

Post autor: oldj » 22 wrz 2013, o 18:52

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

bakala12
Gość Specjalny
Gość Specjalny
Posty: 3044
Rejestracja: 25 mar 2010, o 15:34
Płeć: Mężczyzna
Lokalizacja: Gołąb

Liczba ciągów rosnących

Post autor: bakala12 » 23 wrz 2013, o 13:13

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

ODPOWIEDZ