Wzór włączeń i wyłączeń-problem

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
xxx150
Użytkownik
Użytkownik
Posty: 47
Rejestracja: 10 sty 2011, o 18:16
Płeć: Mężczyzna
Lokalizacja: Wroclaw
Podziękował: 9 razy

Wzór włączeń i wyłączeń-problem

Post autor: xxx150 »

Witam, mam taki problem: Na ile sposobów można rozmieścić 10 różnych przedmiotów pomiędzy 3 osoby, tak aby każda miała co najmniej jeden?
Normalnie zrobiłbym to tak:
\(\displaystyle{ 3^{10}}\)-wszystkie możliwości
\(\displaystyle{ 3 \cdot 2^{10}}\) przypadek gdy jedna osoba nie dostaje żadnego przedmiotu
\(\displaystyle{ 3}\) przypadek gdy wszystko trafia do jednej osoby, więc przechodząc do wyniku
\(\displaystyle{ 3^{10}-3 \cdot 2^{10}-3}\)
Ale teraz korzystając ze wzoru wł-wył: wszystkich funkcji ze zbioru \(\displaystyle{ A}\), gdzie \(\displaystyle{ \left| A\right|=10}\), w zbiór \(\displaystyle{ B}\), gdzie \(\displaystyle{ \left| B\right|=3}\) jest:
\(\displaystyle{ \sum_{k=0}^{3}(-1)^{k} {3\choose k}(3-k)^{10}}\), czyli w moim przypadku
\(\displaystyle{ 3^{10}-3 \cdot 2^{10}+3}\)
Niestety nie rozumiem, gdzie popełniam błąd czy w moim myśleniu czy coś jest nie tak ze wzorem, który stosuje. Bardzo proszę o pomoc.
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Wzór włączeń i wyłączeń-problem

Post autor: norwimaj »

xxx150 pisze: \(\displaystyle{ 3 \cdot 2^{10}}\) przypadek gdy jedna osoba nie dostaje żadnego przedmiotu
To nie jest dokładnie tak. Jest \(\displaystyle{ 2^{10}}\) możliwości, że pierwsza osoba nic nie dostaje, \(\displaystyle{ 2^{10}}\) możliwości, że druga osoba nic nie dostaje, i \(\displaystyle{ 2^{10}}\) możliwości, że trzecia osoba nic nie dostaje. To nie są rozłączne przypadki, więc nie można ich tak po prostu dodać.

Wynik uzyskany za pomocą wzoru włączeń i wyłączeń jest prawidłowy.
ODPOWIEDZ