Permütasyon ve kombinasyon

Toplama ve çarpma yoluyla sayma, faktöriyel, permütasyon ve kombinasyon, binom açılımı ve Pascal üçgeni.

  • 9…11. sınıflar
  • 25 dk
  • 10 soru
  • Ders 56 / 92

Bu derste öğreneceklerin

  • Çarpma ve toplama yoluyla olasılıkları saymak
  • Sıranın önemli olup olmadığına göre permütasyon veya kombinasyon seçmek
  • Binomu Pascal üçgeniyle açmak ve istenen katsayıyı bulmak

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

N = n₁ · n₂ · … · nₖ

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.

N = n + m

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.

Basit anlatım

Ç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

a) Üç adım (çorba, ana yemek, içecek); çarpma yoluyla sayma: 3 · 4 · 2 = 24.
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.
Derinlemesine
|A ∪ B| = |A| + |B| − |A ∩ B|

İç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

2'ye bölünenler: 50, 3'e: 33, 5'e: 20.
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.

Okumaya devam etmek için ücretsiz kaydol

Dersin geri kalan bölümleri, test ve notlar Educora hesabıyla açılır. Kayıt bir dakika sürer; ilerlemen tüm cihazlarında saklanır.

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.

P(n, n) = n!

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.

Basit anlatım

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

Önde kimin durduğuna göre hepsini yazalı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

a) 5! = 1 · 2 · 3 · 4 · 5 = 120.
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.)
Derinlemesine

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

1) 7 rakamın hepsi farklı olsaydı 7! = 5040 sıralama olurdu. Ama iki 1'in, üç 2'nin ya da iki 3'ün yerini değiştirmek aynı sayıyı verir; bu yüzden her sayı 2! · 3! · 2! = 24 kez sayılmıştır: 5040 / 24 = 210.
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

P(n, r) = n! / (n − r)! = n · (n − 1) · … · (n − r + 1)P(n, r) = n! / (n − r)! = n · (n − 1) · … · (n − r + 1)

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.

C(n, r) = n! / (r! · (n − r)!) = P(n, r) / r!C(n, r) = n! / (r! · (n − r)!) = P(n, r) / 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.

Basit anlatım

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)
Her ikili sol sütunda iki kez görünür (2! = 2 sıralama), bu yüzden C(3, 2) = P(3, 2) / 2! = 6 / 2 = 3.
Ne yapıyoruz?Sıra önemli mi?FormülÖrnek
n elemanın hepsini sıralarızevetn!rafta 5 kitap: 120
n elemandan r tanesini seçip sıralarızevetP(n, r)25 kişiden başkan, yardımcı, sekreter: 13 800
n elemandan r tanesini yalnızca seçerizhayırC(n, r)25 kişiden 3 temsilci: 2300
r yerin her birine n seçenekten biri (tekrar olabilir)evetnʳ4 haneli PIN: 10⁴ = 10 000
Hangi formülü seçmeli: önce “sıra önemli mi?” sorusunu cevapla.

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

a) Görevler farklı, sıra önemli: P(25, 3) = 25 · 24 · 23 = 13 800.
b) Üç temsilci eşit haklara sahip, sıra önemli değil: C(25, 3) = P(25, 3) / 3! = 13 800 / 6 = 2300.
C(n, r) = C(n, n − r)C(n, r) + C(n, r + 1) = C(n + 1, r + 1)C(n, 0) = C(n, n) = 1

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).

Basit anlatım

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.

  1. C(10, 3) için paya 10'dan başlayarak azalan 3 sayı yaz: 10 · 9 · 8 = 720.
  2. Paydaya 3! = 1 · 2 · 3 = 6 yaz.
  3. Böl: 720 : 6 = 120. Önce sadeleştirmek daha kolaydır: 9 : 3 = 3 ve 8 : 2 = 4, o zaman 10 · 3 · 4 = 120.
  4. 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

a) 4 kızdan 2'si ve 6 erkekten 3'ü, çarpma yoluyla: C(4, 2) · C(6, 3) = 6 · 20 = 120.
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.
Derinlemesine

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

1) n = 10, m = 3: C(12, 2) = (12 · 11)/2 = 66.
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

(a + b)ⁿ = C(n, 0)aⁿ + C(n, 1)aⁿ⁻¹b + C(n, 2)aⁿ⁻²b² + … + C(n, n)bⁿ

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: +, −, +, …

Basit anlatım

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³.

nBinom katsayılarıToplam
011 = 2⁰
11 12 = 2¹
21 2 14 = 2²
31 3 3 18 = 2³
41 4 6 4 116 = 2⁴
51 5 10 10 5 132 = 2⁵
61 6 15 20 15 6 164 = 2⁶
Pascal üçgeni. Kenarlarda 1 bulunur, içteki her sayı üstündeki iki sayının toplamıdır: 10 = 4 + 6, 20 = 10 + 10. n. satır, (a + b)ⁿ açılımının katsayılarıdır.
Derinlemesine

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

Her malzeme ya pizzadadır ya değildir: 2⁸ = 256 pizza (sade pizza da dahil).
Ç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

Simülasyon yükleniyor…
Binom katsayıları ortaya göre simetriktir: C(10, r) = C(10, 10 − r). En büyüğü ortadadır: C(10, 5) = 252. Hepsinin toplamı 2¹⁰ = 1024’tür. n büyüdükçe sütunlar “çan” biçimini alır; bu, normal dağılıma giden yoldur.

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

a) 4. satır: 1, 4, 6, 4, 1. 2'nin kuvvetleri: 1, 2, 4, 8, 16.
(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.
Derinlemesine

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

1) (1 + 0,01)¹⁰ = 1 + 10 · 0,01 + 45 · 0,0001 + 120 · 0,000001 + … ≈ 1 + 0,1 + 0,0045 + 0,00012 = 1,10462. Hesap makinesi 1,104622… verir.
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ʳ.
Bu derste bir hata ya da yanlışlık mı gördün?

Kendini test et

10 soru. Her doğru cevap XP kazandırır.

Soru 1 / 10

Soru 1 / 10. Tüm rakamları farklı olan kaç tane 4 haneli PIN kodu vardır? (PIN 0 ile başlayabilir.)