Matematika Diskrit - Teori Menghitung
Dalam kehidupan sehari-hari, seringkali seseorang perlu mencari tahu jumlah semua kemungkinan hasil untuk serangkaian peristiwa. Misalnya, berapa cara yang dipilih majelis hakim yang terdiri dari 6 laki-laki dan 4 perempuan dari 50 laki-laki dan 38 perempuan? Berapa banyak 10 angka PAN berhuruf berbeda yang dapat dibuat sedemikian rupa sehingga lima huruf pertama adalah huruf kapital, empat angka berikutnya adalah digit dan yang terakhir adalah huruf kapital. Untuk memecahkan masalah ini, teori penghitungan matematika digunakan.Counting terutama mencakup aturan penghitungan dasar, aturan permutasi, dan aturan kombinasi.
Aturan Jumlah dan Produk
Itu Rule of Sum dan Rule of Product digunakan untuk menguraikan soal-soal penghitungan yang sulit menjadi soal-soal sederhana.
The Rule of Sum- Jika urutan tugas $ T_1, T_2, \ dots, T_m $ masing-masing dapat dilakukan dalam $ w_1, w_2, \ dots w_m $ (syaratnya adalah tidak ada tugas yang dapat dilakukan secara bersamaan), maka banyaknya cara untuk lakukan salah satu dari tugas ini adalah $ w_1 + w_2 + \ dots + w_m $. Jika kita menganggap dua tugas A dan B yang saling terpisah (yaitu $ A \ cap B = \ emptyset $), maka secara matematis $ | A \ cup B | = | A | + | B | $
The Rule of Product- Jika urutan tugas $ T_1, T_2, \ dots, T_m $ dapat diselesaikan dalam $ w_1, w_2, \ dots w_m $ cara masing-masing dan setiap tugas tiba setelah terjadinya tugas sebelumnya, maka ada $ w_1 \ kali w_2 \ times \ dots \ times w_m $ cara untuk melakukan tugas. Secara matematis, jika tugas B tiba setelah tugas A, maka $ | A \ times B | = | A | \ times | B | $
Contoh
Question- Seorang anak laki-laki tinggal di X dan ingin bersekolah di Z. Dari rumahnya X dia harus mencapai Y terlebih dahulu dan kemudian Y ke Z. Dia dapat pergi dari X ke Y melalui 3 rute bus atau 2 rute kereta. Dari sana, ia dapat memilih 4 rute bus atau 5 rute kereta untuk mencapai Z. Ada berapa cara untuk pergi dari X ke Z?
Solution- Dari X ke Y, dia bisa masuk $ 3 + 2 = 5 $ cara (Aturan Jumlah). Setelah itu, dia bisa pergi Y ke Z dalam $ 4 + 5 = 9 $ cara (Aturan Jumlah). Oleh karena itu dari X ke Z dia bisa masuk $ 5 \ times 9 = 45 $ cara (Aturan Produk).
Permutasi
SEBUAH permutationadalah pengaturan dari beberapa elemen yang urutannya penting. Dengan kata lain Permutasi adalah Kombinasi elemen yang teratur.
Contoh
Dari himpunan S = {x, y, z} dengan mengambil dua sekaligus, semua permutasi adalah -
$ xy, yx, xz, zx, yz, zy $.
Kita harus membentuk permutasi tiga digit angka dari satu set angka $ S = \ lbrace 1, 2, 3 \ rbrace $. Tiga digit angka yang berbeda akan terbentuk saat kita menyusun digitnya. Permutasi akan menjadi = 123, 132, 213, 231, 312, 321
Jumlah Permutasi
Jumlah permutasi 'n' hal berbeda yang diambil 'r' pada satu waktu dilambangkan dengan $ n_ {P_ {r}} $
$$ n_ {P_ {r}} = \ frac {n!} {(n - r)!} $$
dimana $ n! = 1.2.3. \ titik (n - 1) .n $
Proof - Biarkan ada 'n' elemen yang berbeda.
Ada banyak cara untuk mengisi tempat pertama. Setelah mengisi tempat pertama (n-1) jumlah elemen tersisa. Karenanya, ada (n-1) cara untuk mengisi tempat kedua. Setelah mengisi tempat pertama dan kedua, tersisa (n-2) jumlah elemen. Karenanya, ada (n-2) cara untuk mengisi tempat ketiga. Sekarang kita dapat menggeneralisasi jumlah cara untuk mengisi tempat ke-r sebagai [n - (r – 1)] = n – r + 1
Jadi, totalnya tidak. cara untuk mengisi dari tempat pertama hingga tempat ke-r -
$ n_ {P_ {r}} = n (n-1) (n-2) ..... (nr + 1) $
$ = [n (n-1) (n-2) ... (nr + 1)] [(nr) (nr-1) \ titik 3.2.1] / [(nr) (nr-1) \ titik 3.2.1] $
Karenanya,
$ n_ {P_ {r}} = n! / (nr)! $
Beberapa rumus permutasi penting
Jika ada n elemen yang $ a_1 $ adalah sejenis, $ a_2 $ adalah sejenis dari jenis lain; $ a_3 $ serupa dari jenis ketiga dan seterusnya dan $ a_r $ adalah $ r ^ {th} $ kind, di mana $ (a_1 + a_2 + ... a_r) = n $.
Maka jumlah permutasi dari n objek ini adalah = $ n! / [(a_1! (a_2!) \ dots (a_r!)] $.
Jumlah permutasi dari n elemen berbeda yang mengambil n elemen sekaligus = $ n_ {P_n} = n! $
Jumlah permutasi dari n elemen berbeda yang mengambil r elemen pada satu waktu, saat x hal tertentu selalu menempati tempat tertentu = $ n-x_ {p_ {rx}} $
Jumlah permutasi dari n elemen yang berbeda ketika r benda tertentu selalu bersatu adalah - $ r! (n − r + 1)! $
Jumlah permutasi dari n elemen yang berbeda ketika r hal tertentu tidak pernah bersatu adalah - $ n! - [r! (n − r + 1)!] $
Jumlah permutasi melingkar dari n elemen berbeda yang diambil x elemen pada saat = $ ^ np_ {x} / x $
Jumlah permutasi melingkar dari n hal yang berbeda = $ ^ np_ {n} / n $
Beberapa masalah
Problem 1 - Dari sekumpulan 6 kartu yang berbeda, berapa banyak cara kita dapat mengubahnya?
Solution- Karena kita mengambil 6 kartu sekaligus dari setumpuk 6 kartu, permutasi akan menjadi $ ^ 6P_ {6} = 6! = 720 $
Problem 2 - Dalam berapa cara susunan huruf dari kata 'READER'?
Solution - Ada 6 huruf word (2 E, 1 A, 1D dan 2R.) Pada kata 'READER'.
Permutasi akan menjadi $ = 6! / \: [(2!) (1!) (1!) (2!)] = 180. $
Problem 3 - Bagaimana huruf pada kata 'ORANGE' dapat diatur sehingga konsonan hanya menempati posisi genap?
Solution- Ada 3 vokal dan 3 konsonan pada kata 'ORANGE'. Banyaknya cara menyusun konsonan di antara mereka sendiri $ = ^ 3P_ {3} = 3! = 6 $. Sisa 3 tempat kosong akan diisi oleh 3 vokal di $ ^ 3P_ {3} = 3! = 6 $ cara. Oleh karena itu, jumlah permutasi adalah $ 6 \ dikali 6 = 36 $
Kombinasi
SEBUAH combination adalah pemilihan beberapa elemen yang urutannya tidak menjadi masalah.
Banyaknya kombinasi dari n benda, diambil r sekaligus adalah -
$$ ^ nC_ {{r}} = \ frac {n! } {r! (nr)! } $$
Problem 1
Tentukan jumlah himpunan bagian dari himpunan $ \ lbrace1, 2, 3, 4, 5, 6 \ rbrace $ yang memiliki 3 elemen.
Solution
Kardinalitas himpunan adalah 6 dan kita harus memilih 3 elemen dari himpunan. Di sini, pemesanan tidak menjadi masalah. Karenanya, jumlah subset akan menjadi $ ^ 6C_ {3} = 20 $.
Problem 2
Ada 6 pria dan 5 wanita dalam satu ruangan. Dalam berapa cara kita bisa memilih 3 pria dan 2 wanita dari kamar?
Solution
Jumlah cara memilih 3 pria dari 6 pria adalah $ ^ 6C_ {3} $ dan jumlah cara memilih 2 wanita dari 5 wanita adalah $ ^ 5C_ {2} $
Oleh karena itu, jumlah total cara adalah - $ ^ 6C_ {3} \ times ^ 5C_ {2} = 20 \ times 10 = 200 $
Problem 3
Berapa banyak cara Anda dapat memilih 3 kelompok berbeda yang terdiri dari 3 siswa dari total 9 siswa?
Solution
Mari kita beri nomor pada kelompok sebagai 1, 2 dan 3
Untuk memilih 3 siswa untuk 1 st kelompok, jumlah cara - $ ^ 9C_ {3} $
Jumlah cara memilih 3 siswa untuk 2 nd kelompok setelah memilih kelompok 1 - $ ^ 6C_ {3} $
Jumlah cara memilih 3 siswa untuk 3 rd grup setelah memilih 1 st dan 2 nd kelompok - $ ^ 3C_ {3} $
Karenanya, jumlah total cara $ = ^ 9C_ {3} \ times ^ 6C_ {3} \ times ^ 3C_ {3} = 84 \ times 20 \ times 1 = 1680 $
Identitas Pascal
Identitas Pascal yang pertama kali diturunkan oleh Blaise Pascal pada abad ke - 17 menyatakan bahwa banyaknya cara pemilihan k unsur dari n unsur sama dengan penjumlahan bilangan cara pemilihan (k-1) unsur dari (n-1) unsur. dan jumlah cara untuk memilih elemen dari n-1 elemen.
Secara matematis, untuk setiap bilangan bulat positif k dan n: $ ^ 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}} $
Prinsip Pigeonhole
Pada tahun 1834, matematikawan Jerman, Peter Gustav Lejeune Dirichlet, menyatakan prinsip yang disebutnya prinsip laci. Sekarang, ini dikenal sebagai prinsip lubang merpati.
Pigeonhole Principlemenyatakan bahwa jika lubang merpati lebih sedikit dari jumlah total merpati dan setiap merpati dimasukkan ke dalam lubang merpati, maka harus ada setidaknya satu lubang merpati dengan lebih dari satu merpati. Jika n merpati dimasukkan ke dalam m pigeonholes di mana n> m, ada lubang dengan lebih dari satu pigeonholes.
Contoh
Sepuluh pria berada di sebuah ruangan dan mereka sedang berjabat tangan. Jika setiap orang berjabat tangan setidaknya sekali dan tidak ada orang yang menjabat tangan orang yang sama lebih dari sekali, maka dua orang mengambil bagian dalam jumlah jabat tangan yang sama.
Setidaknya harus ada dua orang di kelas 30 yang namanya diawali dengan alfabet yang sama.
Prinsip Inklusi-Pengecualian
Itu Inclusion-exclusion principlemenghitung bilangan pokok dari gabungan beberapa set non-disjoint. Untuk dua himpunan A dan B, prinsipnya menyatakan -
$ | A \ cangkir B | = | A | + | B | - | A \ cap B | $
Untuk tiga himpunan A, B dan C, prinsipnya menyatakan -
$ | A \ cangkir B \ cangkir C | = | A | + | B | + | C | - | A \ cap B | - | A \ cap C | - | B \ cap C | + | A \ cap B \ cap C | $
Rumus umum -
$ | \ bigcup_ {i = 1} ^ {n} A_i | = \ sum \ limit_ {1 \ leq i <j <k \ leq n} | A_i \ cap A_j | + \ sum \ limit_ {1 \ leq i < j <k \ leq n} | A_i \ cap A_j \ cap A_k | - \ titik + (- 1) ^ {\ pi-1} | A_1 \ cap \ dots \ cap A_2 | $
Problem 1
Berapa banyak bilangan bulat dari 1 sampai 50 yang merupakan kelipatan 2 atau 3 tetapi tidak keduanya?
Solution
Dari 1 sampai 100, ada $ 50/2 = 25 $ angka yang merupakan kelipatan 2.
Ada $ 50/3 = 16 $ angka yang merupakan kelipatan 3.
Ada $ 50/6 = 8 $ angka yang merupakan kelipatan dari 2 dan 3.
Jadi, $ | A | = 25 $, $ | B | = 16 $ dan $ | A \ cap B | = 8 $.
$ | A \ cangkir B | = | A | + | B | - | A \ cap B | = 25 + 16 - 8 = 33 $
Problem 2
Dalam kelompok yang terdiri dari 50 siswa, 24 orang menyukai minuman dingin dan 36 menyukai minuman panas dan setiap siswa menyukai setidaknya satu dari dua minuman tersebut. Berapa banyak yang menyukai kopi dan teh?
Solution
Misalkan X adalah kumpulan siswa yang menyukai minuman dingin dan Y adalah kumpulan orang yang menyukai minuman panas.
Jadi, $ | X \ cangkir Y | = 50 $, $ | X | = 24 $, $ | Y | = 36 $
$ | X \ cap Y | = | X | + | Y | - | X \ cangkir Y | = 24 + 36 - 50 = 60 - 50 = 10 $
Makanya, ada 10 siswa yang menyukai teh dan kopi.