MATERI OLIMPIADE MATEMATIKA SMP KOMBINASI DAN PERMUTASI

Masuk ke materi Permutasi dan Kombinasi, tantangan terbesar bagi siswa SMP bukanlah menghitung faktorialnya, melainkan menganalisis kapan harus menggunakan yang mana. Dalam suasana kompetisi, soal tidak pernah secara eksplisit menyebutkan "gunakan permutasi" atau "gunakan kombinasi".

Sebagai strategi pengajaran, selalu tekankan satu pertanyaan kunci ini kepada siswa setiap kali mereka bertemu soal pencacahan: "Jika saya menukar posisi dua elemen yang terpilih, apakah hasilnya dihitung sebagai sesuatu yang baru/berbeda?" * Jika YA $\rightarrow$ Permutasi (Urutan mutlak penting).

Jika TIDAK $\rightarrow$ Kombinasi (Hanya peduli pada siapa yang terpilih, bukan posisinya).

Berikut adalah penjabaran rinci untuk kedua konsep tersebut dalam standar olimpiade:

1. Permutasi (Penyusunan)

Permutasi berkaitan dengan penempatan objek pada "slot" atau posisi tertentu yang memiliki identitas berbeda (misalnya: juara 1-2-3, posisi ketua-sekretaris, susunan angka, susunan huruf).

A. Permutasi Dasar (Memilih $r$ dari $n$ objek berbeda)

Konsep: Memilih beberapa objek lalu menyusunnya.

Rumus:

$$P(n,r) = \frac{n!}{(n-r)!}$$

Catatan: Jarang keluar dalam bentuk mentah di olimpiade. Biasanya digabung dengan aturan perkalian dasar.

B. Permutasi dengan Unsur Identik (Sangat Sering Muncul)

Konsep: Menyusun $n$ objek, tetapi ada beberapa objek yang kembar/identik (tidak bisa dibedakan satu sama lain).

Rumus: Jika dari $n$ objek terdapat $k_1$ objek tipe 1, $k_2$ objek tipe 2, dan seterusnya, maka banyak susunannya adalah:

$$\frac{n!}{k_1! \cdot k_2! \dots k_m!}$$

Aplikasi Olimpiade:

Mencari banyak anagram dari sebuah kata (contoh: susunan huruf dari kata "MATEMATIKA").

Jalur terpendek pada grid/kartesian (kombinasi langkah Kanan dan Atas).

C. Permutasi Siklis (Melingkar)

Konsep: Menyusun objek dalam lingkaran. Karena lingkaran tidak memiliki "ujung" awal atau akhir, penyusunan $(A-B-C)$ sama dengan $(B-C-A)$ dan $(C-A-B)$ jika diputar searah jarum jam.

Rumus Dasar:

$$(n-1)!$$

Aplikasi Olimpiade (Modifikasi): Soal siklis murni terlalu mudah. Biasanya soal dimodifikasi menjadi: "6 orang duduk melingkar, tetapi A dan B harus selalu berdampingan, dan C tidak boleh bersebelahan dengan D." Di sini, siswa harus menggabungkan permutasi siklis dengan prinsip "mengikat" objek (menganggap A dan B sebagai 1 kesatuan) dan prinsip komplemen.

2. Kombinasi (Pemilihan)

Kombinasi murni berfokus pada pembentukan himpunan bagian (subset). Urutan elemen di dalam himpunan tidak mengubah identitas himpunan tersebut ($\{A, B\} = \{B, A\}$).

A. Kombinasi Dasar

Konsep: Memilih $r$ objek dari $n$ objek tanpa memperhatikan urutan.

Rumus:

$$C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$

Aplikasi Olimpiade: Memilih anggota tim, berjabat tangan, atau memilih perwakilan.

B. Kombinasi dalam Geometri

Olimpiade sangat menyukai perpaduan kombinatorika dan geometri. Siswa harus bisa memetakan objek geometri menjadi titik-titik kombinasi.

Contoh Kasus: * Banyaknya diagonal segi-$n$: Memilih 2 titik dari $n$ titik untuk membuat garis $C(n,2)$, lalu dikurangi $n$ (karena $n$ garis tersebut adalah sisi luar, bukan diagonal). Rumusnya menjadi $C(n,2) - n$.

Banyaknya segitiga yang bisa dibentuk dari $n$ titik di mana tidak ada 3 titik yang segaris: $C(n,3)$.

C. Kombinasi dengan Pengulangan (Stars and Bars)

Ini adalah materi "senjata rahasia" untuk kompetisi tingkat lanjut. Seringkali siswa menghabiskan waktu mendaftar kasus satu per satu secara manual, padahal bisa diselesaikan dengan Stars and Bars.

Konsep: Mencari banyaknya solusi bulat non-negatif dari persamaan linear $x_1 + x_2 + \dots + x_k = n$. (Bayangkan mendistribusikan $n$ permen identik kepada $k$ anak).

Rumus (Solusi Bulat Non-Negatif / $x_i \ge 0$):

$$\binom{n+k-1}{k-1}$$

Rumus (Solusi Bulat Positif / $x_i \ge 1$):

$$\binom{n-1}{k-1}$$

Aplikasi Olimpiade: "Berapa banyak cara membagikan 10 apel identik kepada 3 orang anak jika setiap anak minimal mendapat 1 apel?" ---

Tips Visualisasi untuk Siswa

Untuk membedakan rumusnya secara visual, tunjukkan pada siswa bahwa rumus Kombinasi $C(n,r)$ membagi rumus Permutasi $P(n,r)$ dengan $r!$.

Jelaskan maknanya: "Kita membagi dengan $r!$ untuk 'menghapus' efek urutan dari objek-objek yang sudah terpilih tersebut, karena kita menganggap urutan itu tidak penting."

LATIHAN SOAL

1. Dari angka-angka $1, 2, 3, 4, 5, 6, 7$, akan dibentuk bilangan 4 digit tanpa angka berulang. Berapa banyak bilangan yang nilainya lebih dari $4000$ dan merupakan bilangan ganjil?
2. Dalam sebuah organisasi terdapat ketua, wakil ketua, sekretaris, dan bendahara. Jika tersedia 8 calon pengurus (termasuk Andi dan Budi), berapa banyak susunan pengurus yang mungkin jika Andi hanya bersedia menjadi ketua, dan Budi tidak bersedia menjadi sekretaris?
3. Enam buah buku berbeda yang terdiri dari 3 buku Matematika, 2 buku Fisika, dan 1 buku Biologi akan disusun berderet di rak. Berapa banyak susunan yang mungkin jika buku Fisika tidak boleh saling bersebelahan?
4. Sebuah kata sandi terdiri dari 6 karakter berbeda (kombinasi huruf dan angka). Jika harus terdiri dari tepat 4 huruf vokal dan 2 angka genap tak nol, berapa banyak kemungkinan kata sandi yang dapat dibuat? (Huruf vokal: A, E, I, O, U; Angka genap tak nol: 2, 4, 6, 8).
5. Terdapat 5 anak laki-laki dan 4 anak perempuan. Mereka akan berbaris memanjang. Berapa banyak cara menyusun barisan tersebut jika anak perempuan harus selalu berada di urutan bernomor genap?
6. Berapa banyak "kata" (susunan huruf) baru yang dapat dibentuk dari kata OLIMPIADE sedemikian rupa sehingga semua huruf vokal (O, I, I, A, E) saling bersebelahan?
7. Seekor semut berada di titik $(0,0)$ dan ingin pergi ke titik $(6,4)$ dengan hanya bergerak ke kanan (1 satuan) atau ke atas (1 satuan). Berapa banyak rute yang bisa dilalui jika semut wajib melewati titik $(3,2)$?
8. Terdapat 10 bendera yang terdiri dari 4 bendera merah identik, 3 bendera kuning identik, dan 3 bendera hijau identik. Berapa banyak susunan bendera pada satu tiang vertikal jika bendera merah tidak boleh diletakkan di ujung atas maupun ujung bawah?
9. Sebuah gedung memiliki 8 lantai. Sebuah lift bergerak dari lantai 1 ke lantai 8, dan berhenti tepat 3 kali di lantai-lantai antara (lantai 2 sampai 7). Ada berapa banyak kombinasi urutan pemberhentian lift tersebut?
10. Berapa banyak bilangan 7 digit yang dapat dibentuk menggunakan angka $1, 1, 2, 2, 2, 3, 4$ sedemikian rupa sehingga angka $3$ dan $4$ tidak saling bersebelahan?
11. Delapan orang utusan dari 4 sekolah berbeda (tiap sekolah 2 utusan) duduk mengelilingi meja bundar. Berapa banyak cara mereka duduk jika utusan dari sekolah yang sama harus selalu duduk berdampingan?
12. Enam orang (A, B, C, D, E, F) duduk melingkar. Berapa banyak susunan posisi duduk jika A dan B tidak boleh duduk bersebelahan?
13. Seorang perajin ingin membuat sebuah gelang dari 7 buah manik-manik yang bentuk dan ukurannya sama, tetapi warnanya semuanya berbeda. Berapa banyak gelang berbeda yang dapat dibuat? (Petunjuk: gelang dapat dibalik).
14. Tiga pria dan tiga wanita duduk mengelilingi meja bundar. Berapa banyak cara mereka duduk agar tidak ada dua wanita yang duduk berdampingan?
15. Sebuah keluarga yang terdiri dari kakek, nenek, ayah, ibu, dan 3 orang anak duduk melingkar. Kakek dan nenek harus selalu berdampingan, sedangkan ketiga anak tidak boleh ada yang duduk berdampingan satu sama lain. Berapa banyak susunan posisi duduk keluarga tersebut?
16. Sebuah delegasi beranggotakan 4 orang akan dipilih dari 6 guru dan 5 siswa. Berapa banyak cara memilih delegasi tersebut jika di dalamnya harus memuat minimal 2 orang guru?
17. Dalam sebuah pertemuan, terdapat 12 orang. Empat orang di antaranya saling bermusuhan satu sama lain (keempatnya tidak ada yang mau berjabat tangan satu sama lain). Sisa orang lainnya bersedia berjabat tangan dengan siapa saja. Berapa total jabat tangan yang terjadi di ruangan tersebut?
18. Pada sebuah tes kompetensi, seorang peserta wajib mengerjakan 8 dari 10 soal yang diberikan. Jika soal nomor 1, 3, dan 5 wajib dikerjakan, dan dari soal nomor 8 hingga 10 minimal harus dikerjakan 1 soal, berapa banyak variasi pilihan soal yang bisa dikerjakan peserta?
19. Sebanyak 9 orang siswa akan dibagi ke dalam 3 kelompok kerja (Kelompok A, B, dan C) yang masing-masing beranggotakan 3 orang. Berapa banyak cara pembagian kelompok tersebut?
20. Dari himpunan angka $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$, akan dipilih 3 angka secara acak. Berapa banyak cara pemilihan agar jumlah ketiga angka yang terpilih tersebut merupakan bilangan genap?
21. Diberikan sebuah segi-12 beraturan (dodekagon). Berapa banyak diagonal yang dapat ditarik dari segi-12 tersebut?
22. Terdapat 10 titik pada sebuah lingkaran. Berapa banyak tali busur yang dapat dibuat dengan menghubungkan titik-titik tersebut, dan berapa banyak titik potong maksimal di dalam lingkaran yang terbentuk dari tali-tali busur tersebut?
23. Pada sebuah papan catur berukuran $8 \times 8$ kotak, terdapat berapa banyak total persegi panjang yang bisa terbentuk (termasuk yang berbentuk persegi)?
24. Diberikan 8 buah titik sebidang, di mana tepat 4 titik di antaranya terletak pada satu garis lurus. Selain keempat titik tersebut, tidak ada 3 titik yang segaris. Berapa banyak segitiga yang dapat dibentuk dari kedelapan titik tersebut?
25. Sepuluh garis lurus digambar pada sebuah bidang datar sedemikian rupa sehingga tidak ada dua garis yang sejajar dan tidak ada tiga garis yang berpotongan di satu titik. Berapa banyak total segitiga yang dibentuk oleh garis-garis tersebut?
26. Berapa banyak solusi bilangan bulat positif $(x, y, z \ge 1)$ yang memenuhi persamaan $x + y + z = 15$?
27. Seorang guru memiliki 20 buah permen identik yang akan dibagikan kepada 4 orang anak didiknya. Jika guru tersebut mensyaratkan setiap anak minimal harus mendapatkan 2 buah permen, berapa banyak cara pembagian permen tersebut?
28. Berapa banyak solusi bilangan bulat non-negatif $(a, b, c, d \ge 0)$ yang memenuhi pertidaksamaan $a + b + c + d \le 10$? (Petunjuk: ubah pertidaksamaan menjadi persamaan dengan menambahkan variabel 'dummy' $e \ge 0$).
29. Tiga buah dadu standar enam sisi yang identik dilempar secara bersamaan. Berapa banyak kombinasi mata dadu berbeda yang mungkin muncul? (Mata dadu $\{1, 2, 2\}$ dianggap sama dengan $\{2, 1, 2\}$).
30. Berapa banyak cara membagikan 12 apel identik ke dalam 3 keranjang (Merah, Kuning, Hijau) sedemikian rupa sehingga keranjang Merah minimal berisi 1 apel, keranjang Kuning minimal berisi 2 apel, dan keranjang Hijau maksimal berisi 4 apel?