Ayrık Matematik - Sayma Teorisi
Günlük yaşamda, çoğu zaman bir dizi olay için olası tüm sonuçların sayısını bulmak gerekir. Örneğin, 6 erkek ve 4 kadından oluşan bir yargıçlar kurulu 50 erkek ve 38 kadın arasından kaç şekilde seçilebilir? İlk beş harf büyük harf, sonraki dördü rakam ve sonuncusu yine büyük harf olacak şekilde kaç farklı 10 harfli PAN numarası üretilebilir. Bu problemleri çözmek için matematiksel sayma teorisi kullanılır.Counting esas olarak temel sayma kuralını, permütasyon kuralını ve kombinasyon kuralını kapsar.
Toplam ve Çarpım Kuralları
Rule of Sum ve Rule of Product zor sayma problemlerini basit problemlere ayırmak için kullanılır.
The Rule of Sum- Bir görev dizisi $ T_1, T_2, \ dots, T_m $ sırasıyla $ w_1, w_2, \ dots w_m $ yollarında yapılabilir (koşul, hiçbir görevin aynı anda gerçekleştirilememesidir), o zaman bu görevlerden biri $ w_1 + w_2 + \ dots + w_m $ şeklindedir. Ayrık olan iki görevi (yani $ A \ cap B = \ emptyset $), matematiksel olarak $ | A \ cup B | = | A | + | B | $
The Rule of Product- Bir görev dizisi $ T_1, T_2, \ dots, T_m $ sırasıyla $ w_1, w_2, \ dots w_m $ yollarında yapılabilir ve her görev bir önceki görevin gerçekleşmesinden sonra gelirse, o zaman $ w_1 \ kere olur w_2 \ times \ dots \ times w_m $ görevleri gerçekleştirmenin yolları. Matematiksel olarak, eğer bir B görevi A görevinden sonra gelirse, $ | A \ times B | = | A | \ kere | B | $
Misal
Question- X'te bir erkek çocuk yaşıyor ve Z'deki Okula gitmek istiyor. X'teki evinden önce Y'ye, sonra Y'den Z'ye varması gerekiyor. X'den Y'ye ya 3 otobüs güzergahı ya da 2 tren yolu ile gidebilir. Oradan Z'ye ulaşmak için 4 otobüs güzergahı veya 5 tren güzergahı seçebilir. X'den Z'ye gitmek için kaç yol vardır?
Solution- X'ten Y'ye, 3 $ + 2 = 5 $ yolla gidebilir (Toplam Kuralı). Daha sonra Y'den Z'ye 4 $ + 5 = 9 $ yolla gidebilir (Toplam Kuralı). Dolayısıyla X'ten Z'ye 5 $ \ times 9 = 45 $ yolla gidebilir (Ürün Kuralı).
Permütasyonlar
Bir permutationsıranın önemli olduğu bazı unsurların bir düzenlemesidir. Başka bir deyişle, bir Permütasyon, öğelerin sıralı bir Kombinasyonudur.
Örnekler
Bir seferde iki alarak S = {x, y, z} kümesinden tüm permütasyonlar -
$ xy, yx, xz, zx, yz, zy $.
$ S = \ lbrace 1, 2, 3 \ rbrace $ sayılarından üç basamaklı bir permütasyon oluşturmalıyız. Rakamları düzenlediğimizde farklı üç haneli sayılar oluşacaktır. Permütasyon = 123, 132, 213, 231, 312, 321 olacaktır.
Permütasyon Sayısı
Bir seferde alınan 'n' farklı şeyin permütasyonlarının sayısı 'r' $ n_ {P_ {r}} $ ile gösterilir
$$ n_ {P_ {r}} = \ frac {n!} {(n - r)!} $$
nerede $ n! = 1.2.3. \ noktalar (n - 1) .n $
Proof - "N" farklı öğe olmasına izin verin.
İlk sırayı doldurmanın n sayıda yolu vardır. İlk sırayı doldurduktan sonra (n-1) eleman sayısı kalır. Dolayısıyla, ikinci sırayı doldurmanın (n-1) yolları vardır. Birinci ve ikinci sırayı doldurduktan sonra (n-2) eleman sayısı kalır. Bu nedenle üçüncü sırayı doldurmanın (n-2) yolları vardır. Şimdi r'ninci yeri doldurmanın yollarının sayısını [n - (r – 1)] = n – r + 1 şeklinde genelleyebiliriz
Yani, toplam hayır. birinci sıradan ikinci sıraya kadar doldurmanın yolları -
$ n_ {P_ {r}} = n (n-1) (n-2) ..... (nr + 1) $
$ = [n (n-1) (n-2) ... (nr + 1)] [(nr) (nr-1) \ nokta 3.2.1] / [(nr) (nr-1) \ noktalar 3.2.1] $
Bu nedenle
$ n_ {P_ {r}} = n! / (nr)! $
Bazı önemli permütasyon formülleri
$ A_1 $ 'ın bir tür benzer olduğu n öğe varsa , $ a_2 $ başka türden benzerdir; $ a_3 $ benzer üçüncü türdür ve bu böyle devam eder ve $ a_r $ $ r ^ {th} $ türündedir, burada $ (a_1 + a_2 + ... a_r) = n $.
O halde, bu n nesnenin permütasyon sayısı = $ n! / [(a_1! (a_2!) \ noktalar (a_r!)] $.
Bir seferde n eleman alan n farklı elemanın permütasyon sayısı = $ n_ {P_n} = n! $
X belirli şeyler her zaman belirli yerleri işgal ettiğinde, bir seferde r öğesi alan n farklı öğenin permütasyonlarının sayısı = $ n-x_ {p_ {rx}} $
R belirtilen şeyler her zaman bir araya geldiğinde n farklı öğenin permütasyon sayısı - $ r! (n − r + 1)! $
R belirtilen şeyler asla bir araya gelmediğinde n farklı öğenin permütasyonlarının sayısı - $ n! - [r! (n − r + 1)!] $
Aynı anda x öğe alınan n farklı öğenin dairesel permütasyonlarının sayısı = $ ^ np_ {x} / x $
N farklı şeyin dairesel permütasyon sayısı = $ ^ np_ {n} / n $
Bazı problemler
Problem 1 - 6 farklı karttan kaç şekilde izin verebiliriz?
Solution- 6 kartlık desteden bir seferde 6 kart aldığımız için permütasyon $ ^ 6P_ {6} = 6 olacaktır! = 720 $
Problem 2 - 'OKUYUCU' kelimesinin harfleri kaç şekilde düzenlenebilir?
Solution - 'READER' kelimesinde 6 harfli kelime (2 E, 1 A, 1D ve 2R.) Vardır.
Permütasyon $ = 6 olacaktır! / \: [(2!) (1!) (1!) (2!)] = 180. $
Problem 3 - 'TURUNCU' kelimesinin harfleri, ünsüzlerin yalnızca çift konumlarda kalması için nasıl düzenlenebilir?
Solution- 'TURUNCU' kelimesinde 3 ünlü ve 3 ünsüz vardır. Ünsüzleri kendi aralarında düzenlemenin yolu sayısı $ = ^ 3P_ {3} = 3! = 6 $. Kalan 3 boş yer $ ^ 3P_ {3} = 3 olarak 3 sesli harfle doldurulacaktır! = 6 $ yol. Dolayısıyla, toplam permütasyon sayısı 6 $ \ times 6 = 36 $ 'dır
Kombinasyonlar
Bir combination sıranın önemli olmadığı bazı belirli öğelerin seçimidir.
Bir seferde r alınan n şeyin tüm kombinasyonlarının sayısı -
$$ ^ nC_ {{r}} = \ frac {n! } {r! (nr)! } $$
Problem 1
3 elemanlı $ \ lbrace1, 2, 3, 4, 5, 6 \ rbrace $ kümesinin alt kümelerinin sayısını bulun.
Solution
Setin önemi 6'dır ve setten 3 element seçmemiz gerekir. Burada sıralama önemli değil. Bu nedenle, alt kümelerin sayısı $ ^ 6C_ {3} = 20 $ olacaktır.
Problem 2
Bir odada 6 erkek ve 5 kadın var. Odadan 3 erkek ve 2 kadın kaç şekilde seçilebilir?
Solution
6 erkekten 3 erkek seçmenin yolu $ ^ 6C_ {3} $ ve 5 kadından 2 kadını seçmenin yolu $ ^ 5C_ {2} $ şeklindedir.
Dolayısıyla, toplam yol sayısı - $ ^ 6C_ {3} \ times ^ 5C_ {2} = 20 \ times 10 = 200 $ şeklindedir
Problem 3
Toplam 9 öğrenciden 3 öğrenciden oluşan 3 farklı grubu kaç yolla seçebilirsiniz?
Solution
Grupları 1, 2 ve 3 olarak sıralayalım
1 için 3 öğrenciye seçtiğiniz için st $ ^ 9C_ {3} $ - grubun yolların sayısının
1. grubu seçtikten sonra 2. grup için 3 öğrenci seçme yolu sayısı - $ ^ 6C_ {3} $
3 3 öğrenciye seçtiğiniz için yollar sayısı rd 1 seçtikten sonra grubun st ve 2 nd $ ^ 3C_ {3} $ - grubun
Dolayısıyla, toplam yol sayısı $ = ^ 9C_ {3} \ times ^ 6C_ {3} \ times ^ 3C_ {3} = 84 \ times 20 \ times 1 = 1680 $
Pascal'ın Kimliği
İlk 17 Blaise Pascal ile elde Paskal kimliği, inci yüzyılda, n elemanlarından k elemanları seçmek için yollar sayısı (n-1) elemanları ile (k-1) elemanları seçmek için yollar sayısının toplamına eşit olduğu durumları ve n-1 öğelerinden öğe seçmenin yollarının sayısı.
Matematiksel olarak, herhangi bir pozitif tam sayı k ve n için: $ ^ nC_ {k} = ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $
Proof -
$$ ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $$
$ = \ frac {(n-1)! } {(k-1)! (nk)! } + \ frac {(n-1)! } {k! (nk-1)! } $
$ = (n-1)! (\ frac {k} {k! (nk)!} + \ frac {nk} {k! (nk)!}) $
$ = (n-1)! \ frac {n} {k! (nk)! } $
$ = \ frac {n! } {k! (nk)! } $
$ = n_ {C_ {k}} $
Pigeonhole Prensibi
1834'te Alman matematikçi Peter Gustav Lejeune Dirichlet, çekmece ilkesi adını verdiği bir ilkeyi belirtti. Şimdi, güvercin deliği ilkesi olarak biliniyor.
Pigeonhole Principletoplam güvercin sayısından daha az güvercin deliği varsa ve her bir güvercin bir güvercin deliğine yerleştirilmişse, birden fazla güvercin içeren en az bir güvercin deliği olması gerektiğini belirtir. N> m olan m güvercin deliğine n güvercin konursa, birden fazla güvercin olduğu bir delik vardır.
Örnekler
Bir odada on adam var ve el sıkışmalarına katılıyorlar. Eğer herkes en az bir kez el sıkışırsa ve hiç kimse aynı adamın elini birden fazla sıkmazsa, aynı sayıda el sıkışmasına iki adam katılır.
30 kişilik bir sınıfta isimleri aynı alfabe ile başlayan en az iki kişi olmalıdır.
Dahil Etme-Dışlama ilkesi
Inclusion-exclusion principlebirden çok ayrık olmayan kümenin birleşiminin esas sayısını hesaplar. İki grup A ve B için, ilke şu şekildedir:
$ | A \ fincan B | = | A | + | B | - | A \ cap B | $
Üç set A, B ve C için ilke şu şekildedir:
$ | A \ fincan B \ fincan C | = | A | + | B | + | C | - | A \ cap B | - | A \ cap C | - | B \ cap C | + | A \ cap B \ cap C | $
Genelleştirilmiş formül -
$ | \ bigcup_ {i = 1} ^ {n} A_i | = \ sum \ limits_ {1 \ leq i <j <k \ leq n} | A_i \ cap A_j | + \ sum \ limits_ {1 \ leq i < j <k \ leq n} | A_i \ cap A_j \ cap A_k | - \ dots + (- 1) ^ {\ pi-1} | A_1 \ cap \ dots \ cap A_2 | $
Problem 1
1'den 50'ye kadar kaç tam sayı 2 veya 3'ün katlarıdır, ancak ikisi birden değildir?
Solution
1'den 100'e kadar, 50 $ / 2 = 25 $ sayıları 2'nin katlarıdır.
3'ün katları 50 $ / 3 = 16 $ sayı vardır.
Hem 2 hem de 3'ün katları olan 50 $ / 6 = 8 $ sayıları vardır.
Yani, $ | A | = 25 $, $ | B | = 16 $ ve $ | A \ cap B | = 8 $.
$ | A \ fincan B | = | A | + | B | - | A \ cap B | = 25 + 16 - 8 = 33 $
Problem 2
50 kişilik bir grupta 24'ü soğuk içecekleri, 36'sı sıcak içecekleri sever ve her öğrenci iki içecekten en az birini sever. Kaç kişi hem kahve hem de çayı sever?
Solution
X, soğuk içecekleri seven öğrenciler, Y ise sıcak içecekleri seven insanlar olsun.
Yani, $ | X \ cup Y | = 50 $, $ | X | = 24 $, $ | Y | = 36 $
$ | X \ cap Y | = | X | + | Y | - | X \ cup Y | = 24 + 36 - 50 = 60 - 50 = 10 $
Dolayısıyla hem çay hem de kahveyi seven 10 öğrenci var.