İ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.
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.
