• Source: 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. 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


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




= Aturan penjumlahan

=
Aturan penjumlahan (atau aturan dasar menambah) adalah aturan yang menyatakan bahwa bila ada himpunan



A


{\displaystyle A}

dan



B


{\displaystyle B}

dengan anggota himpunan adalah



a


{\displaystyle a}

dan



b


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



a
+
b


{\displaystyle a+b}

.
Lebih formalnya, bila




S

1


,
…
,

S

n




{\displaystyle S_{1},\dots ,S_{n}}

himpunan lepas berpasangan, maka aturan penjumlahan dapat dirumuskan sebagai





|


S

1



|

+

|


S

2



|

+
⋯
+

|


S

n



|

=

|


S

1


∪

S

2


∪
⋯
∪

S

n



|



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


atau disingkat sebagai





∑

i
=
1


n



|


S

i



|

=

|


⋃

i
=
1


n



S

i



|



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




1
+
1
+
1
+
1
+
1
=
5


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

.




= Aturan perkalian

=
Aturan perkalian (atau aturan dasar mengalikan) adalah aturan yang menyatakan bahwa bila ada



n
(
A
)


{\displaystyle n(A)}

cara untuk



A


{\displaystyle A}

dan



n
(
B
)


{\displaystyle n(B)}

cara untuk



B


{\displaystyle B}

, maka banyaknya cara untuk



A


{\displaystyle A}

dan



B


{\displaystyle B}

adalah



n
(
A
)
⋅
n
(
B
)


{\displaystyle n(A)\cdot n(B)}

. Sebagai permisalan, pada gambar di samping, diketahui



A


{\displaystyle A}

memiliki tiga elemen, yakni



{
1
,
2
,
3
}


{\displaystyle \{1,2,3\}}

. Hal yang serupa untuk



B


{\displaystyle B}

yang memiliki tiga elemen, yakni



{
1
,
2
,
3
}


{\displaystyle \{1,2,3\}}

. Maka, banyaknya cara untuk mengkombinasikan



{
A
,
B
}


{\displaystyle \{A,B\}}

dan



{
1
,
2
,
3
}


{\displaystyle \{1,2,3\}}

adalah



3
×
2
=
6


{\displaystyle 3\times 2=6}

cara.
Aturan perkalian dalam teori himpunan dapat dianggap sebagai hasilkali Kartesius (dilambangkan



×


{\displaystyle \times }

), yakni





|


S

1



|

⋅

|


S

2



|

⋯

|


S

n



|

=

|


S

1


×

S

2


×
⋯
×

S

n



|



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

.




Prinsip inklusi-eksklusi



Prinsip inklusi-eksklusi merupakan perluasan diagram Venn yang melibatkan himpunan-himpunan. Prinsip ini kemudian diaplikasi secara variatif. Untuk diberikan suatu himpunan



A


{\displaystyle A}

dan



B


{\displaystyle B}

, prinsip inklusi-eksklusi dirumuskan sebagai





|

A
∪
B

|

=

|
A
|

+

|
B
|

−

|

A
∩
B

|



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

.




Pembuktian bijektif



Pembuktian bijektif ialah teorema yang mendefinisikan jika fungsi



f


{\displaystyle f}

yang memetakan himpunan



A


{\displaystyle A}

ke himpunan



B


{\displaystyle B}

adalah bijektif, maka diperoleh bahwa




|

A

|

=

|

B

|



{\displaystyle |A|=|B|}

.




Perhitungan ganda


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.




Prinsip rumah burung


Prinsip rumah burung atau prinsip sarang merpati atau prinsip sangkar merpati menyatakan bahwa untuk dua bilangan asli



m


{\displaystyle m}

dan



n


{\displaystyle n}

,



n
>
m


{\displaystyle n>m}

, jika



n


{\displaystyle n}

burung ditaruh di dalam



m


{\displaystyle m}

rumah atau kotak, maka paling sedikit satu kotak berisi lebih dari satu burung.




Fungsi pembangkit


Fungsi pembangkit merupakan suatu fungsi yang berbentuk deret kuasa. Dengan menjadikan suku-suku barisan menjadi koefisien dari variabel



x


{\displaystyle x}

di dalam bentuk formal deret kuasa, fungsi ini dapat merepresentasikan barisan secara efektif. Fungsi pembangkit pada barisan




a

0


,

a

1


,

a

2


,
…


{\displaystyle a_{0},a_{1},a_{2},\dots }

dapat dirumuskan sebagai




G
(
x
)
=

∑

n
=
0


∞



a

n



x

n




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

.




Relasi rekurensi



Relasi rekurensi adalah suatu persamaan yang bergantung pada suku-suku sebelumnya. Lebih umumnya, relasi rekurensi pada suku




a

n




{\displaystyle a_{n}}

(dimana



n


{\displaystyle n}

bilangan bulat positif) bergantung pada suku-suku sebelumnya, yakni




a

n
−
1


,

a

n
−
2


,
…
,

a

1




{\displaystyle a_{n-1},a_{n-2},\dots ,a_{1}}

.




Rujukan






= Catatan kaki

=




= Referensi

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

Kata Kunci Pencarian:

• Kaidah pencacahan
• Urutan total
• Romawi Kuno
• Logaritma
• Unsur kimia
• Forensik digital
• Daftar dewa-dewi Romawi
• Sejarah kimia
• Daftar padanan istilah tata boga
• Daftar masalah matematika yang belum terpecahkan