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 meliputi kajian dasar dalam cabang matematika (yaitu kombinatorika), di antaranya aturan penjumlahan dan aturan perkalian.^[2]

Aturan penjumlahan (atau aturan dasar menambah^[3]) adalah aturan yang menyatakan bahwa bila ada himpunan ${\displaystyle A}$ dan ${\displaystyle B}$ dengan anggota himpunan adalah ${\displaystyle a}$ dan ${\displaystyle b}$ dan bila kedua himpunan adalah saling lepas, maka banyaknya cara mengambil satu anggota tersebut adalah dengan cara menjumlahkan anggota pada kedua himpunan, yakni ${\displaystyle a+b}$.

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

${\displaystyle |S_{1}|+|S_{2}|+\cdots +|S_{n}|=|S_{1}\cup S_{2}\cup \cdots \cup S_{n}|}$^[4][5]

atau disingkat sebagai

${\displaystyle \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

${\displaystyle 1+1+1+1+1=5}$.

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

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

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

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

${\displaystyle \left|A\cup B\right|=\left|A\right|+\left|B\right|-\left|A\cap B\right|}$.

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

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 atau prinsip sarang merpati atau prinsip sangkar merpati menyatakan bahwa untuk dua bilangan asli ${\displaystyle m}$ dan ${\displaystyle n}$, ${\displaystyle n>m}$, jika ${\displaystyle n}$ burung ditaruh di dalam ${\displaystyle m}$ rumah atau kotak, maka paling sedikit satu kotak berisi lebih dari satu burung.

Fungsi pembangkit merupakan suatu fungsi yang berbentuk deret kuasa. Dengan menjadikan suku-suku barisan menjadi koefisien dari variabel ${\displaystyle x}$ di dalam bentuk formal deret kuasa, fungsi ini dapat merepresentasikan barisan secara efektif.^[10] Fungsi pembangkit pada barisan ${\displaystyle a_{0},a_{1},a_{2},\dots }$ dapat dirumuskan sebagai

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

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

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. 

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