Uzasadnij wzór:
\(\displaystyle{ m!=\sum_{i=1}^{m}i{\cdot}c_{m}(i)}\)
gdzie \(\displaystyle{ c_{m}(i)}\) oznacza liczbę permutacji zbioru m elementowego z i punktami stałymi.
permutacje i silnia
- epicka_nemesis
- Użytkownik
- Posty: 419
- Rejestracja: 27 gru 2010, o 00:05
- Płeć: Kobieta
- Lokalizacja: Poznan
- Podziękował: 60 razy
- Pomógł: 28 razy
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
permutacje i silnia
Pewnie istnieje jakieś natychmiastowe rozwiązanie z użyciem pięknej interpretacji kombinatorycznej, ale pomyślałem, że można po prostu bezczelnie policzyć \(\displaystyle{ c_{m}(i)}\):
\(\displaystyle{ c_{m}(i)={m \choose i}N(m-i)}\), gdzie N(m-i) to liczba nieporządków w zbiorze o \(\displaystyle{ m-i}\) elementach, bo na \(\displaystyle{ {m \choose i}}\) sposobów wybieramy \(\displaystyle{ i}\) punktów stałych ze zb. \(\displaystyle{ m}\)-elementowego, a pozostałe \(\displaystyle{ m-i}\) permutujemy tak, aby żaden z nich nie "pozostał na starym miejscu". Zatem mamy
\(\displaystyle{ \sum_{i=1}^{m}ic_{m}(i)= \sum_{i=1}^{m}i{m \choose i} N(m-i)}\)
Teraz skorzystajmy z tożsamości \(\displaystyle{ k{n \choose k}=n{n-1 \choose k-1}}\):
\(\displaystyle{ \sum_{i=1}^{m}i{m \choose i} N(m-i)= \sum_{i=1}^{m}m{m-1 \choose i-1}N(m-i)}\)
Następnie przesuńmy indeksy:
\(\displaystyle{ \sum_{i=1}^{m}m{m-1 \choose i-1}N(m-i)= \\=\sum_{i=0}^{m-1}m{m-1 \choose i}N(m-1-i)=m \sum_{i=0}^{m-1}{m-1 \choose i}N(m-1-i)=m\cdot (m-1)!}\)
I gotowe.
Krótkie zdanie czy dwa wyjaśnienia: \(\displaystyle{ \sum_{i=0}^{m-1}{m-1 \choose i}N(m-1-i)= \sum_{i=0}^{m-1}c_{m-1}(i)}\) (wypr. jak wyżej). A zatem sumujemy od \(\displaystyle{ i=0}\) do \(\displaystyle{ i=m-1}\)
permutacje zbioru o \(\displaystyle{ m-1}\) elementach, mające dokładnie i punktów stałych - no czyli łącznie otrzymujemy wszystkie permutacje zbioru \(\displaystyle{ m-1}\)-elementowego.
Wybacz brzydotę, jak wspominałem pewnie odpowiednia interpretacja rozwala to w jednej linijce, ale że nie umiem myśleć, to muszę się chwytać przekształceń algebraicznych jak tonący brzytwy.
\(\displaystyle{ c_{m}(i)={m \choose i}N(m-i)}\), gdzie N(m-i) to liczba nieporządków w zbiorze o \(\displaystyle{ m-i}\) elementach, bo na \(\displaystyle{ {m \choose i}}\) sposobów wybieramy \(\displaystyle{ i}\) punktów stałych ze zb. \(\displaystyle{ m}\)-elementowego, a pozostałe \(\displaystyle{ m-i}\) permutujemy tak, aby żaden z nich nie "pozostał na starym miejscu". Zatem mamy
\(\displaystyle{ \sum_{i=1}^{m}ic_{m}(i)= \sum_{i=1}^{m}i{m \choose i} N(m-i)}\)
Teraz skorzystajmy z tożsamości \(\displaystyle{ k{n \choose k}=n{n-1 \choose k-1}}\):
\(\displaystyle{ \sum_{i=1}^{m}i{m \choose i} N(m-i)= \sum_{i=1}^{m}m{m-1 \choose i-1}N(m-i)}\)
Następnie przesuńmy indeksy:
\(\displaystyle{ \sum_{i=1}^{m}m{m-1 \choose i-1}N(m-i)= \\=\sum_{i=0}^{m-1}m{m-1 \choose i}N(m-1-i)=m \sum_{i=0}^{m-1}{m-1 \choose i}N(m-1-i)=m\cdot (m-1)!}\)
I gotowe.
Krótkie zdanie czy dwa wyjaśnienia: \(\displaystyle{ \sum_{i=0}^{m-1}{m-1 \choose i}N(m-1-i)= \sum_{i=0}^{m-1}c_{m-1}(i)}\) (wypr. jak wyżej). A zatem sumujemy od \(\displaystyle{ i=0}\) do \(\displaystyle{ i=m-1}\)
permutacje zbioru o \(\displaystyle{ m-1}\) elementach, mające dokładnie i punktów stałych - no czyli łącznie otrzymujemy wszystkie permutacje zbioru \(\displaystyle{ m-1}\)-elementowego.
Wybacz brzydotę, jak wspominałem pewnie odpowiednia interpretacja rozwala to w jednej linijce, ale że nie umiem myśleć, to muszę się chwytać przekształceń algebraicznych jak tonący brzytwy.
- epicka_nemesis
- Użytkownik
- Posty: 419
- Rejestracja: 27 gru 2010, o 00:05
- Płeć: Kobieta
- Lokalizacja: Poznan
- Podziękował: 60 razy
- Pomógł: 28 razy