Dowód na liczbach Stirlinga

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
K4M1L
Użytkownik
Użytkownik
Posty: 16
Rejestracja: 10 cze 2019, o 17:31
Płeć: Mężczyzna
Podziękował: 5 razy

Dowód na liczbach Stirlinga

Post autor: K4M1L »

Udowodnić następujące równości dla liczb Stirlinga
\(\displaystyle{ a) S\left( n,2\right) = 2^{n-1} - 1 \\b) S\left( n,n-1\right) = c\left( n,n-1\right) = {n \choose 2} }\)
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Dowód na liczbach Stirlinga

Post autor: Premislav »

a) Dzielimy zbiór \(\displaystyle{ n}\)-elementowy na \(\displaystyle{ 2}\) niepuste, rozłączne podzbiory. W tym celu wyróżnijmy jakiś element w tym zbiorze i wybierzmy niepusty podzbiór naszego zbioru \(\displaystyle{ n}\)-elementowego, do którego element ten nie będzie należał. Pozostałych elementów jest \(\displaystyle{ n-1}\), zatem do wyboru mamy \(\displaystyle{ 2^{n-1}-1}\) podzbiorów (oprócz pustego).
b) Dzielimy zbiór \(\displaystyle{ n}\)-elementowy na \(\displaystyle{ n-1}\) niepustych, parami rozłącznych podzbiorów. Będziemy mieć więc \(\displaystyle{ n-2}\) podzbiorów jednoelementowych i \(\displaystyle{ 1}\) podzbiór dwuelementowy. Na \(\displaystyle{ {n\choose 2}}\) sposobów wybieramy elementy tego jednego zbioru dwuelementowego, pozostałe umieszczamy w singletonach.
janusz47
Użytkownik
Użytkownik
Posty: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Re: Dowód na liczbach Stirlinga

Post autor: janusz47 »

a)

\(\displaystyle{ n\geq 2 , \ \ S(n,2) = 2^{n-1} -1 }\)

Indukcja względem \(\displaystyle{ n }\)

\(\displaystyle{ n = 2, \ \ S(2,2) = 1 }\) - prawda

\(\displaystyle{ (2 \leq n = k ) \rightarrow ( n = k+1) }\)

\(\displaystyle{ S(k+1,2) = S(k,1) +2S(k,2)= 1 +2(2^{k-1} -1)= 1 +2^{k}-2 = 2^{(k+1)-1}- 1.}\)

Skorzystaliśmy z równania rekurencyjnej dla liczb Stirlinga:

\(\displaystyle{ S(n,k) = S(n-1, k-1) + k\cdot S((n -1), k) \ \ (1)}\)

c.b.d.o.

b)

Z równania (1) dla \(\displaystyle{ k = 1,2,...,(n-1)}\)

\(\displaystyle{ (n-1) + (n-2) + (n-3) + ...+ 1 = n^2 -( 1+ 2+ ...+ n ) = n^2 - \frac{1+n}{2}n = \frac{2n^2 - n+n^2}{2} = \frac{n^2 -n}{2} = \frac{n(n-1)}{2} = {n\choose 2} }\)

Dowód równania \(\displaystyle{ (1) }\) można znaleźć na przykład w książce Witolda Lipskiego i Wiktora Marka Analiza kombinatoryczna. PWN Warszawa 1986.
ODPOWIEDZ