Kombinasyon Tanımı
\( n \) elemanlı bir \( A \) kümesinin elemanlarıyla sıra gözetmeksizin oluşturulan \( r \) elemanlı alt kümelerin her birine kombinasyon denir. Kombinasyonda seçim önemlidir, elemanlar seçildikten sonraki 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! \cdot (n - r)!} \)
\( A = \{ a, b, c, d \} \) olmak üzere,
\( C(4, 2) = \dfrac{4!}{2! \cdot (4 - 2)!} = 6 \)
\( A \) kümesinin 2'li kombinasyonları: ab, ac, ad, bc, bd, cd
\( B = \{ 1, 2, 3, 4, 5 \} \) olmak üzere,
\( C(5, 4) = \dfrac{5!}{4! \cdot (5 - 4)!} = 5 \)
\( B \) kümesinin 4'lü kombinasyonları: 1234, 1235, 1245, 1345, 2345
Kombinasyon hesaplamasında kullanabileceğimiz kısa bir yol şu şekildedir: \( n \)'nin \( r \)'li kombinasyonunu hesaplarken, 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 ise \( r \)'nin faktöriyelinin açılımı yazılır. Aşağıda bu yönteme iki örnek verilmiştir.
\( C(8, 2) = \dfrac{\overbrace{8 \cdot 7}^\text{2 kez}}{\underbrace{2 \cdot 1}_\text{2!}} = 28 \)
\( 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 \)
Kombinasyon İşlem Kuralları
0 sayısının faktöriyeli tanım gereği 1'e eşittir.
\( 0! = 1 \)
\( n \) elemanlı bir kümenin \( 0 \)'lı ve \( n \)'li kombinasyonları her zaman 1'e eşittir. \( n \) elemanlı bir küme içinden seçilebilecek 0 elemanlı tek alt küme boş kümedir. \( n \) elemanlı bir küme içinden seçilebilecek \( n \) elemanlı tek alt küme kümenin kendisidir.
\( C(n, 0) = C(n, n) = \dfrac{n!}{0! \cdot n!} = 1 \)
\( C(5, 0) = \dfrac{5!}{0! \cdot (5 - 0)!} \) \( = \dfrac{5!}{0! \cdot 5!} = 1 \)
\( C(5, 5) = \dfrac{5!}{5! \cdot (5 - 5)!} \) \( = \dfrac{5!}{5! \cdot 0!} = 1 \)
\( n \) elemanlı bir kümenin \( 1 \)'li ve \( (n - 1) \)'li kombinasyonları her zaman \( n \)'e eşittir. \( n \) elemanlı bir küme içinden seçilebilecek 1 elemanlı alt kümeler ayrı ayrı her bir elemandan oluşan alt kümelerdir. \( n \) elemanlı bir küme içinden seçilebilecek \( (n - 1) \) elemanlı alt kümeler de kümenin kendisinden ayrı ayrı her bir elemanın çıkartıldığı alt kümelerdir.
\( C(n, 1) = C(n, n - 1) \) \( = \dfrac{n!}{1! \cdot (n - 1)!} = n \)
\( C(5, 1) = \dfrac{5!}{1! \cdot (5 - 1)!} \) \( = \dfrac{5!}{1! \cdot 4!} = 5 \)
\( C(5, 4) = \dfrac{5!}{4! \cdot (5 - 4)!} \) \( = \dfrac{5!}{4! \cdot 1!} = 5 \)
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! \cdot (n - r)!} \)
Bu kuralı tersten şu şekilde de ifade edebiliriz: \( 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, k) = C(8, 2) \) ise,
\( k = 2 \) ya da \( k = 6 \)
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) \)
\( C(8, 3) + C(8, 4) = C(9, 4) \)
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} \)
Kombinasyonun Kullanım Alanları
Kombinasyon sayma konusu dışında aşağıdaki konularda da karşımıza çıkmaktadır.
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,
\( \text{r elemanlı alt küme sayısı} = C(n, r) \)
\( n \) elemanlı bir kümenin \( 0 \le r \le n \) olmak koşuluyla 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 \)
Pascal Üçgeni
"Binom Açılımı" konusunda göreceğimiz Pascal Üçgeni'nin 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ı bize yine \( 2^n \) değerini verir.
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ını aşağıdaki şekilde ifade edebiliriz.
\( (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} \)