---
title: "Kombinatorika dan Pencacahan"
book: "Matematika Sekolah Menengah Atas"
subject: math
language: id
chapter: 27
exercises: 10
source: https://one-course.com/books/math/2/id/chapter/27-kombinatorika-dan-pencacahan
---

# Bab 27 — Kombinatorika dan Pencacahan

Kombinatorika adalah seni mencacah tanpa mendaftar. Dua asasnya yang paling dasar — jumlahkan ukuran pilihan yang [saling lepas](https://one-course.com/books/math/2/id/chapter/9-peluang-dan-penyampelan#def-g10-proba-operations), kalikan banyaknya pilihan yang saling bebas — sudah cukup untuk mencacah [susunan](#def-g12-comb-tuples), [permutasi](#def-g12-comb-permutation) dan himpunan bagian suatu himpunan berhingga, dan berpuncak pada teorema binomial.

## 27.1 Dua asas pencacahan

Kita menulis $\abs{E}$ untuk banyaknya anggota (*kardinalitas*) suatu himpunan berhingga $E$.

**Proposisi 27.1 (Asas penjumlahan).**

Jika himpunan berhingga $E$ dipartisi menjadi himpunan bagian $A_1, \dots, A_k$ ([saling lepas](https://one-course.com/books/math/2/id/chapter/9-peluang-dan-penyampelan#def-g10-proba-operations) sepasang demi sepasang, dengan gabungan $E$), maka

$$
\abs{E} = \abs{A_1} + \abs{A_2} + \dots + \abs{A_k}.
$$

**Proposisi 27.2 (Asas perkalian).**

Jika sebuah objek dibangun lewat $k$ pilihan berturut-turut, dengan $n_1$ pilihan pada langkah pertama dan, *apa pun pilihan sebelumnya*, $n_i$ pilihan pada langkah ke-$i$, maka banyaknya objek yang terbangun adalah $n_1 \times n_2 \times \dots \times n_k$.

**Bukti.** Kedua pernyataan itu dibuktikan dengan induksi pada $k$; kasus $k = 2$ pada pernyataan kedua sama dengan mencacah larik persegi panjang baris demi baris. ∎

**Contoh 27.3.**

Sebuah rumah makan menawarkan 4 hidangan pembuka, 6 hidangan utama, 3 hidangan penutup: $4 \times 6 \times 3 = 72$ santapan tiga hidangan yang berbeda.

## 27.2 Tupel, permutasi, faktorial

**Definisi 27.4 (Tupel-kkk).**

Suatu *tupel-$k$* dari himpunan $E$ adalah daftar terurut $(x_1, \dots, x_k)$ beranggotakan $E$, dengan pengulangan diperbolehkan. Tupel-$k$ yang anggotanya *berbeda* disebut *susunan* $k$ anggota $E$.

**Proposisi 27.5.**

Misalkan $\abs E = n$. Banyaknya tupel-$k$ dari $E$ adalah $n^k$. Banyaknya [susunan](#def-g12-comb-tuples) $k$ anggota $E$ ($0 \leq k \leq n$) adalah

$$
n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!},
$$

dengan $n! = 1 \times 2 \times \dots \times n$ (dan $0! = 1$) yang disebut *faktorial* dari $n$.

**Bukti.** Asas perkalian: untuk tupel-$k$ ada $n$ pilihan pada masing-masing $k$ langkahnya; untuk [susunan](#def-g12-comb-tuples), ada $n$ pilihan bagi $x_1$, lalu $n - 1$ bagi $x_2$ (satu anggotanya sudah terpakai), …, $n - k + 1$ bagi $x_k$. ∎

**Definisi 27.6 (Permutasi).**

Suatu *permutasi* dari $E$ adalah [susunan](#def-g12-comb-tuples) seluruh $n$ anggota $E$, yaitu pengurutan $E$. Menurut [Proposisi 27.5](#prop-g12-comb-tuples) (kasus $k = n$), banyaknya permutasi suatu himpunan beranggota $n$ adalah $n!$.

**Contoh 27.7.**

Lima pelari dapat mencapai garis akhir dalam $5! = 120$ urutan yang berbeda. Banyaknya podium yang mungkin (tiga tempat teratas) adalah $5 \times 4 \times 3 = 60$.

## 27.3 Kombinasi dan koefisien binomial

**Definisi 27.8 (Kombinasi).**

Suatu *kombinasi* dari $k$ anggota $E$ adalah himpunan bagian $E$ yang beranggota $k$ (tanpa urutan, tanpa pengulangan). Banyaknya ditulis $\dbinom{n}{k}$, dibaca “$n$ pilih $k$”.

**Teorema 27.9.**

Untuk $0 \leq k \leq n$:

$$
\binom{n}{k} = \frac{n!}{k!\,(n-k)!} .
$$

**Bukti.** Cacahlah [susunan](#def-g12-comb-tuples) $k$ anggota $E$ dengan dua cara. Secara langsung: $\frac{n!}{(n-k)!}$. Atau, pilihlah dahulu himpunan bagian yang mendasarinya ($\binom nk$ cara), lalu urutkan ($k!$ cara); asas perkaliannya memberi $\binom{n}{k}\,k!$. Dengan menyamakan keduanya, $\binom nk = \frac{n!}{k!(n-k)!}$. ∎

**Proposisi 27.10 (Identitas dasar).**

Untuk $0 \leq k \leq n$:

$$
\binom{n}{0} = \binom{n}{n} = 1, \qquad
\binom{n}{1} = n, \qquad
\binom{n}{k} = \binom{n}{n-k},
$$

dan *kaidah Pascal*: untuk $1 \leq k \leq n-1$,

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

**Bukti.** Kesetangkupan $\binom nk = \binom{n}{n-k}$ berlaku sebab pengambilan [komplemennya](https://one-course.com/books/math/2/id/chapter/9-peluang-dan-penyampelan#def-g10-proba-operations) memasangkan himpunan bagian beranggota $k$ dengan yang beranggota $(n-k)$, satu lawan satu. Untuk [kaidah Pascal](#prop-g12-comb-identities), tetapkan satu anggota $a \in E$ lalu pilahlah himpunan bagian beranggota $k$ itu menjadi yang memuat $a$ — yang diperoleh dengan menambahkan $a$ pada himpunan bagian beranggota $(k-1)$ dari $E \setminus \{a\}$, dan banyaknya $\binom{n-1}{k-1}$ — serta yang tidak memuat $a$, yaitu himpunan bagian beranggota $k$ dari $E \setminus \{a\}$, yang banyaknya $\binom{n-1}{k}$. Simpulkan dengan asas penjumlahannya. ∎

[Kaidah Pascal](#prop-g12-comb-identities) membangkitkan koefisiennya baris demi baris, dan itulah yang disebut *[segitiga Pascal](https://one-course.com/books/math/2/id/chapter/19-distribusi-binomial#prop-g11-binom-pascal)*: setiap isian adalah jumlah dua isian di atasnya.

![Segitiga Pascal, baris n = 0 sampai 5: kaidah Pascal 41 + 42 = 52 sedang beraksi.](https://one-course.com/images/onecourse/chapters/math-2/g12-comb/fig-37a02167c00d.svg)

*[Segitiga Pascal](https://one-course.com/books/math/2/id/chapter/19-distribusi-binomial#prop-g11-binom-pascal), baris $n = 0$ sampai $5$: [kaidah Pascal](#prop-g12-comb-identities) $\binom{4}{1} + \binom{4}{2} = \binom{5}{2}$ sedang beraksi.*

**Teorema 27.11 (Teorema binomial).**

Untuk semua $a, b \in \R$ (atau $\C$) dan $n \in \N$:

$$
(a+b)^n = \sum_{k=0}^{n} \binom{n}{k}\, a^{k}\, b^{\,n-k} .
$$

**Bukti.** Jabarkan hasil kali $(a+b)(a+b)\cdots(a+b)$ ($n$ faktor): setiap suku pada penjabarannya memilih $a$ atau $b$ pada tiap faktornya, dan menghasilkan $a^k b^{n-k}$ dengan $k$ menyatakan banyaknya faktor yang menyumbang $a$. Banyaknya cara memilih $k$ faktor itu di antara $n$ faktornya adalah $\binom nk$, dan itulah koefisien $a^k b^{n-k}$. ∎

**Akibat 27.12.**

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

**Bukti.** Ambil $a = b = 1$, lalu $a = -1$, $b = 1$ pada teorema binomialnya. Identitas pertamanya juga bermakna langsung: himpunan beranggota $n$ mempunyai $2^n$ himpunan bagian (tiap anggotanya masuk atau tidak: asas perkalian), yang dipilah menurut ukurannya. ∎

**Metode 27.13 (Memilih model yang tepat).**

Sebelum mencacah, jawablah dua pertanyaan: *apakah urutannya penting?* dan *apakah pengulangan diperbolehkan?*

|  | urutan penting | urutan tak penting |
| --- | --- | --- |
| pengulangan boleh | $n^k$ (tupel) | (universitas) |
| tanpa pengulangan | $\frac{n!}{(n-k)!}$ ([susunan](#def-g12-comb-tuples)) | $\binom nk$ (himpunan bagian) |

Mengambil bola dari sebuah guci: *dengan pengembalian, berurutan* $\to$ tupel; *tanpa pengembalian, berurutan* $\to$ [susunan](#def-g12-comb-tuples); *segenggam sekaligus* $\to$ himpunan bagian.

## 27.4 Latihan

**Latihan 27.1 ★.**

Sebuah pelat nomor terdiri atas 2 huruf (A–Z), lalu 3 angka, lalu 2 huruf. Berapa banyak pelat yang mungkin? Berapa yang tak punya karakter berulang?

**Solusi Latihan 27.1.**

Asas perkalian: $26^2 \times 10^3 \times 26^2 = 26^4 \times 10^3 = 456\,976\,000$.

Tanpa karakter yang berulang, keempat hurufnya harus berbeda ($26 \times 25 \times 24 \times 23$ cara, dengan mengisi kedudukan hurufnya berurutan) dan ketiga angkanya berbeda ($10 \times 9 \times 8$):

$$
26 \times 25 \times 24 \times 23 \times 10 \times 9 \times 8
= 358\,800 \times 720 = 258\,336\,000 .
$$

**Latihan 27.2 ★.**

Hitunglah $\dbinom{8}{3}$, $\dbinom{10}{8}$, lalu sederhanakan $\dfrac{\binom{n}{2}}{\binom{n+1}{2}}$.

**Solusi Latihan 27.2.**

$\dbinom83 = \dfrac{8 \times 7 \times 6}{3!} = 56$; $\dbinom{10}{8} = \dbinom{10}{2} = \dfrac{10 \times 9}{2} = 45$;

$$
\frac{\binom n2}{\binom{n+1}2}
= \frac{n(n-1)/2}{(n+1)n/2} = \frac{n-1}{n+1}.
$$

**Latihan 27.3 ★.**

Di sebuah kelas berisi 30 murid, harus dipilih satu panitia beranggota 4 murid, lalu seorang ketua dan seorang bendahara dari dalam panitia itu (satu orang tidak boleh merangkap kedua jabatan). Berapa banyak hasil yang mungkin?

**Solusi Latihan 27.3.**

Pilihlah panitianya: $\binom{30}{4}$ cara. Lalu pilihlah ketua dan bendaharanya di antara yang 4 itu, berurutan: $4 \times 3 = 12$ cara. Seluruhnya

$$
\binom{30}{4} \times 12 = 27\,405 \times 12 = 328\,860 .
$$

**Latihan 27.4 ★.**

Jabarkan $(x + 2)^5$ dan $(1 - x)^6$ dengan teorema binomial. Berapakah koefisien $x^3$ pada $(2x + 3)^7$?

**Solusi Latihan 27.4.**

$$
(x+2)^5 = x^5 + 10x^4 + 40x^3 + 80x^2 + 80x + 32 ,
$$

$$
(1-x)^6 = 1 - 6x + 15x^2 - 20x^3 + 15x^4 - 6x^5 + x^6 .
$$

Pada $(2x+3)^7$, suku dalam $x^3$ adalah $\binom{7}{3}(2x)^3\,3^4 = 35 \times 8 \times 81\, x^3$, sehingga koefisiennya $22\,680$.

**Latihan 27.5 ★★.**

Satu tangan poker baku terdiri atas 5 kartu dari satu pak berisi 52 kartu.

1. Ada berapa banyak tangan yang mungkin?
2. Berapa banyak tangan yang memuat tepat satu kartu raja? Sekurang-kurangnya satu kartu raja?
3. Berapa banyak tangan yang berbentuk tiga-dua (tiga kartu berperingkat sama, dua kartu berperingkat lain yang sama)?

**Solusi Latihan 27.5.**

*1.* $\dbinom{52}{5} = 2\,598\,960$.

*2.* Tepat satu kartu raja: pilihlah kartunya ($4$ cara) lalu lengkapi dengan $4$ kartu bukan raja: $4 \times \binom{48}{4} = 4 \times 194\,580 = 778\,320$. Sekurang-kurangnya satu kartu raja, lewat pencacahan [komplemennya](https://one-course.com/books/math/2/id/chapter/9-peluang-dan-penyampelan#def-g10-proba-operations): $\binom{52}{5} - \binom{48}{5} = 2\,598\,960 - 1\,712\,304 = 886\,656$.

*3.* Pilihlah peringkat bagi tiga kartu sekawannya ($13$), warnanya ($\binom43 = 4$), peringkat bagi pasangannya ($12$ yang tersisa), lalu warnanya ($\binom42 = 6$): $13 \times 4 \times 12 \times 6 = 3744$.

**Latihan 27.6 ★★.**

Ada berapa banyak anagram (penyusunan ulang hurufnya, bermakna atau tidak) yang dimiliki kata MATH? Dan kata BANANA? (Petunjuk untuk BANANA: tempatkan dahulu ketiga huruf A-nya.)

**Solusi Latihan 27.6.**

Kata MATH mempunyai 4 huruf yang berbeda: $4! = 24$ anagram.

Kata BANANA mempunyai 6 huruf: tiga A, dua N, satu B. Pilihlah kedudukan huruf A-nya ($\binom63$), lalu kedudukan huruf N di antara sisanya ($\binom32$), dan huruf B mengambil tempat terakhirnya:

$$
\binom{6}{3}\binom{3}{2} = 20 \times 3 = 60 .
$$

(Setara dengan $\frac{6!}{3!\,2!\,1!} = 60$.)

**Latihan 27.7 ★★.**

Buktikan identitas $k\dbinom{n}{k} = n\dbinom{n-1}{k-1}$ ($1 \leq k \leq n$) dengan dua cara: lewat rumus [faktorialnya](#prop-g12-comb-tuples), dan dengan mencacah lewat dua cara pasangan (panitia beranggota $k$ orang, ketuanya) yang dipilih dari $n$ orang.

**Solusi Latihan 27.7.**

*Secara aljabar:*

$$
k\binom nk = \frac{k\,n!}{k!(n-k)!} = \frac{n!}{(k-1)!\,(n-k)!}
= n\,\frac{(n-1)!}{(k-1)!\bigl((n-1)-(k-1)\bigr)!} = n\binom{n-1}{k-1}.
$$

*Lewat pencacahan ganda:* cacahlah pasangan (panitia beranggota $k$, ketuanya). Pilihlah panitianya dahulu ($\binom nk$) lalu ketuanya ($k$): ada $k\binom nk$ pasangan. Atau pilihlah ketuanya dahulu ($n$ pilihan) lalu $k-1$ anggota lainnya dari $n-1$ yang tersisa: ada $n\binom{n-1}{k-1}$ pasangan.

**Latihan 27.8 ★★.**

Sebuah lintasan pada bidang berjalan dari $(0,0)$ ke $(m, n)$ dengan langkah satuan ke timur atau ke utara. Tunjukkan bahwa banyaknya lintasan itu $\dbinom{m+n}{m}$.

**Solusi Latihan 27.8.**

Sebuah lintasan terdiri atas tepat $m + n$ langkah, dengan $m$ langkah ke timur dan $n$ ke utara; lintasan itu sepenuhnya ditentukan oleh himpunan saat (di antara yang $m+n$) ketika langkahnya ke timur. Ada $\binom{m+n}{m}$ pilihan semacam itu.

**Latihan 27.9 ★★★.**

Buktikan *identitas Vandermonde*: untuk $0 \leq k \leq m + n$,

$$
\binom{m+n}{k} = \sum_{j=0}^{k} \binom{m}{j}\binom{n}{k-j},
$$

dengan mencacah himpunan bagian beranggota $k$ dari himpunan yang terbelah menjadi satu kelompok beranggota $m$ dan satu kelompok beranggota $n$. Simpulkan bahwa $\displaystyle\sum_{j=0}^{n}\binom{n}{j}^{\!2} = \binom{2n}{n}$.

**Solusi Latihan 27.9.**

Belahlah himpunan berisi $m + n$ orang menjadi kelompok $A$ beranggota $m$ dan kelompok $B$ beranggota $n$. Suatu himpunan bagian beranggota $k$ memuat sejumlah $j$ anggota $A$ ($0 \leq j \leq k$) dan $k - j$ anggota $B$; untuk $j$ yang tetap ada $\binom mj \binom{n}{k-j}$ himpunan bagian semacam itu, dan asas penjumlahan atas $j$ memberi identitas Vandermonde.

Dengan $m = n = k$:

$$
\binom{2n}{n} = \sum_{j=0}^n \binom nj \binom{n}{n-j}
= \sum_{j=0}^n \binom nj^{2},
$$

dengan memakai kesetangkupan $\binom{n}{n-j} = \binom nj$.

**Latihan 27.10 ★★★.**

Dengan teorema binomial, tunjukkan bahwa untuk semua $n \geq 1$,

$$
\sum_{k=1}^{n} k \binom{n}{k} = n\,2^{n-1}.
$$

(Petunjuk: turunkan $(1+x)^n$, atau pakailah [Latihan 27.7](#exo-g12-comb-7).)

**Solusi Latihan 27.10.**

*Lewat [Latihan 27.7](#exo-g12-comb-7):*

$$
\sum_{k=1}^n k\binom nk = \sum_{k=1}^n n\binom{n-1}{k-1}
= n\sum_{j=0}^{n-1}\binom{n-1}{j} = n\,2^{n-1},
$$

menurut [Akibat 27.12](#cor-g12-comb-sums). *Lewat penurunan:* menurunkan $(1+x)^n = \sum_k \binom nk x^k$ memberi $n(1+x)^{n-1} = \sum_k k \binom nk x^{k-1}$; lalu hitung nilainya di $x = 1$.

## 27.5 Soal: Seni mencacah dua kali

**Soal 27.1.**

Soal akhir pekan — bintang dan batang, topi yang tertukar semua, dan identitas yang terbukti dengan mencacah satu hal dua cara

Muslihat terdalam dalam kombinatorika sesungguhnya sederhana sekali: cacahlah kumpulan yang sama dua kali, dengan dua cara yang berbeda, lalu samakan jawabannya. Soal ini melatih model pada [Metode 27.13](#met-g12-comb-model), menambahkan satu teknik yang tak diperlukan uraian bab ini — *bintang dan batang* milik pencacahan es krim — lalu mencacah *topi yang tertukar semua* yang masyhur itu secara eksak, dan menemukan bilangan $\frac1\eu$ menunggu di dasar tumpukan topinya, kemunculannya yang ketiga di dalam buku ini.

**Bagian I — Memilih modelnya.**

1. Cacahlah pelat nomor yang tersusun atas $2$ huruf lalu $3$ angka; kemudian anagram kata BANANA.
2. Dari satu pak berisi $32$ kartu, cacahlah tangan beranggota $5$ kartu; lalu tangan yang memuat tepat $2$ dari $4$ kartu raja.
3. Sebuah robot berjalan dari $(0,0)$ ke $(4,3)$ hanya dengan langkah satuan ke kanan atau ke atas: ada berapa lintasan? (Sandikan lintasannya sebagai kata dalam huruf R dan U.)
4. Jabarkan $(1 + x)^4$ dengan teorema binomial ( [Teorema 27.11](#thm-g12-comb-binomial) ); lalu hitung nilainya di $x = 1$ dan $x = -1$ : dua identitas mana tentang bilangan $\binom nk$ yang jatuh dari situ?
5. Buktikan dengan pencacahan ganda bahwa $k\binom nk = n\binom{n-1}{k-1}$ (cacahlah panitia-beserta-ketuanya dengan dua cara), lalu simpulkan $\sum_{k=0}^{n} k\binom nk = n\,2^{n-1}$ .

**Bagian II — Bintang dan batang.**

6. Sebuah kedai es krim menjual $4$ rasa; kamu memesan $10$ sendok (rasanya boleh berulang, urutan di dalam cangkirnya tidak penting). Sandikan pesanannya sebagai deretan $10$ bintang (sendoknya) yang dipisahkan oleh $3$ batang (pergantian rasanya), lalu cacahlah pesanannya.
7. Cacahlah tripel [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) tak negatif dengan $x + y + z = 12$ .
8. Cacahlah tripel [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) *positif* dengan $x + y + z = 12$ (substitusikan $x = 1 + x'$ , dan seterusnya).
9. Ada berapa monomial berbeda yang muncul pada penjabaran $(a + b + c)^5$ ?
10. Ujilah kewarasan caranya: cacahlah pesanan $3$ sendok dari $2$ rasa dengan rumusnya, lalu daftarkan semuanya dan bandingkan.
11. Sebutkan dengan tepat di mana “sendoknya identik” masuk ke dalam penyandiannya — lalu cacahlah apa yang terjadi jika sebaliknya sendoknya dimakan berurutan (kedudukannya berbeda), dengan daftar periksa pada [Metode 27.13](#met-g12-comb-model) .

**Bagian III — Topi yang tertukar semua.** Suatu *[permutasi](#def-g12-comb-permutation) kacau* adalah pembagian ulang $n$ topi kepada $n$ pemiliknya yang membuat *tak seorang pun* menerima topinya sendiri; misalkan $D_n$ mencacahnya. ([Soal 18.1](https://one-course.com/books/math/2/id/chapter/18-peluang-dan-peubah-acak#pb-g11-prob-1) menunjukkan bahwa satu tamu rata-rata memperoleh kembali topinya sendiri — kini kita mencacah pesta yang sepenuhnya sial itu secara eksak.)

12. Hitunglah $D_1$ , $D_2$ , $D_3$ dengan mendaftar, lalu $D_4$ dengan sabar (atau dengan cerdik).
13. Berilah alasan bagi rekurensi $D_n = (n - 1)\left(D_{n-1} + D_{n-2}\right)$ : tamu 1 menerima suatu topi $k \neq 1$ ( $n - 1$ pilihan); lalu pilahlah menurut apakah tamu $k$ menerima topi 1 atau tidak. Periksalah bahwa itu menghasilkan kembali $D_4$ , lalu hitunglah $D_5$ .
14. Untuk $n = 3$ , buktikan dengan pemuatan–pengeluaran (kurangkan pemberian yang menetapkan sekurang-kurangnya satu topi, lalu tambahkan kembali kelebihan cacahnya) bahwa $D_3 = 3!\left(1 - \frac{1}{1!} + \frac{1}{2!} -  \frac{1}{3!}\right)$ , lalu nyatakan rumus umumnya.
15. Hitunglah $\frac{D_5}{5!}$ lalu bandingkan dengan $\frac1\eu \approx 0.3679$ : peluang bahwa sebuah pesta besar yang dikocok tertukar sepenuhnya adalah $\frac1\eu$ — penampilan singkat ketiga tetapan ini, sesudah undian dan sekretaris pada [Soal 23.1](https://one-course.com/books/math/2/id/chapter/23-eksponen-dan-logaritma#pb-g12-exp-1) . (Sebabnya: rumus pada pertanyaan 14 adalah awal sebuah deret masyhur untuk $\eu^{-1}$ , yang diceritakan dalam jilid universitas.)
16. Tukar kado di antara $10$ sahabat: namanya diambil secara acak seragam. Berapa peluang pengambilannya sah (tak seorang pun mengambil namanya sendiri), dan berapa kali pengambilan ulang yang patut mereka harapkan?

**Bagian IV — Mencacah dua kali, menang dua kali.**

17. Lema jabat tangan: pada pesta mana pun, menjumlahkan atas para tamunya banyaknya tangan yang dijabat masing-masing akan mencacah tiap jabat tangan tepat dua kali. Simpulkan bahwa *banyaknya tamu yang menjabat sejumlah ganjil tangan selalu genap* — lalu periksalah bahwa pernyataan itu masuk akal pada pesta bertiga.
18. Buktikan permatanya, $1^3 + 2^3 + \dots + n^3 = (1 + 2 + \dots + n)^2$ , dengan induksi, lalu periksalah untuk $n = 3$ . (Jumlah Gauss kecil, yang dikuadratkan, ternyata mencacah pangkat tiga.)
19. Identitas Vandermonde ( [Latihan 27.9](#exo-g12-comb-9) ) lewat lintasan: tafsirkan $\binom{2n}{n}$ sebagai lintasan kekisi semacam pertanyaan 3 dari $(0,0)$ ke $(n,n)$ , potonglah setiap lintasan di perpotongannya dengan diagonal lawannya, lalu jelaskan bagaimana $\sum_j \binom nj^2$ muncul.
20. Penutup — empat jurus sang pencacah, masing-masing satu baris dengan satu contoh dari soal ini: kalikan tahapannya dan jumlahkan kasusnya; sandikan dengan cerdik (bintang dan batang, kata lintasan); cacahlah hal yang sama dua kali (panitia-beserta-ketua, jabat tangan); kurangkan yang tak diinginkan lalu perbaiki kelebihan cacahnya ( [permutasi](#def-g12-comb-permutation) kacau). Lalu perhatikan ke mana pencacahan ini bekerja selanjutnya: peluang, dan lintasan pada bab matriks dan graf.

**Solusi Soal 27.1.**

**1.** Ada $26^2 \times 10^3 = 676\,000$ pelat. Kata BANANA: $6$ huruf dengan A yang tiga kali dan N yang dua kali, jadi $\frac{6!}{3!\,2!} = 60$ anagram.

**2.** Ada $\binom{32}{5} = 201\,376$ tangan; dan $\binom42 \binom{28}{3} = 6 \times 3\,276 = 19\,656$ tangan dengan tepat dua kartu raja.

**3.** Sebuah lintasan adalah kata dengan $4$ huruf R dan $3$ huruf U: pilihlah kedudukan huruf U-nya, jadi $\binom73 = 35$.

**4.** $(1+x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4$. Di $x = 1$: $\sum_k \binom nk = 2^n$; di $x = -1$: $\sum_k (-1)^k \binom nk = 0$ — yaitu jumlah barisnya dan jumlah baris berselang-seling pada [segitiga Pascal](https://one-course.com/books/math/2/id/chapter/19-distribusi-binomial#prop-g11-binom-pascal).

**5.** Panitia beranggota $k$ orang beserta ketuanya, dari $n$ orang: pilihlah panitianya lalu ketuanya ($\binom nk \times k$), atau ketuanya lalu anggota lainnya ($n \times \binom{n-1}{k-1}$): keduanya sama. Dengan menjumlahkan atas $k$, ruas kanannya berjumlah $n \sum_j \binom{n-1}{j} = n\,2^{n-1}$.

**6.** Deretan $10$ bintang dan $3$ batang menyandikan pesanannya (sendok rasa 1 sebelum batang pertama, dan seterusnya); deretannya berisi $13$ lambang dan ditentukan oleh kedudukan batangnya, jadi ada $\binom{13}{3} = 286$ pesanan.

**7.** Ada $12$ bintang dan $2$ batang, jadi $\binom{14}{2} = 91$.

**8.** Dengan $x', y', z' \geq 0$ dan $x' + y' + z' = 9$: ada $\binom{11}{2} = 55$.

**9.** Sebuah monomial $a^i b^j c^k$ dengan $i + j + k = 5$: ada $\binom72 = 21$.

**10.** Menurut rumusnya: $3$ bintang, $1$ batang, jadi $\binom41 = 4$; dan daftarnya: $(3,0)$, $(2,1)$, $(1,2)$, $(0,3)$, jadi cocok.

**11.** “Identik” masuk ketika sebuah pesanan dinyatakan tak lebih daripada *cacah* tiap rasanya — bintangnya tidak membawa nama. Jika sendoknya dimakan berurutan, masing-masing dari $10$ kedudukan yang berbeda itu memilih rasanya secara bebas, sehingga ada $4^{10} = 1\,048\,576$ [barisan](https://one-course.com/books/math/2/id/chapter/20-barisan#def-g12-seq-sequence) — model yang lain dan dunia yang lain ([Metode 27.13](#met-g12-comb-model): selalu tanyakan *berurutan? berbeda? boleh berulang?*).

**12.** $D_1 = 0$; $D_2 = 1$ (bertukar); $D_3 = 2$ (dua kitaran-$3$); $D_4 = 9$.

**13.** Tamu 1 menerima topi $k \neq 1$: ada $n - 1$ pilihan. Jika tamu $k$ menerima topi 1, maka $n - 2$ tamu sisanya menukar seluruh topinya sendiri: ada $D_{n-2}$ cara. Jika tamu $k$ *tidak* menerima topi 1, namailah ulang topi 1 sebagai topi terlarang bagi tamu $k$: maka $n - 1$ tamu sisanya tertukar semua, ada $D_{n-1}$ cara. Jadi $D_n = (n-1)(D_{n-1} + D_{n-2})$. Periksalah: $D_4 = 3(2 + 1) = 9$; dan $D_5 = 4(9 + 2) = 44$.

**14.** Dari $3! = 6$ pemberian itu, kurangkan yang menetapkan sekurang-kurangnya satu topi: ada tiga yang menetapkan satu topi tertentu ($2!$ masing-masing, $3 \times 2 = 6$), yang melebihkan cacah pasangannya ($3$ pasangan, $1!$ masing-masing) sehingga harus dikembalikan, lalu identitasnya dikurangkan lagi ($1$): jadi $D_3 = 6 - 6 + 3 - 1 = 2$, yaitu $3!\left(1 - 1 + \frac12 - \frac16\right) = 2$. Secara umum $D_n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!}$.

**15.** $\frac{D_5}{120} = \frac{44}{120} \approx
0.3667$, sudah dekat dengan $\frac1\eu \approx 0.3679$: jumlah berselang-seling $1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \dots$ berbaris menuju $\eu^{-1}$. Topi pada pesta besar tertukar semua kira-kira $36.8\,\%$ waktunya — tetapan milik undian dan sekretaris itu, untuk penampakan ketiganya.

**16.** $\P(\text{sah}) = \frac{D_{10}}{10!} \approx
0.368$. Setiap pengambilan ulang berhasil dengan peluang $\approx \frac1\eu$, jadi harapan banyaknya pengambilan kira-kira $\eu \approx 2.7$: sediakanlah tiga kali putaran topi.

**17.** Setiap jabat tangan menyumbang $2$ pada cacah derajat seluruhnya, sehingga jumlah bilangan jabat tangan semua tamu bernilai genap. Jumlah [bilangan bulat](https://one-course.com/books/math/2/id/chapter/1-bilangan-dan-himpunan-bilangan#def-g10-numbers-sets) bernilai genap hanya jika banyaknya suku ganjil itu genap: jadi penjabat ganjil selalu berpasangan. (Pada pesta bertiga: profil jabat tangan yang mungkin tak pernah punya tepat satu atau tiga isian ganjil — periksalah keempat graf yang mungkin.)

**18.** Untuk $n = 1$: $1 = 1$. Jika $1^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$, maka dengan menambahkan $(n+1)^3$:

$$
\frac{n^2(n+1)^2}{4} + (n+1)^3
= \frac{(n+1)^2\left(n^2 + 4n + 4\right)}{4}
= \left(\frac{(n+1)(n+2)}{2}\right)^{\!2} :
$$

itulah pewarisannya. Untuk $n = 3$: $1 + 8 + 27 = 36 = 6^2$.

**19.** Sebuah lintasan menuju $(n, n)$ menempuh $2n$ langkah dan memotong diagonal lawannya $x + y = n$ di tepat satu titik kekisi $(j, n - j)$; separuh pertamanya adalah lintasan dengan $j$ huruf R di antara $n$ langkah ($\binom nj$ pilihan), dan separuh keduanya, yang dibaca mundur, juga demikian ($\binom nj$ lagi, menurut kesetangkupannya). Dengan menjumlahkan atas titik potongnya: $\binom{2n}{n} = \sum_j \binom nj^2$ — identitas Vandermonde, yang tergambar.

**20.** Kalikan tahapannya, jumlahkan kasusnya: pelat nomor dan tangan poker. Sandikan: lintasan sebagai kata RU, pesanan sebagai bintang dan batang. Cacahlah dua kali: panitia-beserta-ketua, jabat tangan, lintasan yang terpotong di tengah. Kurangkan lalu perbaiki: topi yang tertukar semua, dengan $\frac1\eu$ sebagai sisanya. Persinggahan berikutnya: cacahan ini di bawah pecahan peluang, dan pangkat matriks ketetanggaan yang mencacah lintasan dua bab lagi.