Liczba Stirlinga, dówod.

[Richard del Ferro]

Poproszę o wskazówki do zadania.
Chciałbym rozwiązać to zadanie kombinatorycznie, lecz nie bardzo mi to wychodzi.

\(\displaystyle{ \left[ \frac{n+1}{n-1}\right] =2 {n+1 \choose 3} +3 {n+1 \choose 4}}\) dla \(\displaystyle{ n>2}\)

gdzie \(\displaystyle{ [x]}\) – liczba Stirlinga pierwszego rodzaju (dla cykli).

Na zajęciach było rozwiązanie jakoś, że dzielimy na dwa dwuelementowe cykle LUB na dwa cykle jeden jednoelementowy, a jeden trójelementowy.

I ja tego właśnie nie rozumiem? Czemu akurat tak, skoro mamy podzielić na \(\displaystyle{ n-1}\) cykli?

[arek1357]

Wzór na ilość cykli w permutacji \(\displaystyle{ n+1}\) elementowej to:

(*) \(\displaystyle{ \frac{(n+1)!}{1^{a_{1}} \cdot2^{a_{2}} \cdot ... \cdot (n+1)^{a_{n+1}}\cdot a_{1}! \cdot ... \cdot a_{n+1}! }}\)

tego nie muszę tłumaczyć szczególnie, najmądrzejszym...

Druga sprawa, to w partycji liczby\(\displaystyle{ n+1}\) na \(\displaystyle{ n-1}\) składników występuje:

1. Albo na początku trójka, a potem same jedynki.

Tu będą cykle postaci:

\(\displaystyle{ (...)(.)(.)...(.)}\) – jest ich \(\displaystyle{ n-1}\) .

2. Albo na początku dwie dwójki, a potem same jedynki.

Tu będą cykle postaci:

\(\displaystyle{ (..)(..)(.)...(.)}\) – jest ich \(\displaystyle{ n-1}\) .

Co ze wzoru (*) da ci możliwości:

W pierwszym przypadku:

\(\displaystyle{ \frac{(n+1)!}{3 \cdot (n-2)!}= \frac{(n-1)n(n+1)}{3}}\)

W drugim i ostatnim przypadku da ci:

\(\displaystyle{ \frac{(n+1)!}{2^2 \cdot 2! \cdot (n-3)!}= \frac{(n-2)(n-1)n(n+1)}{8}}\)

To było dla: \(\displaystyle{ n+1>3}\)

dla:
\(\displaystyle{ n+1=3}\) można na piechotę sprawdzić i też zachodzi...

Jak porównasz ze swoim wzorem, otrzymasz to samo.

Fajnie tak zrobić coś z głupia mądrzejszym od siebie...

Poza tym zapisuj podziały permutacji na cykle tak:

\(\displaystyle{ c(n,k)}\)

lub:

\(\displaystyle{ \left[\begin{array}{c}n\\k \end{array}\right]}\)

To taka dobra rada "Wujka Dobra Rada"...

A poza tym jest pewna drobna różnica między liczbą podziałów permutacji na cykle, a liczbami Stirlinga pierwszego rodzaju, ale to sobie doczytaj...

A tak na marginesie:

Na zajęciach było rozwiązanie jakoś, że dzielimy na dwa dwuelementowe cykle LUB na dwa cykle jeden jednoelementowy a jeden trójelementowy.

Współczuję wam bo macie ciulowo na tych zajęciach. Moja Pani ot Fszystkiego szybko by wprowadziła tam porządek i to liniowy...

[Mruczek]

To zadanie już kiedyś było: https://www.matematyka.pl/417880.htm?hilit=%20stirlinga

[arek1357]

No bo w sumie nawet nie trzeba odwoływać się do pierwszego wzoru , który na początku napisałem wystarczą kombinacje...
Ale niech se chłopaczek popodziwia wzorek... który mu na wykładzie nie pokazali...

[Richard del Ferro]

Dzieki Mruczek za odpowiedź