Na ile sposobów można wybrać 4 buty...

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
edaro
Użytkownik
Użytkownik
Posty: 268
Rejestracja: 18 gru 2006, o 20:01
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 56 razy
Pomógł: 16 razy

Na ile sposobów można wybrać 4 buty...

Post autor: edaro »

Mamy 10 par butów. Na ile sposobów możemy wybrać 4 buty, tak aby była co najmniej jedna para.

Moje rozwiązanie:
\(\displaystyle{ {20 \choose 1}{18 \choose 1}{17 \choose 1} + {20 \choose 1}{18 \choose 1}}\)

Czy jest poprawne?
mat_61
Użytkownik
Użytkownik
Posty: 4618
Rejestracja: 8 lis 2009, o 10:22
Płeć: Mężczyzna
Lokalizacja: Racibórz
Pomógł: 866 razy

Na ile sposobów można wybrać 4 buty...

Post autor: mat_61 »

Nie wiem jaki był Twój sposób rozumowania ale nie jest to poprawne rozwiązanie. Zauważ, że wyliczona wg Twojego sposobu ilość możliwości jest większa niż ilość wszystkich możliwych zbiorów 4 -elementowych utworzonych ze zbioru 20-elementowego czyli \(\displaystyle{ {20 \choose 4}}\)

Możesz albo obliczyć ilość możliwości zdarzenia przeciwnego: wśród wybranych butów nie będzie żadnej pary, albo wprost jako sumę zdarzeń (wśród wybranych butów będzie jedna para + wśród wybranych butów będą dwie pary).
edaro
Użytkownik
Użytkownik
Posty: 268
Rejestracja: 18 gru 2006, o 20:01
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 56 razy
Pomógł: 16 razy

Na ile sposobów można wybrać 4 buty...

Post autor: edaro »

Korzystając ze zdarzenia przeciwnego daje to nam
\(\displaystyle{ {20 \choose 4} - {10 \choose 2}{8 \choose 2}}\)

a z sumy zdarzeń zrobiłbym
\(\displaystyle{ {20 \choose 3} + {20 \choose 2}}\)

ale wyniki są różne :]
mat_61
Użytkownik
Użytkownik
Posty: 4618
Rejestracja: 8 lis 2009, o 10:22
Płeć: Mężczyzna
Lokalizacja: Racibórz
Pomógł: 866 razy

Na ile sposobów można wybrać 4 buty...

Post autor: mat_61 »

A mógłbyś opisać skąd masz ten drugi składnik przy pierwszym sposobie liczenia? Czym jest np. wybór, który liczysz jako \(\displaystyle{ {10 \choose 2}}\) ?
Ostatnio zmieniony 13 lis 2010, o 16:50 przez mat_61, łącznie zmieniany 2 razy.
edaro
Użytkownik
Użytkownik
Posty: 268
Rejestracja: 18 gru 2006, o 20:01
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 56 razy
Pomógł: 16 razy

Na ile sposobów można wybrać 4 buty...

Post autor: edaro »

Biorę 2 buty ze wszystkich lewych ?
mat_61
Użytkownik
Użytkownik
Posty: 4618
Rejestracja: 8 lis 2009, o 10:22
Płeć: Mężczyzna
Lokalizacja: Racibórz
Pomógł: 866 razy

Na ile sposobów można wybrać 4 buty...

Post autor: mat_61 »

Oczywiście jak wybierzesz 2 buty ze wszystkich lewych to na pewno nie będzie pary. Ale z tego nic nie wynika. Mogę się domyślać, że \(\displaystyle{ {8 \choose 2}}\) to wybór dwóch prawych butów z ośmiu które nie są parą do dwóch wylosowanych wcześniej. Zauważ jednak, że jeżeli nie ma być pary, to mogą być 3 lewe i 1 prawy (oczywiście nie do pary), 4 prawe itd.

Natomiast z sumy zdarzeń poprawny jest tylko drugi składnik tzn. wybór dwóch par z 10. Natomiast wybór dokładnie jednej pary już nie.
edaro
Użytkownik
Użytkownik
Posty: 268
Rejestracja: 18 gru 2006, o 20:01
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 56 razy
Pomógł: 16 razy

Na ile sposobów można wybrać 4 buty...

Post autor: edaro »

Hmmm... sumą zdarzeń:
\(\displaystyle{ {20 \choose 3} \cdot 3 + {20 \choose 2}}\)

jak to zrobić zdarzeniem przeciwnym to na razie nie wiem. Pomysł jest taki:
1) Biorę jeden dowolny but
2) Biorę jeden but, tak aby nie był do pary z wcześniejszym
3) Biorę jeden but, tak aby nie był do pary z wcześniejszymi 2-ma
4) Biorę but tak, aby nie był do pary z żadnym z wcześniejszych

daje to
\(\displaystyle{ {20 \choose 4} - 20\cdot18\cdot16\cdot14 < 0}\)
mat_61
Użytkownik
Użytkownik
Posty: 4618
Rejestracja: 8 lis 2009, o 10:22
Płeć: Mężczyzna
Lokalizacja: Racibórz
Pomógł: 866 razy

Na ile sposobów można wybrać 4 buty...

Post autor: mat_61 »

Suma zdarzeń - pierwszy składnik nie za bardzo. Zauważ, że ma być tylko jedna para, czyli masz 10 możliwości wyboru. Trzeci but dowolny z pozostałych (czyli z 18), a czwarty but dowolny z wyjątkiem tego do pary wylosowanego jako trzeci (czyli z 16). Oczywiście wybór np. w trzecim kroku buta nr 12 a w czwartym buta nr 17, to taki sam wybór jak wybranie w trzecim kroku buta nr 17 a w czwartym buta nr 12. Musisz więc podzielić tą ilość przez 2! (czyli ilość permutacji dwóch elementów). Będzie więc:

\(\displaystyle{ 10 \cdot \frac{18 \cdot 16}{2!}}\)

Drugi składnik, to ma być wybór 2 par z 10 a nie z 20.

Pomysł na wariant ze zdarzeniem przeciwnym jak najbardziej dobry. Zapomniałeś tylko uwzględnić to (tak jak w przykładzie powyżej), że nie jest istotna kolejność losowanych elementów.
edaro
Użytkownik
Użytkownik
Posty: 268
Rejestracja: 18 gru 2006, o 20:01
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 56 razy
Pomógł: 16 razy

Na ile sposobów można wybrać 4 buty...

Post autor: edaro »

\(\displaystyle{ {20 \choose 4} - \frac{20*18*16*14}{4!}}\)
mat_61
Użytkownik
Użytkownik
Posty: 4618
Rejestracja: 8 lis 2009, o 10:22
Płeć: Mężczyzna
Lokalizacja: Racibórz
Pomógł: 866 razy

Na ile sposobów można wybrać 4 buty...

Post autor: mat_61 »

Teraz jest OK.
Oczywiście identyczny wynik otrzymasz robiąc obliczenia drugim sposobem.
edaro
Użytkownik
Użytkownik
Posty: 268
Rejestracja: 18 gru 2006, o 20:01
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 56 razy
Pomógł: 16 razy

Na ile sposobów można wybrać 4 buty...

Post autor: edaro »

A jeżeli kolejność elementów miałaby znaczenie to jak wyglądałoby to sumą zdarzeń?
mat_61
Użytkownik
Użytkownik
Posty: 4618
Rejestracja: 8 lis 2009, o 10:22
Płeć: Mężczyzna
Lokalizacja: Racibórz
Pomógł: 866 razy

Na ile sposobów można wybrać 4 buty...

Post autor: mat_61 »

Jeżeli nie ma znaczenia kolejność elementów i mamy obliczoną ilość zdarzeń, to teraz chcąc uwzględnić kolejność wystarczy tą ilość pomnożyć przez permutację tych elementów.
Skoro tutaj mamy 1485 różnych 4-elementowych zbiorów to z każdego z tych zbiorów możemy utworzyć 4! ciągów.

Oczywiście jeżeli w zadaniu byłby tylko wariant gdzie ważna byłaby kolejność elementów, to wówczas sposób zrobienia mógłby być inny. Np. Zamiast kombinacji byłyby wariacje bez powtórzeń (bo kombinacja \(\displaystyle{ C^{k}_{n}}\) pomnożona przez permutację \(\displaystyle{ P_{k}}\) daje wariację bez powtórzeń \(\displaystyle{ V^{k}_{n}}\))
ODPOWIEDZ