Zadanie z kombinatoryki

Question

Witam,

trudzę się z rozwiązaniem następującego zadania:

Na ile sposobów można posadzić 8 osób przy 4 nierozróżnialnych okrągłych stolikach, przy założeniu, że przy każdym stoliku siedzi co najmniej jedna osoba i liczy się kto obok kogo siedzi.

Czy należy znaleźć ilość możliwych podziałów zbioru osób na 4 rozłączne niepuste podzbiory uporządkowane, przy czym kolejność w jakiej występują te podzbiory nie ma znaczenia bo stoły są nierozróżnialne?

Jeżeli już mam x osób przy danym stole to mogę je posadzić przy nim na x! sposobów? Tylko jakie znaczenie ma, że stół jest okrągły - czy to będzie (x - 1)! sposobów?

Wiem, pytania być może są głupie i nie logiczne za co przepraszam. :( Liczę na Państwa pomoc w dojściu do rozwiązania.

Answer 1

Zgodnie z kalkulatorem 6769 sposobów. Korzystamy z pierwszego wzoru na tej stronie, ponieważ:

(...) i liczy się kto obok kogo siedzi.

oznacza, że mamy do czynienia z permutacją.

Answer 2

Ciekawe zadanie. Wygląda na trudne. Ale spróbuję pomóc.

Ja najpierw posadziłbym 4 osoby przy stołach, bo przy każdym musi ktoś siedzieć. Na ile sposobów można posadzić tak 4 osoby z 8? Gdyby te stoły były rozróżnialne, to było by 8!/4!. Tutaj stołów nie rozróżniamy, więc mogę podzielić ten wynik przez 4!(bo kolejność w jakiej będę sadzać ludzi nie ma tutaj znaczenia).

Co dalej? Ano teraz każdą z 4 osób mogę posadzić przy dowolnym stole - przy każdym już ktoś siedzi, więc mam wolną rękę. Pierwszą posadzę na 4 sposoby, drugą też. Razem będzie 4^4. Byłoby dobrze, gdyby kolejność nie miała znaczenia. A ma.

Natomiast co to oznacza, że liczy się kto obok kogo siedzi? Czy przy każdym stoliku jest pewna ilość krzeseł na których można posadzić? Czy jeśli posadzę dwie osoby obok siebie to znaczy, że nie mogę już nikogo posadzić między nich?

Ja to widzę tak: mamy 4 stoliki, przy nich siedzą 4 osoby, teraz chcemy umieścić gdzieś jedną z pozostałej czwórki. Do dowolnego stolika, ale jak rozumiem ma znaczenie, czy usiądzie po prawej stronie czy lewej. Ale najpierw posadźmy, w tej chwili nie ma znaczenia, czy siedzi po prawej czy lewej, bo jak posadzę drugą osobę przy stoliku, to nie wpływa to na kolejność(bo niby jak? jest po prawej, czy lewej? to w tej chwili nie gra roli). Dla pierwszej osoby daje to 4 możliwości. Teraz kolejna. W 3 stolikach można posadzić na 1 sposób, ale w jednym na 2(po prawej albo lewej stronie jednego z siedzących przy 2 osobowym stoliku). To 5 sposobów. Kolejną posadzimy na 6 wg. tego rozumowania. Ostatnią na 7.

No ale mogę się mylić albo coś źle zrozumieć. Jaka była dokładna treść zadania?

Comments

Gdyby te stoły były rozróżnialne, to było by 8!/4!

Nie do końca. To wyrażenie oznacza liczbę 4-elementowych permutacji, które możesz utworzyć z 8 elementów. A przecież przy każdym stole mogą siedzieć po 2 osoby albo przy dwóch stołach po 3 osoby i przy pozostałych dwóch po 1. Tak więc w tym wzorze ciężko mieszać stoły z liczbą osób.

Natomiast co to oznacza, że liczy się kto obok kogo siedzi?

To oznacza, że ważna jest kolejność w podzbiorach, które są zdefiniowane przez liczbę osób siedzących przy danym stoliku. Tak więc badamy permutacje, a nie kombinacje. Ustalenie tego faktu jest kluczowe przy rozwiązywaniu tego typu zadań.

---

 kurczę, teraz widzę, że zabieram się do pomocy a tu takie braki w wiedzy, trochę wstyd... oczywiście masz rację, mój błąd.

---

Liczą się chęci zrozumienia zagadnienia i podjęcie działania. To jest podstawa i to się bardzo ceni. Nieraz już rozgryzałem zagadnienie od złej strony, orientowałem się gdy trafiałem na rozbieżności w rozumowaniu. Wtedy trzeba dalej przeszukiwać materiały. Ale nie jest źle. Mamy dostęp do Internetu, wyobraź sobie jakby było ciężko biegać do biblioteki za każdym razem i wertować setki książek ;)