Liczby Stirlinga II rodzaju Macierzanka: Hej,właśnie mierzę się z liczbami Stirlinga drugiego rodzaju. Wymyśliłem kilka przykładów dla ćwiczenia i chciałbym sprawdzić, czy poprawnie interpretuję właściwości liczb. Pragnąc nie przerażać czytelników długością wpisu, zamierzam najpierw przedstawić swoje rozumowanie, zaś w następnych postach poprosić o sprawdzenie przykładów. Postanowiłem znaleźć wzory jawne dla następujących liczb Stirlinga: a) S(n, n−3) − rozdzielam n rozróżnialnych elementów do n−3 nierozróżnialnych kategorii Rozważam trzy przypadki: 1) n−3>0 dlatego najmniejszą wartość, którą może przyjąć n, stanowi 4. Wybieram najprostszy przypadek, rozdzielając 4 elementy z n−elementowego zbioru, tworząc pierwszy podzbiór (kategorię):

n 4

2) Następnie wyróżniam trzy elementy z n−elementowego zbioru, następnie 3 elementy z (n−3)−elementowego zbioru (po usunięciu trzech elementów), by utworzyć dwie kategorie; ze względu na nierozróżnialność kategorii, wykluczam powtarzające się konfiguracje przez podzielenie przez 2.

	n 3	n−3 3
12

3) kończę, analizując konstrukcję trzech podzbiorów, w których umieszczam po 2 obiekty, wśród których wyłączam powtarzające się układy dzięki dzieleniu przez 6;

1	n 2	n−2 2	n−4 2
6

4) wzór jawny stanowi suma wszystkich przypadków:

	n 4		n 3	n−3 3		1	n 2	n−2 2	n−4 2
S(n, n−3)=		+12			+
						6

Będę wdzięczny za każdą korektę i wskazówkę.

Macierzanka: Rozumiem, że bezbłędnie rozwiązuję?

jc: n=6

6 4		1		6 3		3 3		1		6 2		4 2		2 2
	+						+
		2						6

= 15 + 20/2 + 15*6/6 = 15+10+15=40 Czy tyle wynosi S(6,3) ?

Macierzanka: Ohohohoho...Gdy liczę ręcznie z k−kombinacjami otrzymuję prawie 8000... Proszę o pomoc i wytłumaczenie.

Pytający: n= =(n−3)+1+1+1= =(n−4)+2+1+1= =(n−5)+3+1+1= =(n−5)+2+2+1= =(n−6)+4+1+1= =(n−6)+3+2+1= =(n−6)+2+2+2= = ... // można by tak wyliczać i wyliczać (i będą to sumy różnych składników dla odpowiednio dużych n)

Pytający: Znaczy nie masz co rozpatrywać w ten sposób przypadków, bo zawsze znajdziesz większe n, w którym tych przypadków będzie jeszcze więcej. Zastanów się, skąd wziął się wzór rekurencyjny: S₂(n,k)=k*S₂(n−1,k)+S₂(n−1,k−1)

Pytający: Wróć, ale pogmatwałem, porąbało mi się, przepraszam. To co wyżej pisałem byłoby, gdybyś chciał rozpisać uniwersalnie S₂(n,4), nie S₂(n,n−3).

	n 4		n 3	n−3 2		n 3*2		6!
S2(n,n−3)=		+			+		*		=
								(2!)3*3!

	n 4		n 3	n−3 2		1	n 2	n−2 2	n−4 2
=		+			+
						3!

Więc tylko trochę pomieszałeś.

Macierzanka: Myślę, że jeżeli zastanawiałem się przez kilka godzin, muszę już poprosić o wyjaśnienie krok po kroku tworzenia wzoru jawnego.

Macierzanka: Przepraszam, nie odświeżyła się strona, gdy umieszczałem wpis.

Macierzanka: Mniej przepraszam, potrzebuję wyjaśnienia. :')

	n 3	n−3 2
Dlaczego			? Dlaczego zmiana na 2?

Pytający: Generalnie masz n−elementowy zbiór i chcesz go podzielić na (n−3) rozłączne podzbiory sumujące się całego tego zbioru. Każdy z tych podzbiorów musi mieć co najmniej 1 element, to oczywiste. Zatem zastanawiając się na licznościami tych podzbiorów mamy na ten moment (n−3) podzbiorów o liczności 1 i trzeba jakoś dołożyć do nich pozostałe 3 elementy. Mamy: 3= =3= =2+1= =1+1+1 Kolejne podziały 3 na składniki odpowiadają różnym podziałom na podzbiory: 3 // dorzucamy 3 elementy do któregoś podzbioru jednoelementowego, więc zostanie nam (n−3−1) podzbiorów jednoelementowych i będzie 1 podzbiór 1+3=4−elementowy 2+1 // dorzucamy 2 elementy do któregoś podzbioru jednoelementowego i 1 element do jakiegoś innego podzbioru jednoelementowego, w wyniku otrzymujemy (n−3−2) podzbiory jednoelementowe, 1 podzbiór 2+1=3−elementowy i 1 podzbiór 1+1=2−elementowy 1+1+1 // jw, otrzymujemy (n−3−3) podzbiory jednoelementowe i 3 podzbiory 1+1=2−elementowe W ten sposób masz wszystkie możliwości i pozostaje policzyć.

n 3	n−3 2
		// to wybór podzbioru 3−elementowego, z pozostałych elementów wybór podzbioru

2−elementowego, pozostałe (n−5) elementów stanowi (n−5) podzbiorów jednoelementowych; łącznie 1+1+(n−5)=n−3 podzbiorów

Pytający: "Każdy z tych podzbiorów musi mieć co najmniej 1 element", bo rozdzielamy oczywiście na niepuste podzbiory.

Macierzanka: Drogi Pytający, moc obliczeniowa Twojego mentalnego komputera właśnie zagwarantowała Ci liczbę bitcoinów zwanych wdzięcznością odpowiadającą liczbie co najmniej S(n, n−3). Podejrzewam, że Stirling nie wytłumaczyłby dokładniej i bardziej przejrzyście. Dziękuję!

Pytający: Proszę bardzo! Acz podejrzewam, że to Twoje kolejne błędne podejrzenie.