İkinci tür Stirling sayıları nedir?
S(n,k) ile gösterilen (bazen {n üstte k} ya da S2(n,k) biçiminde de yazılan) ikinci tür Stirling sayısı, n etiketli (birbirinden ayırt edilebilir) nesneden oluşan bir kümeyi tam olarak k tane boş olmayan, etiketsiz alt kümeye (bloklara) bölmenin kaç farklı yolu olduğunu sayar. Bu hesaplayıcı tüm bir satırı hesaplar: sabit bir n için k = 0, 1, 2, ..., n değerlerine karşılık gelen S(n,k) değerlerini, yani Stirling üçgeninin n. satırındaki her değeri listeler. Bu, herhangi bir bölgeye bağlı olmayan, saf matematiksel bir kombinatorik büyüklüktür.
Nasıl kullanılır?
Negatif olmayan bir n tam sayısı (kümenizdeki eleman sayısı) girin ve gönderin. Araç, k ve S(n,k) olmak üzere iki sütunlu bir tablo döndürür; ayrıca satır toplamını da verir; bu toplam Bell sayısı B(n)'dir ve işlemin doğruluğunu kontrol etmek için pratik bir yoldur. Tüm değerler sınırsız hassasiyetli tam sayılarla hesaplanır; böylece sayılar 64-bitlik bir değerin sığdırabileceğinin çok ötesine geçtiğinde bile (ki bu durum n = 20-25 dolaylarında ortaya çıkar) kesin kalırlar.
Formülün açıklaması
En sağlam yöntem, \(S(0,0) = 1\) temel durumundan başlayarak inşa edilen yineleme bağıntısıdır:
$$S(n,k) = k\cdot S(n-1,k) + S(n-1,k-1)$$Sınır değerleri şunlardır: n ≥ 1 için \(S(n,0) = 0\), \(S(n,n) = 1\), n ≥ 1 için \(S(n,1) = 1\) ve k > n için \(S(n,k) = 0\). Ayrıca açık bir kapalı form da vardır:
$$S(n,k) = \frac{1}{k!} \cdot \sum (-1)^{k-j} \binom{k}{j} j^n$$ancak bu formül kayan noktalı hesapta büyük sadeleşme hatalarına yol açtığı için biz kesin tam sayılarla yineleme bağıntısını kullanıyoruz.
Çözümlü örnek (n = 5)
5. satır şöyledir: k=0 → 0, k=1 → 1, k=2 → 15, k=3 → 25, k=4 → 10, k=5 → 1. 4. satırdan = [0,1,7,6,1] doğrulayalım:
$$S(5,2) = 2\cdot 7 + 1 = 15$$$$S(5,3) = 3\cdot 6 + 7 = 25$$$$S(5,4) = 4\cdot 1 + 6 = 10$$Satır toplamı \(0+1+15+25+10+1 = 52\)'dir ve bu da Bell sayısı \(B(5) = 52\)'ye eşittir.
Stirling Üçgeni, İkinci Tür (Satır 0–8) ve Bell Sayıları
İkinci tür Stirling sayısı \(S(n,k)\), \(n\) adet farklı elemanlı bir kümeyi tam olarak \(k\) adet boş olmayan, etiketsiz alt kümeye bölmenin yollarının sayısını verir. Her girdi \(S(n,k) = k\,S(n-1,k) + S(n-1,k-1)\) yineleme bağıntısını izler; burada \(S(0,0)=1\) ve \(n\ge 1\) için \(S(n,0)=0\)'dır. Satır toplamı Bell sayısıdır: \(B(n)=\sum_{k=0}^{n} S(n,k)\), yani \(n\) elemanlı bir kümenin toplam bölüntü sayısıdır.
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Satır toplamı B(n) |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | ||||||||
| 1 | 0 | 1 | 1 | |||||||
| 2 | 0 | 1 | 1 | 2 | ||||||
| 3 | 0 | 1 | 3 | 1 | 5 | |||||
| 4 | 0 | 1 | 7 | 6 | 1 | 15 | ||||
| 5 | 0 | 1 | 15 | 25 | 10 | 1 | 52 | |||
| 6 | 0 | 1 | 31 | 90 | 65 | 15 | 1 | 203 | ||
| 7 | 0 | 1 | 63 | 301 | 350 | 140 | 21 | 1 | 877 | |
| 8 | 0 | 1 | 127 | 966 | 1701 | 1050 | 266 | 28 | 1 | 4140 |
Boş hücreler, sıfır olduğu tanım gereği \(k>n\) olan konumlardır.
Tablo nasıl okunur
- Yinelemenin örnek kontrolü: \(S(8,3) = 3\cdot S(7,3) + S(7,2) = 3\cdot 301 + 63 = 903 + 63 = 966\).
- Bir başka kontrol: \(S(8,4) = 4\cdot S(7,4) + S(7,3) = 4\cdot 350 + 301 = 1400 + 301 = 1701\).
- \(n=5\) için satır toplamı kontrolü: \(0+1+15+25+10+1 = 52 = B(5)\).
- Kenar değerler: \(S(n,1)=1\) ve \(S(n,n)=1\); ayrıca \(S(n,2)=2^{n-1}-1\) (örneğin \(S(8,2)=127\)).
Sıkça sorulan sorular
n ≥ 1 için S(n,0) neden 0'dır? Boş olmayan bir kümeyi sıfır bloğa bölemezsiniz; yalnızca boş kümenin boş bölünüşü vardır ve bu da \(S(0,0) = 1\) sonucunu verir.
Satır toplamı nedir? S(n,k) değerlerinin tüm k için toplamı, n elemanlı bir kümenin toplam bölünüş sayısı olan Bell sayısı B(n)'i verir.
n en fazla ne kadar olabilir? Bu araç n = 200'e kadar değer kabul eder; değerler devasa boyutlara ulaşır ama büyük tam sayı aritmetiği sayesinde kesin kalır.