Menghitung : Berapa jumlah susunan objek yang mungkin dibuat?

Kombinatorika juga mempelajari cara untuk menghitung banyaknya susunan objek tanpa perlu mendaftar.

kombinatorika

Kita telah melihat permasalahan kombinatorika untuk menemukan salah satu susunan objek, dilanjutkan dengan mendaftarkan seluruh kemungkinan susunannya.

Sambil mendaftarkan, kamu akan tergoda untuk menanyakan, Ada berapa banyak semua kemungkinannya? Pertanyaan ini sangat penting karena dapat membantumu mengambil keputusan untuk berhenti mendaftar ataupun meneruskannya.

Dalam banyak kasus, kemungkinan susunan bisa menjadi terlalu banyak.

Berapa warna?

Dalam halaman web seperti yang sedang kamu lihat sekarang, biasanya setiap warna dituliskan menggunakan kode 6 digit heksadesimal. Digit heksadesimal terdiri atas 16 simbol: 10 angka dari 0-9, dan 6 huruf dari A-F.

#349D3F
#194D34
#D0718E
#5E8BC9
#C68753
#D2CDEE
#B4403C
#24516B

Dengan struktur kode digit warna semacam ini, ada berapa warna yang dapat dihasilkan?

Berapa ya?

Kode warna ini terdiri dari 7 karakter. Karakter pertama sudah pasti #, jadi hanya satu kemungkinan.

#
1

Karakter kedua bisa salah satu dari 0-9 atau A-F, totalnya ada 16 kemungkinan.

#	0-9,A-F
1	16

Demikian juga karakter ketiga masih sama: Salah satu dari 0-9, A-F. Jadi totalnya ada 16 kemungkinan.

#	0-9,A-F	0-9,A-F
1	16	16

Sejauh ini, karena untuk masing-masing digit kedua yang bisa didaftarkan bergilir 0 hingga F (16 kemungkinan), bisa disusul dengan digit ketiga yang bergilir dari 0-F (16 kemungkinan), berarti totalnya adalah 16×16 = 256.

#	0	0
		...
		F
	1	0
		...
		F
	2	0
		...
		F
	...	0
		...
		F
	F	0
		...
		F

Demikian seterusnya, hingga keenam digitnya:

#	0-F	0-F	0-F	0-F	0-F	0-F
1	16	16	16	16	16	16

Total seluruh kemungkinannya adalah:

1×16×16×16×16×16×16

= 16⁶
= 16.777.216

Jadi totalnya ada 16,7 juta warna berbeda yang dapat diwakili oleh kode seperti ini.

Teorema 4 warna

Tidak semua susunan dapat dihitung dengan mudah. Ada sebuah teorema dalam teori Graf yang disebut sebagai teorema empat warna. Teorema ini disebutkan pertama kali oleh Francis Guthrie pada tahun 1852, dan baru berhasil dibuktikan pada tahun 1976 oleh Kenneth Appel dan Wolfgang Haken. Jadi perlu kurang lebih 125 tahun untuk membuktikan teorema ini.

Permasalahannya seperti ini:

Dalam sebuah peta, kita memberi warna yang berbeda untuk daerah yang bersebelahan agar daerah-daerah tersebut dapat dibedakan secara sekilas. Misalnya provinsi Surakarta dengan Yogyakarta bersebelahan, maka jika kita mewarnai Surakarta dengan warna hijau, Yogyakarta tidak boleh lagi diwarnai dengan hijau.

Tentunya kita dapat mewarnai setiap daerah dengan warna yang berbeda-beda. Namun jika sebuah negara memiliki 50 provinsi, berarti kita akan memerlukan 50 warna yang berbeda. Tentunya tidak perlu sebanyak itu, bukan? Ternyata, kita hanya memerlukan cukup empat warna saja untuk mewarnai peta dalam bidang dua dimensi.

Berikutnya: Optimasi