szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 3 kwi 2017, o 17:52 
Użytkownik

Posty: 24
Lokalizacja: Szczecin
Proszę o pomoc, jakim wzorem mogę zaprezentować taką sytuację:

Spośród n wszystkich zaproszonych gości k gości nie lubi się nawzajem. Mamy do dyspozycji s stołów po m miejsc każdy.

Na ile sposobów można usadzić wszystkich gości, tak żeby osoby, które nie lubią się nawzajem nie siedziały przy jednym stole?

Dla ułatwienia prowadzący pozwolił nam przyjąć parę stałych. Mamy 5 stołów, po 5 miejsc każdy. A liczba gości, którzy nie mogą usiąść przy jednym stole to 4.

Uznałem, że 4 osoby, co się nie lubią, nie lubią się jednocześnie, tzn. każdy z nich siedzi osobno przy innym stole. A więc takich możliwości jest:

{5 \choose 4}  \cdot {5 \choose 1} ^{4} =3125

I te 3125 muszę odjąć od liczby wszystkich możliwych kombinacji, czyli:

{25 \choose 5} \cdot {20 \choose 5}\cdot {15 \choose 5}\cdot {10 \choose 5}\cdot {5 \choose 5} ??

Czy w dobry sposób podejmuje się rozwiązania tego?
Góra
Kobieta Offline
PostNapisane: 3 kwi 2017, o 20:40 
Użytkownik
Avatar użytkownika

Posty: 663
Lokalizacja: Wrocław
Wszystkich możliwości usadzenia 25 ludzi przy pięciu pięcioosobowych stolikach jest
{25 \choose 5}  \cdot  {20 \choose 5}  \cdot  {15 \choose 5}  \cdot  {10 \choose 5} \cdot {5 \choose 5} \approx 623\cdot10^{12}
takich możliwości, że każdy z czterech "wybranych" będzie siedzieć przy innym stoliku jest
{5 \choose 4}  \cdot  {21 \choose 5}  \cdot  \left[{4 \choose 1}  \cdot  {16 \choose 4}\right] \cdot \left[{3 \choose 1}  \cdot  {12 \choose 4}\right] \cdot \left[{2 \choose 1}  \cdot  {8 \choose 4}\right] \cdot \left[{1 \choose 1}  \cdot  {4 \choose 4}\right] \approx
\approx  154\cdot10^{12}
Góra
Kobieta Offline
PostNapisane: 3 kwi 2017, o 21:47 
Użytkownik

Posty: 24
Lokalizacja: Szczecin
Dziękuję za pomoc :)

Mam jeszcze dwa pytania. Gdybyśmy spośród 25 gości wydzielili pary osób, które się nie lubią np: x _{1} nie lubi się z x _{2}, co oznacza, że nie mogą siedzieć przy tym samym stoliku i y_{1} nie lubi się z y _{2}, co oznacza, że też nie mogą siedzieć przy tym samym stole, ale nie ma żadnych zastrzeżeń, żeby siedzieć przy x _{1} lub x _{2}.

Mam problem, żeby zapisać ogólny wzór dla takich par. Jak robię to po kolei dla dwóch par, to wychodzi mi taka liczba kombinacji:

\left[  {5 \choose 1}  \cdot  {5 \choose 1} \right]  \cdot \left[  {4 \choose 1}  \cdot  {5 \choose 1} \right]  \cdot  \left[  {3 \choose 1}  \cdot  {5 \choose 1}  \cdot   {2 \choose 1}  \cdot  {4 \choose 1}  \right]  \cdot  \left[  {2 \choose 1}  \cdot  {5 \choose 1} +  {1 \choose 1}  \cdot  {4 \choose 1}  \cdot  {1 \choose 1}   \cdot  {5 \choose 1} +
+ {1 \choose 1}  \cdot  {4 \choose 1}  \cdot  {1 \choose 1}   \cdot  {5 \choose 1} + {2 \choose 1}  \cdot  {4 \choose 1}  \right]

I to wszystko razy 21! jeszcze.

Dla 3 par to już jakaś masakra, dlatego szukam wzoru ogólnego...
Góra
Kobieta Offline
PostNapisane: 3 kwi 2017, o 23:42 
Użytkownik
Avatar użytkownika

Posty: 663
Lokalizacja: Wrocław
Na pewno coś masz nie tak, gdyż 21! \approx 51\cdot10^{18}

x_1 i x_2 mogą zajmować miejsca na sposobów {5 \choose 2} \cdot 2
w ten sposób mamy przy stolikach zajęte miejsca 1,1,0,0,0
więc wszystkich możliwych usadzeń 25 ludzi jest
{5 \choose 2} \cdot 2 \cdot  {23 \choose 4}  \cdot  {19 \choose 4}  \cdot  {15 \choose 5} \cdot  {10 \choose 5} \cdot  {5 \choose 5} \approx 519 \cdot 10^{12}

x_1 i x_2 mogą zajmować miejsca na sposobów {5 \choose 2} \cdot 2
przy stolikach możemy mieć układy: 1,1,1,1,0
y_1 i y_2 mogą zajmować miejsca na sposobów {2 \choose 0} \cdot {3 \choose 2} \cdot 2
w tej sytuacji możliwych usadzeń 25 ludzi jest
{5 \choose 2} \cdot 2 \cdot {2 \choose 0} \cdot {3 \choose 2} \cdot 2 \cdot{21 \choose 4}  \cdot  {17 \choose 4}  \cdot  {13 \choose 4} \cdot  {9 \choose 4} \cdot  {5 \choose 5} \approx 154 \cdot 10^{12}
lub przy stolikach możemy mieć układy: 2,1,1,0,0
y_1 i y_2 mogą zajmować miejsca na sposobów {2 \choose 1}\cdot  {3 \choose 1} \cdot 2
w tej sytuacji możliwych usadzeń 25 ludzi jest
{5 \choose 2} \cdot 2 \cdot  {2 \choose 1}\cdot  {3 \choose 1} \cdot 2 \cdot{21 \choose 3}  \cdot  {18 \choose 4}  \cdot  {14 \choose 4} \cdot  {10 \choose 5} \cdot  {5 \choose 5} \approx 246 \cdot 10^{12}
lub przy stolikach możemy mieć układy: 2,2,0,0,0
y_1 i y_2 mogą zajmować miejsca na sposobów {2 \choose 2}\cdot  {3 \choose 0} \cdot 2
w tej sytuacji możliwych usadzeń 25 ludzi jest
{5 \choose 2} \cdot 2 \cdot  {2 \choose 2}\cdot  {3 \choose 0} \cdot 2 \cdot{21 \choose 3}  \cdot  {18 \choose 3}  \cdot  {15 \choose 5} \cdot  {10 \choose 5} \cdot  {5 \choose 5} \approx 33 \cdot 10^{12}
łącznie wszystkich możliwych usadzeń przy dwóch parach "wrogów" jest 433\,231\,610\,011\,200 \approx 433\cdot10^{12}

przy trzech parach sprawa się mocniej komplikuje :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Kombinacje z n-elementami, trzy pary z n osób  Browning0  0
 Kombinacje - zadanie 10  iceman2  4
 Kombinacje i hotele ;)  alternox  1
 Słowotok - liczba wszystkich ciągów  przem_as  0
 Oblicz kombinacje liczb  madzia309  9
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl