Liczba pozdzbiorów o danej własności

[Downonmyluck]

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.

[Mruczek]

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}}\).

[Downonmyluck]

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.