Kombinacje ze stołami i liczbą gości

[dosia290]

Proszę o pomoc, jakim wzorem mogę zaprezentować taką sytuację:

Spośród \(\displaystyle{ n}\) wszystkich zaproszonych gości \(\displaystyle{ k}\) gości nie lubi się nawzajem. Mamy do dyspozycji \(\displaystyle{ s}\) stołów po \(\displaystyle{ 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:

\(\displaystyle{ {5 \choose 4} \cdot {5 \choose 1} ^{4} =3125}\)

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

\(\displaystyle{ {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?

[kinia7]

Wszystkich możliwości usadzenia 25 ludzi przy pięciu pięcioosobowych stolikach jest
\(\displaystyle{ {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
\(\displaystyle{ {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}\)
\(\displaystyle{ \approx 154\cdot10^{12}}\)

[dosia290]

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: \(\displaystyle{ x _{1}}\) nie lubi się z \(\displaystyle{ x _{2}}\), co oznacza, że nie mogą siedzieć przy tym samym stoliku i \(\displaystyle{ y_{1}}\) nie lubi się z \(\displaystyle{ y _{2}}\), co oznacza, że też nie mogą siedzieć przy tym samym stole, ale nie ma żadnych zastrzeżeń, żeby siedzieć przy \(\displaystyle{ x _{1}}\) lub \(\displaystyle{ 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:

\(\displaystyle{ left[ {5 choose 1} cdot {5 choose 1}
ight] cdot left[ {4 choose 1} cdot {5 choose 1}
ight] cdot left[ {3 choose 1} cdot {5 choose 1} cdot {2 choose 1} cdot {4 choose 1}
ight] cdot left[ {2 choose 1} cdot {5 choose 1} + {1 choose 1} cdot {4 choose 1} cdot {1 choose 1} cdot {5 choose 1} +}\)
\(\displaystyle{ + {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 \(\displaystyle{ 21!}\) jeszcze.

Dla 3 par to już jakaś masakra, dlatego szukam wzoru ogólnego...

[kinia7]

Na pewno coś masz nie tak, gdyż \(\displaystyle{ 21! \approx 51\cdot10^{18}}\)

\(\displaystyle{ x_1}\) i \(\displaystyle{ x_2}\) mogą zajmować miejsca na sposobów \(\displaystyle{ {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
\(\displaystyle{ {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}}\)

\(\displaystyle{ x_1}\) i \(\displaystyle{ x_2}\) mogą zajmować miejsca na sposobów \(\displaystyle{ {5 \choose 2} \cdot 2}\)
przy stolikach możemy mieć układy: 1,1,1,1,0
\(\displaystyle{ y_1}\) i \(\displaystyle{ y_2}\) mogą zajmować miejsca na sposobów \(\displaystyle{ {2 \choose 0} \cdot {3 \choose 2} \cdot 2}\)
w tej sytuacji możliwych usadzeń 25 ludzi jest
\(\displaystyle{ {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
\(\displaystyle{ y_1}\) i \(\displaystyle{ y_2}\) mogą zajmować miejsca na sposobów \(\displaystyle{ {2 \choose 1}\cdot {3 \choose 1} \cdot 2}\)
w tej sytuacji możliwych usadzeń 25 ludzi jest
\(\displaystyle{ {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
\(\displaystyle{ y_1}\) i \(\displaystyle{ y_2}\) mogą zajmować miejsca na sposobów \(\displaystyle{ {2 \choose 2}\cdot {3 \choose 0} \cdot 2}\)
w tej sytuacji możliwych usadzeń 25 ludzi jest
\(\displaystyle{ {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 \(\displaystyle{ 433\,231\,610\,011\,200 \approx 433\cdot10^{12}}\)

przy trzech parach sprawa się mocniej komplikuje