İkinci Tür Stirling Sayısı Nedir?
S(n,k) ile gösterilen ikinci tür Stirling sayısı, n adet birbirinden farklı (etiketli) elemandan oluşan bir kümeyi tam olarak k tane boş olmayan, etiketsiz alt kümeye ayırmanın kaç farklı yolu olduğunu sayar. Kombinatoriğin temel büyüklüklerinden biridir; küme parçalanışları, örten fonksiyonlar (sürjeksiyonlar) ve Bell sayılarıyla ilgili problemlerde karşımıza çıkar. Tamamen matematiksel bir araçtır ve her yerde aynı şekilde işler.
Bu Hesaplayıcı Nasıl Kullanılır?
Küme boyutu n ile alt küme sayısı k değerlerini girin. Her ikisi de negatif olmayan tam sayılar olmalıdır. Hesapla düğmesine bastığınızda, parçalanışların tam sayısı olan \(S(n,k)\) değerini elde edersiniz. Eğer k, n'den büyükse sonuç 0 çıkar; çünkü eleman sayınızdan daha fazla boş olmayan alt küme oluşturamazsınız.
Formülün Açıklaması
Açık biçim şöyledir:
$$S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j} j^{n}$$Burada \(C(k,j)\) binom katsayısıdır. Eşdeğer ve sayısal açıdan daha güvenli bir yol ise şu yineleme bağıntısıdır:
$$S(n,k) = k\,S(n-1,k) + S(n-1,k-1)$$Başlangıç değerleri ise \(S(0,0)=1\), n>0 için \(S(n,0)=0\) ve k>0 için \(S(0,k)=0\) şeklindedir. Bu hesaplayıcı, kayan nokta hatalarından (sadeleşme kaynaklı kayıplardan) kaçınmak için yineleme bağıntısını kullanır. İşe yarayan özel durumlar: \(S(n,1)=1\), \(S(n,n)=1\) ve \(S(n,2)=2^{n-1}-1\).
Çözümlü Örnek
n=5 ve k=2 için: özel durumu kullanırsak
$$S(5,2)=2^{5-1}-1=16-1=15$$Yineleme bağıntısı da bunu doğrular:
$$S(5,2)=2\cdot S(4,2)+S(4,1)=2\cdot 7+1=15$$Yani 5 elemanlı bir kümeyi boş olmayan iki gruba ayırmanın 15 farklı yolu vardır.
n için 0'dan 10'a kadar İkinci Tür Stirling Sayıları S(n,k) Tablosu
Her girdi, n etiketli elemanlı bir kümenin tam olarak k boş olmayan, etiketsiz bloğa bölünme sayısıdır. Tablo \(S(n,k)=k\cdot S(n-1,k)+S(n-1,k-1)\) yinelemesinden, \(S(0,0)=1\) ve \(n\ge 1\) için \(S(n,0)=S(0,n)=0\) ile oluşturulmuştur. Boş hücreler \(k>n\) durumlarıdır; burada S(n,k)=0'dır. Son sütun satır toplamıdır ve Bell sayısı B(n)'dir. Örneğin S(10,4) = 34105.
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 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 | ||
| 9 | 0 | 1 | 255 | 3025 | 7770 | 6951 | 2646 | 462 | 36 | 1 | 21147 | |
| 10 | 0 | 1 | 511 | 9330 | 34105 | 42525 | 22827 | 5880 | 750 | 45 | 1 | 115975 |
Yineleme ile bir girdinin kontrolü: \(S(6,3)=3\cdot S(5,3)+S(5,2)=3\cdot 25+15=90\). Her zaman \(S(n,1)=1\), \(S(n,2)=2^{n-1}-1\), \(S(n,n-1)=\binom{n}{2}\) ve \(S(n,n)=1\) geçerlidir.
Temel Terimler ve Gösterim
- Küme bölümlemesi
- Bir kümenin, birleşimi tüm kümeyi veren, boş olmayan ve ikişer ikişer ayrık alt kümelere (bloklara) ayrılması. Blokların sırası ve bir blok içindeki sıra önemli değildir.
- Etiketli ve etiketsiz
- n eleman etiketlidir (ayırt edilebilir, ör. 1, 2, …, n). k alt küme ise etiketsizdir: iki bloğun yer değiştirmesi aynı bölümlemeyi verir. Bloklar etiketli olsaydı, sayı bunun yerine k!·S(n,k) olurdu.
- Boş olmayan blok
- k alt kümenin her birinde en az bir eleman bulunmalıdır. Bu yüzden n ≥ 1 için S(n,0)=0 ve k > n olduğunda S(n,k)=0'dır.
- S(n,k) gösterimi
- İkinci tür Stirling sayısı, ayrıca \(\left\{ n \atop k \right\}\) ile de yazılır. \(S(n,k)=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}(k-j)^{n}\) ile hesaplanır.
- Bell sayısı B(n)
- Bir n elemanlı kümenin herhangi bir sayıda bloğa bölünmesinin toplam sayısı: \(B(n)=\sum_{k=0}^{n}S(n,k)\). İlk değerler 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975'tir.
- Binom katsayısı
- \(\binom{k}{j}=\frac{k!}{j!\,(k-j)!}\), k elemanın içinden j eleman seçmenin yollarının sayısıdır. Yukarıdaki içerme-dışlama formülünde yer alır.
- Örten fonksiyon (surjection)
- Bir n-kümesinden bir k-kümesine, k-kümenin her elemanının en az bir kez değer olarak alındığı fonksiyon. Bu tür fonksiyonların sayısı \(k!\cdot S(n,k)\)'dir: tanım kümesini k bloğa bölün, sonra blokları k hedefe k! yolla atayın.
İkinci tür ile birinci tür. İkinci tür Stirling sayıları, bir kümenin k bloğa bölünmesini sayar. Birinci tür Stirling sayıları, \(c(n,k)\) veya \(\left[ n \atop k \right]\) (işaretsiz) ile yazılır ve tam olarak k devirli n elemanlı permütasyonları sayar. Farklı bir yinelemeyi sağlarlar, \(c(n,k)=(n-1)\,c(n-1,k)+c(n-1,k-1)\), ve işaretlerle birlikte birbirlerinin ters matrisleridir.
Sıkça Sorulan Sorular
S(0,0) neden 1'e eşittir? Geleneksel olarak boş kümenin, sıfır parçaya tek bir parçalanışı vardır: boş parçalanış.
k > n olduğunda ne olur? Sonuç 0'dır; çünkü her alt küme boş olmayan olmak zorundadır ve elinizde yeterince eleman yoktur.
Bunun Bell sayılarıyla ilişkisi nedir? \(S(n,k)\) değerlerini k=0'dan n'ye kadar tüm k için topladığınızda, n elemanlı bir kümenin toplam parçalanış sayısı olan Bell sayısı \(B(n)\)'yi elde edersiniz.