szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 8 kwi 2018, o 18:30 
Użytkownik

Posty: 306
Lokalizacja: Polska
Uzasadnij że
Liczby Stirlinga II rodzaju spełniają następującą tożsamość
\left\{ \begin{matrix} n+1\\ m+1\\ \end{matrix} \right\} =  \sum_{k=m}^{n} {n \choose k}\left\{ \begin{matrix} k\\ m\\ \end{matrix} \right\}
Góra
Mężczyzna Offline
 Tytuł: Uzasadnij że
PostNapisane: 8 kwi 2018, o 21:22 
Użytkownik

Posty: 3626
Dla dowodu rozważmy zbiór wszystkich S(n+1, m+1) podziałów zbioru X=\{ 1,...,n+1\}.

Zbiór ten rozpada się na rozłączne klasy odpowiadające różnym podzbiorom zbioru X będącym blokiem zawierającym element n+1.

Zauważmy, że dla każdego b- elementowego podzbioru B \subseteq X istnieje dokładnie S(n+1-b, m ) podziałów zbioru X na m+1 bloków zawierających zbiór B w charakterze bloku.

Istotnie każdy taki podział odpowiada jednoznacznie podziałowi zbioru X\setminus B na m bloków.

Zbiór b - elementowy B \subseteq  X zawierający element n+1 możemy wybrać na {n \choose b-1} sposobów.

Stąd:

S(n+1, m+1) = \sum_{b=1}^{n+1- m}{n\choose b-1}S(n+1-b , m) = \\ =\sum_{b=1}^{n+1-m}{n\choose  n+1-b}S (n+1-b, m) = \sum_{k=m}^{n}{n\choose k}S(k, m).

c.b.d.o.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 pewna tożsamosc  blost  8
 Podzielność liczb naturalnych - zadanie 2  Ann_91  2
 Ile liczb 2-cyfrowych  kugelsicher  1
 Ile jest liczb naturalnych...  anakonda1234561  1
 Tożsamość z silnią  Majeskas  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl