Farklı Nesnelerin Özdeş Kutulara Dağıtımı
Bu problem tipinde amaç birbirinden farklı \( n \) nesnenin özdeş \( k \) kutuya dağıtım sayısını hesaplamaktır.
Bu problem tipini her kutuya dağıtılabilecek nesne sayısına göre dört başlık altında inceleyebiliriz.
Her Kutuda Herhangi Bir Sayıda Nesne
Bu problem tipinde nesneler kutulara herhangi bir koşul olmaksızın dağıtılır (bazı kutular boş kalabilir ya da bir kutuya birden fazla nesne konabilir).
\( n \) farklı nesnenin \( k \) özdeş kutuya herhangi bir koşul olmaksızın farklı dağıtım sayısı \( = \displaystyle\sum_{i = 1}^{k} S(n, i) \)
Farklı nesnelerin \( k \) özdeş kutuya dağıtımını bir kümenin elemanlarının \( k \) alt kümeye parçalanış problemi olarak düşünebiliriz. Bu problem tipinde bazı kutular boş kalabildiği için farklı dağıtım sayısı sadece \( k \) alt kümeye parçalanışları değil, \( 1, 2, \ldots, k - 1 \) alt kümeye parçalanışları da içerir.
Önceki bölümlerde gördüğümüz üzere, \( n \) elemanlı bir kümenin boş olmayan \( k \) alt kümeye parçalanışı ikinci türden Stirling sayıları ile hesaplanır ve \( S(n, k) \) ile gösterilir. Buna göre bir kümenin \( 1, 2, \ldots, k \) alt kümeye parçalanış sayılarının toplamı aşağıdaki gibi olur.
\( S(n, 1) + S(n, 2) + \ldots + S(n, k) \) \( = \displaystyle\sum_{i = 1}^{k} S(n, i) \)
6 kişi 3 özdeş balona kaç farklı şekilde binebilir?
Çözümü GösterSorudaki kişiler farklı nesnelere, özdeş balonlar da nesnelerin dağıtılacağı özdeş kutulara karşılık gelmektedir.
Balonlar özdeş olduğu için, problemi bir kümenin elemanlarının farklı parçalanış sayısı problemi olarak kurgulayabiliriz.
Her balonda en az bir kişi bulunmalı koşulu verilmediği için bazı balonlar boş kalabilir, dolayısıyla kişilerin 1, 2 ve 3 alt kümeye parçalanış sayılarının toplamını almamız gerekir. Balonlar özdeş olduğu için kişilerin parçalandığı alt kümeler balonlarla tek bir şekilde eşleşebilir.
\( \displaystyle\sum_{i = 1}^{3} S(n, i) = S(6, 1) + S(6, 2) + S(6, 3) \)
İkinci türden Stirling sayıları sayfasında gördüğümüz tabloya göre bu formüldeki değerler aşağıdaki gibidir.
\( S(6, 1) = 1 \)
\( S(6, 2) = 31 \)
\( S(6, 3) = 90 \)
Buna göre 6 kişinin 3 balona herhangi bir koşul olmaksızın toplam dağıtım sayısı aşağıdaki gibi olur.
\( S(6, 1) + S(6, 2) + S(6, 3) \) \( = 1 + 31 + 90 = 122 \)
Her Kutuda En Fazla Bir Nesne
Bu problem tipinde nesneler kutulara her kutuda en fazla bir nesne olacak şekilde dağıtılır. Her kutuda en fazla bir nesne olabileceği için, bu problemlerde \( n \le k \) koşulunun sağlanması gerekir (nesne sayısı kutu sayısından fazla olamaz), aksi takdirde farklı dağıtım sayısı 0 olur.
\( n \le k \) olmak üzere,
\( n \) farklı nesnenin \( k \) özdeş kutuya her kutuda en fazla bir nesne olacak şekilde farklı dağıtım sayısı \( = 1 \)
Bu problem tipinde iki özdeş kutudaki birer nesne kutular arasında yer değiştirirse ya da bir kutudaki nesne boş özdeş bir kutuya aktarılırsa yeni bir dağıtım oluşmaz. Bu yüzden nesneler kutulara tek bir şekilde dağıtılabilir.
4 çocuk bir havuzdaki 6 özdeş deniz yatağına her deniz yatağında en fazla bir çocuk olacak şekilde kaç farklı şekilde binebilir?
Çözümü GösterSorudaki çocuklar farklı nesnelere, özdeş deniz yatakları da nesnelerin dağıtılacağı özdeş kutulara karşılık gelmektedir.
İki özdeş deniz yatağındaki çocuklar deniz yatakları arasında yer değiştirirse ya da bir deniz yatağındaki çocuk diğer boş bir deniz yatağına geçerse yeni bir dağıtım oluşmaz. Bu yüzden nesneler kutulara tek bir şekilde dağıtılabilir.
4 çocuğun 6 özdeş deniz yatağına her deniz yatağında en fazla bir çocuk olacak şekilde farklı dağıtım sayısı \( = 1 \)
Her Kutuda En Az Bir Nesne
Bu problem tipinde nesneler kutulara her kutuda en az bir nesne olacak şekilde dağıtılır. Her kutuda en az bir nesne olabileceği için, bu problemlerde \( n \ge k \) koşulunun sağlanması gerekir (nesne sayısı kutu sayısından az olamaz), aksi takdirde farklı dağıtım sayısı 0 olur.
\( n \ge k \) olmak üzere,
\( n \) farklı nesnenin \( k \) özdeş kutuya her kutuda en az bir nesne olacak şekilde dağıtım sayısı \( = S(n, k) \)
Farklı nesnelerin \( k \) özdeş kutuya dağıtımını bir kümenin elemanlarının \( k \) alt kümeye parçalanış problemi olarak düşünebiliriz. Önceki bölümlerde gördüğümüz üzere, \( n \) elemanlı bir kümenin boş olmayan \( k \) alt kümeye parçalanışı ikinci türden Stirling sayıları ile hesaplanır ve \( S(n, k) \) ile gösterilir.
6 öğrenci okul bahçesinde kaç farklı şekilde 3 gruba ayrılabilir?
Çözümü GösterSorudaki öğrenciler farklı nesnelere, oluşacak gruplar da farklı nesnelerin dağıtılacağı özdeş kutulara karşılık gelmektedir.
Gruplar özdeş olduğu ve hiçbir grup boş olamayacağı için problemi 6 elemanlı bir kümenin 3 alt kümeye parçalanış problemi olarak modelleyebiliriz, bu da \( S(6, 3) \) sayısına karşılık gelir.
İkinci türden Stirling sayıları sayfasında gördüğümüz tabloya göre \( S(6, 3) = 90 \)'dır.
Buna göre 6 öğrenci 90 farklı şekilde 3 gruba ayrılabilir.
Her Kutuda Tek Bir Nesne
Bu problem tipinde nesneler kutulara her kutuda sadece bir nesne olacak şekilde dağıtılır. Her kutuda sadece bir nesne olabileceği için, bu problemlerde \( n = k \) koşulunun sağlanması gerekir (nesne sayısı kutu sayısına eşit olmalıdır), aksi takdirde farklı dağıtım sayısı 0 olur.
\( n = k \) olmak üzere,
\( n \) farklı nesnenin \( k \) özdeş kutuya her kutuda sadece bir nesne olacak şekilde farklı dağıtım sayısı \( = 1 \)
Bu problem tipinde iki özdeş kutudaki birer nesne kutular arasında yer değiştirirse yeni bir dağıtım oluşmaz. Bu yüzden nesneler kutulara tek bir şekilde dağıtılabilir.
5 bebek 5 özdeş bebek arabasına kaç farklı şekilde konabilir?
Çözümü GösterSorudaki bebekler farklı nesnelere, özdeş bebek arabaları da nesnelerin dağıtılacağı özdeş kutulara karşılık gelmektedir.
İki özdeş bebek arabasındaki bebekler arabalar arasında yer değiştirirse yeni bir dağıtım oluşmaz. Bu yüzden nesneler kutulara tek bir şekilde dağıtılabilir.
5 bebeğin 5 özdeş bebek arabasına farklı dağıtım sayısı \( = 1 \)