Bir banka kartının 4 haneli PIN kodu kaç farklı şekilde olabilir? Her haneye 10 rakamdan biri yazılır: 10 · 10 · 10 · 10 = 10 000 seçenek. 25 kişilik bir sınıftan 3 temsilci kaç farklı şekilde seçilebilir? 2300 şekilde! Tüm seçenekleri tek tek yazmak imkânsızdır; kombinatorik, onları listelemeden saymayı öğretir. Olasılık, kriptografi ve programlama bu bilgilere dayanır.
Çarpma ve toplama yoluyla sayma
Burada
- n₁, n₂, …, nₖ
- her adımdaki seçenek sayısı
- N
- toplam sonuç sayısı
Çarpma yoluyla sayma: seçim art arda birkaç adımda yapılıyorsa (“hem bu hem o”), her adımdaki seçenek sayıları çarpılır.
Burada
- n, m
- ortak elemanı olmayan iki gruptaki seçenek sayıları
Toplama yoluyla sayma: seçim “ya bu ya o” biçimindeyse ve gruplar ortak eleman içermiyorsa seçenek sayıları toplanır.
Çarpma kuralını bir ağaç gibi düşün. Murad'ın 3 gömleği (beyaz, mavi, yeşil) ve 2 pantolonu (siyah, gri) var. Her gömlekten 2 dal çıkar, her pantolon için bir dal; bu yüzden toplam 3 · 2 = 6 kombin olur: beyaz–siyah, beyaz–gri, mavi–siyah, mavi–gri, yeşil–siyah, yeşil–gri. Eğer yalnızca tek bir eşya seçecekse, ya 3 şapkadan birini ya da 2 atkıdan birini, seçenekler toplanır: 3 + 2 = 5. Kısacası: “hem bu hem şu” ise çarp, “ya bu ya şu” ise topla.
Çarpma ve toplama yoluyla sayma
Problem
a) Bir kafede 3 çeşit çorba, 4 çeşit ana yemek ve 2 çeşit içecek var. Bir çorba, bir ana yemek ve bir içecekten oluşan kaç farklı öğle yemeği sipariş edilebilir?
b) Rakamları farklı kaç tane üç basamaklı sayı vardır?
c) Leyla raftaki 5 romandan veya 7 şiir kitabından birini seçecek. Kaç seçeneği var?
Çözümü gösterÇözümü gizle
Çözüm
b) Yüzler basamağı 0 olamaz: 9 seçenek. Onlar basamağı: 0 dahil, ilk rakam dışında herhangi biri: 9 seçenek. Birler basamağı: kalan 8 rakam. 9 · 9 · 8 = 648.
c) “Ya roman ya şiir kitabı”; toplama yoluyla sayma: 5 + 7 = 12.
İçerme–dışlama ilkesi. İki grup kesişiyorsa toplama kuralı ortak elemanları iki kez sayar, bu yüzden onlar bir kez çıkarılır. Üç grup için: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. Burada |A|, A kümesinin eleman sayısıdır.
2'ye, 3'e ya da 5'e bölünenler
Problem
1, 2, …, 100 sayılarından kaç tanesi 2'ye, 3'e ya da 5'e bölünür?
Çözümü gösterÇözümü gizle
Çözüm
6'ya: 16, 10'a: 10, 15'e: 6; 30'a: 3.
50 + 33 + 20 − 16 − 10 − 6 + 3 = 74.
Demek ki 100 − 74 = 26 sayı bunların hiçbirine bölünmez; örneğin 1, 7, 11, 13 ve 5'ten büyük bütün asal sayılar.
Faktöriyel ve permütasyon
FaktöriyelTanım
n! = 1 · 2 · 3 · … · n; 1'den n'ye kadar bütün doğal sayıların çarpımı. Tanım gereği 0! = 1'dir. Örneğin 5! = 120, 10! = 3 628 800; faktöriyel çok hızlı büyür.
Burada
- n
- sıralanan farklı elemanların sayısı
Permütasyon sayısı: n farklı elemanı bir sıraya dizmenin yol sayısı. Birinci yer için n, ikinci yer için n − 1 seçenek kalır ve böyle devam eder.
Hepsini yaz
Problem
Aysel (A), Leyla (L) ve Murad (M) bir sırada kaç farklı şekilde durabilir?
Çözümü gösterÇözümü gizle
Çözüm
A önde: ALM, AML
L önde: LAM, LMA
M önde: MAL, MLA
6 sıralama çıktı. Sayma kuralı da aynısını söyler: ilk yer için 3, ikinci için 2, sonuncu için 1 seçenek: 3 · 2 · 1 = 3! = 6.
Permütasyonlar
Problem
a) 5 farklı kitap bir rafa kaç farklı şekilde dizilebilir?
b) 6 öğrenci bir sıraya diziliyor. Aysel ile Murad yan yana durmak zorundaysa kaç farklı sıralama vardır?
Çözümü gösterÇözümü gizle
Çözüm
b) Aysel ile Murad'ı “yapıştırıp” tek bir eleman sayalım: 5 eleman 5! = 120 şekilde dizilir. Çiftin içinde ise 2! = 2 şekilde durabilirler.
120 · 2 = 240. (Koşul olmasaydı 6! = 720 olurdu.)
Tekrarlanan nesneler ve yuvarlak masa
Problem
1) 1, 1, 2, 2, 2, 3, 3 rakamlarının her birini tam bir kez kullanarak kaç farklı yedi basamaklı sayı yazılabilir?
2) Yalnızca masanın çevresindeki sıra önemliyse, 6 kişi yuvarlak bir masaya kaç farklı şekilde oturabilir?
Çözümü gösterÇözümü gizle
Çözüm
2) Herkesi bir sandalye kaydırmak aynı oturuşu verir ve her oturuşun 6 böyle dönmesi vardır: 6!/6 = 5! = 120. Başka bir deyişle: bir kişinin yerini sabitleyip kalan 5 kişiyi sıralarız.
r'li permütasyon ve kombinasyon
Burada
- n
- toplam eleman sayısı
- r
- seçilip sıralanan eleman sayısı (r ≤ n)
r'li permütasyon: n elemandan r tanesini seçip sıralarız; sıra önemlidir. Sağ tarafta n'den başlayarak azalan r tane çarpan vardır.
Burada
- n
- toplam eleman sayısı
- r
- seçilen eleman sayısı; sıra dikkate alınmaz
Kombinasyon: n elemandan r tanesini yalnızca seçeriz; sıra önemli değildir. r elemanlı her grup permütasyonlarda r! kez sayıldığı için r!'e böleriz.
Sıra ne zaman önemlidir? Üç öğrenci, A, B ve C alalım ve ikisini seçelim. İkisine farklı görevler verilirse (kaptan ve yardımcısı) AB ile BA farklı seçimlerdir. Sadece bir yarışmaya gidecek bir ikiliyseler, AB ile BA aynı ikilidir.
| Kaptan ve yardımcısı (sıra önemli) | Sadece ikili (sıra önemli değil) |
|---|---|
| AB, BA | {A, B} |
| AC, CA | {A, C} |
| BC, CB | {B, C} |
| toplam 6 = P(3, 2) | toplam 3 = C(3, 2) |
| Ne yapıyoruz? | Sıra önemli mi? | Formül | Örnek |
|---|---|---|---|
| n elemanın hepsini sıralarız | evet | n! | rafta 5 kitap: 120 |
| n elemandan r tanesini seçip sıralarız | evet | P(n, r) | 25 kişiden başkan, yardımcı, sekreter: 13 800 |
| n elemandan r tanesini yalnızca seçeriz | hayır | C(n, r) | 25 kişiden 3 temsilci: 2300 |
| r yerin her birine n seçenekten biri (tekrar olabilir) | evet | nʳ | 4 haneli PIN: 10⁴ = 10 000 |
Sıra önemli mi, değil mi?
Problem
25 öğrencilik bir sınıfta:
a) sınıf başkanı, başkan yardımcısı ve sekreter kaç farklı şekilde seçilebilir?
b) bir konferansa gidecek 3 temsilci kaç farklı şekilde seçilebilir?
Çözümü gösterÇözümü gizle
Çözüm
b) Üç temsilci eşit haklara sahip, sıra önemli değil: C(25, 3) = P(25, 3) / 3! = 13 800 / 6 = 2300.
Burada
- n, r
- r ≤ n olan doğal sayılar
Birinci özellik: r eleman seçmek, kalan n − r elemanı “dışarıda bırakmak” demektir. İkinci özellik Pascal üçgeninin kurulma kuralıdır: C(5, 2) + C(5, 3) = 10 + 10 = 20 = C(6, 3).
C(5, 2) + C(5, 3) = C(6, 3) neden doğrudur? Bunu bir hikâye açıklar. Aralarında Aysel'in de olduğu 6 öğrenciden 3 kişilik bir takım seçiyoruz: C(6, 3) = 20 takım. Her takımda Aysel ya vardır ya yoktur. Aysel'li takımlar: kalan 5 kişiden 2 kişi daha seçeriz, C(5, 2) = 10. Aysel'siz takımlar: 3 kişinin hepsini kalan 5 kişiden seçeriz, C(5, 3) = 10. 10 + 10 = 20. C(5, 2) = C(5, 3) eşitliği de bu kadar basittir: gidecek 2 kişiyi seçmek, kalacak 3 kişiyi seçmekle aynıdır.
- C(10, 3) için paya 10'dan başlayarak azalan 3 sayı yaz: 10 · 9 · 8 = 720.
- Paydaya 3! = 1 · 2 · 3 = 6 yaz.
- Böl: 720 : 6 = 120. Önce sadeleştirmek daha kolaydır: 9 : 3 = 3 ve 8 : 2 = 4, o zaman 10 · 3 · 4 = 120.
- r büyükse tersine çevir: C(20, 18) = C(20, 2) = (20 · 19) / 2 = 190.
Sınav tipi soru: grup seçimi
Problem
Bir kulüpte 6 erkek ve 4 kız var. 5 kişilik bir takım seçilecek.
a) Tam 2 kız içeren kaç takım vardır?
b) En az bir kız içeren kaç takım vardır?
c) Kulüpten rastgele 2 kişi seçiliyor. İkisinin de kız olma olasılığı nedir?
Çözümü gösterÇözümü gizle
Çözüm
b) Tümleyeni kullanırız: “en az bir kız” = tüm takımlar − kızsız takımlar. C(10, 5) − C(6, 5) = 252 − 6 = 246.
c) Tüm ikililer: C(10, 2) = 45, iki kızlı ikililer: C(4, 2) = 6. P = 6/45 = 2/15 ≈ 0,13.
Olimpiyatların klasik bir fikri yıldızlar ve çubuklar yöntemidir. n özdeş nesneyi m kişi arasında paylaştırmak, bir sıraya n yıldız ve m − 1 çubuk dizmekle aynıdır: çubuklar sırayı m parçaya böler. Örneğin ★★|★★★★★|★★★, 2, 5 ve 3 demektir. n + m − 1 yer arasından yalnızca çubukların yerlerini seçeriz; bu yüzden yolların sayısı C(n + m − 1, m − 1)'dir.
Şekerleri paylaştırmak
Problem
1) 10 özdeş şeker 3 çocuk arasında kaç farklı şekilde paylaştırılabilir?
2) Her çocuk en az bir şeker almak zorundaysa kaç yol vardır?
Çözümü gösterÇözümü gizle
Çözüm
2) Önce her çocuğa birer şeker verelim; kalan 7 şeker serbestçe paylaştırılır: C(9, 2) = (9 · 8)/2 = 36.
Aynı sayılar, x + y + z = 10 denkleminin negatif olmayan tam sayı (66) ve pozitif tam sayı (36) çözümlerinin sayısıdır.
Binom açılımı ve Pascal üçgeni
Burada
- n
- doğal sayı üs
- C(n, r)
- binom katsayıları
Binom açılımı. Genel terim: C(n, r) · aⁿ⁻ʳ · bʳ. Açılımda n + 1 terim vardır, katsayıların toplamı 2ⁿ'dir. (a − b)ⁿ açılımında işaretler sırayla değişir: +, −, +, …
Bildiğinden başla: (a + b)² = a² + 2ab + b²; katsayılar 1, 2, 1, Pascal üçgeninin 2. satırıdır. Bir kez daha (a + b) ile çarparsan (a + b)³ = a³ + 3a²b + 3ab² + b³ olur; 3. satır: 1, 3, 3, 1. İki düzen yardımcı olur: terimden terime a'nın kuvveti birer birer azalır, b'ninki artar ve her terimde iki kuvvetin toplamı n'dir. n = 3 için: a³, a²b, ab², b³.
| n | Binom katsayıları | Toplam |
|---|---|---|
| 0 | 1 | 1 = 2⁰ |
| 1 | 1 1 | 2 = 2¹ |
| 2 | 1 2 1 | 4 = 2² |
| 3 | 1 3 3 1 | 8 = 2³ |
| 4 | 1 4 6 4 1 | 16 = 2⁴ |
| 5 | 1 5 10 10 5 1 | 32 = 2⁵ |
| 6 | 1 6 15 20 15 6 1 | 64 = 2⁶ |
n. satırdaki katsayıların toplamı neden 2ⁿ'dir? Binom açılımında a = b = 1 yazalım: (1 + 1)ⁿ = C(n, 0) + C(n, 1) + … + C(n, n). Sayarak yapılan bir kanıt da vardır: n elemanlı bir kümenin 2ⁿ alt kümesi vardır (her eleman ya alınır ya alınmaz) ve bunların C(n, r) tanesi tam r elemanlıdır. a = 1, b = −1 yazarsak C(n, 0) − C(n, 1) + C(n, 2) − … = 0 çıkar: bir kümenin çift sayıda elemanlı alt kümeleri, tek sayıda elemanlı alt kümeleri kadardır.
Pizza malzemeleri
Problem
Bir pizzacıda 8 çeşit malzeme var. Kaç farklı pizza sipariş edilebilir (herhangi bir malzeme seçimi, hiç malzeme olmaması da dahil)? Bunların kaçında malzeme sayısı çifttir?
Çözümü gösterÇözümü gizle
Çözüm
Çift ve tek sayıda malzemeli pizzalar eşit sayıdadır; bu yüzden 128 pizzada malzeme sayısı çifttir. 8. satırla kontrol: C(8, 0) + C(8, 2) + C(8, 4) + C(8, 6) + C(8, 8) = 1 + 28 + 70 + 28 + 1 = 128 ✓.
Etkileşimli
Binom açılımı ve katsayı
Problem
a) (x + 2)⁴ ifadesini açın.
b) (2x − 1)⁵ açılımında x²'nin katsayısını bulun.
Çözümü gösterÇözümü gizle
Çözüm
(x + 2)⁴ = x⁴ + 4 · 2x³ + 6 · 4x² + 4 · 8x + 16 = x⁴ + 8x³ + 24x² + 32x + 16.
b) Genel terim: C(5, r) · (2x)⁵⁻ʳ · (−1)ʳ. x² için 5 − r = 2 ⇒ r = 3.
C(5, 3) · 2² · (−1)³ = 10 · 4 · (−1) = −40.
Binom açılımı aynı zamanda yaklaşık hesap ve olasılık aracıdır. x küçükse x², x³, … içeren terimler çabucak küçülür; bu yüzden (1 + x)ⁿ ≈ 1 + nx + C(n, 2)x². Bir para n kez atıldığında her yazı-tura dizisinin olasılığı 1/2ⁿ'dir, tam r tura ise C(n, r) dizide gelir; bu, üniversite olasılık kuramının temel yasalarından biri olan binom dağılımıdır.
Yaklaşık hesap ve para atma
Problem
1) 1,01¹⁰'u hesap makinesi olmadan yaklaşık olarak bulun.
2) Bir para 10 kez atılıyor. Tam 5 kez tura gelme olasılığı nedir?
Çözümü gösterÇözümü gizle
Çözüm
2) 2¹⁰ = 1024 eşit olasılıklı dizi vardır ve bunların C(10, 5) = 252 tanesinde tam 5 tura vardır: P = 252/1024 = 63/256 ≈ 0,246. Yani en olası sonuç bile dört seriden birinden daha az gelir.
Unutma
- Çarpma yoluyla sayma: art arda adımların seçenekleri çarpılır; toplama yoluyla sayma: “ya/ya da” seçenekleri toplanır.
- n!, n elemanın tüm sıralanışlarının sayısıdır.
- Sıra önemliyse P(n, r) = n!/(n − r)!, değilse C(n, r) = n!/(r!(n − r)!).
- “En az bir” türündeki sorularda tersini tümünden çıkarmak daha kolaydır.
- (a + b)ⁿ açılımının katsayıları Pascal üçgeninin n. satırıdır; genel terim C(n, r)aⁿ⁻ʳbʳ.