Matematyka.pl

Witam,
mam problem z zadaniem z matematyki dyskretnej:
Podaj zwartą postać symboli \(\displaystyle{ S(n,3)}\) i \(\displaystyle{ S(n, n-2)}\) dla \(\displaystyle{ n \ge 3 }\).
Oczywiście chodzi o liczby Stirlinga drugiego rodzaju.
Niestety nikt nie wytłumaczył mi w jaki sposób można to zrobić, a w internecie nie mogę znaleźć żadnych przykładów.

arek1357 pisze: ↑17 lis 2019, o 19:26 \(\displaystyle{ S(n,k)= \frac{1}{k!} \sum_{i=1}^{k} (-1)^{k-i} {k \choose i}i^n }\)

A jakiś dowód w taki sposób mogę to otrzymać?

To nie tak hop siup zasada włączeń i wyłączeń, indukcja itd... , są książki na ten temat ...

arek1357 pisze: ↑19 lis 2019, o 23:21 To nie tak hop siup zasada włączeń i wyłączeń, indukcja itd... , są książki na ten temat ...

To wiem, ale czy mogę po prostu za \(\displaystyle{ k }\) wstawić \(\displaystyle{ n-2 }\) i to już koniec zadania?

Nie, bo to nie będzie zwarta postać. Musisz pozbyć się znaku sumy. Nie za ładny wynik wyjdzie:

\(\displaystyle{ S(n, 3) = \frac {3^{n-1}+1} 2 - 2^{n-1}}\)

\(\displaystyle{ S(n, n-2) = \frac{1}{24} (n-2)(n-1) \cdot n \cdot (3n - 5)}\)

Pierwszy wynik jest bardzo ładny, a drugi lepiej prezentuje się w formie
\(\displaystyle{ {n\choose 3}+3{n\choose 4}}\), w której to łatwo widać schemat dowodu przez bajeczkę kombinatoryczną.

Premislav pisze: ↑20 lis 2019, o 17:20 Pierwszy wynik jest bardzo ładny, a drugi lepiej prezentuje się w formie
\(\displaystyle{ {n\choose 3}+3{n\choose 4}}\), w której to łatwo widać schemat dowodu przez bajeczkę kombinatoryczną.

Czy w przypadku \(\displaystyle{ S(n,3) }\) też mam napisać taką "bajkę" ?

A można, jak najbardziej, jeszcze jak.

Na przykład taką:
dzielimy zbiór \(\displaystyle{ n}\)-elementowy na trzy niepuste, parami rozłączne podzbiory. Popatrzmy na te zbiory jak na pudełka, do których wrzucamy poszczególne elementy.
Korzystamy z zasady włączeń i wyłączeń: dla trzech zbiorów, by to zliczyć. Wszystkich przyporządkowań elementów tym pudełkom jest \(\displaystyle{ 3^{n}}\), odejmujemy od nich te, w których do pewnych dwóch pudełek trafią wszystkie elementy (gdyż podzbiory, na które dzielimy zbiór, mają być niepuste), a takich jest \(\displaystyle{ {3\choose 2}2^{n}}\), następnie zauważmy, że odejmując te przypadki, w których co najmniej jedno pudełko jest puste, policzyliśmy \(\displaystyle{ 6}\) razy układ, w którym do jednego pudełka trafiają wszystkie elementy zbioru, a powinniśmy policzyć tylko \(\displaystyle{ 3}\) razy (wszystkie w pierwszym pudełku, w drugim pudełku, w trzecim pudełku). Dlaczego tak się stało? Dla ustalenia uwagi, na przykład sytuację, w której wszystkie elementy trafiły do pierwszego pudełka zliczyliśmy raz jako sytuację, w której łącznie do pierwszego i drugiego pudełka trafiły wszystkie elementy, a drugi raz jako sytuację, w której do pierwszego i trzeciego pudełka trafiły wszystkie elementy.
Zatem musimy jeszcze dodać \(\displaystyle{ 3}\).
Na koniec zauważmy, że numeracja pudełek nie ma znaczenia, więc otrzymany wynik, czyli \(\displaystyle{ 3^{n}-{3\choose 2}2^{n}+3}\) dzielimy przez \(\displaystyle{ 3!=6}\), dostając \(\displaystyle{ \frac{3^{n-1}+1}{2}-2^{n-1}}\).

Dziękuję bardzo.