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. Dalam tulisan ini, kita akan membahas soal isian singkat.

Tulisan ini adalah bagian dari seri Pembahasan Soal ON MIPA-PT Matematika. Jadi, setelah membaca tulisan ini, pastikan anda mengetuk tautan tersebut. Di sana tersedia pembahasan soal-soal ON MIPA-PT lainnya.

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...

Pembahasan

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...

Pembahasan

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...

Pembahasan

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...

Pembahasan

Sebelum menyelesaikan soal ini, ada beberapa hal yang perlu kita ketahui.$$k {n \choose k}=n {n-1 \choose k-1} \quad \ldots \textbf{(1)}$$

Bukti
$$\begin{aligned}k {n \choose k} &= k \frac{n!}{(n-k)!k!} \\&= k \frac{n(n-1)!}{(n-k)!k(k-1)!} \\&= \frac{n(n-1)!}{(n-k)!(k-1)!} \\&= n\frac{(n-1)!}{((n-1)-(k-1))!(k-1)!} \\&= n {n-1 \choose k-1}\end{aligned}$$Terbukti.

$${n \choose k}={n-1 \choose k-1}+{n-1 \choose k} \quad \ldots \textbf{(2)}$$

Bukti
Misal $A=\{ 1,2,3,\cdots,n \}$. Banyaknya subset dari $A$ yang terdiri dari $k$ anggota dapat dihitung dengan dua cara.

Cara I: Kita dapat memilih $k$ anggota dari himpunan $A$ yang akan menjadi anggota subset. Banyaknya subset yang mungkin adalah ${n \choose k}$.

Cara II: Tinjau salah satu anggota $A$, misalnya 1. Ada dua kasus yang mungkin dalam membentuk subset dengan $k$ anggota, yaitu 1) 1 merupakan anggota subset, dan 2) 1 bukan anggota subset. Jika $1$ merupakan anggota subset, maka ada sebanyak ${n-1 \choose k-1}$ cara untuk memilih $k-1$ anggota lainnya. Sedangkan, jika $1$ bukan anggota subset, maka ada sebanyak ${n-1 \choose k}$ cara untuk membentuk subset dengan $k$ anggota tersebut. Berdasarkan aturan penjumlahan, banyaknya subset yang mungkin adalah ${n-1 \choose k-1}+{n-1 \choose k}$.

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

$$\sum_{k=2}^m(-1)^k {m \choose k}=m-1 \quad \ldots \textbf{(3)}$$

Bukti:
Berdasarkan teorema binomial, diperoleh$$\begin{aligned}(1+(-1))^n &= \sum_{k=0}^m 1^{m-k} (-1)^k {m \choose k} \\0^n &= \sum_{k=0}^m (-1)^k {m \choose k} \\0 &= (-1)^0 {m \choose 0} + (-1)^1 {m \choose 1} + \sum_{k=2}^m (-1)^k {m \choose k} \\0 &= 1-m+\sum_{k=2}^m (-1)^k {m \choose k}\end{aligned}$$Tambahkan $m-1$ pada kedua ruas, sehingga diperoleh$$\sum_{k=2}^m(-1)^k {m \choose k}=m-1$$Terbukti.

Itulah tiga hal yang perlu kita ingat, sebelum menjawab soal ini.

Berdasarkan sifat $\textbf{(1)}$, diperoleh$$\begin{aligned}\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}\end{aligned}$$

Berdasarkan sifat $\textbf{(2)}$, diperoleh ${n-1 \choose k-1}={n \choose k}-{n-1 \choose k}$, sehingga$$\begin{aligned}\sum_{k=2}^n (-1)^k k {n \choose k} &= n\sum_{k=2}^n (-1)^k \left[ {n \choose k}-{n-1 \choose k} \right] \\&= n \left[ \sum_{k=2}^n (-1)^k {n \choose k}-\sum_{k=2}^n (-1)^k {n-1 \choose k} \right] \\&= n \left[ \sum_{k=2}^n (-1)^k {n \choose k}-\left(\sum_{k=2}^{n-1} (-1)^k {n-1 \choose k} + (-1)^n {n-1 \choose n} \right) \right]\end{aligned}$$

Berdasarkan sifat $\textbf{(3)}$, diperoleh $\sum_{k=2}^n (-1)^k {n \choose k}=n-1$ dan $\sum_{k=2}^{n-1} (-1)^k {n-1 \choose k}=(n-1)-1$. Akibatnya$$\begin{aligned}\sum_{k=2}^n (-1)^k k {n \choose k} &= n \left[ (n-1)-(n-1-1)+0 \right] \\&= n \cdot 1 \\&= n\end{aligned}$$Jadi, $\sum_{k=2}^n (-1)^k k {n \choose k} = 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...

Pembahasan

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. Dengan cara yang sama dengan kasus II, diperoleh 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 nilai $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}\sum_{v \in V} \text{deg}(v) &= 2 \lvert E \rvert \\1+3+3+3+2+\text{deg}(v_6) &= 2 \cdot 8 \\12+\text{deg}(v_6) &= 16 \\\text{deg}(v_6) &= 4\end{aligned}$$Jadi, derajat dari titik $v_6$ adalah 4.

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