Udowodnij poniższą równość dla liczb Stirlinga 2 rodzaju:
\(\displaystyle{ \left\{ \begin{matrix} n\\ n-2\\ \end{matrix} \right\}={n+1 \choose 4}+2{n \choose 4}}\)
Udowodnij równość z liczbami Stirlinga
-
uczen23
- Użytkownik
- Posty: 52
- Rejestracja: 8 paź 2016, o 12:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 9 razy
Udowodnij równość z liczbami Stirlinga
Ostatnio zmieniony 17 cze 2018, o 20:09 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Więcej szacunku dla Stirlinga.
Powód: Więcej szacunku dla Stirlinga.
-
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
Re: Udowodnij równość z liczbami sterlinga
*Stirlinga.
Dzielimy zbiór n-elementowy na \(\displaystyle{ n-2}\) niepustych (rozłącznych parami oczywiście) podzbiorów.
Takich podziałów jest właśnie \(\displaystyle{ \left\{ \begin{matrix} n\\ n-2\\ \end{matrix} \right\}}\)
Z drugiej strony możemy też na to spojrzeć tak: podzbiorów rozłącznych niepustych ma być \(\displaystyle{ n-2}\), wszystkich elementów jest \(\displaystyle{ n}\). No to wniosek z tego płynie taki, że albo będzie jeden podzbiór o \(\displaystyle{ 3}\) elementach i \(\displaystyle{ n-3}\) singletonów, albo \(\displaystyle{ n-4}\) singletonów i dwa zbiory dwuelementowe.
Na \(\displaystyle{ {n \choose 3}}\) sposobów możemy wybrać elementy tego zbioru trójelementowego, no a pozostałe z automatu dajemy na singletony jak do rzeźni.
A jak tworzymy dwuelementowe: wybieramy cztery elementy, które trafią do tych dwuelementowych na \(\displaystyle{ {n \choose 4}}\) sposobów i na \(\displaystyle{ 3}\) sposoby rozbijamy na dwa dwuelementowe (zauważ bowiem, że wystarczy zliczyć, ile jest możliwości np. utworzenia dwuelementowych, w których znajdzie się pierwszy wybrany w ten sposób element spośród tych \(\displaystyle{ 4}\): znajdzie się w tym samym dubletonie z drugim, trzecim albo czwartym, nie ma więcej możliwości).
Resztę dzielimy na singletony na \(\displaystyle{ \left\{n-4 \atop n-4\right\}=1}\) sposobów.
Pozostaje sprawdzić, że \(\displaystyle{ {n \choose 3}+3{n\choose 4}={n+1 \choose 4}+2{n \choose 4}}\), co jest bardzo łatwe i zostawiam to jako ćwiczenie.
Ale możliwe, że chodziło o to, żeby jakąś interpretacją kombinatoryczną od razu dostać prawą stronę, jednak szczerze powiedziawszy mam to w nosie, ponieważ nic takiego nie pojawiło się w poleceniu.
Dzielimy zbiór n-elementowy na \(\displaystyle{ n-2}\) niepustych (rozłącznych parami oczywiście) podzbiorów.
Takich podziałów jest właśnie \(\displaystyle{ \left\{ \begin{matrix} n\\ n-2\\ \end{matrix} \right\}}\)
Z drugiej strony możemy też na to spojrzeć tak: podzbiorów rozłącznych niepustych ma być \(\displaystyle{ n-2}\), wszystkich elementów jest \(\displaystyle{ n}\). No to wniosek z tego płynie taki, że albo będzie jeden podzbiór o \(\displaystyle{ 3}\) elementach i \(\displaystyle{ n-3}\) singletonów, albo \(\displaystyle{ n-4}\) singletonów i dwa zbiory dwuelementowe.
Na \(\displaystyle{ {n \choose 3}}\) sposobów możemy wybrać elementy tego zbioru trójelementowego, no a pozostałe z automatu dajemy na singletony jak do rzeźni.
A jak tworzymy dwuelementowe: wybieramy cztery elementy, które trafią do tych dwuelementowych na \(\displaystyle{ {n \choose 4}}\) sposobów i na \(\displaystyle{ 3}\) sposoby rozbijamy na dwa dwuelementowe (zauważ bowiem, że wystarczy zliczyć, ile jest możliwości np. utworzenia dwuelementowych, w których znajdzie się pierwszy wybrany w ten sposób element spośród tych \(\displaystyle{ 4}\): znajdzie się w tym samym dubletonie z drugim, trzecim albo czwartym, nie ma więcej możliwości).
Resztę dzielimy na singletony na \(\displaystyle{ \left\{n-4 \atop n-4\right\}=1}\) sposobów.
Pozostaje sprawdzić, że \(\displaystyle{ {n \choose 3}+3{n\choose 4}={n+1 \choose 4}+2{n \choose 4}}\), co jest bardzo łatwe i zostawiam to jako ćwiczenie.
Ale możliwe, że chodziło o to, żeby jakąś interpretacją kombinatoryczną od razu dostać prawą stronę, jednak szczerze powiedziawszy mam to w nosie, ponieważ nic takiego nie pojawiło się w poleceniu.