Dalam tulisan ini, kita akan membahas soal Kombinatorika dalam ON MIPA-PT Matematika Tahun 2018. Soal kombinatorika terdiri dari delapan soal isian singkat dan tiga soal uraian. Sebelum masuk pada pembahasan, mari perhatikan daftar isi berikut.

Tulisan ini adalah bagian dari seri Pembahasan Soal ON MIPA-PT Matematika. Jadi, pastikan anda mengetuk tautan tersebut setelah membaca tulisan ini. :)

Pembahasan Soal Isian Kombinatorika

Nomor 1

Banyaknya subset dari himpunan $\{ 1,2,\cdots,25 \}$ yang terdiri dari 3 bilangan sehingga dalam sebuah subset tidak terdapat dua bilangan berurutan adalah...

Misalkan $M$ adalah himpunan dengan $m$ anggota dan $K$ adalah subset dari $M$ dengan $k$ anggota. Himpunan $K$ dapat dinyatakan sebagai barisan biner dengan panjang $m$. Angka 1 menyatakan anggota yang bersesuaian merupakan anggota subset dan angka 0 menyatakan anggota yang bersesuaian bukan anggota subset. Misalnya kita punya himpunan $M=\{a,b,c,d,e\}$. Subset $K=\{a,c,d\}$ dari $M$ dapat dinyatakan sebagai barisan biner $10110$.

Diketahui himpunan $\{ 1,2,\cdots,25 \}$. Akan dicari banyaknya subset yang terdiri dari 3 bilangan sehingga dalam sebuah subset tidak terdapat dua bilangan berurutan. Dalam konteks barisan biner, soal ini dapat dipandang sebagai banyaknya barisan biner dengan panjang 25 yang terdiri dari 3 angka 1 dan 22 angka 0, dimana angka 1 tidak boleh berdampingan.

Pertama, tuliskan 22 angka 0 secara berurutan. Agar angka 1 tidak berdampingan, ketiga angka 1 harus ditempatkan di antara dua angka 0 atau pada ujung barisan. Banyaknya posisi yang mungkin untuk menempatkan angka 1 adalah 23 (2 pada bagian ujung dan 21 pada bagian tengah). Banyaknya cara menempatkan 3 objek pada 23 tempat yang tersedia adalah$${23 \choose 3}=\frac{23!}{(23-3)!3!}=1771$$Jadi, banyaknya subset dari himpunan $\{ 1,2,\cdots,25 \}$ yang terdiri dari 3 bilangan sehingga dalam sebuah subset tidak terdapat dua bilangan berurutan adalah 1771.

Nomor 2

Sebuah klub bulu tangkis mempunyai 35 anggota terdiri dari 15 anak laki-laki dan 20 anak perempuan. Klub akan membentuk 10 pasangan ganda campuran. Banyaknya cara yang mungkin untuk membentuk 10 pasangan ganda campuran adalah...

Pertama, pilih masing-masing 10 anak laki-laki dan perempuan yang akan dipasangkan. Banyaknya cara adalah ${15 \choose 10}{20 \choose 10}$. Selanjutnya, anak laki-laki pertama dapat dipasangkan dengan 1 dari 10 anak perempuan, anak laki-laki kedua dengan 1 dari 9 anak perempuan yang tersisa, dan seterusnya, sampai pada anak laki-laki kesepuluh. Berdasarkan aturan perkalian, ada sebanyak $10!$ cara.

Jadi, banyaknya cara yang mungkin untuk membentuk 10 pasangan ganda campuran adalah $10!{15 \choose 10}{20 \choose 10}$.

Nomor 3

Sebuah toko roti memproduksi 8 jenis donat. Donat dikemas dalam kotak berisi 12 buah donat. Banyaknya cara untuk mengisi sebuah kotak sehingga terdapat sedikitnya satu buah donat untuk setiap jenis adalah...

Misalkan $x_i$ menyatakan banyaknya donat jenis $i$ dalam kotak, untuk $1 \leq i \leq 8$. Banyaknya cara mengisi sebuah kotak sehingga terdapat sedikitnya satu buah donat untuk setiap jenis sama dengan banyaknya solusi bilangan bulat dari$$x_1+x_2+\cdots+x_8=12, \quad x_i \geq 1, \: 1 \leq i \leq 8$$

Banyaknya solusi persamaan persamaan di atas, sama dengan banyaknya solusi bilangan bulat non negatif dari$$y_1+y_2+\cdots+y_8=4$$dengan $y_i=x_i-1$, untuk $1 \leq i \leq 8$, yaitu sebanyak$${4+8-1 \choose 4}={11 \choose 4}=\frac{11!}{(11-4)!4!}=330$$Jadi, banyaknya cara untuk mengisi sebuah kotak sehingga terdapat sedikitnya satu buah donat untuk setiap jenis adalah 330.

Nomor 4

Untuk bilangan bulat positif $n \geq 2$, nilai dari $\sum_{k=2}^n (-1)^k k {n \choose k}$ adalah...

Perhatikan bahwa$$k {n \choose k}=n{n-1 \choose k-1}$$

Ini dapat dibuktikan dengan argumentasi kombinatorial. Misalkan terdapat $n$ siswa dalam suatu kelas. Akan dibentuk sebuah tim yang terdiri dari $k$ siswa, di mana salah seorang di antaranya merupakan ketua tim. Banyak tim yang mungkin terbentuk dapat dihitung dengan dua cara.

Cara I. Kita mulai dengan memilih $k$ anggota tim dari $n$ siswa. Kemudian, memilih $1$ orang ketua tim dari $k$ anggota yang telah terpilih. Berdasarkan aturan perkalian, banyak tim yang mungkin terbentuk adalah ${n \choose k} {k \choose 1}=k {n \choose k}$.

Cara II. Kita mulai dengan memilih $1$ orang ketua tim dari $n$ siswa. Kemudian, kita lanjutkan dengan memilih $k-1$ anggota tim dari $n-1$ siswa yang tersisa. Berdasarkan aturan perkalian, banyak tim yang mungkin terbentuk adalah ${n \choose 1}{n-1 \choose k-1}=n {n-1 \choose k-1}$.

Berdasarkan kedua cara di atas, dapat disimpulkan bahwa $k {n \choose k}=n{n-1 \choose k-1}$. Terbukti.

Akibatnya, jumlahan pada soal dapat ditulis sebagai$$\sum_{k=2}^n (-1)^k k {n \choose k}=\sum_{k=2}^n (-1)^k n {n-1 \choose k-1}=n\sum_{k=2}^n (-1)^k {n-1 \choose k-1}$$

Misalkan $m=k-1$, sehingga batas bawah pada sigma menjadi $m=2-1=1$ dan batas atas menjadi $n-1$.$$\sum_{k=2}^n (-1)^k k {n \choose k}=n\sum_{m=1}^{n-1} (-1)^{m+1} {n-1 \choose m}=-n\sum_{m=1}^{n-1} (-1)^m {n-1 \choose m} \quad \ldots(1)$$

Berdasarkan teorema binomial, kita dapat menulis ekspansi $(-1+1)^{n-1}$ sebagai$$\begin{aligned}(-1+1)^{n-1} &= \sum_{m=0}^{n-1} (-1)^m 1^{n-1-m} {n-1 \choose m} \\0^{n-1} &= \sum_{m=0}^{n-1} (-1)^m {n-1 \choose m} \\0 &= (-1)^0 {n-1 \choose 0} + \sum_{m=1}^{n-1} (-1)^{m} {n-1 \choose m} \\0 &= 1 + \sum_{m=1}^{n-1} (-1)^{m} {n-1 \choose m} \\-1 &= \sum_{m=1}^{n-1} (-1)^{m} {n-1 \choose m} \quad \ldots (2)\end{aligned}$$

Substitusi persamaan (2) ke persamaan (1), sehingga$$\sum_{k=2}^n (-1)^k k {n \choose k}=-n \cdot (-1)=n$$

Nomor 5

Misalkan $b_n$ adalah banyaknya untaian atas $n$ huruf yang dapat dibentuk dengan menggunakan A, B, dan C sedemikian sehingga bila huruf A muncul bukan sebagai huruf akhir pada untaian, maka A harus segera diikuti oleh B. Relasi rekurensi dari barisan $\{ b_n \}$ adalah...

Misalkan untaian yang memenuhi disebut untaian cantik. Untaian cantik atas $n$ huruf dapat diawali dengan huruf A, B, atau C.

Kasus I. Huruf pertama adalah A. Berdasarkan syarat untaian cantik, huruf berikutnya harus B. Sehingga untaian ini harus diawali dengan AB. Banyaknya untaian yang memenuhi sama dengan banyaknya untaian cantik atas $n-2$ huruf, yang dinyatakan sebagai $b_{n-2}$. Mengapa? Karena yang kita lakukan adalah menambahkan AB pada awal setiap untaian cantik atas $n-2$ huruf. Jadi, banyaknya untaian cantik pada kasus I adalah $b_{n-2}$.

Kasus II. Huruf pertama adalah B. Tidak ada batasan mengenai huruf berikutnya, sehingga banyaknya untaian cantik dengan huruf pertama B sama dengan banyaknya untaian cantik atas $n-1$ huruf, yaitu sebanyak $b_{n-1}$.

Kasus III. Huruf pertama adalah C. Serupa dengan kasus II, banyaknya untaian cantik pada kasus III adalah $b_{n-1}$.

Berdasarkan tiga kasus di atas, banyaknya untaian cantik atas $n$ huruf adalah $b_n=2b_{n-1}+b_{n-2}$.

Untuk nilai awal, kita memerlukan $b_1$ dan $b_2$. Untuk $n=1$, banyaknya untaian cantik adalah 3, yaitu A, B, dan C. Untuk $n=2$, banyaknya untaian cantik adalah 7, yaitu AB, BA, BB, BC, CA, CB, dan CC. Jadi, relasi rekurensi dari barisan $\{ b_n \}$ adalah$$b_n=2b_{n-1}+b_{n-2}, \: \text{ untuk } n \geq 3, \: \text{ dengan } b_1=3 \text{ dan } b_2=7$$

Nomor 6

Diberikan permutasi $\pi = \left( \begin{array}{cccc} 1 & 2 & \cdots & n \\ \pi (1) & \pi (2) & \cdots & \pi (n) \end{array} \right)$ atas himpunan $\{ 1,2,\cdots,n \}$ dengan $n \geq 7$. Banyaknya permutasi $\pi$ sehingga $\pi (1)=5$ atau $\pi (3)=7$ atau $\pi (6)=2$ adalah...

Pembahasan

Kita akan menyelesaikan soal ini dengan prinsip inklusi dan eksklusi.Misalkan $S$ adalah himpunan semua permutasi $\pi$ atas $\{ 1,2,\cdots,n \}$. Definisikan$$\begin{aligned}A &= \{ \pi \in S \mid \pi(1)=5 \} \\B &= \{ \pi \in S \mid \pi(3)=7 \} \\C &= \{ \pi \in S \mid \pi(6)=2 \}\end{aligned}$$Jawaban dari soal ini adalah $\mid A \cup B \cup C \mid$

Pertama, kita menghitung $S_1$ yang nilainya $\mid A \mid + \mid B \mid + \mid C \mid$. Kita mulai dari $\mid A \mid$. Karena nilai $\pi (1)$ telah ditetapkan, kita tinggal menghitung banyak cara memilih nilai untuk $\pi (2),\pi (3),\ldots,\pi(n)$. Ada sebanyak $n-1$ nilai yang mungkin untuk $\pi(2)$, $n-2$ untuk $\pi(3)$, dan seterusnya. Berdasarkan aturan perkalian diperoleh $\mid A \mid=(n-1)!$. Dengan cara yang sama, diperoleh $\mid B \mid=\mid C \mid=(n-1)!$. Sehingga$$S_1=\mid A \mid + \mid B \mid + \mid C \mid=3(n-1)!$$

Dengan cara yang sama, kita dapat menghitung $S_2$ dan $S_3$.$$\begin{aligned}S_2 &= \mid A \cap B \mid + \mid A \cap C \mid +\mid B \cap C \mid = 3(n-2)! \\S_3 &= \mid A \cap B \cap C \mid =(n-3)!\end{aligned}$$

Berdasarkan prinsip inklusi dan eksklusi, diperoleh$$\begin{aligned}\mid A \cup B \cup C \mid &= S_1-S_2+S_3 \\&= 3(n-1)!-3(n-2)!+(n-3)! \\&= 3(n-1)(n-2)(n-3)!-3(n-2)(n-3)!+(n-3)! \\&= (n-3)![3(n-1)(n-2)-3(n-2)+1] \\&= (n-3)!(3n^2-9n+6-3n+6+1) \\&= (n-3)!(3n^2-12n+13)\end{aligned}$$Jadi, banyaknya permutasi $\pi$ sehingga $\pi (1)=5$ atau $\pi (3)=7$ atau $\pi (6)=2$ adalah $(n-3)!(3n^2-12n+13)$.

Nomor 7

Dalam bentuk paling sederhana, fungsi pembangkit eksponensial (exponential generating function) dari barisan $(0!,1!,2!,3!,\cdots,n!,\cdots)$ adalah...

Pembahasan

Berdasarkan definisi fungsi pembangkit eksponensial diperoleh$$\begin{aligned}f(x) &= 0! + 1!x + 2!\frac{x^2}{2!} + 3!\frac{x^3}{3!} + \cdots + n!\frac{x^n}{n!} + \cdots \\&= 1+x+x^2+x^3+\cdots+x^n+\cdots\end{aligned}$$

Untuk $\lvert x \rvert < 1$, diperoleh$$f(x)=\frac{1}{1-x}$$Jadi, fungsi pembangkit eksponensial dari barisan $(0!,1!,2!,3!,\cdots,n!,\cdots)$, dalam bentuk paling sederhana adalah $f(x)=\frac{1}{1-x}$, untuk $\lvert x \rvert < 1$.

Nomor 8

Diberikan sebuah graf sederhana $G$ atas 6 titik $v_1,v_2,\cdots,v_6$. Bila $G$ mempunyai 8 sisi dan derajat dari titk-titik $v_1,v_2,\cdots,v_5$ masing-masing adalah 1, 3, 3, 3, dan 2, maka derajat dari titik $v_6$ adalah...

Pembahasan

Sebelum menjawab soal ini, kita perlu mengingat teorema berikut.

Teorema

Jika $G=(V,E)$ adalah graf tak berarah atau graf ganda, maka $\sum_{v \in V} \text{deg}(v)=2 \lvert E \rvert$.

Diketahui $G=(6,8)$ dan derajat dari 5 titik pada graf. Graf sederhana merupakan graf tak berarah, sehingga berdasarkan teorema di atas, diperoleh$$\begin{aligned}2 \lvert E \rvert &= \sum_{v \in V} \text{deg}(v) \\2 \cdot 8 &= 1+3+3+3+2+\text{deg}(v_6) \\16 &= 12+\text{deg}(v_6) \\4 &= \text{deg}(v_6)\end{aligned}$$Jadi, derajat dari titik $v_6$ adalah 4.

Pembahasan Soal Uraian Kombinatorika

Nomor 1

Perhatikan barisan Fibonacci dengan relasi rekurensi, untuk $n \geq 2$, $f_n=f_{n-1}+f_{n-2}$, $f_0=0$, $f_1=1$. Definisikan matriks $F=\left[ \begin{array}{cc} 1&1\\ 1&0 \end{array} \right] = \left[ \begin{array}{cc} f_2&f_1\\ f_1&f_0 \end{array} \right]$.

  1. Buktikan bahwa$$F^n = \left[ \begin{array}{cc} 1&1\\ 1&0 \end{array} \right]^n = \left[ \begin{array}{cc} f_{n+1}&f_n\\ f_n&f_{n-1} \end{array} \right]$$
  2. Buktikan bahwa$$f_{n+1}f_{n-1}-f_n^2 = \begin{cases} 1&, \text{bila n genap}\\ -1&, \text{bila n ganjil} \end{cases}$$

Bagian a
Misalkan $P(n)$ adalah pernyataan$$F^n = \left[ \begin{array}{cc} 1&1\\ 1&0 \end{array} \right]^n = \left[ \begin{array}{cc} f_{n+1}&f_n\\ f_n&f_{n-1} \end{array} \right]$$Kita akan membuktikan bahwa $P(n)$ bernilai benar, untuk setiap bilangan asli $n$, dengan induksi matematika.

Langkah Dasar
Kita akan menunjukkan bahwa $P(1)$ bernilai benar.Untuk $n=1$, diperoleh$$F^1 = \left[ \begin{array}{cc} 1&1\\ 1&0 \end{array} \right]^1 = \left[ \begin{array}{cc} f_2&f_1\\ f_1&f_0 \end{array} \right]$$Jadi, $P(1)$ bernilai benar.

Langkah Induksi
Asumsikan $P(k)$ bernilai benar, yaitu$$F^k = \left[ \begin{array}{cc} f_{k+1}&f_k\\ f_k&f_{k-1} \end{array} \right]$$Akan ditunjukkan bahwa $P(k+1)$ juga bernilai benar. Perhatikan bahwa$$\begin{aligned}F^{k+1} &= F^kF &\text{[Pemangkatan matriks]} \\&= \left[ \begin{array}{cc} f_{k+1}&f_k\\ f_k&f_{k-1} \end{array} \right] \left[ \begin{array}{cc} 1&1\\ 1&0 \end{array} \right] &\text{[Asumsi]} \\&= \left[ \begin{array}{cc} f_{k+1}+f_k&f_{k+1}\\ f_k+f_{k-1}&f_k \end{array} \right] &\text{[Perkalian matriks]} \\&= \left[ \begin{array}{cc} f_{k+2}&f_{k+1}\\ f_{k+1}&f_k \end{array} \right] &\text{[Definisi relasi rekurensi]}\end{aligned}$$Jadi, $P(k+1)$ juga bernilai benar. Berdasarkan induksi matematika, $P(n)$ bernilai benar, untuk setiap bilangan asli $n$.

Pembahasan soal nomor 1a juga tersedia dalam bentuk video. Silakan tonton video pada link berikut, untuk mendapatkan penjelasan yang lebih detail!
Pembahasan Soal Uraian 1a Kombinatorika 2018

Bagian b
Berdasarkan sifat determinan, kita dapat menulis$$\text{det}(F^n)=[\text{det}(F)]^n \quad \ldots(1)$$

Perhatikan bahwa$$\text{det}(F^n)=\begin{vmatrix}f_{n+1}&f_n\\f_n&f_{n-1}\end{vmatrix}=f_{n+1}f_{n-1}-f_n^2$$dan$$\text{det}(F)=\begin{vmatrix}1&1\\1&0\end{vmatrix}=-1$$

Akibatnya, persamaan $(1)$ menjadi$$f_{n+1}f_{n-1}-f_n^2=(-1)^n$$

Bila $n$ genap maka $(-1)^n=1$ sedangkan bila $n$ ganjil maka $(-1)^n=-1$. Dengan demikian$$f_{n+1}f_{n-1}-f_n^2 = \begin{cases} 1&, \text{bila n genap}\\ -1&, \text{bila n ganjil} \end{cases}$$Terbukti.

Nomor 2

Andaikan $G$ adalah sebuah graf sederhana (simple graph). Bila $e$ adalah sebuah sisi yang menghubungkan titik $u$ dan titik $v$ di $G$, maka dikatakan bahwa titik $u$ bertetangga dengan titik $v$. Derajat dari sebuah titik $v$ di $G$ adalah banyaknya titik-titik yang bertetangga dengan $v$. Perlihatkan bahwa pada sebuah graf sederhana $G$ terdapat sedikitnya dua titik dengan derajat sama.

Misalkan $G$ graf sederhana dengan $n$ titik dan $x$ adalah sebarang titik pada $G$. Terdapat $n-1$ titik yang dapat bertetangga dengan $x$. Akibatnya derajat yang mungkin dari $x$ adalah anggota dari$$\{ 0,1,2,\cdots,n-1 \}$$

Perhatikan bahwa $G$ tidak mungkin memuat dua titik dengan derajat $0$ dan $n-1$. Artinya, jika $G$ memuat titik berderajat $0$ maka dapat dipastikan $G$ tidak memuat titik berderajat $n-2$. Begitupun sebaliknya.

Hal di atas dapat dibuktikan dengan kontradiksi. Andaikan $G$ memuat dua titik, sebutlah $A$ dan $B$, yang secara berturut-turut berderajat $0$ dan $n-1$. Karena $b$ berderajat $n-1$, maka $b$ bertetangga dengan semua titik lain pada $G$, termasuk $A$. Akibatnya, titik $A$ berderajat minimal 1. Kontradiksi dengan pengandaian bahwa $A$ berderajat $0$.

Dengan demikian, derajat yang mungkin dimiliki oleh sebarang titik pada $G$ adalah anggota dari$$\{ 0,1,\cdots,n-2 \} \text{ atau } \{ 1,2,\cdots,n-1 \}$$

Keduanya beranggotakan $n-1$ objek. Karena $G$ terdiri dari $n$ titik, maka berdasarkan Prinsip Sangkar Burung, terdapat sedikitnya dua titik dengan derajat sama. Terbukti.

Nomor 3

Tentukan banyaknya cara untuk mewarnai bujur sangkar $1 \times 1$ pada persegi panjang $1 \times n$ dengan menggunakan warna merah, hijau, atau biru sedemikian sehingga terdapat sejumlah genap bujur sangkar berwarna merah.

Pewarnaan tersebut menggunakan warna merah, hijau, atau biru, dengan syarat banyaknya bujur sangkar merah merupakan bilangan genap.Fungsi pembangkit eksponensial untuk penyusunan ini adalah$$f(x) = \left( 1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots \right) \left( 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots \right)^2$$Banyaknya cara mewarnai bujur sangkar $1 \times 1$ pada persegi panjang $1 \times n$ dengan syarat yang diberikan sama dengan koefisien $\frac{x^n}{n}$ pada $f(x)$.Perhatikan bahwa$$\begin{aligned}f(x) &= \left( 1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots \right) \left( 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots \right)^2 \\&= \left( \frac{e^x+e^{-x}}{2} \right) \left( e^x \right)^2 \\&= \left( \frac{e^x+e^{-x}}{2} \right)e^{2x} \\&= \frac{1}{2} \left( e^{3x} + e^x \right) \\&= \frac{1}{2} \left( \sum_{i=0}^{\infty} \frac{(3x)^i}{i!} + \sum_{i=0}^{\infty} \frac{x^i}{i!} \right) \\&= \frac{1}{2} \left( \sum_{i=0}^{\infty} \frac{3^ix^i}{i!} + \sum_{i=0}^{\infty} \frac{x^i}{i!} \right) \\&= \frac{1}{2} \left( \sum_{i=0}^{\infty} \frac{3^ix^i + x^i}{i!} \right) \\&= \frac{1}{2} \left( \sum_{i=0}^{\infty} \frac{(3^i + 1) x^i}{i!} \right)\end{aligned}$$

Suku yang memuat $\frac{x^n}{n!}$ adalah$$\frac{1}{2} \cdot \frac{(3^n + 1) x^n}{n!} = \frac{3^n + 1}{2} \cdot \frac{x^n}{n!}$$dengan koefisien$$\frac{3^n + 1}{2}$$Jadi, banyaknya cara mewarnai bujur sangkar $1 \times 1$ pada persegi panjang $1 \times n$ dengan syarat yang diberikan adalah $\frac{3^n + 1}{2}$.

Semoga bermanfaat! Jika ada yang perlu diperbaiki atau anda punya solusi yang berbeda, silakan beritahu melalui komentar.