Dowód liczby Stirlinga

[Szakul1]

Pokaż, że:
1. \(\displaystyle{ S(n;\ n-2)= {n+1 \choose 4}+2 \cdot {n \choose 4}}\)
2. \(\displaystyle{ \sum_{k=1}^{n} k \cdot s(n;\ k)=s(n+1;\ 2)}\)

[Premislav]

1. Dzielimy zbiór \(\displaystyle{ n}\)-elementowy na \(\displaystyle{ n-2}\) niepuste, parami rozłączne zbiory.
Powstanie więc bądź to \(\displaystyle{ n-3}\) singletonów i jeden zbiór trójelementowy, bądź \(\displaystyle{ n-4}\) singletony i dwa zbiory dwuelementowe. W tym pierwszym przypadku wybieramy
na \(\displaystyle{ {n \choose 3}}\) sposoby elementy zbioru trójelementowego, a dla pozostałych tworzymy singletony, więc mamy \(\displaystyle{ {n\choose 3}}\) takich podziałów, w których jest jeden podzbiór trójelementowy i \(\displaystyle{ n-3}\) singletony, a w tym drugim przypadku na \(\displaystyle{ {n \choose 4}}\) sposoby wybieramy elementy, które wejdą w skład zbiorów dwuelementowych i na \(\displaystyle{ 3}\) sposoby (wystarczy ustalić jakiś element spośród tych czterech wybranych i zauważyć, że na trzy sposoby możemy dobrać do niego jeden z trzech pozostałych, który będzie z nim w tym samym dubletonie) rozbijamy otrzymany podzbiór czteroelementowy na dwa podzbiory dwuelementowe, a pozostałe elementy pakujemy w singletonach. Zatem
\(\displaystyle{ S(n;n-2)={n \choose 3}+3{n \choose 4}}\) i pozostaje sprawdzić, że
\(\displaystyle{ {n \choose 3}+3{n \choose 4}={n+1 \choose 4}+2 \cdot {n \choose 4}}\),
co zostawiam jako nietrudne ćwiczenie.

[Szakul1]

w drugim są liczby pierwszego rodzaju, czyli wzór rekurencyjny jest:
\(\displaystyle{ s(n+1;2)=n \cdot s(n;2)+s(n;1)}\)

-- 23 cze 2019, o 21:45 --

\(\displaystyle{ {n \choose 3}+3{n \choose 4}={n+1 \choose 4}+2 \cdot {n \choose 4}}\)
\(\displaystyle{ {n \choose 3}= {n+1 \choose 4}- {n \choose 4}}\)
\(\displaystyle{ {n \choose 3}= \frac{(n+1)n(n-1)(n-2)}{4!}- \frac{n(n-1)(n-2)(n-3)}{4!}}\)
\(\displaystyle{ {n \choose 3}= \frac{n(n-1)(n-2) \cdot 4}{4!}}\)
Zostawiam dla innych.
Faktycznie pierwszy punkt bardzo ładnie rozwiązany.