1. Pokaż, że liczby Bella spełniają następujący warunek \(\displaystyle{ B _{n} < n!}\)
dla \(\displaystyle{ n > 2}\)
2. Udowodnij, że dla liczb Stirlinga II rodzaju zachodzi równość:
\(\displaystyle{ S\left( n,k\right) = \sum_{i=k-1}^{n-1} {n-1 \choose i} S\left( i,k-1\right)}\)
z góry dziękuję za pomoc
Liczby Bella, Stirlinga
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Liczby Bella, Stirlinga
W obu przykładach można indukcyjnie, ale ładniej interpretacją geometryczną.
Ad 1) Liczby Bella zliczają nam ilość podziałów zbioru. Przypiszmy danej permutacji zbioru \(\displaystyle{ \{1,2,\ldots ,n\}}\) podział w taki sposób, że dzielimy permutację na podciągi rosnące i wtedy w jednym podzbiorze podziału znajdą się elementy jednego ciągu rosnącego. Przykładowo dla \(\displaystyle{ n=8}\) permutacja:
\(\displaystyle{ \left( \begin{matrix} 1 &2 & 3&4&5&6&7&8\\ 2&4&7&6&5&8&1&3\end{matrix}\right)}\)
koduje nam podział \(\displaystyle{ \{2,4,7\} \cup \{6\} \cup \{5,8\} \cup \{1,3\}}\).
Takie przypisanie w oczywisty sposób jest "na" (bo każdy podział da się tak zakodować...), ale nie jest różnowartościowe (...bo dla \(\displaystyle{ n>2}\) identyczne podziały mogą być wyznaczone przez różne permutacje), zatem istotnie \(\displaystyle{ B_n<n!}\).
Ad 2) Po lewej stronie mamy liczbę podziałów zbioru \(\displaystyle{ \{1,2, \ldots n\}}\) na \(\displaystyle{ k}\) podzbiorów. Możemy je zliczać także inaczej - ustalamy dowolny element, np. \(\displaystyle{ 1}\) i wybieramy na \(\displaystyle{ i}\) sposobów elementy które nie będą w podzbiorze z \(\displaystyle{ 1}\); następnie te które nie będą dzielimy na \(\displaystyle{ k-1}\) podzbiorów. Oczywiście \(\displaystyle{ i}\) może być najmniej równe \(\displaystyle{ k-1}\) (bo musimy stworzyć jeszcze \(\displaystyle{ k-1}\) przynajmniej jednoelementowych podzbiorów) i co najwyżej \(\displaystyle{ n-1}\) (jeśli jedynka jest w zbiorze jednoelementowym), stąd zakres sumowania.
Q.
Ad 1) Liczby Bella zliczają nam ilość podziałów zbioru. Przypiszmy danej permutacji zbioru \(\displaystyle{ \{1,2,\ldots ,n\}}\) podział w taki sposób, że dzielimy permutację na podciągi rosnące i wtedy w jednym podzbiorze podziału znajdą się elementy jednego ciągu rosnącego. Przykładowo dla \(\displaystyle{ n=8}\) permutacja:
\(\displaystyle{ \left( \begin{matrix} 1 &2 & 3&4&5&6&7&8\\ 2&4&7&6&5&8&1&3\end{matrix}\right)}\)
koduje nam podział \(\displaystyle{ \{2,4,7\} \cup \{6\} \cup \{5,8\} \cup \{1,3\}}\).
Takie przypisanie w oczywisty sposób jest "na" (bo każdy podział da się tak zakodować...), ale nie jest różnowartościowe (...bo dla \(\displaystyle{ n>2}\) identyczne podziały mogą być wyznaczone przez różne permutacje), zatem istotnie \(\displaystyle{ B_n<n!}\).
Ad 2) Po lewej stronie mamy liczbę podziałów zbioru \(\displaystyle{ \{1,2, \ldots n\}}\) na \(\displaystyle{ k}\) podzbiorów. Możemy je zliczać także inaczej - ustalamy dowolny element, np. \(\displaystyle{ 1}\) i wybieramy na \(\displaystyle{ i}\) sposobów elementy które nie będą w podzbiorze z \(\displaystyle{ 1}\); następnie te które nie będą dzielimy na \(\displaystyle{ k-1}\) podzbiorów. Oczywiście \(\displaystyle{ i}\) może być najmniej równe \(\displaystyle{ k-1}\) (bo musimy stworzyć jeszcze \(\displaystyle{ k-1}\) przynajmniej jednoelementowych podzbiorów) i co najwyżej \(\displaystyle{ n-1}\) (jeśli jedynka jest w zbiorze jednoelementowym), stąd zakres sumowania.
Q.