Naskah Soal & Pembahasan ONMIPA PT 2018 — Kombinatorika

Banyaknya subset beranggota $k$ dari $\{1, 2, \dots, n\}$ tanpa dua bilangan berurutan diberikan oleh rumus $\binom{n - k + 1}{k}$.

Untuk $n = 25$ dan $k = 3$:

$\binom{25 - 3 + 1}{3} = \binom{23}{3} = \frac{23 \times 22 \times 21}{3 \times 2 \times 1} = 1771.$

Pilih 10 anak laki-laki dari 15: $\binom{15}{10}$ cara. Pilih 10 anak perempuan dari 20: $\binom{20}{10}$ cara. Pasangkan 10 anak laki-laki dan 10 anak perempuan terpilih: $10!$ cara.

Total cara:

$\binom{15}{10} \times \binom{20}{10} \times 10! = \frac{15!}{10! 5!} \times \frac{20!}{10! 10!} \times 10! = \frac{20! 15!}{5! 10! 10!}.$

Karena setiap jenis 8 donat harus ada minimal 1 buah, terpakai 8 donat. Sisa 4 donat bebas dipilih dari 8 jenis donat.

Banyaknya cara dengan pengulangan (Stars and Bars):

$\binom{4 + 8 - 1}{4} = \binom{11}{4} = \frac{11 \times 10 \times 9 \times 8}{4 \times 3 \times 2 \times 1} = 330.$

Dari Teorema Binomial: $\sum_{k=2}^n \binom{n}{k} x^k = (1 + x)^n - nx - 1$.

Turunkan terhadap $x$ lalu kalikan dengan $x$:

$\sum_{k=2}^n k \binom{n}{k} x^k = n x (1 + x)^{n-1} - nx.$

Substitusi $x = -1$:

$\sum_{k=2}^n (-1)^k k \binom{n}{k} = n (-1) (1 - 1)^{n-1} - n(-1) = 0 + n = n.$

Bagi kasus berdasarkan huruf pertama untaian berpanjang $n$:

• Jika diawali huruf $B$ atau $C$ ($2$ pilihan), sisa untaian berpanjang $n-1 \implies 2 b_{n-1}$.
• Jika diawali huruf $A$, huruf berikutnya harus $B$ (diikuti pasangan $AB$), sisa untaian berpanjang $n-2 \implies b_{n-2}$.

Maka relasi rekurensinya adalah $b_n = 2b_{n-1} + b_{n-2}$ untuk $n \ge 3$ dengan kondisi awal $b_1 = 3, b_2 = 7$.

Definisikan himpunan kejadian $A = \{\pi \mid \pi(1)=5\}$, $B = \{\pi \mid \pi(3)=7\}$, dan $C = \{\pi \mid \pi(6)=2\}$.

• $|A| = |B| = |C| = (n-1)!$
• $|A \cap B| = |A \cap C| = |B \cap C| = (n-2)!$
• $|A \cap B \cap C| = (n-3)!$

Berdasarkan Prinsip Inklusi-Eksklusi:

$|A \cup B \cup C| = 3(n-1)! - 3(n-2)! + (n-3)!.$

Fungsi pembangkit eksponensial dari barisan $h_n = n!$ adalah:

$g^{(e)}(x) = \sum_{n=0}^\infty n! \frac{x^n}{n!} = \sum_{n=0}^\infty x^n = \frac{1}{1 - x}.$

Berdasarkan Lemma Jabat Tangan (Handshaking Lemma):

$\sum_{i=1}^6 \text{deg}(v_i) = 2 \cdot |E|$

$1 + 3 + 3 + 3 + 2 + \text{deg}(v_6) = 2(8) = 16$

$12 + \text{deg}(v_6) = 16 \implies \text{deg}(v_6) = 4.$

(a) Bukti dengan induksi matematika:

• Basis $n=1$: $F^1 = \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix} = \begin{bmatrix}f_2 & f_1 \\ f_1 & f_0\end{bmatrix}$ (benar).
• Langkah induksi: Andaikan $F^n = \begin{bmatrix}f_{n+1} & f_n \\ f_n & f_{n-1}\end{bmatrix}$. $F^{n+1} = F \cdot F^n = \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix} \begin{bmatrix}f_{n+1} & f_n \\ f_n & f_{n-1}\end{bmatrix} = \begin{bmatrix}f_{n+1} + f_n & f_n + f_{n-1} \\ f_{n+1} & f_n\end{bmatrix} = \begin{bmatrix}f_{n+2} & f_{n+1} \\ f_{n+1} & f_n\end{bmatrix}.$

(b) Hitung determinan kedua ruas dari persamaan (a): $\det(F^n) = (\det F)^n = (1(0) - 1(1))^n = (-1)^n$ $\det \begin{bmatrix}f_{n+1} & f_n \\ f_n & f_{n-1}\end{bmatrix} = f_{n+1} f_{n-1} - f_n^2$ Maka $f_{n+1} f_{n-1} - f_n^2 = (-1)^n$, bernilai $1$ untuk $n$ genap dan $-1$ untuk $n$ ganjil.

Misalkan $G$ memiliki $n$ buah titik. Derajat dari setiap titik di $G$ berkisar di $\{0, 1, 2, \dots, n-1\}$.

• Jika $G$ memiliki titik berderajat $0$ (titik terisolasi), maka tidak ada titik yang berderajat $n-1$ (sebab tidak bisa bertetangga dengan titik terisolasi). Maka pilihan derajat hanya $\{0, 1, \dots, n-2\}$ ($n-1$ kemungkinan untuk $n$ titik).
• Jika $G$ tidak memiliki titik berderajat $0$, maka pilihan derajat hanyalah $\{1, 2, \dots, n-1\}$ ($n-1$ kemungkinan untuk $n$ titik).

Berdasarkan Prinsip Sarang Burung Merpati (Pigeonhole Principle), karena terdapat $n$ titik dan hanya $n-1$ kemungkinan nilai derajat, haruslah terdapat sedikitnya 2 titik yang memiliki derajat sama.

Gunakan Fungsi Pembangkit Eksponensial (Exponential Generating Function):

• Merah (genap): $M(x) = \sum_{k=0}^\infty \frac{x^{2k}}{(2k)!} = \frac{e^x + e^{-x}}{2}$.
• Hijau & Biru (bebas): $H(x) = B(x) = \sum_{k=0}^\infty \frac{x^k}{k!} = e^x$.

Fungsi pembangkit total $g(x) = M(x) H(x) B(x)$:

$g(x) = \frac{e^x + e^{-x}}{2} \cdot e^x \cdot e^x = \frac{e^{3x} + e^x}{2} = \sum_{n=0}^\infty \frac{3^n + 1}{2} \frac{x^n}{n!}$

Banyaknya cara mewarnai persegi panjang $1 \times n$ adalah $\dfrac{3^n + 1}{2}$.