Kombinasyon Tanımı
\( n \) elemanlı bir \( A \) kümesinin elemanları arasından bir sıra gözetmeksizin \( r \) elemanın seçim işlemine kombinasyon denir. Permütasyon işleminde elemanların dizilişi önemliyken kombinasyonda diziliş önemli değildir.
\( n \) elemanlı bir kümenin \( r \) elemanlı kombinasyonu \( C(n, r) \) ya da \( \binom{n}{r} \) ile gösterilir ve aşağıdaki formülle hesaplanır.
\( n, r \in \mathbb{N}, \quad r \le n \) olmak üzere,
\( C(n, r) = \binom{n}{r} = \dfrac{n!}{r!\ (n - r)!} \)
\( A = \{ \text{Eda}, \text{Ela}, \text{Can}, \text{Cem} \} \) olmak üzere,
\( A \) kümesinin 2'li kombinasyonları:
\( C(4, 2) = \dfrac{4!}{2!\ (4 - 2)!} = 6 \)
\( A \) kümesinin 2 elemanlı alt kümeleri:
\( \{\text{Eda}, \text{Ela}\}, \{\text{Eda}, \text{Can}\} \)
\( \{\text{Eda}, \text{Cem}\}, \{\text{Ela}, \text{Can}\} \)
\( \{\text{Ela}, \text{Cem}\}, \{\text{Can}, \text{Cem}\} \)
\( A \) kümesinin 3'lü kombinasyonları:
\( C(4, 3) = \dfrac{4!}{3!\ (4 - 3)!} = 4 \)
\( A \) kümesinin 3 elemanlı alt kümeleri:
\( \{\text{Eda}, \text{Ela}, \text{Can}\}, \{\text{Eda}, \text{Ela}, \text{Cem}\} \)
\( \{\text{Eda}, \text{Can}, \text{Cem}\}, \{\text{Ela}, \text{Can}, \text{Cem}\} \)
Kombinasyonda seçilen elemanların sırası önemli olmadığı için, yukarıdaki 2'li kombinasyonlarda \( \{\text{Eda}, \text{Ela}\} \) seçimine ek olarak \( \{\text{Ela}, \text{Eda}\} \) kümesinin seçime dahil edilmesine gerek yoktur.
Pratik bir yol olarak, \( n \)'nin \( r \)'li kombinasyonunu hesaplamak için paya \( n \)'den başlayarak ve birer eksilterek \( r \) sayının çarpımı yazılır (son sayının faktöriyeli alınmaz), paydaya da \( r \) faktöriyelin açılımı yazılır.
\( C(12, 4) = \dfrac{\overbrace{12 \cdot 11 \cdot 10 \cdot 9}^\text{4 kez}}{\underbrace{4 \cdot 3 \cdot 2 \cdot 1}_\text{4!}} = 495 \)
\( C(6, 2) - C(5, 3) + C(4, 1) \) işleminin sonucu kaçtır?
Çözümü Göster\( \dfrac{6!}{2!\ (6 - 2)!} - \dfrac{5!}{3!\ (5 - 3)!} + \dfrac{4!}{1!\ (4 - 1)!} \)
\( = \dfrac{6 \cdot 5}{2 \cdot 1} - \dfrac{5 \cdot 4 \cdot 3}{3 \cdot 2 \cdot 1} + \dfrac{4}{1} \)
\( = 15 - 10 + 4 = 9 \) bulunur.
\( n \gt 0 \) olmak üzere,
\( \binom{n}{2} + \binom{n}{1} = 3(n + 1) \) olduğuna göre, \( n \) kaçtır?
Çözümü Göster\( \dfrac{n!}{2!\ (n - 2)!} + \dfrac{n!}{1!\ (n - 1)!} = 3(n + 1) \)
\( \dfrac{n(n - 1)}{2} + \dfrac{n}{1} = 3n + 3 \)
\( \dfrac{n^2 - n}{2} + n = 3n + 3 \)
\( n^2 + n = 6n + 6 \)
\( n^2 - 5n - 6 = 0 \)
\( (n + 1)(n - 6) = 0 \)
\( n \) pozitif olduğu için \( n = 6 \) bulunur.
Kombinasyon İşlem Kuralları
0 ve 1'in faktöriyel değerleri 1'dir.
\( 0! = 1! = 1 \)
\( n \lt r \) olduğu durumda \( C(n, r) \) sıfıra eşittir. Bu durum 3 elamanlı bir kümenin 5 elemanlı alt kümelerinin sayısı sıfırdır ya da 3 kişilik bir grup içinden 5 kişi sıfır farklı şekilde seçilebilir şeklinde yorumlanabilir.
\( n \lt r \) olmak üzere,
\( C(n, r) = 0 \)
\( C(3, 5) = 0 \)
\( r \gt 0 \) olmak üzere, \( C(0, r) \) sıfıra eşittir. Bu durum boş kümenin 3 elemanlı alt kümelerinin sayısı sıfırdır ya da boş bir sınıftan 3 kişi sıfır farklı şekilde seçilebilir şeklinde yorumlanabilir.
\( r \gt 0 \) olmak üzere,
\( C(0, r) = 0 \)
\( C(0, 3) = 0 \)
\( C(0, 0) \) 1'e eşittir. Bu durum boş kümenin boş küme olan alt küme sayısı 1'dir şeklinde yorumlanabilir.
\( C(0, 0) = 1 \)
\( n \) elemanlı bir kümenin \( 0 \)'lı ve \( n \)'li kombinasyonları 1'e eşittir. \( n \) elemanlı bir küme içinden seçilebilecek 0 elemanlı tek alt küme boş küme, \( n \) elemanlı tek alt küme kümenin kendisidir.
\( C(n, 0) = \dfrac{n!}{0!\ n!} = 1 \)
\( C(n, n) = \dfrac{n!}{n!\ (n - n)!} = 1 \)
\( A = \{ a, b, c, d, e \} \) olmak üzere,
\( C(5, 0) = \dfrac{5!}{0!\ (5 - 0)!} \) \( = 1 \)
\( A \)'nın 0'lı kombinasyonu: \( \emptyset \)
\( C(5, 5) = \dfrac{5!}{5!\ (5 - 5)!} \) \( = 1 \)
\( A \)'nın 5'li kombinasyonu: \( \{a, b, c, d, e\} \)
\( n \) elemanlı bir kümenin \( 1 \)'li ve \( (n - 1) \)'li kombinasyonları \( n \)'ye eşittir. \( n \) elemanlı bir küme içinden seçilebilecek 1 elemanlı alt kümelerin her biri kümenin tek bir elemanını içerir. \( n \) elemanlı bir küme içinden seçilebilecek \( (n - 1) \) elemanlı alt kümeler kümenin kendisinden sırayla tek bir elemanın çıkartıldığı alt kümelerdir.
\( C(n, 1) = \dfrac{n!}{1!\ (n - 1)!} = n \)
\( C(n, n - 1) = \dfrac{n!}{(n - 1)!\ 1!} = n \)
\( C(5, 1) = \dfrac{5!}{1!\ (5 - 1)!} \) \( = \dfrac{5!}{1!\ 4!} = 5 \)
\( A \)'nın 1'li kombinasyonları: \( \{a\}, \{b\}, \{c\}, \{d\}, \{e\} \)
\( C(5, 4) = \dfrac{5!}{4!\ (5 - 4)!} \) \( = \dfrac{5!}{4!\ 1!} = 5 \)
\( A \)'nın 4'lü kombinasyonları: \( \{a, b, c, d\}, \{a, b, c, e\}, \) \( \{a, b, d, e\}, \{a, c, d, e\}, \) \( \{b, c, d, e\} \)
Yukarıdaki iki kuralın bir uzantısı olarak, \( n \) elemanlı bir kümenin \( r \)'li ve \( (n - r) \)'li kombinasyonları birbirine eşittir.
\( C(n, r) = C(n, n - r) \) \( = \dfrac{n!}{r!\ (n - r)!} \)
\( C(100, 60) = C(100, 40) \)
\( C(1000, 5) = C(1000, 995) \)
Bir diğer ifadeyle, \( n \) elemanlı bir kümenin \( r \)'li ve \( k \)'lı kombinasyonları birbirine eşitse bu sayılar ya birbirine eşittir ya da toplamları \( n \)'ye eşittir.
\( r \le n, \quad k \le n \) olmak üzere,
\( C(n, r) = C(n, k) \) ise,
\( r = k \) veya \( r + k = n \)
\( C(8, 3) = C(8, k) \) ise,
\( k = 3 \) ya da \( k = 5 \)
Pascal Formülü
Pascal üçgeni konusunda görsel olarak da göreceğimiz aşağıdaki kuralı burada formül olarak paylaşıyoruz.
\( C(n, r) + C(n, r + 1) = C(n + 1, r + 1) \)
\( \binom{n}{r} + \binom{n}{r + 1} = \binom{n + 1}{r + 1} \)
\( C(8, 3) + C(8, 4) = C(9, 4) \)
İSPATI GÖSTER
\( C(n, r) + C(n, r + 1) = \dfrac{n!}{r!\ (n - r)!} + \dfrac{n!}{(r + 1)!\ (n - r - 1)!} \)
Paydaları eşitlemek için birinci kesri \( (r + 1) \) ile, ikinci kesri \( (n - r) \) ile genişletelim.
\( = \dfrac{n!\ (r + 1)}{r!\ (r + 1)\ (n - r)!} + \dfrac{n!\ (n - r)}{(r + 1)!\ (n - r - 1)!\ (n - r)} \)
Paydalardaki yeni çarpanları faktöriyellere dahil edelim.
\( = \dfrac{n!\ (r + 1)}{(r + 1)!\ (n - r)!} + \dfrac{n!\ (n - r)}{(r + 1)!\ (n - r )!} \)
Paylardaki çarpanları parantez içlerine dağıtalım.
\( = \dfrac{n!\ r + n! + n!\ n - n!\ r}{(r + 1)!\ (n - r)!} \)
\( = \dfrac{n!\ (n + 1)}{(r + 1)!\ (n - r)!} \)
\( = \dfrac{(n + 1)!}{(r + 1)!\ (n - r)!} \)
Yukarıdaki ifade \( (n + 1) \)'in \( (r + 1) \)'li kombinasyonuna eşittir.
\( = C(n + 1, r + 1) \)
\( C(n, n - 1) + 2C(n, n - 2) = 100 \) eşitliğini sağlayan \( n \) doğal sayısı kaçtır?
Çözümü Göster\( C(n, k) = C(n, n - k) \) olduğu için aşağıdaki iki özdeşliği yazabiliriz.
\( C(n, n - 1) = C(n, 1) \)
\( C(n, n - 2) = C(n, 2) \)
Bu iki değeri soruda verilen eşitlikte yerine koyalım.
\( C(n, 1) + 2C(n, 2) = 100 \)
\( n + 2 \cdot \dfrac{n(n - 1)}{2} = 100 \)
\( n + n(n - 1) = 100 \)
\( n + n^2 - n = 100 \)
\( n^2 = 100 \)
\( n \) doğal sayı olduğu için \( n = 10 \) olur.
\( \binom{10}{x + 3} = \binom{10}{2x - 2} \) denklemini sağlayan \( x \) değerlerinin toplamı kaçtır?
Çözümü Göster\( C(n, r) = C(n, k) \) şeklindeki bir eşitlik \( r = k \) ya da \( r + k = n \) olduğunda sağlanır.
Buna göre verilen eşitlik iki şekilde sağlanır.
Durum 1: \( r = k \)
\( x + 3 = 2x - 2 \)
\( x = 5 \)
Durum 2: \( r + k = n \)
\( (x + 3) + (2x - 2) = 10 \)
\( 3x + 1 = 10 \)
\( x = 3 \)
Buna göre \( x \)'in alabileceği değerler toplamı \( 5 + 3 = 8 \) olur.
\( \binom{79}{a^2 + 1} - \binom{79}{a + 6} = \binom{79}{a + 7} - \binom{79}{a^2} \) olduğuna göre,
\( a \)'nın alabileceği tam sayı değerlerin toplamı kaçtır?
Çözümü GösterVerilen eşitliği aşağıdaki özdeşliğe benzetmeye çalışalım.
\( \binom{n}{r} + \binom{n}{r + 1} = \binom{n + 1}{r + 1} \)
Negatif işaretli terimleri eşitliğin karşı tarafına atalım.
\( \binom{79}{a^2} + \binom{79}{a^2 + 1} = \binom{79}{a + 6} + \binom{79}{a + 7} \)
Yukarıdaki özdeşliği kullanalım.
\( \binom{80}{a^2 + 1} = \binom{80}{a + 7} \)
\( C(n, r) = C(n, k) \) şeklindeki bir eşitlik \( r = k \) ya da \( r + k = n \) olduğunda sağlanır.
Buna göre verilen eşitlik iki şekilde sağlanır.
Durum 1: \( r = k \)
\( a^2 + 1 = a + 7 \)
\( a^2 - a - 6 = 0 \)
\( (a - 3)(a + 2) = 0 \)
\( a = 3 \) veya \( a = -2 \)
İki değeri de yerine koyduğumuzda bir tanımsızlık oluşmaz, dolayısıyla iki değer de geçerli birer çözümdür.
Durum 2: \( r + k = n \)
\( (a^2 + 1) + (a + 7) = 80 \)
\( a^2 + a - 72 = 0 \)
\( (a + 9)(a - 8) = 0 \)
\( a = -9 \) veya \( a = 8 \)
\( a = -9 \) değerini yerine koyduğumuzda \( r + 7 \) ifadesi negatif olur, dolayısıyla bu değer geçerli bir çözüm değildir.
\( a \in \{-2, 3, 8\} \)
Buna göre \( a \)'nın alabileceği tam sayı değerlerin toplamı \( -2 + 3 + 8 = 9 \) olarak bulunur.
Kombinasyon - Permütasyon İlişkisi
Permütasyon ve kombinasyon formülleri arasında aşağıdaki ilişki kurulabilir.
\( 0 \le r \le n \) olmak üzere,
\( P(n, r) = C(n, r) \cdot r! \)
\( P(5, 3) = 5 \cdot 4 \cdot 3 = 60 \)
\( C(5, 3) = 10 \)
\( P(5, 3) = C(5, 3) \cdot 3! \)
\( 60 = 10 \cdot 6 \)
İSPATI GÖSTER
Permütasyon ve kombinasyon formülleri aşağıdaki gibidir.
\( P(n, r) = \dfrac{n!}{(n - r)!} \)
\( C(n, r) = \dfrac{n!}{r! \cdot (n - r)!} \)
Buna göre, kombinasyon formülünü \( r! \) ile çarparsak permütasyon formülünü elde ederiz.
\( C(n, r) \cdot r! = \dfrac{n!}{r! \cdot (n - r)!} \cdot r! \)
\( = \dfrac{n!}{(n - r)!} = P(n, r) \)
Buna göre iki formül arasında aşağıdaki ilişkiyi kurabiliriz.
\( P(n, r) = C(n, r) \cdot r! \)
Buna göre \( n \)'nin \( r \)'li permütasyonu aşağıdaki iki işlemin arka arkaya gerçekleştirildiği bir işlem olarak düşünülebilir.
- \( n \) elemanlı bir küme içinden \( r \) elemanın seçilmesi (\( C(n, r) \))
- Seçilen bu \( r \) elemanın farklı permütasyonlarının/dizilişlerinin bulunması (\( r! \))
5 kişinin katıldığı bir yarışmada 1., 2. ve 3. kaç farklı şekilde belirlenebilir?
Çözümü GösterYarışmacıları bir küme olarak tanımlayalım.
\( A = \{ a, b, c, d, e \} \)
Soru bir permütasyon/diziliş sorusudur. Buna göre 5 yarışmacının 3'lü dizilişlerinin sayısı \( P(5, 3) = \frac{5!}{(5 - 3)!} = 60 \) olur.
abc, abd, abe, ..., edc
Soruyu alternatif olarak kombinasyon kullanarak da çözebiliriz. Buna göre 5 yarışmacı içinden dereceye giren 3 yarışmacı \( C(5, 3) = \frac{5!}{3!\ (5 - 3)!} = 10 \) farklı şekilde seçilebilir. Daha sonra seçilen bu 3 yarışmacı aralarında \( 3! = 6 \) farklı şekilde dizilebilirler, dolayısıyla oluşan farklı diziliş sayısı yukarıda bulduğumuz gibi \( 10 \cdot 6 = 60 \) olur.
\( P(5, 3) = C(5, 3) \cdot 3! \)
Kombinasyonun Kullanım Alanları
Kombinasyonun bazı kullanım alanları aşağıdaki gibidir.
Alt Küme Sayısı
\( n \) elemanlı bir kümenin \( r \)'li kombinasyonu aynı zamanda o kümenin \( r \) elemanlı alt küme sayısını verir.
\( n \) elemanlı bir kümenin \( r \) elemanlı alt kümelerinin sayısı \( = C(n, r) \)
6 elemanlı bir kümenin 2 elemanlı alt kümelerinin sayısı:
\( C(6, 2) = \dfrac{6!}{2!\ (6 - 2)!} = 15 \)
\( 0 \le r \le n \) olmak koşuluyla, \( n \) elemanlı bir kümenin tüm \( r \) elemanlı alt kümelerinin toplamı \( 2^n \)'e, yani kümeler konusunda gördüğümüz toplam alt küme sayı formülüne eşittir.
\( C(n, 0) + C(n, 1) + C(n, 2) + \ldots \) \( + C(n, n - 1) + C(n, n) \) \( = 2^n \)
5 elemanlı bir kümenin tüm alt kümelerinin sayısı:
\( 2^5 = 32 \)
5 elemanlı bir kümenin 0, 1, 2, 3, 4, 5 elemanlı alt kümelerinin sayısı:
\( C(5, 0) = 1 \)
\( C(5, 1) = 5 \)
\( C(5, 2) = 10 \)
\( C(5, 3) = 10 \)
\( C(5, 4) = 5 \)
\( C(5, 5) = 1 \)
\( 1 + 5 + 10 + 10 + 5 + 1 = 32 \)
Pascal Üçgeni
Binom açılımı konusunda göreceğimiz Pascal üçgeninin her kutusundaki değerler o kutunun karşılık geldiği satır (\( n \)) ve sütun (\( r \)) için \( C(n, r) \) değerini verir. Ayrıca bir satırdaki tüm değerlerin toplamı yine \( 2^n \) değerini verir.
Belirli bir \( n \) sayısının çift sayı kombinasyonlarının toplamı tek sayı kombinasyonlarının toplamına eşittir.
\( C(n, 0) + C(n, 2) + C(n, 4) + \ldots = 2^{n - 1} \)
\( C(n, 1) + C(n, 3) + C(n, 5) + \ldots = 2^{n - 1} \)
Binom Katsayıları
Binom açılımı konusunda göreceğimiz iki terimli ifadelerin kuvvetlerinin açılımındaki katsayılar da kombinasyon formülleri ile hesaplanabilir. Bir binom ifadenin açılımı aşağıdaki şekilde ifade edilir.
\( (x + y)^n = \binom{n}{0} x^{n - 0}y^0 \) \( + \binom{n}{1} x^{n - 1}y \) \( + \binom{n}{2} x^{n - 2}y^2 + \ldots \) \( + \binom{n}{k} x^{n - k}y^k + \ldots \) \( + \binom{n}{n} x^{n - n}y^{n - 0} \)
\( \binom{10}{3} + \binom{10}{4} + \ldots + \binom{10}{9} + \binom{10}{10} \) işleminin sonucu kaçtır?
Çözümü Göster\( \binom{n}{r} \) ifadesi \( n \) elemanlı bir kümenin \( r \) elemanlı alt kümelerinin sayısını verir.
\( n \) elemanlı bir kümenin tüm alt kümelerinin sayısı \( 2^n \) olur.
\( \binom{10}{0} + \binom{10}{1} + \ldots + \binom{10}{9} + \binom{10}{10} = 2^n \)
Buna göre sorudaki ifadeye \( A \) dersek \( A \)'yı aşağıdaki şekilde yazabiliriz.
\( A = 2^{10} - \binom{10}{0} - \binom{10}{1} - \binom{10}{2} \)
\( = 1024 - 1 - 10 - \dfrac{10 \cdot 9}{2} = 968 \) bulunur.
\( \binom{9}{0} + \binom{9}{1} + \binom{9}{2} + \binom{9}{3} + \binom{9}{4} \) toplamının sonucu kaçtır?
Çözümü Göster\( n \) elemanlı bir kümenin \( r \) elemanlı alt kümelerinin sayısı \( \binom{n}{r} \) ile bulunur.
\( n \) elemanlı bir kümenin tüm alt kümelerinin sayısı \( 2^n \) ile bulunur.
\( \binom{n}{r} = \binom{n}{n - r} \) özdeşliğini kullanalım.
\( \binom{9}{0} = \binom{9}{9} \), \( \binom{9}{1} = \binom{9}{8} \), \( \binom{9}{2} = \binom{9}{7} \), \( \binom{9}{3} = \binom{9}{6} \), \( \binom{9}{4} = \binom{9}{5} \) olur.
Buna göre verilen ifade 9 elemanlı bir kümenin tüm alt kümelerinin sayısının yarısına eşittir.
\( \dfrac{2^9}{2} = 2^8 \) bulunur.