Witam,
muszę przyznać, że nie wiem zbytnio nawet co to są te metody kombinatoryczne.. Rozumiem, że nie mogę tego zrobić poprzez indukcję?
\(\displaystyle{ s\left( n+1,n-1\right) = 2 {n+1 \choose 3} + 3 {n+1 \choose 4}}\)
Co tutaj trzeba zrobić?
Wykorzystując metody kombinatoryczne uzasadnij równość
-
Mruczek
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Wykorzystując metody kombinatoryczne uzasadnij równość
Ta liczba Stirlinga oznacza liczbę permutacji \(\displaystyle{ n + 1}\) elementowych o \(\displaystyle{ n - 1}\) cyklach. Jakie cykle mogą mieć te permutacje? No mamy o dwa więcej elementów niż cykli - te dodatkowe elementy znajdą się na jednym cyklu (tworząc cykl trzyelementowy, a pozostałe cykle jednoelementowe) lub na dwóch cyklach (tworząc dwa cykle dwuelementowe, a pozostałe jednoelementowe). Na ile sposobów może tak się stać?
W przypadku z cyklem trzyelementowym trzeba wybrać które elementy mają się na nim znaleźć na \(\displaystyle{ {n+1 \choose 3}}\) i ustawić je w pewnej kolejności na tym cyklu - można to zrobić na \(\displaystyle{ 2}\) sposoby, dlatego w tym przypadku mamy \(\displaystyle{ 2 {n+1 \choose 3}}\) permutacji.
W przypadku z dwoma cyklami dwuelementowymi najpierw wybieramy \(\displaystyle{ 4}\) elementy, które mają się znaleźć na tych cyklach na \(\displaystyle{ {n+1 \choose 4}}\) sposoby, a potem decydujemy które elementy mają być z którymi na tych dwóch cyklach - cztery elementy możemy podzielić na dwa zbiory dwuelementowe na \(\displaystyle{ 3}\) sposoby, dlatego tutaj mamy \(\displaystyle{ 3 {n+1 \choose 4}}\) permutacji.
Łącznie wszystkich permutacji \(\displaystyle{ n + 1}\) elementowych o \(\displaystyle{ n - 1}\) cyklach jest \(\displaystyle{ 2 {n+1 \choose 3} + 3 {n+1 \choose 4}}\), dlatego \(\displaystyle{ s\left( n+1,n-1\right) = 2 {n+1 \choose 3} + 3 {n+1 \choose 4}}\).
W przypadku z cyklem trzyelementowym trzeba wybrać które elementy mają się na nim znaleźć na \(\displaystyle{ {n+1 \choose 3}}\) i ustawić je w pewnej kolejności na tym cyklu - można to zrobić na \(\displaystyle{ 2}\) sposoby, dlatego w tym przypadku mamy \(\displaystyle{ 2 {n+1 \choose 3}}\) permutacji.
W przypadku z dwoma cyklami dwuelementowymi najpierw wybieramy \(\displaystyle{ 4}\) elementy, które mają się znaleźć na tych cyklach na \(\displaystyle{ {n+1 \choose 4}}\) sposoby, a potem decydujemy które elementy mają być z którymi na tych dwóch cyklach - cztery elementy możemy podzielić na dwa zbiory dwuelementowe na \(\displaystyle{ 3}\) sposoby, dlatego tutaj mamy \(\displaystyle{ 3 {n+1 \choose 4}}\) permutacji.
Łącznie wszystkich permutacji \(\displaystyle{ n + 1}\) elementowych o \(\displaystyle{ n - 1}\) cyklach jest \(\displaystyle{ 2 {n+1 \choose 3} + 3 {n+1 \choose 4}}\), dlatego \(\displaystyle{ s\left( n+1,n-1\right) = 2 {n+1 \choose 3} + 3 {n+1 \choose 4}}\).