Liczba Stirlinga

[Hubkor]

Czuję się w ciemnej materii.

Pierwsze zadanie jakie mam:
Wyznaczyc wzory na liczby \(\displaystyle{ S(n; 1), S(n; 2), S(n; n-1), S(n; n-2)}\) bazujac na ich definicjach.

Mam odpowiedź ale nic z niej nie rozumiem.

Siłuje się z tym, a przypuszczalnie jest jakiś łatwiejszy wzór. Otóż szukam i wikipedia mi nie na wiele pomogła, nie rozumiem nawet jak liczyć ten znak Stirlinga bo nie jest to dwumian Newtona.

Znalazłem tą stronkę:

Na stronie 35 jest przykład \(\displaystyle{ n=5, k=2}\) co ostatecznie wynosi \(\displaystyle{ 30}\).
Pare stron dalej jest ten sam przykłd jako liczba sterlinga II rzędu wynik \(\displaystyle{ 10}\).

Tymczasem mam drugie zadanie z uczelni:
Korzystajac z wynikow poprzedniego zadania oraz z zależznosci rekurencyjnych dla liczb
Stirlinga II-go rodzaju wyliczyc \(\displaystyle{ S(5; 2), S(5; 3), S(6; 3), S(7; 4)}\).
I odp.
\(\displaystyle{ S(5; 2) = S(4; 1) + 2 \cdot S(4; 2) = 1 + 2(S(3; 1) + 2S(3; 2)) = 1 + 2(1 + 2 3) = 15.}\)

Pomijając już że nie wiem jak powstają powyższe przekształcenia to, ten sam przykład ma dwa inne wyniki?

Z góry dziękuje za pomoc.

[Qń]

Dla \(\displaystyle{ n=5,k=2}\) liczba Stirlinga I rodzaju wynosi \(\displaystyle{ 30}\), a liczba Stirlinga drugiego rodzaju wynosi \(\displaystyle{ 15}\) - nie ma w tym żadnej sprzeczności, bo to dwa zupełnie inne symbole.

Jeśli chodzi o wyliczanie obu tych liczb dla małych \(\displaystyle{ n,k}\) - wystarczy skorzystać ze wzoru rekurencyjnego.

Co do liczenia niektórych liczb Stirlinga II rodzaju z definicji - oczywiście ktoś mógłby Ci przedstawić rozumowanie, ale zapewne byłoby to samo rozumowanie, które już znasz i którego nie rozumiesz. Może więc raczej, żeby nie marnować cudzego czasu wytłumaczysz co jest dla Ciebie niejasnego w tym zagadnieniu?

Q.

[Hubkor]

nie ma w tym żadnej sprzeczności, bo to dwa zupełnie inne symbole.

Przepraszam, źle spojrzałem na jeden z przykładów i zrobiłem niepotrzebny problem.

Jeśli chodzi o wyliczanie obu tych liczb dla małych - wystarczy skorzystać ze wzoru rekurencyjnego.

Mam wzór rekurencyjny na wikipedii, ale najwyraźniej totalnie nie umiem go użyć, bo dla \(\displaystyle{ n=5 k=2}\) wychodzi mi... \(\displaystyle{ 64}\)

Mógłbyś pokazać jak się go używa?

[Qń]

Wzór rekurencyjny to:
\(\displaystyle{ \left\{
\begin{matrix}
n\\
k\\
\end{matrix}
\right\}
=
k
\left\{
\begin{matrix}
n - 1\\
k\\
\end{matrix}
\right\}
+
\left\{
\begin{matrix}
n - 1\\
k - 1\\
\end{matrix}
\right\}}\)

W takim razie:
\(\displaystyle{ \left\{
\begin{matrix}
5\\
2\\
\end{matrix}
\right\}
=
2\cdot
\left\{
\begin{matrix}
4\\
2\\
\end{matrix}
\right\}
+
\left\{
\begin{matrix}
4\\
1\\
\end{matrix}
\right\}}\)
i do każdej nowej liczby Stirlinga znów stosujemy ten sam wzór.

Ewentualnie możemy też skorzystać z tego, że dla \(\displaystyle{ n>0}\) jest:
\(\displaystyle{ \left\{
\begin{matrix}
n\\
1\\
\end{matrix}
\right\}=1}\)
co przyśpieszy obliczenia.

Q.

[Hubkor]

Ok, podstawiac umiem. Zrobiłem to wcześniej. Nie w tym problem. Może się wydawać idiotyczny, ale nic nie poradzę, tak bywa . Do tej pory ucząc się kombinatoryki miałem działania głównie za pomocą dwumianu Newtona, silni. Takiej klamerki, czy wcześniej kwadrtowego nawiasu nie przypominam sobie (chyba że z algebry liniowej, ale to przeciez nie macierze).
Czyli meritum na czym polegają działania w tych klamerkach? (bo nawet w instrukcji Latexu nie ma takich żebym to napisał).

[Qń]

Mam wzór rekurencyjny na wikipedii, ale najwyraźniej totalnie nie umiem go użyć

Ok, podstawiac umiem.

Zdecyduj się.

Takiej klamerki, czy wcześniej kwadrtowego nawiasu nie przypominam sobie

Ta jak to piszesz "klamerka" to właśnie liczba Stirlinga drugiego rodzaju. Czasem oznacza się ją też przez \(\displaystyle{ S(n,k)}\) - ale to pod warunkiem, że z kontekstu wynika o który rodzaj chodzi.

Definicja obu rodzajów liczb Stirlinga jest kombinatoryczna (I rodzaju: liczba permutacji zbioru \(\displaystyle{ n}\)-elementowego o \(\displaystyle{ k}\) cyklach; II rodzaju: liczba podziałów zbioru \(\displaystyle{ n}\)-elementowego na \(\displaystyle{ k}\) części) i z tejże definicji kombinatorycznej wynikają wzory rekurencyjne, a także różne własności typu:
\(\displaystyle{ \left\{ \begin{matrix} n\\ n-1\\ \end{matrix} \right\}=\binom n2}\)

O ile jednak symbol Newtona można obliczać przy użyciu silni, o tyle na liczby Stirlinga żadnego wzoru jawnego nie ma i można je obliczać tylko rekurencyjnie.

Q.