Kajian permutasi dan kombinasi dalam prinsip Pigeonhole

ABSTRAK

Suatu Prinsip yang menarik, yang dapat terlihat bukan suatu hal yang luar biasa, namun pada kenyataanya prinsip ini sangat berarti dalam penggunaanya. Prinsip ini dikenal dengan nama Prinsip Pigeonhole.

Prinsip Pigeonhole atau dikenal juga sebagai Prinsip Laci Dirichlet atau Prinsip Kotak Sepatu. Prinsip ini sering kali memudahkan dalam membuktikan keberadaan suatu obyek dengan suatu karakteristik tertentu dalam suatu tempat. Prinsip ini didefinisikan sebagai berikut:

Jika terdapat m obyek menempati n tempat, dan m > n, maka sedikitnya satu tempat akan dihuni dua atau lebih obyek, dimana m dan n bilangan bulat positif.

Secara Umum, jika terdapat m obyek menempati n tempat, dan m > (k,n), maka sedikitnya satu tempat akan dihuni sebanyak k atau lebih obyek, dimana m,k dan n bilangan bulat positif.

Prinsip Pigeonhole ini tidak memberitahukan bagaimana mencari suatu obyek dengan karakteristik tertentu di dalam tempat atau berapa banyak obyek tersebut. Oleh sebab itu diperlukan berbagai metode perhitungan Matematika Diskrit dalam mencari dan menentukan banyaknya obyek dalam suatu tempat. Salah satu metode yang perhitungan dalam Matematika Diskrit adalah Permutasi dan Kombinasi. Metode ini dapat menunjukkan banyaknya suatu susuna yang dapat dibentuk dari suatu kumpulan obyek yang berbeda dalam suatu tempat, baik yang dipilih seluruhnya atau sebagian. Selain itu dapat juga menunjukkan pemilihan obyek-obyek tersebut dengan susunan tidak terurut, serta dapat menunjukkan susunan obyek dimana obyek-obyek tersebut terdapat beberapa kumpulan obyek yang identik. Dengan demikian metode ini dapat mencari obyek dengan suatu karakteristik tertentu dalam suatu tempat dan dapat menentukan banyaknya obyek tersebut.