Latihan Akhir Modul Kombinatorika ONMIPA

Halaman ini berisi latihan akhir modul Kombinatorika yang terdiri dari 10 Soal Isian Singkat dan 5 Soal Essay Pembuktian untuk menguji pemahaman konsep secara komprehensif.

Bagian I: 10 Soal Isian Singkat

✏️ Latihan Soal 1 (Susunan Kata UNLAM Tanpa Vokal Berdekatan)

Banyaknya cara menyusun huruf-huruf dari kata “UNLAM” sedemikian sehingga huruf vokal tidak saling berdekatan adalah…

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Kata “UNLAM” terdiri dari 5 huruf berbeda: Konsonan ${N, L, M}$ (3 huruf) dan Vokal ${U, A}$ (2 huruf).

Susun konsonan terlebih dahulu: $3! = 6$ cara.
Terdapat 4 sela tempat di antara konsonan untuk menempatkan vokal: _ N _ L _ M _.
Pilih 2 sela dari 4 sela untuk 2 vokal: $P (4, 2) = 4 \times 3 = 12$ cara.

Total cara = $6 \times 12 = 72$ . $■$

✏️ Latihan Soal 2 (Pencacahan Tidak Habis Dibagi 4 Maupun 6)

Berapa banyak bilangan asli $n \leq 1000$ yang tidak habis dibagi 4 maupun 6?

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Total $N = 1000$ .

$A_{4}$ (habis dibagi 4): $⌊ 1000/4 ⌋ = 250$ .
$A_{6}$ (habis dibagi 6): $⌊ 1000/6 ⌋ = 166$ .
$A_{4} \cap A_{6}$ (habis dibagi $KPK (4, 6) = 12$ ): $⌊ 1000/12 ⌋ = 83$ .

Banyaknya yang habis dibagi 4 atau 6:

$∣ A_{4} \cup A_{6} ∣ = 250 + 166 - 83 = 333$

Maka banyaknya bilangan yang tidak habis dibagi 4 maupun 6 adalah $1000 - 333 = 667$ . $■$

✏️ Latihan Soal 3 (Derajat Minimum k Graf Sederhana)

Sebuah graf sederhana memiliki 8 titik dengan derajat masing-masing adalah $k, k, k, 3, 3, 4, 4, 5$ . Nilai minimum $k$ yang mungkin agar graf tersebut dapat terbentuk adalah…

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan:

Berdasarkan Handshaking Lemma, jumlah seluruh derajat harus genap:

$\sum d (v) = 3 k + 3 + 3 + 4 + 4 + 5 = 3 k + 19$

Agar $3 k + 19$ genap, maka $3 k$ harus ganjil $⟹ k$ harus ganjil. 2. Pada graf sederhana 8 titik, derajat maksimum tiap titik adalah $8 - 1 = 7$ . 3. Jumlah titik berderajat ganjil harus genap: Titik lain berderajat ${3, 3, 5}$ (3 titik ganjil). Karena $3 k$ berasal dari 3 titik berderajat $k$ , jika $k$ ganjil maka total titik ganjil adalah $3 + 3 = 6$ (genap, memenuhi). 4. Nilai $k$ ganjil terkecil adalah $1$ . (Cek kelayakan: deret derajat $5, 4, 4, 3, 3, 1, 1, 1$ memenuhi kriteria Havel-Hakimi).

Maka nilai minimum $k = 1$ . $■$

✏️ Latihan Soal 4 (Koefisien x^12 pada FPB)

Koefisien dari $x^{12}$ pada fungsi pembangkit biasa $A (x) = (1 + x + x^{2} + x^{3} + x^{4})^{4}$ adalah…

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: $A (x) = (\frac{1 - x ^{5}}{1 - x})^{4} = (1 - 4 x^{5} + 6 x^{10} - 4 x^{15} + \dots) \sum_{n = 0}^{\infty} (3 n + 3) x^{n}$ . Mencari koefisien $x^{12}$ :

Dari $1 \cdot (3 12 + 3) = (3 15) = 455$ .
Dari $- 4 x^{5} \cdot (3 7 + 3) = - 4 \cdot (3 10) = - 4 (120) = - 480$ .
Dari $6 x^{10} \cdot (3 2 + 3) = 6 \cdot (3 5) = 6 (10) = 60$ .

Total koefisien = $455 - 480 + 60 = 35$ . $■$

✏️ Latihan Soal 5 (Membagi Bola Identik ke Kotak Tanpa Kosong)

Banyaknya cara menempatkan 5 bola identik ke dalam 3 kotak berbeda dengan syarat tidak ada kotak yang kosong adalah…

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Beri masing-masing kotak 1 bola terlebih dahulu ( $x_{i} \geq 1 ⟹ y_{i} = x_{i} - 1 \geq 0$ ). Tersisa $5 - 3 = 2$ bola identik untuk 3 kotak berbeda. Berdasarkan Stars and Bars ( $r = 2, n = 3$ ):

$(2 2 + 3 - 1) = (2 4) = 6 cara. ■$

✏️ Latihan Soal 6 (Jumlah Derajat Graf Lengkap K10)

Berapa jumlah seluruh derajat titik pada graf lengkap $K_{10}$ ?

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Pada $K_{10}$ , ada 10 titik dan masing-masing berderajat 9. Jumlah seluruh derajat = $10 \times 9 = 90$ . $■$

✏️ Latihan Soal 7 (Suku ke-8 Rekurensi Linier)

Suku ke-8 ( $a_{8}$ ) dari barisan yang didefinisikan dengan $a_{n} = 3 a_{n - 1} - 2 a_{n - 2}$ dengan $a_{0} = 1$ dan $a_{1} = 3$ adalah…

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Persamaan karakteristik: $r^{2} - 3 r + 2 = 0 ⟹ (r - 1) (r - 2) = 0 ⟹ r_{1} = 1, r_{2} = 2$ . Solusi umum: $a_{n} = α (1)^{n} + β (2)^{n} = α + β 2^{n}$ .

$a_{0} = 1 ⟹ α + β = 1$ .
$a_{1} = 3 ⟹ α + 2 β = 3$ . Pengurangan: $β = 2 ⟹ α = - 1$ . Maka $a_{n} = 2^{n + 1} - 1$ . Untuk $n = 8$ : $a_{8} = 2^{9} - 1 = 512 - 1 = 511$ . $■$

✏️ Latihan Soal 8 (Derangement D5)

Banyaknya permutasi dari ${1, 2, 3, 4, 5}$ yang merupakan derangement (tidak ada elemen di posisi aslinya) adalah…

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: $D_{5} = 5! (\frac{1}{2 !} - \frac{1}{3 !} + \frac{1}{4 !} - \frac{1}{5 !}) = 120 (\frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}) = 44$ . $■$

✏️ Latihan Soal 9 (Prinsip Pigeonhole Selisih 10)

Jika 11 bilangan bulat dipilih secara acak dari himpunan ${1, 2, \dots, 20}$ , maka pasti terdapat dua bilangan yang selisihnya adalah…

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Kelompokkan 20 bilangan ke dalam 10 pasangan (sangkar) yang berselisih 10:

${(1, 11), (2, 12), (3, 13), \dots, (10, 20)}$

Karena memilih 11 bilangan dari 10 pasangan (sangkar), berdasarkan Pigeonhole Principle, pasti ada 2 bilangan yang berasal dari pasangan yang sama, sehingga selisih keduanya adalah 10. $■$

✏️ Latihan Soal 10 (String Biner Panjang 7 Tanpa 11)

Banyaknya string biner panjang 7 yang tidak memuat sub-string “11” adalah…

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Relasi Fibonacci $b_{n} = b_{n - 1} + b_{n - 2}$ dengan $b_{1} = 2, b_{2} = 3$ .

$b_{3} = 5, b_{4} = 8, b_{5} = 13, b_{6} = 21, b_{7} = 34$ . Maka banyaknya string biner panjang 7 tanpa “11” adalah $34$ . $■$

Bagian II: 5 Soal Essay Pembuktian

✏️ Latihan Soal 11 (Pembuktian Dua Orang dengan Jumlah Kenalan Sama)

Buktikan bahwa di dalam sebuah pesta yang dihadiri oleh $n$ orang ( $n \geq 2$ ), selalu terdapat setidaknya dua orang yang memiliki jumlah kenalan yang sama di antara tamu-tamu tersebut. (Asumsikan hubungan kenalan bersifat simetris dan tidak ada yang mengenal dirinya sendiri).

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan:

Objek (Merpati): $n$ orang tamu di pesta.
Wadah (Sangkar): Jumlah kenalan yang mungkin untuk setiap orang, yaitu ${0, 1, 2, \dots, n - 1}$ .
Analisis Kasus:
1. Jika ada orang yang mengenal $0$ orang, maka tidak ada orang yang bisa mengenal $n - 1$ orang. Kemungkinan nilai kenalan yang ada hanya ${0, 1, \dots, n - 2}$ (ada $n - 1$ kemungkinan sangkar).
2. Jika tidak ada orang yang mengenal $0$ orang, maka kemungkinan nilai kenalan adalah ${1, 2, \dots, n - 1}$ (ada $n - 1$ kemungkinan sangkar).
Kesimpulan: Dalam kedua kasus, ada $n$ orang dan hanya $n - 1$ kemungkinan jumlah kenalan. Berdasarkan Prinsip Sarang Merpati (Pigeonhole Principle), pasti terdapat setidaknya dua orang yang memiliki jumlah kenalan yang sama. $■$

✏️ Latihan Soal 12 (EGF untuk Angka 0 Genap & 1 Minimal Sekali)

Gunakan fungsi pembangkit eksponensial untuk menentukan banyaknya cara menyusun barisan panjang $n$ dari angka ${0, 1, 2}$ sedemikian sehingga angka 0 muncul dalam jumlah genap dan angka 1 muncul setidaknya satu kali.

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Fungsi pembangkit eksponensial (EGF) untuk masing-masing angka:

Angka 0 (Genap): $\frac{e ^{x} + e ^{- x}}{2}$
Angka 1 (Minimal 1): $e^{x} - 1$
Angka 2 (Bebas): $e^{x}$

Total EGF $\hat{A} (x)$ :

$\hat{A} (x) = (\frac{e ^{x} + e ^{- x}}{2}) (e^{x} - 1) e^{x} = \frac{1}{2} (e^{2 x} + 1) (e^{x} - 1) = \frac{1}{2} (e^{3 x} - e^{2 x} + e^{x} - 1)$

Mencari koefisien $\frac{x ^{n}}{n !}$ untuk $n \geq 1$ :

$\hat{A} (x) = \sum_{n = 1}^{\infty} (\frac{3 ^{n} - 2 ^{n} + 1}{2}) \frac{x ^{n}}{n !}$

Maka banyaknya cara adalah $a_{n} = \frac{3 ^{n} - 2 ^{n} + 1}{2}$ . $■$

✏️ Latihan Soal 13 (Batas Maksimum Sisi Graf dengan k Komponen)

Misalkan $G$ adalah graf sederhana dengan $n$ titik dan $k$ komponen terhubung. Buktikan bahwa jumlah sisi maksimal di $G$ adalah:

$∣ E ∣ \leq \frac{( n - k ) ( n - k + 1 )}{2}$

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Misalkan komponen-komponen terhubung dari $G$ memiliki $n_{1}, n_{2}, \dots, n_{k}$ titik, sehingga $\sum_{i = 1}^{k} n_{i} = n$ dengan $n_{i} \geq 1$ .

Sisi maksimal di komponen ke- $i$ (graf lengkap $K_{n_{i}}$ ) adalah $(2 n _{i}) = \frac{n _{i} ( n _{i} - 1 )}{2}$ .
Jumlah total sisi maksimal: $∣ E ∣ \leq \sum_{i = 1}^{k} \frac{n _{i} ( n _{i} - 1 )}{2} = \frac{1}{2} \sum_{i = 1}^{k} n_{i}^{2} - \frac{n}{2}$ .
Untuk memaksimalkan $\sum n_{i}^{2}$ dengan syarat $\sum n_{i} = n$ dan $n_{i} \geq 1$ , kita harus memilih $k - 1$ komponen berupa titik isolasi ( $n_{1} = n_{2} = \dots = n_{k - 1} = 1$ ) dan komponen terbesar berisi $n_{k} = n - (k - 1) = n - k + 1$ titik.
Maka:

$\sum_{i = 1}^{k} n_{i}^{2} \leq (k - 1) (1^{2}) + (n - k + 1)^{2} = k - 1 + (n - k + 1)^{2}$

Substitusi ke rumus sisi:

$∣ E ∣ \leq \frac{1}{2} [(n - k + 1)^{2} + k - 1 - n] = \frac{( n - k ) ( n - k + 1 )}{2} . ■$

✏️ Latihan Soal 14 (Solusi Bulat Terbatas dengan PIE)

Tentukan banyaknya solusi bulat dari $x_{1} + x_{2} + x_{3} + x_{4} = 18$ dengan batasan $0 \leq x_{i} \leq 7$ untuk setiap $i = 1, 2, 3, 4$ . Gunakan Prinsip Inklusi-Eksklusi.

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan:

Total solusi non-negatif tanpa syarat atas: $N = (18 18 + 4 - 1) = (3 21) = 1330$ .
Pelanggaran $P_{i}$ : $x_{i} \geq 8$ .
1 Pelanggaran ( $∣ A_{i} ∣$ ): $x_{1}^{'} + x_{2} + x_{3} + x_{4} = 18 - 8 = 10 ⟹ (3 10 + 3) = (3 13) = 286$ . Ada $(1 4) = 4$ cara.
2 Pelanggaran ( $∣ A_{i} \cap A_{j} ∣$ ): $x_{1}^{'} + x_{2}^{'} + x_{3} + x_{4} = 18 - 16 = 2 ⟹ (3 2 + 3) = (3 5) = 10$ . Ada $(2 4) = 6$ cara.
3 Pelanggaran: $18 - 24 < 0 ⟹ 0$ .

Menggunakan PIE:

$Banyak solusi = 1330 - 4 (286) + 6 (10) - 0 = 1330 - 1144 + 60 = 246 solusi. ■$

✏️ Latihan Soal 15 (Pembuktian Kombinatorik Identitas Kuasa Binomial)

Tunjukkan bahwa untuk setiap bilangan asli $n$ , berlaku identitas kombinatorik berikut menggunakan argumen kombinatorik (combinatorial proof):

$\sum_{k = 0}^{n} (k n)^{2} = (n 2 n)$

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan:

Ruas Kanan $(n 2 n)$ : Menyatakan banyaknya cara memilih sebuah komite beranggotakan $n$ orang dari kelompok $2 n$ orang yang terdiri dari $n$ pria dan $n$ wanita.
Ruas Kiri $\sum_{k = 0}^{n} (k n)^{2}$ : Kita dapat memilih $n$ orang komite dengan membagi berdasarkan berapa banyak pria yang dipilih ( $k$ orang pria, di mana $0 \leq k \leq n$ ).
- Jika dipilih $k$ pria dari $n$ pria, ada $(k n)$ cara.
- Maka sisa $n - k$ orang komite harus dipilih dari $n$ wanita, ada $(n - k n)$ cara.
- Menggunakan identitas simetri $(n - k n) = (k n)$ , banyaknya cara memilih $k$ pria dan $n - k$ wanita adalah:

$(k n) \cdot (n - k n) = (k n) \cdot (k n) = (k n)^{2}$

Menjumlahkan untuk semua nilai $k \in {0, 1, \dots, n}$ memberikan total cara memilih komite. Karena kedua ruas menghitung objek yang sama, maka terbukti $\sum_{k = 0}^{n} (k n)^{2} = (n 2 n)$ . $■$

Navigasi Sub-Topik

← Sub-Topik Sebelumnya: Fungsi Pembangkit
Kembali ke Materi Kombinatorika

Latihan Akhir Modul Kombinatorika ONMIPA

Bagian I: 10 Soal Isian Singkat

Bagian II: 5 Soal Essay Pembuktian

Navigasi Sub-Topik

Materi Terkait (Linked References) (1)

Fungsi Pembangkit Biasa & Eksponensial

Diskusi & Tanya Jawab

Title