Usadzanie osób przy stolikach.

[K4milC]

Mam problem z zadaniem.

Na ile sposobów możemy rozsadzić n osób przy dokładnie k okrągłych stolikach, jeżeli przy stolikach może siedzieć nieograniczona liczba osób, natomiast liczy się kto koło kogo siedzi (i po której stronie)?

Kompletnie nie wiem jak się za to zabrać.

[arek1357]

Przy stoliku okrągłym \(\displaystyle{ n}\) osób może siedzieć na \(\displaystyle{ (n-1)!}\) sposobów, zadanie jest równoważne temu ile jest różnych cykli o długości \(\displaystyle{ n}\)...

Natomiast druga część zadania jest nie do końca precyzyjna bo nie wiadomo czy stoliki są rozróżnialne między sobą czy nie...

Bo jeżeli są rozróżnialne trzeba najpierw każdemu zaaplikować ludzi którzy będą na nich siedzieć, dopuszczam takie rozkłady gdzie ilość ludzi przy stoliku będzie równa zero...

a więc wzór: \(\displaystyle{ k^n}\) , \(\displaystyle{ k}\) - stoliki rozróżnialne... wariacje z powtórzeniami (ludzie rozróżnialni też)...

I teraz załóżmy, że przy każdym takim "rozkładzie przy i - tym stoliku siedzi \(\displaystyle{ r_{i}}\) osób , mamy wtedy bardzo mało "zwarty" wzór:

\(\displaystyle{ \sum_{k^n , r_{1}+r_{2}+...+r_{k}=n}^{} \prod_{i=1}^{k}(r_{i}-1)! }\) przyjmując \(\displaystyle{ (-1)!=1}\)

Gdy stoliki nierozróżnialne to najpierw też przyporządkowujesz stolikom ludzi (ludzie są rozróżnialni) więc dzieje się coś na kształt podziału zbioru na niepuste rozłączne podzbiory, a potem cyklicznie permutujesz każdy stolik...

Ale najpierw trzeba wybrać te stoliki przy których siedzi przynajmniej jedna osoba, ale że stoliki są nierozróżnialne to wystarczy nam tylko ich ilość , czyli:

\(\displaystyle{ k=1,2,3,...,k}\)

I robisz podziały \(\displaystyle{ n}\) elementów rozróżnialnych (ludzi) w zbiory nierozróżnialne (stoliki)..., zadane wzorem:

\(\displaystyle{ S(n,k)= \frac{1}{k!} \sum_{i=1}^{k} (-1)^{k-i} {k \choose i}i^n }\)

Każdy taki układ odpowiada:

\(\displaystyle{ S(n,k)}\) - cyklom no i sumujesz po \(\displaystyle{ S(n,k)}\)

\(\displaystyle{ \sum_{k=1}^{k}\sum_{S(n,k)}^{} \prod_{i=1}^{k}(r_{i}-1)! }\)

gdzieś mniej więcej na tę nutę...

Do drugiego punktu dam przykład, żeby było jaśniej:

niech.: \(\displaystyle{ n=4,k=2}\)

czterech ludzi i dwa stoliki nierozróżnialne...

najpierw liczmy: \(\displaystyle{ S(4,1)=1}\)

Potem \(\displaystyle{ S(4,2)=7}\)

Razem:

\(\displaystyle{ \sum_{k=1}^{2} \sum_{S(4,k)}^{} \prod_{i=1}^{k}(r_{i}-1)! =\sum_{S(4,1)}^{} \prod_{i=1}^{1}(r_{i}-1)! + \sum_{S(4,2)}^{}\prod_{i=1}^{2}(r_{i}-1)!= }\)

\(\displaystyle{ = (4-1)!+4 \cdot (3-1)! \cdot (1-1)!+3 \cdot (2-1)! \cdot (2-1)!=6+4 \cdot 2+3 \cdot 1 \cdot 1=17}\)

W przypadku gdy dopuścimy stoliki rozróżnialne to ten sam przypadek dla: \(\displaystyle{ n=4, k=2}\)

Wyniesie: \(\displaystyle{ 34}\) (Co nie znaczy, że zawsze wystarczy pomnożyć lub podzielić przez dwa)...


A co do uzwarcania tych wzorów tu są specjaliści:

Czy istnieje wzór jawny na liczby Stirlinga drugiego rodzaju?

[a4karo]

niech.: \(\displaystyle{ n=4,k=2}\)

czterech ludzi i dwa stoliki nierozróżnialne...

najpierw liczmy: \(\displaystyle{ S(4,1)=1}\)

Potem \(\displaystyle{ S(4,2)=7}\)

Razem:

\(\displaystyle{ \sum_{k=1}^{2} \sum_{S(4,k)}^{} \prod_{i=1}^{k}(r_{i}-1)! =\sum_{S(4,1)}^{} \prod_{i=1}^{1}(r_{i}-1)! + \sum_{S(4,2)}^{}\prod_{i=1}^{2}(r_{i}-1)!= }\)




Czy istnieje wzór jawny na liczby Stirlinga drugiego rodzaju?

Skoro `S(4,2)=7` to co oznacza zapis \(\sum_{S(4,2)}^{}\prod_{i=1}^{2}(r_{i}-1)!\)

[arek1357]

To znaczy może pokażę o co mi biega:

\(\displaystyle{ \left\{ 1,2,3,4\right\} =\left\{ 1\right\} \cup \left\{2,3,4 \right\} \vee \left\{ 2\right\} \cup \left\{1,3,4 \right\} \vee \left\{ 3\right\} \cup \left\{1,2,4 \right\} \vee \left\{ 4\right\} \cup \left\{1,2,3 \right\} \vee \left\{ 1,2\right\} \cup \left\{3,4 \right\} \vee \left\{ 1,3\right\} \cup \left\{2,4 \right\} \vee \left\{ 1,4\right\} \cup \left\{2,3 \right\}}\)

Daje to dokładnie 7 rozkładów na dwa cykle (stoliki), i tak:

Jest \(\displaystyle{ 4 }\) przypadki typu:

\(\displaystyle{ (.)(...)}\)

Oraz \(\displaystyle{ 3}\) przypadki typu:

\(\displaystyle{ (..)(..)}\)

Co daje 7 podziałów w każdym podziale mnożymy ilość cykli , czyli w naszym przypadku:

\(\displaystyle{ (r_{1}-1)! \cdot (r_{2}-1)!}\)

Co daje:

\(\displaystyle{ 4 \cdot (1-1)! \cdot (3-1)!+3 \cdot (2-1)! \cdot (2-1)! }\)

razem jest siedem składników , zapisanych krócej po prostu...

Bo jest tylko dwa cykle (dwa zapełnione stoliki w różny sposób)

W pierwszym przypadku zapełniamy tylko jeden stolik na sposobów:

\(\displaystyle{ S(4,1)=1}\)

co daje cykl o długości cztery, czyli \(\displaystyle{ 6}\) niezależnych cykli....



Mogę ten drugi przypadek gdzie stoliki nierozróżnialne zapisać w jeszcze innej równoważnej formie może i krótszej:

\(\displaystyle{ \sum_{\substack{s_{1}r_{1}+...+s_{k}r_{k}=n \\\\ r_{1}>...>r_{k} \ge 0}}^{} \frac{n!}{r_{1}^{s_{1}} \cdot r_{2}^{s_{2}} \cdot ... \cdot r_{k}^{s_{k}} \cdot s_{1}! \cdot s_{2}! \cdot ... \cdot s_{k}!}\left[ (r_{1}-1)! \right]^{s_{1}} \cdot \left[ (r_{2}-1)! \right]^{s_{2}} \cdot ... \cdot \left[ (r_{k}-1)! \right]^{s_{k}} }\)

Dla.:\(\displaystyle{ n=4 , k=2}\) mamy:

\(\displaystyle{ \frac{4!}{(4!)^1 \cdot 1!} (4-1)!+ \frac{4!}{(2!)^2 \cdot 2!} \left[ (2-1)!\right]^2 +\frac{4!}{1! \cdot 3! \cdot 1! \cdot 1!} (1-1)! \cdot (3-1)!= }\)

\(\displaystyle{ =3!+ \frac{24}{8} \cdot 1^2+4 \cdot 1 \cdot 2=6+3+8=17 }\)

Czyli to samo lecz może i lepiej bo składników w tych sumach jest mniej , a co za tym idzie sumy są krótsze...

[Gosda]

\(\displaystyle{ T(n, k) = k! \cdot s(n, k)}\), gdzie \(\displaystyle{ s(n, k)}\) jest liczbą Stirlinga pierwszego rodzaju bez znaku.

Na przykład dla \(\displaystyle{ (n, k) = (8, 6)}\) mamy \(\displaystyle{ T(8, 6) = 231840}\).