n tane farklı elemandan oluşan bir kümenin altkümelerine birer kombinasyon denir.
n, r
✁
ve 0 ≤ r ≤ n olmak üzere, n elemanlı A
kümesinin r elemanlı altkümelerinden her birine A
kümesinin r’li bir kombinasyonu denir ve C(n, r)
veya
n
r
şeklinde gösterilir.
Anlayacağınız, kümelerde elemanların sıralanışı
önemli olmadığından kombinasyonda da sıra
önemli değildir. Sadece elemanların neler ve kaç
tane olduğu önemlidir.
Bir diğer önemli nokta da
n
r
ifadesinin solunda
P ya da C harfi yazmıyorsa, bunun kombinasyon
olarak anlaşılması gerektiğidir.
C(n, r) nasıl hesaplanır? Yukardaki tanımdan anladığımız kadarıyla kombinasyonla bir miktar
nesneyi seçiyoruz, bunu da permutasyonla sıralı-
yoruz. Peki, r tane nesne kaç değişik şekilde sıralanır? r! kadar değişik şekilde. O halde P(n, r) sayısını r!’e bölmek C(n, r)’yi verecektir.
C(n, r) =
!
( , )
r
P n r
=
( )!. !
!
n r r
n
−
C(n, r) sayısını daha pratik olarak hesaplamak isteyen biri aynen permutasyondaki pratik kuralı
uygular ama o sayıyı r!’e böler.
Örneğin,
C(10, 2) =
2.1
10 9.
, C(13, 3) =
3.2.1
13.12.11
, …
Teorem. C(n, 0) = 1.
Kanıt: C(n, 0) = 1
( 0)!. !0
!
=
n −
n
Teorem. C(n, n) = 1.
Kanıt: C(n, n) = 1
( )!. !
!
=
n − n n
n
Teorem. C(n, r) = C(n, n – r).
Kanıt: Bu teoremi de aynen yukardaki formülü
kullanarak kanıtlayabiliriz ama bu sefer sözlü izah
edelim. C(n, r) ne demek? n tane nesneden r tanesini seçmek. Peki geride ne bıraktığınızı düşündü-
nüz mü? n – r tane nesne. Seçtiğiniz r tane nesne
değiştikçe geride kalan n – r tane nesne de değişir.
Dolayısıyla eşitlik doğrudur.
Teorem. n, r
✁
ve r < n olmak üzere, C(n–1, r–
1) + C(n–1, r) = C(n, r).
Kanıt: C(n–1, r–1) + C(n–1, r) =
=
( )!.( 1)!
( 1)!
− −
−
n r r
n
+
( 1)!. !
( 1)!
n r r
n
− −
−
=
( )!. !
( 1)!.
n r r
n r
−
−
+
( )!. !
( 1)!.( )
n r r
n n r
−
− −
=
( )!. !
( 1)!.( )
n r r
n r n r
−
− + −
=
( )!. !
!
n r r
n
−
= C(n, r).
Soru. C(3, 1) + C(3, 2) toplamı kaçtır?
Çözüm: 1 + 2 = 3 olduğundan C(3, 1) = C(3, 2)
olduğunu biliyoruz. Sadece birini bulup, 2 ile
çarpsak yetecek. C(3, 1) = 3 olduğundan cevap
6’dır.
Soru. C(7, 3) = C(n, 1) – C(n, n) olduğuna göre n
kaçtır?
Çözüm: C(n, 1) – C(n, n) = n – 1 olduğunu biliyoruz. Diğer yandan; C(7, 3) =
3.2.1
5
