Lompat ke isi

Kaidah pencacahan

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas

Dalam matematika, khususnya di cabang matematika kombinatorik, kaidah pencacahan merupakan aturan untuk menghitung banyaknya susunan obyek-obyek tanpa harus merinci semua kemungkinan susunannya.[1] Kaidah pencacahan biasanya meliputi aturan dasar menghitung (seperti aturan penjumlahan dan aturan perkalian), prinsip inklusi-eksklusi, pembuktian bijektif, perhitungan ganda, prinsip rumah burung, fungsi pembangkit, dan relasi rekurensi.

Aturan dasar menghitung

[sunting | sunting sumber]

Aturan dasar menghitung meliputi kajian dasar dalam cabang matematika (yaitu kombinatorika), di antaranya aturan penjumlahan dan aturan perkalian.[2]

Aturan penjumlahan

[sunting | sunting sumber]

Aturan penjumlahan (atau aturan dasar menambah[3]) adalah aturan yang menyatakan bahwa bila ada himpunan dan dengan anggota himpunan adalah dan dan bila kedua himpunan adalah saling lepas, maka banyaknya cara mengambil satu anggota tersebut adalah dengan cara menjumlahkan anggota pada kedua himpunan, yakni .

Lebih formalnya, bila himpunan lepas berpasangan, maka aturan penjumlahan dapat dirumuskan sebagai

[4][5]

atau disingkat sebagai

.

Untuk memahami lebih lanjut, perhatikan contoh berikut: diberikan kelima bangun datar yang berbeda, yakni persegi, lingkaran, segitiga, persegi panjang, dan trapesium. Maka, banyaknya cara mengambil salah satu dari kelima bangun datar tersebut adalah

.
Ilustrasi mengenai aturan perkalian.

Aturan perkalian

[sunting | sunting sumber]

Aturan perkalian (atau aturan dasar mengalikan[6]) adalah aturan yang menyatakan bahwa bila ada cara untuk dan cara untuk , maka banyaknya cara untuk dan adalah . Sebagai permisalan, pada gambar di samping, diketahui memiliki tiga elemen, yakni . Hal yang serupa untuk yang memiliki tiga elemen, yakni . Maka, banyaknya cara untuk mengkombinasikan dan adalah cara.

Aturan perkalian dalam teori himpunan dapat dianggap sebagai hasilkali Kartesius[7] (dilambangkan ), yakni

.

Prinsip inklusi-eksklusi

[sunting | sunting sumber]
Diagram Venn menunjukkan gabungan pada kedua himpunan dan bukan daerah himpunan berwarna putih..

Prinsip inklusi-eksklusi merupakan perluasan diagram Venn yang melibatkan himpunan-himpunan. Prinsip ini kemudian diaplikasi secara variatif.[8] Untuk diberikan suatu himpunan dan , prinsip inklusi-eksklusi dirumuskan sebagai

.

Pembuktian bijektif

[sunting | sunting sumber]

Pembuktian bijektif ialah teorema yang mendefinisikan jika fungsi yang memetakan himpunan ke himpunan adalah bijektif, maka diperoleh bahwa .

Perhitungan ganda

[sunting | sunting sumber]

Perhitungan ganda merupakan teknik pembuktian kombinatorial. Teknik pembuktian ini digunakan untuk membuktikan persamaan dua ekspresi dengan menunjukkan bahwa kedua ekspresi adalah dua cara menghitung kardinalitas sebuah himpunan yang sama.[9]

Prinsip rumah burung

[sunting | sunting sumber]

Prinsip rumah burung atau prinsip sarang merpati atau prinsip sangkar merpati menyatakan bahwa untuk dua bilangan asli dan , , jika burung ditaruh di dalam rumah atau kotak, maka paling sedikit satu kotak berisi lebih dari satu burung.

Fungsi pembangkit

[sunting | sunting sumber]

Fungsi pembangkit merupakan suatu fungsi yang berbentuk deret kuasa. Dengan menjadikan suku-suku barisan menjadi koefisien dari variabel di dalam bentuk formal deret kuasa, fungsi ini dapat merepresentasikan barisan secara efektif.[10] Fungsi pembangkit pada barisan dapat dirumuskan sebagai

.

Relasi rekurensi

[sunting | sunting sumber]

Relasi rekurensi adalah suatu persamaan yang bergantung pada suku-suku sebelumnya. Lebih umumnya, relasi rekurensi pada suku (dimana bilangan bulat positif) bergantung pada suku-suku sebelumnya, yakni .[11]

Catatan kaki

[sunting | sunting sumber]
  1. ^ Asmar Achmad, Modul Matematika Kelas XII KD 3.3, hlm. 6
  2. ^ Astawan, Made (2016-07-22). "Aturan Dasar Menghitung". Ilmu Hitung. Diakses tanggal 2021-12-19. 
  3. ^ Setya Budhi 2006, hlm. 147.
  4. ^ Leung, K. T.; Cheung, P. H. (1988-04-01). Fundamental Concepts of Mathematics (dalam bahasa Inggris). Hong Kong University Press. ISBN 978-962-209-181-8. 
  5. ^ Penner, R. C. (1999). Discrete Mathematics: Proof Techniques and Mathematical Structures (dalam bahasa Inggris). World Scientific. ISBN 978-981-02-4088-2. 
  6. ^ Setya Budhi 2006, hlm. 151.
  7. ^ Johnston, William, and Alex McAllister. A transition to advanced mathematics[pranala nonaktif permanen]. Oxford Univ. Press, 2009. Section 5.1, hlm. 365
  8. ^ "Materi, Soal, dan Pembahasan - Prinsip Inklusi-Eksklusi - Mathcyber1997" (dalam bahasa Inggris). Diakses tanggal 2021-12-15. 
  9. ^ Mamat Rahmat, Metode Double Counting untuk Pembuktian Identitas Matematika
  10. ^ Shiddiq, Mohammad Mahfuzh. "Fungsi Pembangkit - Teknik Menghitung". haimatematika. Diakses tanggal 2021-12-19. 
  11. ^ "Relasi Rekurensi". emodul-matematika.fmipa.unej.ac.id. Diarsipkan dari versi asli tanggal 2020-08-07. Diakses tanggal 2021-12-19. 

Referensi

[sunting | sunting sumber]