Zadanie brzmi tak:
Na ile sposobów możemy rozsadzić 22 osób przy dokładnie 15 okrągłych stolikach, jeżeli przy stolikach może siedzieć
nieograniczona liczba osób, natomiast liczy się to kto koło kogo siedzi?
Co zmieni się jeśli jako warunek zadania dodamy że przy każdym ze stolików powinna siedzieć przynajmniej 1 osoba.
Nie wiem od czego zacząć Proszę o pomoc.
Ilość sposobów rozsadzenia osób
-
norwimaj
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
Ilość sposobów rozsadzenia osób
Wydaje mi się to trudne do zliczenia. Jeżeli chcemy posadzić \(\displaystyle{ n}\) osób przy jednym okrągłym stoliku, to mamy możliwości
\(\displaystyle{ a_n=\begin{cases}1&\text{dla }n=0,1,2,3\\\frac{(n-1)!}2&\text{dla }n\ge3.\end{cases}}\)
Sama klamerkowa postać wzoru już zniechęca do tego, żeby dalej coś z tym robić.
Drugi pomysł, to zliczanie permutacji o odpowiednich cyklach. Tu jednak też są problemy. Jednemu usadzeniu mogą odpowiadać dwie permutacje:
\(\displaystyle{ (1,2,3,4,5,6,7,8),\quad (1,7,6,5,4,3,2),}\)
a innemu cztery:
\(\displaystyle{ (1,2,3,4)(5,6,7,8),\quad (1,2,3,4)(5,8,7,6),\\(1,4,3,2)(5,6,7,8),\quad (1,4,3,2)(5,8,7,6).}\)
Być może da się to jakoś zliczyć, rozważając permutacje o określonej liczbie cykli długości większej niż \(\displaystyle{ 2}\), ale pewnie nie jest to nic krótkiego.
\(\displaystyle{ a_n=\begin{cases}1&\text{dla }n=0,1,2,3\\\frac{(n-1)!}2&\text{dla }n\ge3.\end{cases}}\)
Sama klamerkowa postać wzoru już zniechęca do tego, żeby dalej coś z tym robić.
Drugi pomysł, to zliczanie permutacji o odpowiednich cyklach. Tu jednak też są problemy. Jednemu usadzeniu mogą odpowiadać dwie permutacje:
\(\displaystyle{ (1,2,3,4,5,6,7,8),\quad (1,7,6,5,4,3,2),}\)
a innemu cztery:
\(\displaystyle{ (1,2,3,4)(5,6,7,8),\quad (1,2,3,4)(5,8,7,6),\\(1,4,3,2)(5,6,7,8),\quad (1,4,3,2)(5,8,7,6).}\)
Być może da się to jakoś zliczyć, rozważając permutacje o określonej liczbie cykli długości większej niż \(\displaystyle{ 2}\), ale pewnie nie jest to nic krótkiego.