kombinatoryka pytanie

[july04]

na ile sposobów mogę podzielić 8 czerwonych, 11 zielonych, 6 granatowych klocków pomiędzy 4 osoby tak aby każda dostałą co najmniej jeden klocek?

[kerajs]

Może na tyle:
\(\displaystyle{ {8+4-1 \choose 4-1} \cdot {11+4-1 \choose 4-1} \cdot {6+4-1 \choose 4-1} - {4 \choose 3} {8+3-1 \choose 3-1} \cdot {11+3-1 \choose 3-1} \cdot {6+3-1 \choose 3-1}+ \\ +{4 \choose 2} {8+2-1 \choose 2-1} \cdot {11+2-1 \choose 2-1} \cdot {6+2-1 \choose 2-1}-{4 \choose 1} {8+1-1 \choose 1-1} \cdot {11+1-1 \choose 1-1} \cdot {6+1-1 \choose 1-1}=... }\)

[july04]

Dziękuję za odpowiedź. Chciałbym jeszcze tylko zrozumieć, dlaczego tak to się liczy. Póki co nie odkryłem żadnej innej metody, jak nauczenie się kilku typów zadań na pamięć i analogicznego rozwiązywania podobnych.

[kerajs]

Moim zdaniem uczenie się na pamięć nie zadziała, gdyż nawet mała modyfikacja treści zadania może znacząco wpłynąć na rozwiązanie.
Ponadto, powyższe zadanie nie należy do najprostszych. Tu użyłem kombinacji z powtórzeniami i zasady włączeń i wyłączeń.

Wersja łatwiejsza zadania:
Na ile sposobów można podzielić 8 czerwonych klocków pomiędzy 4 osoby tak, aby każda dostała co najmniej jeden klocek?
\(\displaystyle{ {8+4-1 \choose 4-1} - {4 \choose 3} {8+3-1 \choose 3-1} +{4 \choose 2} {8+2-1 \choose 2-1} -{4 \choose 1} {8+1-1 \choose 1-1}=... }\)
( choć akurat tutaj można szybciej: \(\displaystyle{ {8-1 \choose 4-1}}\) )
Napisz którego fragmentu rozwiązania nie rozumiesz.

[july04]

Niezależnie czy to moja wersja, czy ta łatwiejsza. Mam do czynienia z kombinacją kilku zbiorów. Mam zbiór wszystkich klocków a 25 elementów. trzy rozdzielne zbory jeden ma 8, drugi 11, trzeci 6 elementów oraz zbiór czterech osób. Czego nie rozumiem- gdzie i dlaczego takie a nie inne liczby pojawiają się w dwumianie. Szczególnie nie wiem gdzie znajduje się stwierdzenie- co najmniej jeden, jedna. Wiem pytanie zbyt ogóle- nie oczekuję odpowiedzi na nie.

[kerajs]

Wpierw to przeczytaj:    

Załóżmy że mam znaleźć liczbę rozwiązań równania: \(\displaystyle{ x_1+x_2+x_3=6}\) w liczbach naturalnych dodatnich (np: podzielić 6 cukierków między trójkę dzieci tak aby każde dostało przynajmniej jednego cukierka, albo rozdzielić 6 zadań między trzech studentów tak aby każdy dostał przynajmniej jedno zadanie).
Mogę wypisać rozwiązania podając trójki \(\displaystyle{ x_1,x_2,x_3}\):
\(\displaystyle{ 4,1,1\\
3,2,1\\
3,1,2\\
2,3,1\\
2,2,2\\
2,1,3\\
1,4,1\\
1,3,2\\
1,2,3\\
1,1,4}\)
i je zliczyć (jest ich 10)
Inne podejście to liczbę \(\displaystyle{ 6}\) przedstawić jako sumę jedynek \(\displaystyle{ 1+1+1+1+1+1}\). Aby dostać dowolne rozwiązanie wystarczy dwa plusy zamienić na przecinki (np: \(\displaystyle{ 1,1+1,1+1+1}\) albo \(\displaystyle{ 1+1+1+1,1,1}\))
Czyli ilość rozwiązań to ilość wyborów dwóch plusów (o jeden mniej niż niewiadomych) z pięciu (o jeden mniej niż znana suma). \(\displaystyle{ {5 \choose 2}=10}\) albo \(\displaystyle{ {6-1 \choose 3-1}={5 \choose 2}=10}\)
Ogólnie:
Liczba rozwiązań równania: \(\displaystyle{ x_1+x_2+...+x_n=S \ \ \wedge S \ge n}\) w liczbach naturalnych dodatnich to: \(\displaystyle{ {S-1 \choose n-1}}\)

A co jeśli mam znaleźć liczbę rozwiązań równania: \(\displaystyle{ x_1+x_2+x_3=6}\) w liczbach naturalnych (zero uznaję za naturalne) ?
Wtedy robiąc podstawienie:
\(\displaystyle{ t_1=x_1+1\\
t_2=x_2+1\\
t_3=x_3+1}\)
mam znaleźć liczbę rozwiązań równania: \(\displaystyle{ t_1-1+t_2-1+t_3-1=6}\) w liczbach naturalnych dodatnich. To jest już proste i z tekstu powyżej wiem że ilość ta to: \(\displaystyle{ {6+3-1 \choose 3-1}=28}\).

i odpowiedz na pytania (wystarczy wzorek):
1. Na ile sposobów można podzielić 8 czerwonych klocków pomiędzy 4 osoby?
2. Na ile sposobów można podzielić 8 czerwonych klocków pomiędzy 2 osoby?
3. Na ile sposobów można podzielić 8 czerwonych klocków pomiędzy 4 osoby tak, aby każda dostała co najmniej jeden klocek?
4. Na ile sposobów można podzielić 8 czerwonych klocków pomiędzy 2 osoby tak, aby każda dostała co najmniej jeden klocek?

[july04]

1 \(\displaystyle{ \binom{8}{4}}\)
2 \(\displaystyle{ \binom{8}{2}}\)
3 \(\displaystyle{ \binom{8-1}{4-1}}\)
4 \(\displaystyle{ \binom{8-1}{2-1}}\)

gdyby było Na ile sposobów można podzielić 8 czerwonych klocków pomiędzy 4 osoby tak, aby każda dostała co najmniej dwa klocki?
\(\displaystyle{ \binom{8-1}{4-2}}\)

Dodano po 4 godzinach 26 minutach 35 sekundach:

Wpierw to przeczytaj:    

Załóżmy że mam znaleźć liczbę rozwiązań równania: \(\displaystyle{ x_1+x_2+x_3=6}\) w liczbach naturalnych dodatnich (np: podzielić 6 cukierków między trójkę dzieci tak aby każde dostało przynajmniej jednego cukierka, albo rozdzielić 6 zadań między trzech studentów tak aby każdy dostał przynajmniej jedno zadanie).
Mogę wypisać rozwiązania podając trójki \(\displaystyle{ x_1,x_2,x_3}\):
\(\displaystyle{ 4,1,1\\
3,2,1\\
3,1,2\\
2,3,1\\
2,2,2\\
2,1,3\\
1,4,1\\
1,3,2\\
1,2,3\\
1,1,4}\)
i je zliczyć (jest ich 10)
Inne podejście to liczbę \(\displaystyle{ 6}\) przedstawić jako sumę jedynek \(\displaystyle{ 1+1+1+1+1+1}\). Aby dostać dowolne rozwiązanie wystarczy dwa plusy zamienić na przecinki (np: \(\displaystyle{ 1,1+1,1+1+1}\) albo \(\displaystyle{ 1+1+1+1,1,1}\))
Czyli ilość rozwiązań to ilość wyborów dwóch plusów (o jeden mniej niż niewiadomych) z pięciu (o jeden mniej niż znana suma). \(\displaystyle{ {5 \choose 2}=10}\) albo \(\displaystyle{ {6-1 \choose 3-1}={5 \choose 2}=10}\)
Ogólnie:
Liczba rozwiązań równania: \(\displaystyle{ x_1+x_2+...+x_n=S \ \ \wedge S \ge n}\) w liczbach naturalnych dodatnich to: \(\displaystyle{ {S-1 \choose n-1}}\)

A co jeśli mam znaleźć liczbę rozwiązań równania: \(\displaystyle{ x_1+x_2+x_3=6}\) w liczbach naturalnych (zero uznaję za naturalne) ?
Wtedy robiąc podstawienie:
\(\displaystyle{ t_1=x_1+1\\
t_2=x_2+1\\
t_3=x_3+1}\)
mam znaleźć liczbę rozwiązań równania: \(\displaystyle{ t_1-1+t_2-1+t_3-1=6}\) w liczbach naturalnych dodatnich. To jest już proste i z tekstu powyżej wiem że ilość ta to: \(\displaystyle{ {6+3-1 \choose 3-1}=28}\).

i odpowiedz na pytania (wystarczy wzorek):
1. Na ile sposobów można podzielić 8 czerwonych klocków pomiędzy 4 osoby?
2. Na ile sposobów można podzielić 8 czerwonych klocków pomiędzy 2 osoby?
3. Na ile sposobów można podzielić 8 czerwonych klocków pomiędzy 4 osoby tak, aby każda dostała co najmniej jeden klocek?
4. Na ile sposobów można podzielić 8 czerwonych klocków pomiędzy 2 osoby tak, aby każda dostała co najmniej jeden klocek?

Pytanie dodatkowe, już nie związane dokładniej z zagadnieniem jakie miałem do rozwiązania ale może się pojawić rożny pomysł wykładowcy.

co jeśli np. równanie będzie miało postać:

\(\displaystyle{ x_1+x_2+x_3=6}\) ale z warunkami, że \(\displaystyle{ x_1 \ge 1; x_2 \le 6; 2 \le x_3 \le 8}\) lub inne dowolne warunki. ten ostatni wydaje się najtrudniejszy.

[kerajs]

1 \(\displaystyle{ \binom{8}{4}}\)
2 \(\displaystyle{ \binom{8}{2}}\)

Niestety nie.
1) \(\displaystyle{ {8+4-1 \choose 4-1} }\)
2) \(\displaystyle{ {8+2-1 \choose 2-1} }\)

3 \(\displaystyle{ \binom{8-1}{4-1}}\)
4 \(\displaystyle{ \binom{8-1}{2-1}}\)

OK

Pytanie dodatkowe, już nie związane dokładniej z zagadnieniem jakie miałem do rozwiązania ale może się pojawić rożny pomysł wykładowcy.

co jeśli np. równanie będzie miało postać:

\(\displaystyle{ x_1+x_2+x_3=6}\) ale z warunkami, że \(\displaystyle{ x_1 \ge 1; x_2 \le 6; 2 \le x_3 \le 8}\) lub inne dowolne warunki. ten ostatni wydaje się najtrudniejszy.

Ograniczenia dolne nie są żadnym problemem. Z posiadanych elementów (tu czerwonych klocków) bierzesz i rozdajesz tyle aby każdej niewiadomej brakował jeden element do spełnienia warunku. Dopiero potem liczysz ilość podziałów dla zmniejszonego nierozdanego zbioru elementów.
Tak jak tu:

gdyby było Na ile sposobów można podzielić 8 czerwonych klocków pomiędzy 4 osoby tak, aby każda dostała co najmniej dwa klocki?
\(\displaystyle{ \binom{8-1}{4-2}}\)

To błędna odpowiedź.
Wpierw rozdaję po jednym klocku co da treść:
Na ile sposobów można podzielić 8-4 czerwonych klocków pomiędzy 4 osoby tak, aby każda dostała co najmniej 2-1 klocki?
Odpowiedzią będzie \(\displaystyle{ \binom{8-4-1}{4-1}=1}\)

Ograniczenia z góry to większy problem. Czasami szybciej jest wypisać możliwe zdarzenia niż wyliczać je np: z iloczynu wielomianów. Jednak odłóż ten temat na czas, gdy nabierzesz biegłości w rozwiązywaniu prostszych zadań.

Wyjaśnienia do:

Na ile sposobów można podzielić 8 czerwonych klocków pomiędzy 4 osoby tak, aby każda dostała co najmniej jeden klocek?
\(\displaystyle{ {8+4-1 \choose 4-1} - {4 \choose 3} {8+3-1 \choose 3-1} +{4 \choose 2} {8+2-1 \choose 2-1} -{4 \choose 1} {8+1-1 \choose 1-1}=... }\)
( choć akurat tutaj można szybciej: \(\displaystyle{ {8-1 \choose 4-1}}\) )

Wersję szybszą rozumiesz, gdyż sam wskazałeś poprawny wynik w pytaniu 3)
Wersja z zasady włączeń i wyłączeń:
\(\displaystyle{ {8+4-1 \choose 4-1} }\) to rozdanie klocków między 4 osoby, jednak są tu także układy gdy ktoś (jedna, dwie, a nawet trzy osoby) nic nie dostał. Wobec tego odejmuję rozkłady klocków między trzy osoby: \(\displaystyle{ {8+3-1 \choose 3-1}}\) pomnożone przez możliwe obdarowywane trójki \(\displaystyle{ {4 \choose 3}}\) . To jeszcze nie jest wynik, gdyż układy w których tylko dwie osoby dostały klocki były odjęte dwukrotnie (zamiast tylko raz) . Dodaję więc brakujące układy: \(\displaystyle{ {4 \choose 2} {8+2-1 \choose 2-1} }\) i odejmuję te które znów nadmiarowo były zliczane: \(\displaystyle{ {4 \choose 1} {8+1-1 \choose 1-1}}\).

Jak przeliczysz powyższe, to wyniki z obu wersji są identyczne.