szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 lip 2017, o 20:05 
Użytkownik

Posty: 45
Talia kart składa się z s kolorów, po n kart w kolorze (ponumerowanych od 1 do n). Wyciągamy r kart. Na ile sposobów można to zrobić tak, by wyciągnięto karty o wszystkich numerach? Innymi słowy pytanie jest o ilość takich podzbiorów tych kart, że dany podzbiór zawiera karty o wszystkich numerach.

Nie mogę sobie z tym poradzić, nie licząc jakichś zestawów parokrotnie.
Góra
Mężczyzna Offline
PostNapisane: 12 lip 2017, o 21:00 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Można funkcjami tworzącymi.
Enumerator dla wyciągania kart danej liczby to (1 + x)^{s}, wtedy interesuje nas suma współczynników przy x o potędze \ge 1.
Enumerator dla całego zadania: \prod_{i = 1}^{n} (1 + x _{i} )^{s}. Stąd bierzemy sumę współczynników przy takich jednomianach, które mają wszystkie x_{i} w potędze \ge 1 i jednocześnie sumę potęg równą r.

Można też napisać jakąś rekurencję:
Niech t _{i, j} oznacza liczbę sposobów wyciągnięcia j kart o numerach \le i tak, że wyciągamy co najmniej 1 kartę dla każdego numeru \le i.
Warunki początkowe: t_{0, j}= 1, t_{i, 0} = 0, t_{i, j} = 0 dla i > j, t_{i, j} = 0 dla j > r.
t_{i, j} =  \sum_{k = 1}^{j}  {s \choose k} t_{i - 1, j - k}, dla i, j  \ge 1, i  \le j, j   \le  r - dokładamy nowy numer, wybierając k kart o tym numerze na {s \choose k} sposobów, a z kart o numerach mniejszych wybieramy j - k kart na t_{i - 1, j - k} sposobów.
Wynik to t_{n, r}.
Góra
Mężczyzna Offline
PostNapisane: 12 lip 2017, o 21:17 
Użytkownik

Posty: 45
Nie rozumiem końca. Czemu przyporządkowujesz podzbiorom kolorów karty? Nie wiem, czy się dobrze zrozumieliśmy. Jest n kart, każda o innym numerze. Czyli łącznie jest ich ns. Wszystkich podzbiorów jest zatem {ns \choose r}. Nie umiem jednak znaleźć tych, o które pytają w zadaniu.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Własności relacji - zadanie 7  rafal_85  0
 Maksymalna liczba punktów przecięcia odcinków w okręgu  bastek91  3
 liczba permutacji - zadanie 5  nieOna3  4
 Liczba rozwiązań równania.  Morisson  12
 Liczba kombinacji zbioru z maksymalną sumą  mar1986  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl