5 Sayma Teknikleri
Olasılık Uzayı Örnekleri ve Geometrik Olasılık bölümünde Laplace olasılık uzayını tanımladık (Tanım 4.1): örnek uzay sonlu ve her sonuç eşit olasılıklı olduğunda bir \(A\) olayının olasılığı, uygun durumların sayısının bütün durumların sayısına oranıdır (Önerme 4.2):
\[P(A) = \frac{|A|}{|\Omega|}.\]
Burada \(|A|\), önceki bölümde \(n(A)\) ile de gösterdiğimiz eleman sayısıdır; bu bölümde yalnızca \(|A|\) yazacağız. Bu formül olasılık hesabını iki sayma işine indirger: \(\Omega\)’nın eleman sayısını ve \(A\)’nın eleman sayısını bulmak. Bir zar, iki para gibi küçük deneylerde bu sayılar elle bulunur. Ama örnek uzay binlerce ya da milyarlarca noktadan oluşuyorsa tek tek saymak olanaksızdır. Bir sınıftaki \(23\) kişinin doğum günleri için \(365^{23}\) olası liste vardır; bunların içinde en az iki kişinin doğum gününün çakıştığı listeleri saymak, sistemli bir yöntem olmadan yapılamaz.
Bu bölümde bütün sayma yöntemlerinin dayandığı iki temel kuralı, toplama ve çarpma kurallarını ispatlayacağız; ardından bunlardan permütasyon, kombinasyon, tekrarlı permütasyon (çok terimli katsayı) ve tekrarlı kombinasyon (yıldız–çubuk) formüllerini türeteceğiz. Yol üstünde binom teoremini tümevarımla ispatlayacak, genelleştirilmiş binom katsayısını tanımlayacağız. Her formülü somut sayma problemleriyle sınayacak, sonunda da Laplace uzayında olasılık hesaplarına döneceğiz. Burada kurulan araçlar yalnızca bu bölümün değil, ileride binom, hipergeometrik ve negatif binom dağılımlarının da temelidir.
5.1 Toplama ve Çarpma Kuralları
Her sayma yöntemi iki basit gözleme dayanır. Birincisi, birbirini dışlayan seçenekleri sayarken sayıların toplandığını söyler; ikincisi, art arda yapılan seçimleri sayarken sayıların çarpıldığını söyler. İkisini de ispatlarıyla yazıyoruz, çünkü sonraki her formül bu ikisine indirgenecektir.
Önerme 5.1 (Toplama Kuralı) Bir iş iki farklı yoldan yapılabilsin: birinci yol \(n_1\) farklı biçimde, ikinci yol \(n_2\) farklı biçimde gerçekleştirilebilsin ve iki yolun ortak hiçbir biçimi olmasın. O zaman iş \(n_1 + n_2\) farklı biçimde yapılabilir.
Daha genel olarak, birbirini dışlayan \(k\) yol sırasıyla \(n_1, n_2, \ldots, n_k\) biçimde gerçekleştirilebiliyorsa iş \(n_1 + n_2 + \cdots + n_k\) farklı biçimde yapılabilir.
İspat
Birinci yolun biçimlerinin kümesi \(A_1\), ikincininki \(A_2\) olsun; \(|A_1| = n_1\), \(|A_2| = n_2\) ve varsayım gereği \(A_1 \cap A_2 = \varnothing\). İşi yapmanın bütün biçimleri \(A_1 \cup A_2\) kümesini oluşturur. Ayrık iki sonlu kümenin birleşiminin eleman sayısı, eleman sayılarının toplamıdır: \(A_1\)’in elemanlarını \(1, 2, \ldots, n_1\) sayılarıyla, \(A_2\)’nin elemanlarını \(n_1 + 1, \ldots, n_1 + n_2\) sayılarıyla numaralayalım. Kümeler ayrık olduğundan hiçbir eleman iki numara almaz ve her numara tam bir elemana gider; böylece \(A_1 \cup A_2\) ile \(\{1, 2, \ldots, n_1 + n_2\}\) arasında birebir ve örten bir eşleme kurulmuş olur. Öyleyse \(|A_1 \cup A_2| = n_1 + n_2\).
\(k\) yol için ifade \(k\) üzerinde tümevarımla çıkar: \(A_1 \cup \cdots \cup A_k = (A_1 \cup \cdots \cup A_{k-1}) \cup A_k\) yazılır. Parantez içindeki küme \(A_k\) ile ayrıktır; iki küme için kanıtlanan sonuç ve tümevarım hipotezi birlikte \(|A_1 \cup \cdots \cup A_k| = (n_1 + \cdots + n_{k-1}) + n_k\) verir.
\(\blacksquare\)
Toplama kuralı “ya biri ya öteki” biçimindeki seçimleri sayar. Bir seçimin ardından bir başka seçim geliyorsa ihtiyaç duyulan kural farklıdır.
Önerme 5.2 (Çarpma Kuralı) Bir iş art arda iki adımda yapılsın. Birinci adım \(n_1\) farklı biçimde yapılabilsin ve birinci adım hangi biçimde yapılmış olursa olsun ikinci adım \(n_2\) farklı biçimde yapılabilsin. O zaman iş \(n_1 n_2\) farklı biçimde yapılabilir.
Daha genel olarak, \(k\) adımlı bir işte \(i\)-inci adım, önceki adımlar nasıl yapılmış olursa olsun, \(n_i\) farklı biçimde yapılabiliyorsa iş \(n_1 n_2 \cdots n_k\) farklı biçimde yapılabilir.
İspat
Birinci adımın biçimlerinin kümesi \(A = \{a_1, a_2, \ldots, a_{n_1}\}\) olsun. Birinci adım \(a_i\) biçiminde yapıldığında ikinci adımın biçimlerinin kümesi \(B_i\) olsun; varsayım gereği her \(i\) için \(|B_i| = n_2\). İşi yapmanın bir biçimi, \(b \in B_i\) olmak üzere bir \((a_i, b)\) çiftiyle belirlenir. Bu çiftlerin kümesi
\[\{(a_i, b) : i = 1, \ldots, n_1,\ b \in B_i\} = \bigcup_{i=1}^{n_1} \big(\{a_i\} \times B_i\big)\]
biçiminde yazılır. Sağdaki \(n_1\) küme, ilk bileşenleri farklı olduğundan ikişer ikişer ayrıktır ve her birinin \(n_2\) elemanı vardır. Toplama kuralına göre (Önerme 5.1) birleşimin eleman sayısı
\[\underbrace{n_2 + n_2 + \cdots + n_2}_{n_1 \text{ terim}} = n_1 n_2\]
olur.
\(k\) adım için yine tümevarım: ilk \(k-1\) adım tek bir “birinci adım” gibi görülür. Tümevarım hipotezine göre bu \(n_1 n_2 \cdots n_{k-1}\) biçimde yapılır; ardından \(k\)-ıncı adım, öncekilerden bağımsız olarak, \(n_k\) biçimde yapılır. İki adım için kanıtlanan sonuç \(n_1 n_2 \cdots n_{k-1} \cdot n_k\) verir.
\(\blacksquare\)
Sorudaki bağlaç yol gösterir. “Matematik kitaplarından ya da fizik kitaplarından bir kitap seç” (\(3\) matematik, \(4\) fizik kitabı): seçenekler birbirini dışlar, toplama kuralı, \(3 + 4 = 7\). “Bir matematik ve bir fizik kitabı seç”: seçimler art arda yapılır ve ikincinin seçenek sayısı birincinin seçiminden etkilenmez, çarpma kuralı, \(3 \cdot 4 = 12\).
Çarpma kuralındaki koşula dikkat edilmelidir: ikinci adımın seçenek sayısı birinci adımdan bağımsız olmalıdır; seçeneklerin kendileri değişebilir. Bir torbadan iade etmeden iki top çekerken ikinci çekilişte hangi topların kaldığı ilk çekilişe bağlıdır, ama kalan top sayısı hep bir eksiktir; kural uygulanır.
5.2 Permütasyon
En sık karşılaşılan sayma sorusu şudur: \(n\) farklı nesneden \(r\) tanesi seçilip bir sıraya dizilecekse kaç diziliş vardır? Sıranın önemli olduğu bu düzenlemelere ad verelim.
Tanım 5.1 (Permütasyon) \(n\) farklı nesneden oluşan bir kümenin tamamının ya da bir kısmının belirli bir sıraya dizilmesine bir permütasyon denir. \(n\) nesneden \(r\) tanesinin (\(0 \le r \le n\)) seçilip sıraya dizilmesiyle elde edilen düzenlemeye \(n\) nesnenin bir \(r\)-li permütasyonu denir; seçilen bir nesne yeniden kullanılmaz (yinelemesiz permütasyon). Bu permütasyonların sayısı \(P(n, r)\) ile gösterilir.
Permütasyonda sıra önemlidir: \(a, b, c\) nesnelerinin \(2\)-li permütasyonları \(ab, ba, ac, ca, bc, cb\) olmak üzere altı tanedir; \(ab\) ile \(ba\) farklı sayılır. Bu sayıyı genel olarak veren formül, çarpma kuralının ilk doğrudan uygulamasıdır.
Teorem 5.1 (Permütasyon Sayısı) \(n\) farklı nesnenin \(r\)-li permütasyonlarının sayısı
\[P(n, r) = n(n-1)(n-2) \cdots (n-r+1) = \frac{n!}{(n-r)!}\]
dir. Özel olarak \(n\) nesnenin tümünün sıralanışlarının sayısı \(P(n, n) = n!\) ve \(P(n, 0) = 1\)’dir. Burada \(0! = 1\) kabul edilir.
İspat
Bir \(r\)-li permütasyon \(r\) adımda kurulur: birinci yere konacak nesne seçilir, sonra ikinci yere konacak nesne, …, sonunda \(r\)-inci yere konacak nesne. Birinci yer için \(n\) seçenek vardır. Birinci yer nasıl doldurulmuş olursa olsun, kullanılan nesne bir daha kullanılmayacağından ikinci yer için \(n-1\) seçenek kalır. Genel olarak \(i\)-inci yere gelindiğinde \(i-1\) nesne kullanılmıştır ve \(n-i+1\) seçenek vardır; \(r\)-inci yer için \(n-r+1\) seçenek. Her adımdaki seçenek sayısı önceki adımların nasıl yapıldığına bağlı olmadığından çarpma kuralı (Önerme 5.2) uygulanır:
\[P(n, r) = n(n-1)\cdots(n-r+1).\]
Sağ tarafı \((n-r)!\) ile çarpıp bölelim:
\[n(n-1)\cdots(n-r+1) = \frac{n(n-1)\cdots(n-r+1)\,(n-r)(n-r-1)\cdots 2 \cdot 1}{(n-r)!} = \frac{n!}{(n-r)!}.\]
\(r = n\) için \((n-n)! = 0! = 1\) olduğundan \(P(n, n) = n!\) çıkar. \(r = 0\) için hiçbir yer doldurulmaz; tek bir (boş) düzenleme vardır ve formül \(n!/n! = 1\) verir.
\(\blacksquare\)
Örnek 5.1 (Kitaplıktaki Üç Boş Yer) \(7\) farklı kitap arasından seçilen \(3\) kitap, bir kitaplıktaki \(3\) boş yere kaç farklı biçimde yerleştirilebilir?
Çözüm
Üç boş yer birbirinden farklıdır: soldaki, ortadaki ve sağdaki. Dolayısıyla hangi kitabın hangi yere konduğu önemlidir, yani sıra önemlidir. Aranan sayı \(7\) nesnenin \(3\)-lü permütasyonlarının sayısıdır (Teorem 5.1):
\[P(7, 3) = 7 \cdot 6 \cdot 5 = \frac{7!}{4!} = 210.\]
Çarpma kuralıyla doğrudan da görülür: birinci boş yer için \(7\), ikincisi için \(6\), üçüncüsü için \(5\) seçenek vardır.
\(\blacksquare\)
5.3 Kombinasyon
Çoğu zaman sıra önemli değildir. \(10\) kişiden \(3\) kişilik bir komite seçerken komitenin kimlerden oluştuğu önemlidir, kimin önce seçildiği değil. Bu durumda saydığımız şey diziliş değil, alt kümedir.
Tanım 5.2 (Kombinasyon) \(n\) farklı nesneden \(r\) tanesinin (\(0 \le r \le n\)) sıraya bakılmaksızın seçilmesine, yani \(n\) elemanlı bir kümenin \(r\) elemanlı bir alt kümesine, \(n\) nesnenin bir \(r\)-li kombinasyonu denir. Bu kombinasyonların sayısı \(C(n, r)\) ya da \(\binom{n}{r}\) ile gösterilir ve binom katsayısı diye adlandırılır.
\(a, b, c\) nesnelerinin \(2\)-li kombinasyonları \(\{a, b\}, \{a, c\}, \{b, c\}\) olmak üzere üç tanedir; \(2\)-li permütasyonların altı tanesi, her kombinasyonun iki biçimde sıralanmasıyla oluşur. Bu gözlem genel formülün ispatının ta kendisidir.
Teorem 5.2 (Kombinasyon Sayısı) \(0 \le r \le n\) için
\[C(n, r) = \binom{n}{r} = \frac{n!}{r!\,(n-r)!} = \frac{P(n, r)}{r!}\]
dir. Ayrıca \(\binom{n}{r} = \binom{n}{n-r}\) ve \(\binom{n}{0} = \binom{n}{n} = 1\)’dir.
İspat
\(n\) nesnenin her \(r\)-li permütasyonu iki adımda kurulabilir: önce hangi \(r\) nesnenin kullanılacağı seçilir (bir \(r\)-li kombinasyon; \(C(n, r)\) biçimde), sonra seçilen \(r\) nesne sıraya dizilir (\(P(r, r) = r!\) biçimde). Her permütasyon bu yolla tam bir kez elde edilir, çünkü bir permütasyon hem hangi nesnelerin kullanıldığını hem de sıralarını belirler. İkinci adımdaki seçenek sayısı birinci adımdaki seçimden bağımsız olduğundan çarpma kuralı (Önerme 5.2)
\[P(n, r) = r! \cdot C(n, r)\]
verir. Buradan Teorem 5.1 ile
\[C(n, r) = \frac{P(n, r)}{r!} = \frac{n!}{r!\,(n-r)!}\]
bulunur.
Simetri özelliği: \(r\) elemanlı bir alt küme seçmek, dışarıda bırakılacak \(n-r\) elemanı seçmekle aynı şeydir; alt kümeyi tümleyenine gönderen eşleme birebir ve örtendir. Öyleyse \(\binom{n}{r} = \binom{n}{n-r}\). Aynı sonuç formülden de okunur: \(r\) ile \(n-r\) yer değiştirince payda değişmez. \(r = 0\) için tek alt küme \(\varnothing\), \(r = n\) için tek alt küme kümenin kendisidir; formül de \(0! = 1\) ile \(1\) verir.
\(\blacksquare\)
Binom katsayılarının en önemli özdeşliği, binom teoreminin ispatında gereksinim duyacağımız Pascal özdeşliğidir. Bu özdeşliğin bir sayma yorumu vardır; ispatı da toplama kuralına dayanır.
Lemma 5.1 (Pascal Özdeşliği) \(1 \le r \le n\) için
\[\binom{n+1}{r} = \binom{n}{r-1} + \binom{n}{r}.\]
İspat
\(n+1\) elemanlı bir \(S\) kümesi ve bunun belirli bir \(x\) elemanı alalım. \(S\)’nin \(r\) elemanlı alt kümeleri iki ayrık sınıfa ayrılır: \(x\)’i içerenler ve içermeyenler. \(x\)’i içeren bir alt küme, \(S \setminus \{x\}\) kümesinden seçilen \(r-1\) elemanla belirlenir; \(S \setminus \{x\}\)’in \(n\) elemanı olduğundan bunlar \(\binom{n}{r-1}\) tanedir. \(x\)’i içermeyen bir alt küme, \(S \setminus \{x\}\)’in \(r\) elemanlı bir alt kümesidir; \(\binom{n}{r}\) tane. Toplama kuralı (Önerme 5.1) iki sayıyı toplar ve \(S\)’nin \(r\) elemanlı alt kümelerinin sayısı olan \(\binom{n+1}{r}\)’yi verir.
Cebirsel doğrulama da kısadır:
\[\binom{n}{r-1} + \binom{n}{r} = \frac{n!\,r}{r!\,(n-r+1)!} + \frac{n!\,(n-r+1)}{r!\,(n-r+1)!} = \frac{n!\,(n+1)}{r!\,(n+1-r)!} = \binom{n+1}{r}.\]
\(\blacksquare\)
5.4 Tekrarlı Permütasyon ve Çok Terimli Katsayı
Permütasyon formülü nesnelerin birbirinden farklı olduğunu varsayar. Oysa GAZİANTEP sözcüğünün harflerini sıralarken iki A harfi birbirinden ayırt edilemez; A’ların yerini değiştirmek yeni bir sözcük vermez. Bu tür sayımlar için formülü düzeltmek gerekir.
Teorem 5.3 (Tekrarlı Permütasyon (Çok Terimli Katsayı)) \(n\) nesnenin \(r_1\) tanesi birinci çeşitten, \(r_2\) tanesi ikinci çeşitten, …, \(r_k\) tanesi \(k\)-ıncı çeşitten olsun; \(r_1 + r_2 + \cdots + r_k = n\). Aynı çeşitten nesneler birbirinden ayırt edilmesin. Bu \(n\) nesnenin tümünün bir sıraya farklı dizilişlerinin sayısı
\[\binom{n}{r_1, r_2, \ldots, r_k} = \frac{n!}{r_1!\, r_2! \cdots r_k!}\]
dir. Bu sayıya çok terimli katsayı denir. \(k = 2\) için \(\binom{n}{r, n-r} = \binom{n}{r}\)’dir.
İspat
Aranan sayı \(N\) olsun. Aynı çeşitten nesneleri geçici olarak etiketleyip birbirinden ayırt edilir kılalım: birinci çeşitten nesnelere \(1, \ldots, r_1\), ikinci çeşittekilere \(1, \ldots, r_2\) etiketleri verilsin ve böyle devam edilsin. Artık \(n\) farklı nesne vardır ve Teorem 5.1 gereği bunların \(n!\) sıralanışı bulunur.
Etiketli sıralanışları şöyle de sayabiliriz: önce etiketsiz bir sıralanış seçilir (\(N\) biçimde); sonra bu sıralanışta birinci çeşidin kapladığı \(r_1\) yere etiketler dağıtılır (\(r_1!\) biçimde), ikinci çeşidin kapladığı \(r_2\) yere etiketler dağıtılır (\(r_2!\) biçimde), …, \(k\)-ıncı çeşidin \(r_k\) yerine etiketler dağıtılır (\(r_k!\) biçimde). Her etiketli sıralanış bu yolla tam bir kez elde edilir: etiketler silinince hangi etiketsiz sıralanıştan geldiği, silinmeden önce de her çeşit içinde etiketlerin nasıl dağıtıldığı bellidir. Çarpma kuralı (Önerme 5.2)
\[n! = N \cdot r_1!\, r_2! \cdots r_k!\]
verir; \(N\) çekilince istenen formül çıkar.
İkinci bir yol formülü kombinasyonlarla kurar. \(n\) yerden birinci çeşide ayrılacak \(r_1\) yer \(\binom{n}{r_1}\) biçimde seçilir; kalan \(n - r_1\) yerden ikinci çeşide ayrılacak \(r_2\) yer \(\binom{n - r_1}{r_2}\) biçimde seçilir; bu böyle sürer ve sonunda kalan \(r_k\) yer \(k\)-ıncı çeşide verilir. Çarpma kuralı ve Teorem 5.2 ile
\[\binom{n}{r_1}\binom{n-r_1}{r_2}\cdots\binom{r_k}{r_k} = \frac{n!}{r_1!\,(n-r_1)!}\cdot\frac{(n-r_1)!}{r_2!\,(n-r_1-r_2)!}\cdots\frac{r_k!}{r_k!\,0!} = \frac{n!}{r_1!\,r_2!\cdots r_k!};\]
ara faktöriyeller ikişer ikişer sadeleşir.
\(\blacksquare\)
Örnek 5.2 (GAZİANTEP Sözcüğünün Harfleri) (a) GAZİANTEP sözcüğündeki dokuz harfin tümü kullanılarak, anlamlı olup olmadığına bakılmaksızın, kaç farklı sözcük yazılabilir?
(b) Bu harflerden yedi tanesi kullanılarak kaç farklı yedi harfli sözcük yazılabilir?
Çözüm
GAZİANTEP sözcüğünde dokuz harf vardır: G, A, Z, İ, A, N, T, E, P. A harfi iki kez geçer; öteki yedi harf (G, Z, İ, N, T, E, P) birer kez geçer.
(a) Dokuz nesnenin ikisi aynı çeşittendir (A), kalan yedisi birer çeşittir. Teorem 5.3 ile
\[\frac{9!}{2!\,1!\,1!\,1!\,1!\,1!\,1!\,1!} = \frac{9!}{2!} = \frac{362880}{2} = 181440.\]
(b) Yedi harf seçilip sıralanacaktır. Harflerin tümü farklı olsaydı yanıt \(P(9, 7)\) olurdu; ama iki A birbirinden ayırt edilemediğinden, seçilen yedi harf arasında kaç A bulunduğuna göre durumları ayırmak gerekir. Üç durum birbirini dışlar; toplama kuralıyla (Önerme 5.1) toplanır.
İki A da kullanılır. Kalan beş harf, A dışındaki yedi farklı harften seçilir: \(\binom{7}{5} = 21\) biçimde. Seçilen yedi harfin ikisi özdeş olduğundan sıralanış sayısı \(\frac{7!}{2!} = 2520\)’dir. Bu durumdaki sözcük sayısı \(21 \cdot 2520 = 52920\).
Tam bir A kullanılır. A dışındaki yedi harften altısı seçilir: \(\binom{7}{6} = 7\) biçimde. Yedi harfin hepsi farklıdır: \(7! = 5040\) sıralanış. Bu durumdaki sözcük sayısı \(7 \cdot 5040 = 35280\).
Hiç A kullanılmaz. A dışındaki yedi harfin tümü alınır: \(\binom{7}{7} = 1\) biçimde; \(7! = 5040\) sıralanış. Bu durumdaki sözcük sayısı \(5040\).
Yedi harfli sözcüklerin sayısı
\[52920 + 35280 + 5040 = 93240\]
olur.
\(\blacksquare\)
Çok terimli katsayının ikinci yorumu, farklı nesneleri belirli büyüklükte gruplara ayırmaktır: \(n\) nesneyi, birincisinde \(r_1\), ikincisinde \(r_2\), … nesne olan \(k\) etiketli gruba bölmenin yollarının sayısı da \(\binom{n}{r_1, \ldots, r_k}\)’dir. Nesneleri sıraya dizip her birine grubunun etiketini yazınca bu yorum tekrarlı permütasyona dönüşür.
Örnek 5.3 (Sekiz Öğretmen, Dört Okul) (a) \(8\) öğretmen \(4\) okula kaç farklı biçimde yerleştirilebilir? Bir okula istenildiği kadar öğretmen verilebilir; bazı okullar boş kalabilir.
(b) Her okula tam \(2\) öğretmen düşecek biçimde kaç farklı dağıtım yapılabilir?
Çözüm
Öğretmenler de okullar da birbirinden farklıdır; bir dağıtım, her öğretmenin hangi okula gittiğini söyleyen bir listedir.
(a) Birinci öğretmen için \(4\) okul seçeneği vardır; ikinci öğretmen için de, birincinin seçiminden bağımsız olarak, \(4\) seçenek; bu böyle sürer ve sekizinci öğretmen için de \(4\) seçenek vardır. Çarpma kuralı (Önerme 5.2):
\[4 \cdot 4 \cdots 4 = 4^8 = 65536.\]
(b) Öğretmenleri \(1, \ldots, 8\) diye numaralayalım. Bir dağıtım, \(i\)-inci yerine \(i\)-inci öğretmenin okulunun numarası yazılmış sekiz uzunluğunda bir dizidir; her okula tam iki öğretmen düşeceğinden dizide \(1, 2, 3, 4\) etiketlerinin her biri tam iki kez geçer. Böyle dizilerin sayısı, dördü ikişerli dört çeşitten oluşan sekiz nesnenin tekrarlı permütasyon sayısıdır (Teorem 5.3):
\[\binom{8}{2, 2, 2, 2} = \frac{8!}{2!\,2!\,2!\,2!} = \frac{40320}{16} = 2520.\]
Aynı sonuç adım adım kombinasyonla da bulunur: birinci okulun iki öğretmeni \(\binom{8}{2} = 28\), ikincininki kalan altı kişiden \(\binom{6}{2} = 15\), üçüncününki \(\binom{4}{2} = 6\), dördüncününki \(\binom{2}{2} = 1\) biçimde seçilir; \(28 \cdot 15 \cdot 6 \cdot 1 = 2520\).
\(\blacksquare\)
5.5 Binom Teoremi
\(\binom{n}{r}\) sayılarına binom katsayısı denmesinin nedeni, \((a + x)^n\) açılımının katsayıları olmalarıdır. Bu teorem sayma dünyasıyla cebir dünyasını birbirine bağlar ve ileride binom dağılımının olasılıklarının toplamının \(1\) olduğunu göstermek için gerekecektir.
Teorem 5.4 (Binom Teoremi) \(n = 0, 1, 2, \ldots\) ve \(a, x \in \mathbb{R}\) (ya da \(\mathbb{C}\)) için
\[(a + x)^n = \sum_{r=0}^{n} \binom{n}{r} a^{n-r} x^r.\]
İspat
\(n\) üzerinde tümevarım yapalım. \(n = 0\) için iki taraf da \(1\)’dir; \(n = 1\) için sağ taraf \(\binom{1}{0} a + \binom{1}{1} x = a + x\) olur.
Eşitlik bir \(n \ge 1\) için doğru olsun. O zaman
\[(a+x)^{n+1} = (a+x)(a+x)^n = \sum_{r=0}^{n}\binom{n}{r}a^{n+1-r}x^r + \sum_{r=0}^{n}\binom{n}{r}a^{n-r}x^{r+1}.\]
İkinci toplamda \(s = r + 1\) yazalım:
\[\sum_{r=0}^{n}\binom{n}{r}a^{n-r}x^{r+1} = \sum_{s=1}^{n+1}\binom{n}{s-1}a^{n+1-s}x^{s}.\]
Birinci toplamın \(r = 0\) terimi \(a^{n+1}\), ikinci toplamın \(s = n+1\) terimi \(x^{n+1}\)’dir; geri kalan terimler \(1 \le r \le n\) için birleştirilir:
\[(a+x)^{n+1} = a^{n+1} + \sum_{r=1}^{n}\left[\binom{n}{r} + \binom{n}{r-1}\right]a^{n+1-r}x^r + x^{n+1}.\]
Pascal özdeşliği (Lemma 5.1) köşeli parantezi \(\binom{n+1}{r}\) yapar. \(\binom{n+1}{0} = \binom{n+1}{n+1} = 1\) olduğundan uç terimler de aynı biçime girer:
\[(a+x)^{n+1} = \sum_{r=0}^{n+1}\binom{n+1}{r}a^{n+1-r}x^r.\]
Bu, \(n + 1\) için istenen eşitliktir.
Aynı sonuç bir sayma yorumuyla da görülür. \((a+x)^n = (a+x)(a+x)\cdots(a+x)\) çarpımı açıldığında her terim, \(n\) çarpanın her birinden \(a\) ya da \(x\) seçilerek oluşur. \(x\)’in tam \(r\) çarpandan seçildiği terimlerin her biri \(a^{n-r}x^r\)’ye eşittir ve hangi \(r\) çarpandan seçileceği \(\binom{n}{r}\) biçimde belirlenir; katsayının \(\binom{n}{r}\) olmasının nedeni budur.
\(\blacksquare\)
\(a = x = 1\) alınırsa \(\sum_{r=0}^{n}\binom{n}{r} = 2^n\) çıkar: \(n\) elemanlı bir kümenin bütün alt kümelerinin sayısı \(2^n\)’dir; bu, \(|\mathcal{P}(\Omega)| = 2^{|\Omega|}\) eşitliğinin (Önerme 1.2) sayma ispatıdır. \(a = 1\), \(x = -1\) alınırsa \(\sum_{r=0}^{n}(-1)^r\binom{n}{r} = 0\) çıkar (\(n \ge 1\)): eleman sayısı çift olan alt kümelerin sayısı, eleman sayısı tek olan alt kümelerin sayısına eşittir; her ikisi de \(2^{n-1}\)’dir.
Binom katsayısının tanımındaki \(n\) yerine herhangi bir gerçel sayı konabilir; formüldeki çarpım yine anlamlıdır.
Tanım 5.3 (Genelleştirilmiş Binom Katsayısı) \(\alpha \in \mathbb{R}\) ve \(k = 1, 2, 3, \ldots\) için
\[\binom{\alpha}{k} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k!}, \qquad \binom{\alpha}{0} = 1\]
sayısına genelleştirilmiş binom katsayısı denir. \(\alpha = n\) negatif olmayan bir tam sayı olduğunda \(k \le n\) için bu sayı \(\binom{n}{k}\) ile çakışır; \(k > n\) için çarpanlardan biri (\(\alpha - n = 0\)) sıfır olduğundan \(\binom{n}{k} = 0\) olur.
\(\alpha \in \mathbb{R}\) ve \(|z| < 1\) olan her \(z \in \mathbb{C}\) için
\[(1 + z)^\alpha = \sum_{k=0}^{\infty}\binom{\alpha}{k}z^k\]
dir. Bu, \((1+z)^\alpha\) fonksiyonunun Taylor açılımıdır; ispatı analizin konusudur ve burada yalnızca ifadesi kullanılacaktır. \(|z| = 1\) üzerinde serinin yakınsaması \(\alpha\)’ya bağlıdır; \(|z| < 1\) için her zaman yakınsar. \(\alpha = n\) negatif olmayan bir tam sayı olduğunda \(k > n\) terimleri sıfırdır ve seri binom teoremine indirgenir. \(\alpha = -1\) için \(\binom{-1}{k} = (-1)^k\) olur ve seri geometrik seriye, \(\frac{1}{1+z} = \sum_{k=0}^{\infty}(-1)^k z^k\) eşitliğine döner. Genel olarak \(n \in \mathbb{N}\) için
\[\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}\]
dir (alıştırmalarda ispatlanacaktır); bu özdeşlik negatif binom dağılımının adının kaynağıdır.
5.6 Tekrarlı Kombinasyon: Yıldız–Çubuk Yöntemi
Kombinasyonda her nesne en çok bir kez seçilir. Ama bir pastaneden üç çeşit kurabiyeden yedi tane alırken aynı çeşitten birkaç tane alabiliriz; sıra önemsizdir, tekrar serbesttir. Aynı soru başka kılıklarda da karşımıza çıkar: \(x + y + z = 7\) denkleminin negatif olmayan tam sayı çözümlerini saymak, ya da \(7\) özdeş nesneyi \(3\) farklı kutuya dağıtmak. Üç sorunun yanıtı aynıdır ve zarif bir kodlamayla bulunur.
Teorem 5.5 (Tekrarlı Kombinasyon (Yıldız–Çubuk)) \(n \ge 1\) ve \(r \ge 0\) tam sayılar olsun.
(a) \(x_1 + x_2 + \cdots + x_n = r\) denkleminin negatif olmayan tam sayılardaki (\(x_i \in \{0, 1, 2, \ldots\}\)) çözümlerinin sayısı
\[\binom{n+r-1}{r} = \binom{n+r-1}{n-1}\]
dir. Bu sayı aynı zamanda \(n\) çeşit nesneden tekrara izin vererek \(r\) nesne seçmenin ve \(r\) özdeş nesneyi \(n\) farklı kutuya dağıtmanın yollarının sayısıdır.
(b) \(r \ge n\) ise aynı denklemin pozitif tam sayılardaki (\(x_i \ge 1\)) çözümlerinin sayısı \(\binom{r-1}{n-1}\)’dir.
İspat
(a) Bir \((x_1, \ldots, x_n)\) çözümünü şöyle kodlayalım: \(x_1\) tane yıldız, bir çubuk, \(x_2\) tane yıldız, bir çubuk, …, bir çubuk, \(x_n\) tane yıldız. Örneğin \(n = 3\), \(r = 7\) için \((2, 4, 1)\) çözümü
\[\star\star \mid \star\star\star\star \mid \star\]
dizisine, \((0, 7, 0)\) çözümü \(\mid \star\star\star\star\star\star\star \mid\) dizisine karşılık gelir. Dizide toplam \(r\) yıldız ve \(n - 1\) çubuk, yani \(n + r - 1\) simge vardır. Tersine, \(r\) yıldız ile \(n - 1\) çubuktan oluşan her dizi tam bir çözüm belirler: çubuklar diziyi \(n\) parçaya böler ve \(i\)-inci parçadaki yıldız sayısı \(x_i\)’dir; boş parça \(x_i = 0\) demektir. Öyleyse çözümler ile bu diziler arasında birebir ve örten bir eşleme vardır. Böyle bir dizi, \(n + r - 1\) yerden yıldızların konacağı \(r\) yeri seçmekle belirlenir; Teorem 5.2 ile \(\binom{n+r-1}{r}\) biçimde. Çubukların yerlerini seçmek de aynı şeydir: \(\binom{n+r-1}{n-1}\).
Öteki iki yorum doğrudan eşleşir: \(n\) çeşit nesneden tekrarlı \(r\) nesne seçmek, her çeşitten kaç tane alındığını (\(x_i\)) söylemektir; \(r\) özdeş nesneyi \(n\) kutuya dağıtmak, her kutuya kaç nesne düştüğünü söylemektir. İkisi de \(x_1 + \cdots + x_n = r\) denkleminin negatif olmayan çözümleriyle birebir eşleşir.
(b) \(x_i \ge 1\) koşulunu \(y_i = x_i - 1 \ge 0\) dönüşümüyle kaldıralım. \((x_1, \ldots, x_n)\) pozitif bir çözümse \((y_1, \ldots, y_n)\), \(y_1 + \cdots + y_n = r - n\) denkleminin negatif olmayan bir çözümüdür; tersine her böyle \((y_i)\) dizisi \(x_i = y_i + 1\) ile pozitif bir çözüm verir. Eşleme birebir ve örtendir. (a) şıkkıyla sayı
\[\binom{n + (r-n) - 1}{n-1} = \binom{r-1}{n-1}\]
olur.
\(\blacksquare\)
Örnek 5.4 (Bir Denklemin Çözüm Sayısı) \(x, y, z \in \{0, 1, 2, \ldots\}\) olmak üzere \(x + y + z = 7\) denkleminin kaç farklı çözümü vardır? Çözümler pozitif tam sayılarla sınırlanırsa sayı ne olur?
Çözüm
\(n = 3\) bilinmeyen, toplam \(r = 7\). Teorem 5.5 (a) ile
\[\binom{3+7-1}{7} = \binom{9}{7} = \binom{9}{2} = \frac{9 \cdot 8}{2} = 36.\]
Doğrudan sayarak doğrulayalım: \(x = k\) sabitlenince \(y + z = 7 - k\) denkleminin \(8 - k\) çözümü vardır (\(y = 0, 1, \ldots, 7 - k\) ve \(z\) buna göre belirlenir). \(k = 0, 1, \ldots, 7\) üzerinden toplam \(8 + 7 + \cdots + 1 = 36\).
Pozitif çözümler için (b) şıkkı: \(\binom{7-1}{3-1} = \binom{6}{2} = 15\).
\(\blacksquare\)
Örnek 5.5 (Sekiz Özdeş Beyaz Tahta) (a) \(8\) özdeş beyaz tahta \(4\) okul arasında kaç farklı biçimde paylaştırılabilir? Bir okul hiç tahta almayabilir.
(b) Her okul en az bir tahta alacaksa kaç paylaştırma vardır?
Çözüm
Tahtalar özdeş olduğundan bir paylaştırma yalnızca her okula kaç tahta düştüğüyle, yani \(x_1 + x_2 + x_3 + x_4 = 8\) denkleminin bir çözümüyle belirlenir. Bu, öğretmen örneğinden (Örnek 5.3) temel bir farktır: orada öğretmenler birbirinden farklıydı ve kimin nereye gittiği önemliydi.
(a) Negatif olmayan çözümler (Teorem 5.5):
\[\binom{4+8-1}{8} = \binom{11}{8} = \binom{11}{3} = \frac{11 \cdot 10 \cdot 9}{6} = 165.\]
(b) Pozitif çözümler: \(\binom{8-1}{4-1} = \binom{7}{3} = 35\). Aynı sonuç şöyle de görülür: önce her okula birer tahta verilir, kalan \(4\) özdeş tahta \(4\) okula serbestçe dağıtılır: \(\binom{4+4-1}{4} = \binom{7}{4} = 35\).
\(\blacksquare\)
Bir sayma sorusunda iki şey sorulur: sıra önemli mi ve tekrar var mı. \(n\) farklı nesneden \(r\) tanesi için yanıtlar şöyle özetlenir:
| sıra önemli | sıra önemsiz | |
|---|---|---|
| tekrarsız | \(P(n, r) = \dfrac{n!}{(n-r)!}\) | \(\dbinom{n}{r}\) |
| tekrarlı | \(n^r\) | \(\dbinom{n+r-1}{r}\) |
Sol alt hücre çarpma kuralının doğrudan sonucudur: \(r\) yerin her biri için \(n\) seçenek vardır (öğretmen örneğindeki \(4^8\) gibi). Nesnelerin bir kısmı özdeşse ve tümü sıralanıyorsa tekrarlı permütasyon (Teorem 5.3) devreye girer. Üçüncü bir soru, nesnelerin ayırt edilip edilmediğidir; aşağıdaki iki örnek, bu soruya verilen yanıtın sonucu nasıl değiştirdiğini gösterir.
5.7 Karma Sayma Problemleri
Gerçek problemlerde kurallar tek başına değil, birlikte kullanılır: durumlar toplama kuralıyla ayrılır, her durum çarpma kuralı ve kombinasyon formülleriyle sayılır. Ayrıca sorunun hangi düzenlemeleri “farklı” saydığı, yani varsayımlar, sayımdan önce açıkça belirlenmelidir.
Örnek 5.6 (Yedi Siyah ve Yedi Beyaz Top) \(7\) siyah ve \(7\) beyaz top, her kutuda ikişer top olacak biçimde \(7\) kutuya kaç farklı biçimde dağıtılabilir? Kutular birbirinden farklı (numaralı), aynı renkli toplar özdeş kabul edilecektir.
Çözüm
Varsayımlar sayımı belirler: kutular numaralı olduğundan hangi kutuda ne olduğu önemlidir; aynı renkli toplar özdeş olduğundan bir kutunun içeriği yalnızca renk bileşimiyle belirlenir. Her kutuda iki top olacağından bir kutunun içeriği üç türden biridir: iki siyah (SS), bir siyah bir beyaz (SB), iki beyaz (BB).
Bir dağıtım, \(i\)-inci kutudaki siyah top sayısı \(s_i \in \{0, 1, 2\}\) olmak üzere \((s_1, \ldots, s_7)\) dizisiyle belirlenir; kutudaki beyaz sayısı \(2 - s_i\) olarak kendiliğinden bulunur. Toplam siyah sayısı \(7\) olmalıdır: \(s_1 + \cdots + s_7 = 7\). Bu durumda toplam beyaz sayısı \(14 - 7 = 7\) olur; ikinci koşul kendiliğinden sağlanır.
SS kutularının sayısı \(a\), SB kutularının sayısı \(b\), BB kutularının sayısı \(c\) olsun. O zaman
\[a + b + c = 7, \qquad 2a + b = 7.\]
İkinci denklemden \(b = 7 - 2a\), birinciden \(c = 7 - a - b = a\) çıkar. \(b \ge 0\) olması için \(a \le 3\) gerekir; olası \((a, b, c)\) üçlüleri
\[(0, 7, 0), \quad (1, 5, 1), \quad (2, 3, 2), \quad (3, 1, 3)\]
dir. Her üçlü için hangi kutuların SS, hangilerinin SB, hangilerinin BB olacağını seçmek gerekir; bu, \(7\) kutunun \(a\), \(b\), \(c\) tane olacak biçimde üç çeşide ayrılmasıdır ve Teorem 5.3 ile \(\frac{7!}{a!\,b!\,c!}\) biçimde yapılır:
| \((a, b, c)\) | dağıtım sayısı |
|---|---|
| \((0, 7, 0)\) | \(\dfrac{7!}{0!\,7!\,0!} = 1\) |
| \((1, 5, 1)\) | \(\dfrac{7!}{1!\,5!\,1!} = 42\) |
| \((2, 3, 2)\) | \(\dfrac{7!}{2!\,3!\,2!} = 210\) |
| \((3, 1, 3)\) | \(\dfrac{7!}{3!\,1!\,3!} = 140\) |
Dört durum birbirini dışlar; toplama kuralıyla
\[1 + 42 + 210 + 140 = 393\]
farklı dağıtım vardır.
Varsayım değişirse sonuç değişir. \(14\) topun tümü birbirinden farklı (örneğin numaralı) sayılsaydı, \(14\) topu \(7\) numaralı kutuya ikişer ikişer dağıtmanın sayısı Teorem 5.3 ile \(\frac{14!}{(2!)^7} = 681080400\) olurdu.
\(\blacksquare\)
Örnek 5.7 (Safari Turu) \(9\) kişi, kapasiteleri \(2\), \(4\) ve \(5\) yolcu olan \(3\) araçla safari turuna çıkacaktır ve bütün araçlar kullanılacaktır. \(9\) kişi araçlara kaç farklı biçimde dağılabilir? Şu varsayımlarla çözünüz: kişiler ve araçlar birbirinden farklıdır; bir araç içindeki koltuklar ayırt edilmez, yalnızca kimin hangi araçta olduğu önemlidir; “bütün araçlar kullanılacak” demek her araçta en az bir kişi bulunacak demektir.
Çözüm
Toplam kapasite \(2 + 4 + 5 = 11\) olduğundan iki koltuk boş kalacaktır. Araçlardaki kişi sayıları \((n_1, n_2, n_3)\) olsun;
\[n_1 + n_2 + n_3 = 9, \qquad 1 \le n_1 \le 2, \quad 1 \le n_2 \le 4, \quad 1 \le n_3 \le 5.\]
\(n_1 = 2\) ise \(n_2 + n_3 = 7\) olmalıdır: \((n_2, n_3) \in \{(2, 5), (3, 4), (4, 3)\}\). \(n_1 = 1\) ise \(n_2 + n_3 = 8\): \((n_2, n_3) \in \{(3, 5), (4, 4)\}\). \(n_1 = 0\) birinci aracı boş bırakacağından dışlanır. Beş dağılım biçimi vardır.
Belirli bir \((n_1, n_2, n_3)\) için \(9\) kişiyi araçlara ayırmak, \(9\) kişiyi \(n_1\), \(n_2\), \(n_3\) kişilik üç etiketli gruba bölmektir; Teorem 5.3 ile \(\frac{9!}{n_1!\,n_2!\,n_3!}\) biçimde yapılır:
| \((n_1, n_2, n_3)\) | yol sayısı |
|---|---|
| \((2, 2, 5)\) | \(\dfrac{9!}{2!\,2!\,5!} = 756\) |
| \((2, 3, 4)\) | \(\dfrac{9!}{2!\,3!\,4!} = 1260\) |
| \((2, 4, 3)\) | \(\dfrac{9!}{2!\,4!\,3!} = 1260\) |
| \((1, 3, 5)\) | \(\dfrac{9!}{1!\,3!\,5!} = 504\) |
| \((1, 4, 4)\) | \(\dfrac{9!}{1!\,4!\,4!} = 630\) |
Durumlar birbirini dışladığından toplama kuralıyla
\[756 + 1260 + 1260 + 504 + 630 = 4410\]
farklı yol vardır.
Varsayımların etkisi: “Her araçta en az bir kişi” koşulu kaldırılsaydı \((0, 4, 5)\) durumu da eklenir (\(\frac{9!}{4!\,5!} = 126\)) ve toplam \(4536\) olurdu. Koltuklar da ayırt edilseydi \(11\) farklı koltuğa \(9\) kişi \(P(11, 9) = \frac{11!}{2!} = 19958400\) biçimde oturur; bunlardan birinci aracı boş bırakanlar (iki boş koltuğun ikisi de birinci araçtadır ve \(9\) kişi kalan \(9\) koltuğa \(9! = 362880\) biçimde oturur) çıkarılınca \(19595520\) bulunurdu. Hangi sayının doğru olduğu, sorunun hangi düzenlemeleri farklı saydığına bağlıdır; bu yüzden varsayımlar baştan söylenmelidir.
\(\blacksquare\)
5.8 Laplace Uzayında Olasılık Hesapları
Sayma araçları hazır olduğuna göre bölümün başındaki amaca dönebiliriz. Laplace uzayında (Tanım 4.1) bir olayın olasılığı, olayın ve örnek uzayın eleman sayılarının oranıdır (Önerme 4.2); iki sayı da artık bu bölümün formülleriyle bulunur. Dikkat edilecek tek nokta, örnek uzayı bütün sonuçları eşit olasılıklı kılacak biçimde seçmektir: iki zarın toplamını sayarken \(\{2, \ldots, 12\}\) kümesi eşit olasılıklı değildir, ama sıralı ikililerin kümesi eşit olasılıklıdır.
Örnek 5.8 (Sayma ile Olasılık Hesapları) (a) İki zar atılıyor. Üste gelen sayıların toplamının \(7\) olma olasılığı nedir?
(b) \(10\) kişilik bir topluluktan rastgele \(5\) kişilik bir komite seçiliyor. Topluluktaki belirli iki kişinin ikisinin de komitede olma olasılığı nedir? Yalnızca birinin komitede olma olasılığı? Hiçbirinin olmama olasılığı?
(c) (Doğum günü problemi) Bir odada \(n\) kişi vardır. Yılın \(365\) günü olduğunu ve \(n\) kişinin doğum günlerinden oluşan \(365^n\) sıralı listenin her birinin eşit olasılıklı olduğunu varsayalım. En az iki kişinin doğum gününün aynı olma olasılığını bulunuz; \(n = 23\) için hesaplayınız.
Çözüm
Üç deneyde de sonuçlar sonlu ve eşit olasılıklıdır; Laplace formülü (Önerme 4.2) \(P(A) = |A| / |\Omega|\) kullanılır.
(a) \(\Omega = \{(i, j) : i, j \in \{1, \ldots, 6\}\}\); çarpma kuralıyla \(|\Omega| = 6 \cdot 6 = 36\) ve zarlar hilesizse her sıralı ikili eşit olasılıklıdır. Toplamı \(7\) yapan ikililer
\[(1, 6),\ (2, 5),\ (3, 4),\ (4, 3),\ (5, 2),\ (6, 1)\]
olmak üzere altı tanedir. Öyleyse
\[P(\text{toplam } 7) = \frac{6}{36} = \frac{1}{6}.\]
(b) \(\Omega\), \(10\) kişinin \(5\) elemanlı alt kümelerinin kümesidir: \(|\Omega| = \binom{10}{5} = 252\); rastgele seçim her alt kümeyi eşit olasılıklı kılar. Belirli iki kişiye A ve B diyelim.
İkisi de komitede. A ve B komitede olduğuna göre kalan \(3\) üye öteki \(8\) kişiden seçilir: \(\binom{8}{3} = 56\) komite. Olasılık \(\frac{56}{252} = \frac{2}{9}\).
Yalnızca biri komitede. A’nın olup B’nin olmadığı komitelerde A alınır, kalan \(4\) üye B dışındaki \(8\) kişiden seçilir: \(\binom{8}{4} = 70\). B’nin olup A’nın olmadığı komiteler de \(70\) tanedir. İki durum ayrık olduğundan toplama kuralıyla \(140\) komite; olasılık \(\frac{140}{252} = \frac{5}{9}\).
Hiçbiri komitede değil. \(5\) üyenin tümü öteki \(8\) kişiden seçilir: \(\binom{8}{5} = 56\); olasılık \(\frac{56}{252} = \frac{2}{9}\).
Sağlama: \(\frac{2}{9} + \frac{5}{9} + \frac{2}{9} = 1\); üç olay \(\Omega\)’nın bir parçalanışıdır.
(c) \(\Omega\), \(n\) kişinin doğum günlerinin sıralı listelerinin kümesidir: \(\Omega = \{1, \ldots, 365\}^n\) ve çarpma kuralıyla \(|\Omega| = 365^n\); varsayım gereği her liste eşit olasılıklıdır. \(A\), en az iki kişinin doğum gününün aynı olması olayı olsun. Doğrudan saymak zordur; tümleyeni saymak kolaydır. \(A^c\), bütün doğum günlerinin farklı olması olayıdır ve eleman sayısı \(365\) günden \(n\) tanesinin sıralı seçimidir: \(P(365, n) = 365 \cdot 364 \cdots (365 - n + 1)\). Teorem 3.1 ile
\[P(A) = 1 - P(A^c) = 1 - \frac{365 \cdot 364 \cdots (365 - n + 1)}{365^n} = 1 - \prod_{i=0}^{n-1}\left(1 - \frac{i}{365}\right).\]
\(n > 365\) için \(365 \cdot 364 \cdots (365 - n + 1)\) çarpımında \(365 - 365 = 0\) çarpanı yer aldığından pay sıfırdır ve \(P(A) = 1\) olur: \(366\) kişi arasında çakışma kesindir. \(n = 23\) için çarpım \(0{,}4927\) verir; dolayısıyla
\[P(A) \approx 1 - 0{,}4927 = 0{,}5073.\]
Yani yalnızca \(23\) kişilik bir odada en az iki kişinin doğum gününün çakışması, çakışmamasından daha olasıdır. Birkaç değer daha: \(n = 10\) için \(P(A) \approx 0{,}117\); \(n = 30\) için \(0{,}706\); \(n = 50\) için \(0{,}970\).
\(\blacksquare\)
Laplace formülü ancak \(\Omega\)’nın her noktası eşit olasılıklıysa geçerlidir. (a) şıkkında “toplam \(7\) olur ya da olmaz, iki sonuç, olasılık \(\frac{1}{2}\)” demek yanlıştır; iki sonuç eşit olasılıklı değildir. Aynı biçimde (b) şıkkında komiteleri sıralı \(5\)-liler olarak da sayabilirdik (\(|\Omega| = P(10, 5) = 30240\)); pay da sıralı sayıldığı sürece (\(P(5,2) \cdot P(8,3)\) türünden) oran değişmez. Önemli olan, pay ile paydanın aynı türden nesneleri saymasıdır.
5.9 Alıştırmalar
Alıştırma 5.1 (Sayma Teknikleri) (a) \(5\) kişi bir sıraya kaç farklı biçimde oturabilir? Belirli iki kişinin yan yana oturduğu diziliş sayısı kaçtır?
(b) MATEMATİK sözcüğünün harflerinin tümü kullanılarak kaç farklı sözcük yazılabilir?
(c) \(x_1 + x_2 + x_3 + x_4 = 10\) denkleminin negatif olmayan tam sayı çözümlerinin sayısını bulunuz. Her \(x_i \ge 2\) koşulu altında çözüm sayısı kaçtır?
(d) \((2x - y)^5\) açılımında \(x^2 y^3\) teriminin katsayısını bulunuz.
(e) Bir torbada \(5\) kırmızı, \(4\) mavi top vardır; rastgele \(3\) top çekiliyor. Üçünün de kırmızı olma olasılığı ile tam ikisinin kırmızı olma olasılığını bulunuz.
(f) Üç zar atılıyor. Üç zarın da farklı sayı gösterme olasılığı nedir?
(g) \(\binom{-2}{3}\) ve \(\binom{1/2}{2}\) genelleştirilmiş binom katsayılarını hesaplayınız; \(n \in \mathbb{N}\) için \(\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}\) eşitliğini gösteriniz.
Çözüm
(a) \(5! = 120\) diziliş vardır (Teorem 5.1). Yan yana oturacak iki kişiyi tek bir blok sayalım: \(4\) nesne (\(3\) kişi ve blok) \(4! = 24\) biçimde dizilir, blok içinde iki kişi \(2! = 2\) biçimde sıralanır; çarpma kuralıyla \(24 \cdot 2 = 48\).
(b) MATEMATİK dokuz harflidir: M, A, T ikişer kez; E, İ, K birer kez. Teorem 5.3 ile \(\frac{9!}{2!\,2!\,2!} = \frac{362880}{8} = 45360\).
(c) Teorem 5.5 (a) ile \(\binom{4+10-1}{10} = \binom{13}{3} = 286\). \(x_i \ge 2\) koşulu için \(y_i = x_i - 2 \ge 0\) konursa \(y_1 + y_2 + y_3 + y_4 = 2\) denklemi elde edilir: \(\binom{4+2-1}{2} = \binom{5}{2} = 10\).
(d) Binom teoremi (Teorem 5.4) ile \((2x - y)^5 = \sum_{r=0}^{5}\binom{5}{r}(2x)^{5-r}(-y)^r\). \(x^2 y^3\) terimi \(r = 3\)’e karşılık gelir: \(\binom{5}{3} \cdot 2^2 \cdot (-1)^3 = 10 \cdot 4 \cdot (-1) = -40\).
(e) \(|\Omega| = \binom{9}{3} = 84\). Üçü kırmızı: \(\binom{5}{3} = 10\) çekiliş, olasılık \(\frac{10}{84} = \frac{5}{42}\). Tam ikisi kırmızı: iki kırmızı \(\binom{5}{2} = 10\), bir mavi \(\binom{4}{1} = 4\) biçimde seçilir; çarpma kuralıyla \(40\) çekiliş, olasılık \(\frac{40}{84} = \frac{10}{21}\).
(f) \(|\Omega| = 6^3 = 216\). Üçü farklı: birinci zar için \(6\), ikincisi için \(5\), üçüncüsü için \(4\) değer, \(P(6, 3) = 120\); olasılık \(\frac{120}{216} = \frac{5}{9}\).
(g) \(\binom{-2}{3} = \frac{(-2)(-3)(-4)}{3!} = \frac{-24}{6} = -4\) ve \(\binom{1/2}{2} = \frac{\frac{1}{2}\left(-\frac{1}{2}\right)}{2!} = -\frac{1}{8}\). Genel olarak paydaki \(k\) çarpanın her birinden \(-1\) dışarı alınır:
\[\binom{-n}{k} = \frac{(-n)(-n-1)\cdots(-n-k+1)}{k!} = (-1)^k\frac{n(n+1)\cdots(n+k-1)}{k!} = (-1)^k\frac{(n+k-1)!}{k!\,(n-1)!} = (-1)^k\binom{n+k-1}{k}.\]
\(\blacksquare\)
Sayma araçları elimizde olduğuna göre, bir olayın gerçekleştiği bilgisinin öteki olayların olasılığını nasıl değiştirdiğine geçebiliriz: Koşullu Olasılık, Toplam Olasılık ve Bayes Teoremi.