wyznaczenie wzoru jawnego dla liczb Stirlinga I rodzaju

[SanczoPanczo]

Witam. Mam zadanie z poleceniem:

Wyznacz wzór jawny dla: \(\displaystyle{ \left[ \begin{matrix} n\\ n-2\\ \end{matrix} \right]}\)

Moje obliczenia:

\(\displaystyle{ \left[ \begin{matrix} n\\ n-2\\ \end{matrix} \right] = \left( n-1\right) \left[ \begin{matrix} n-1\\ n-2\\ \end{matrix} \right] + \left[ \begin{matrix} n-1\\ n-3\\ \end{matrix} \right]}\)

Z własności liczb Stirlinga tj.

\(\displaystyle{ \left[ \begin{matrix} n\\ n-1\\ \end{matrix} \right] = \left( \begin{matrix} n\\ 2\\ \end{matrix} \right)}\) , czyli: \(\displaystyle{ \left[ \begin{matrix} n-1\\ n-2\\ \end{matrix} \right] = \left( \begin{matrix} n-1\\ 2\\ \end{matrix}\right) = \frac{\left( n-1\right)! }{2!\left( n-1-2\right)! } = \frac{\left( n-1\right)! }{2\left( n-3\right)! } = \frac{n^3-3n+2}{2}}\)

I to jedyne jakieś "normalne" obliczenia, ponieważ po prawej stronie mam \(\displaystyle{ \left[ \begin{matrix} n-1\\ n-3\\ \end{matrix} \right]}\), gdzie różnica pomiędzy dolną częścią, a górną wynosi 2 i tak wchodzę w pętle, bo to się nie kończy...


W jaki sposób utworzyć ten wzór jawny ?

[Qń]

Najprościej użyć interpretacji kombinatorycznej. Jeśli chcemy, żeby w permutacji zbioru \(\displaystyle{ n}\)-elementowego było \(\displaystyle{ n-2}\) cykli, to albo jest jeden cykl długości trzy, a reszta długości jeden, albo też są dwa cykle długości dwa, a reszta długości jeden. Odpowiedzią będzie więc:
\(\displaystyle{ 2 \cdot {n \choose 3} +3\cdot {n \choose 4}}\) (dlaczego?)

Q.

[SanczoPanczo]

Najprościej użyć interpretacji kombinatorycznej. Jeśli chcemy, żeby w permutacji zbioru \(\displaystyle{ n}\)-elementowego było \(\displaystyle{ n-2}\) cykli, to albo jest jeden cykl długości trzy, a reszta długości jeden, albo też są dwa cykle długości dwa, a reszta długości jeden. Odpowiedzią będzie więc:
\(\displaystyle{ 2 \cdot {n \choose 3} +3\cdot {n \choose 4}}\) (dlaczego?)

Q.

Wybieram opcję "dlaczego?"

Nie chciałbym być upierdliwy, ale ni wała nie mam pojęcia skąd to wziąłeś, skuszę się i poproszę o wytłumaczenie jak dla osła...

[kasa73]

przyłączam się do prośby wytłumaczenia

[Qń]

Jeśli jest jasne, że są tylko dwie takie opcje jak napisałem, to wystarczy zliczyć ile jest każdej z nich.

Jeśli ma być jeden cykl długości trzy, to najpierw wybieramy trzy elementy które w nim będą na \(\displaystyle{ {n \choose 3}}\) sposobów, a następnie ustalamy kolejność w tym cyklu. Opcje są tylko dwie:
\(\displaystyle{ a\to b\to c \to a}\) i \(\displaystyle{ a \to c \to b \to a}\)
czyli musimy pomnożyć przez dwa. Pozostałe \(\displaystyle{ n-3}\) elementów jest w cyklach długości jeden.

Jeśli natomiast mają być dwa cykle dwuelementowe, to najpierw wybieramy do nich cztery elementy na \(\displaystyle{ {n \choose 4}}\) sposobów, a następnie bierzemy do ręki pierwszy z brzegu i na trzy sposoby wybieramy mu kolegę do cyklu. Pozostałe dwa z tych czterech będą w drugim cyklu dwuelementowym, a reszta \(\displaystyle{ n-4}\) będzie w cyklach jednoelementowych.

Q.