İkinci Tür Stirling Sayıları S(n,k) Hesaplayıcı

İkinci Tür Stirling Sayıları S(n,k) Hesaplayıcı

Popüler AI Skill PRO

Hesaplamaya Girin

Formül

S(n,k)=1k!∑j=0k(−1)j(kj)(k−j)nS\!\left(\text{n},\,\text{k}\right) = \frac{1}{\text{k}!}\sum_{j=0}^{\text{k}} (-1)^{j}\binom{\text{k}}{j}\left(\text{k}-j\right)^{\text{n}}
Kullanım istatistikleri

Reklam

Sonuç

İkinci Tür Stirling Sayısı S(5, 2)
15
etiketli elemanları boş olmayan alt kümelere ayırma yolu (Elemanlar: 5 · Alt kümeler: 2)
n (küme boyutu) 5
k (alt kümeler) 2
Gösterim S(n, k)

Bu sayfadaki bir hatayı bildir

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

Etiketsiz iki kutuya ayrılmış dört etiketli top, bir küme bölüntüsünü gösteriyor
S(n,k), etiketli n öğeyi boş olmayan k etiketsiz gruba ayırmanın kaç yolu olduğunu sayar.

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\).

Reklam

Çö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.

Pascal üçgeni gibi dizilmiş küçük Stirling sayılarının üçgen ızgarası
S(n,k) değerlerinden oluşan bir üçgen; her değer üstündeki iki değerden oluşur.

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.

Reklam

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.

Son güncelleme:

Matematik ve İstatistik kategorisinde en popüler

Tüm Matematik ve İstatistik hesap makinelerini gör