Talia kart składa się z \(\displaystyle{ s}\) kolorów, po \(\displaystyle{ n}\) kart w kolorze (ponumerowanych od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\)). Wyciągamy \(\displaystyle{ 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.
Liczba pozdzbiorów o danej własności
-
- Użytkownik
- Posty: 44
- Rejestracja: 25 kwie 2015, o 12:24
- Płeć: Mężczyzna
- Podziękował: 11 razy
- Pomógł: 3 razy
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Re: Liczba pozdzbiorów o danej własności
Można funkcjami tworzącymi.
Enumerator dla wyciągania kart danej liczby to \(\displaystyle{ (1 + x)^{s}}\), wtedy interesuje nas suma współczynników przy \(\displaystyle{ x}\) o potędze \(\displaystyle{ \ge 1}\).
Enumerator dla całego zadania: \(\displaystyle{ \prod_{i = 1}^{n} (1 + x _{i} )^{s}}\). Stąd bierzemy sumę współczynników przy takich jednomianach, które mają wszystkie \(\displaystyle{ x_{i}}\) w potędze \(\displaystyle{ \ge 1}\) i jednocześnie sumę potęg równą \(\displaystyle{ r}\).
Można też napisać jakąś rekurencję:
Niech \(\displaystyle{ t _{i, j}}\) oznacza liczbę sposobów wyciągnięcia \(\displaystyle{ j}\) kart o numerach \(\displaystyle{ \le i}\) tak, że wyciągamy co najmniej \(\displaystyle{ 1}\) kartę dla każdego numeru \(\displaystyle{ \le i}\).
Warunki początkowe: \(\displaystyle{ t_{0, j}= 1}\), \(\displaystyle{ t_{i, 0} = 0}\), \(\displaystyle{ t_{i, j} = 0}\) dla \(\displaystyle{ i > j}\), \(\displaystyle{ t_{i, j} = 0}\) dla \(\displaystyle{ j > r}\).
\(\displaystyle{ t_{i, j} = \sum_{k = 1}^{j} {s \choose k} t_{i - 1, j - k}}\), dla \(\displaystyle{ i, j \ge 1, i \le j, j \le r}\) - dokładamy nowy numer, wybierając \(\displaystyle{ k}\) kart o tym numerze na \(\displaystyle{ {s \choose k}}\) sposobów, a z kart o numerach mniejszych wybieramy \(\displaystyle{ j - k}\) kart na \(\displaystyle{ t_{i - 1, j - k}}\) sposobów.
Wynik to \(\displaystyle{ t_{n, r}}\).
Enumerator dla wyciągania kart danej liczby to \(\displaystyle{ (1 + x)^{s}}\), wtedy interesuje nas suma współczynników przy \(\displaystyle{ x}\) o potędze \(\displaystyle{ \ge 1}\).
Enumerator dla całego zadania: \(\displaystyle{ \prod_{i = 1}^{n} (1 + x _{i} )^{s}}\). Stąd bierzemy sumę współczynników przy takich jednomianach, które mają wszystkie \(\displaystyle{ x_{i}}\) w potędze \(\displaystyle{ \ge 1}\) i jednocześnie sumę potęg równą \(\displaystyle{ r}\).
Można też napisać jakąś rekurencję:
Niech \(\displaystyle{ t _{i, j}}\) oznacza liczbę sposobów wyciągnięcia \(\displaystyle{ j}\) kart o numerach \(\displaystyle{ \le i}\) tak, że wyciągamy co najmniej \(\displaystyle{ 1}\) kartę dla każdego numeru \(\displaystyle{ \le i}\).
Warunki początkowe: \(\displaystyle{ t_{0, j}= 1}\), \(\displaystyle{ t_{i, 0} = 0}\), \(\displaystyle{ t_{i, j} = 0}\) dla \(\displaystyle{ i > j}\), \(\displaystyle{ t_{i, j} = 0}\) dla \(\displaystyle{ j > r}\).
\(\displaystyle{ t_{i, j} = \sum_{k = 1}^{j} {s \choose k} t_{i - 1, j - k}}\), dla \(\displaystyle{ i, j \ge 1, i \le j, j \le r}\) - dokładamy nowy numer, wybierając \(\displaystyle{ k}\) kart o tym numerze na \(\displaystyle{ {s \choose k}}\) sposobów, a z kart o numerach mniejszych wybieramy \(\displaystyle{ j - k}\) kart na \(\displaystyle{ t_{i - 1, j - k}}\) sposobów.
Wynik to \(\displaystyle{ t_{n, r}}\).
Ostatnio zmieniony 12 lip 2017, o 22:20 przez Mruczek, łącznie zmieniany 9 razy.
-
- Użytkownik
- Posty: 44
- Rejestracja: 25 kwie 2015, o 12:24
- Płeć: Mężczyzna
- Podziękował: 11 razy
- Pomógł: 3 razy
Re: Liczba pozdzbiorów o danej własności
Nie rozumiem końca. Czemu przyporządkowujesz podzbiorom kolorów karty? Nie wiem, czy się dobrze zrozumieliśmy. Jest \(\displaystyle{ n}\) kart, każda o innym numerze. Czyli łącznie jest ich \(\displaystyle{ ns}\). Wszystkich podzbiorów jest zatem \(\displaystyle{ {ns \choose r}}\). Nie umiem jednak znaleźć tych, o które pytają w zadaniu.