Kombinacja elementów z podzbiorów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Adam274
Użytkownik
Użytkownik
Posty: 26
Rejestracja: 25 lis 2009, o 11:12
Płeć: Mężczyzna
Lokalizacja: Częstochowa

Kombinacja elementów z podzbiorów

Post autor: Adam274 » 20 paź 2013, o 14:45

Witam. Mam zbiór złożony z podzbiorów składających się z różnej ilości elementów, np.:

\(\left\{ \left\{ 1\right\} , \left\{ 2\right\} , \left\{ 3, 4\right\}, \left\{ 5, 6, 7\right\} \right\}\)

\(n\) - ilość podzbiorów (w przykładzie 4)
\(m_{1}, m_{2}, ..., m_{n}\) - ilość elementów w każdym podzbiorze (w przykładzie 1, 1, 2, 3)

Pytanie jest następujące: na ile sposobów można wybrać k elementów z całego zbioru, biorąc maksymalnie jeden element z każdego podzbioru? Przykładowo, dla k=3 w przytoczonym zbiorze można wybrać te liczby na 17 sposobów, a dla k=4 na 6 sposobów, ale czy jest na to jakiś wzór?

Wiadomo, gdyby każdy podzbiór składał się tylko z jednego elementu, to wszystko sprowadzałoby się do \({n \choose k}\), jednak w tym przypadku brakuje mi pomysłu.

Z góry dzięki za pomoc.

Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 3706
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko

Kombinacja elementów z podzbiorów

Post autor: arek1357 » 21 paź 2013, o 10:13

\(\sum_{m_{i_{1}},...,m_{i_{k}}}^{}m_{i_{1}}m_{i_{2}}...m_{i_{k}}\)

ODPOWIEDZ