Kaidah pencacahan

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 $A$ dan $B$ dengan anggota himpunan adalah $a$ dan $b$ dan bila kedua himpunan adalah saling lepas, maka banyaknya cara mengambil satu anggota tersebut adalah dengan cara menjumlahkan anggota pada kedua himpunan, yakni $a+b$ .

Lebih formalnya, bila $S_{1},\dots ,S_{n}$ himpunan lepas berpasangan, maka aturan penjumlahan dapat dirumuskan sebagai

|S_{1}|+|S_{2}|+\cdots +|S_{n}|=|S_{1}\cup S_{2}\cup \cdots \cup S_{n}|

^[4]^[5]

atau disingkat sebagai

\sum _{i=1}^{n}|S_{i}|=\left|\bigcup _{i=1}^{n}S_{i}\right|

.

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

1+1+1+1+1=5

.

Aturan perkalian[sunting | sunting sumber]

Aturan perkalian (atau aturan dasar mengalikan^[6]) adalah aturan yang menyatakan bahwa bila ada $n(A)$ cara untuk $A$ dan $n(B)$ cara untuk $B$ , maka banyaknya cara untuk $A$ dan $B$ adalah $n(A)\cdot n(B)$ . Sebagai permisalan, pada gambar di samping, diketahui $A$ memiliki tiga elemen, yakni $\{1,2,3\}$ . Hal yang serupa untuk $B$ yang memiliki tiga elemen, yakni $\{1,2,3\}$ . Maka, banyaknya cara untuk mengkombinasikan $\{A,B\}$ dan $\{1,2,3\}$ adalah $3\times 2=6$ cara.

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

|S_{1}|\cdot |S_{2}|\cdots |S_{n}|=|S_{1}\times S_{2}\times \cdots \times S_{n}|

.

Prinsip inklusi-eksklusi[sunting | sunting sumber]

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

\left|A\cup B\right|=\left|A\right|+\left|B\right|-\left|A\cap B\right|

.

Pembuktian bijektif[sunting | sunting sumber]

Pembuktian bijektif ialah teorema yang mendefinisikan jika fungsi $f$ yang memetakan himpunan $A$ ke himpunan $B$ adalah bijektif, maka diperoleh bahwa $|A|=|B|$ .

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 $m$ dan $n$ , $n>m$ , jika $n$ burung ditaruh di dalam $m$ 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 $x$ di dalam bentuk formal deret kuasa, fungsi ini dapat merepresentasikan barisan secara efektif.^[10] Fungsi pembangkit pada barisan $a_{0},a_{1},a_{2},\dots$ dapat dirumuskan sebagai

G(x)=\sum _{n=0}^{\infty }a_{n}x^{n}

.

Relasi rekurensi[sunting | sunting sumber]

Relasi rekurensi adalah suatu persamaan yang bergantung pada suku-suku sebelumnya. Lebih umumnya, relasi rekurensi pada suku $a_{n}$ (dimana $n$ bilangan bulat positif) bergantung pada suku-suku sebelumnya, yakni $a_{n-1},a_{n-2},\dots ,a_{1}$ .^[11]

Rujukan[sunting | sunting sumber]

Catatan kaki[sunting | sunting sumber]

^ Asmar Achmad, Modul Matematika Kelas XII KD 3.3, hlm. 6
^ Astawan, Made (2016-07-22). "Aturan Dasar Menghitung". Ilmu Hitung. Diakses tanggal 2021-12-19.
^ Setya Budhi 2006, hlm. 147.
^ 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.
^ Penner, R. C. (1999). Discrete Mathematics: Proof Techniques and Mathematical Structures (dalam bahasa Inggris). World Scientific. ISBN 978-981-02-4088-2.
^ Setya Budhi 2006, hlm. 151.
^ Johnston, William, and Alex McAllister. A transition to advanced mathematics^{[pranala nonaktif permanen]}. Oxford Univ. Press, 2009. Section 5.1, hlm. 365
^ "Materi, Soal, dan Pembahasan - Prinsip Inklusi-Eksklusi - Mathcyber1997" (dalam bahasa Inggris). Diakses tanggal 2021-12-15.
^ Mamat Rahmat, Metode Double Counting untuk Pembuktian Identitas Matematika
^ Shiddiq, Mohammad Mahfuzh. "Fungsi Pembangkit - Teknik Menghitung". haimatematika. Diakses tanggal 2021-12-19.
^ "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]

Setya Budhi (2006), Langkah Awal Menuju ke Olimpiade Matematika, CV RICARDO, ISBN 979-98175-0-1

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

[FOOTNOTESetya_Budhi2006147-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.

[FOOTNOTESetya_Budhi2006151-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]