szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 22 wrz 2013, o 17:30 
Użytkownik

Posty: 19
Lokalizacja: polska
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].
Góra
PostNapisane: 22 wrz 2013, o 17:46 
Użytkownik
n\choose k
Góra
Mężczyzna Offline
PostNapisane: 22 wrz 2013, o 17:52 
Użytkownik
Avatar użytkownika

Posty: 135
Lokalizacja: Wrocław
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].
Góra
Mężczyzna Offline
PostNapisane: 23 wrz 2013, o 12:13 
Gość Specjalny

Posty: 3051
Lokalizacja: Gołąb
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
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba grafów izomorficznych etykietowanych  Heniek1991  1
 Zliczanie ciągów spełniających warunki.  MgielkaCuba  1
 Wyznaczanie ciągów zero jedynkowych - kombinacje?  Patman  2
 Udowodnić że liczba jest liczbą pierwszą  kordi1221  1
 Liczba dróg monotonicznych - liczby Catalana  alaicja  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl