---
title: "Pencacahan"
book: "Matematika Universitas — Tahun 1"
subject: math
language: id
chapter: 2
exercises: 12
source: https://one-course.com/books/math/3/id/chapter/2-pencacahan
---

# Bab 2 — Pencacahan

Mencacah [himpunan hingga](#def-b1-counting-card) terdengar sederhana — dan dengan cepat menjadi halus. Bab ini mendefinisikan [kardinalitas](#def-b1-counting-card) secara benar (lewat bijeksi, sejalan dengan [Bab 1](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#ch-b1-logic)), menegakkan segelintir asas pencacahan yang darinya segala sesuatu mengikut, lalu menurunkan hasil cacah yang klasik: daftar, [permutasi](#def-b1-counting-objects), [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian, [koefisien binomial](#def-b1-counting-objects).

## 2.1 Kardinalitas himpunan hingga

**Definisi 2.1 (Himpunan hingga, kardinalitas).**

Untuk $n \in \N^*$, tulis $\intint{1}{n} = \{1, 2, \dots,
n\}$. [Himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) $E$ disebut *hingga* bila $E = \emptyset$ atau ada bijeksi dari $\intint{1}{n}$ pada $E$ untuk suatu $n \in \N^*$; bilangan $n$ ini tunggal ([Teorema 2.2](#thm-b1-counting-welldef)) dan merupakan *kardinalitas* dari $E$, ditulis $\abs{E}$ (dengan $\abs{\emptyset} = 0$).

**Teorema 2.2 (Kardinalitas terdefinisi dengan baik).**

Jika $m \neq n$, tidak ada bijeksi dari $\intint{1}{m}$ pada $\intint{1}{n}$. Lebih tepatnya, jika $m > n$ maka tidak ada injeksi dari $\intint{1}{m}$ ke dalam $\intint{1}{n}$.

**Bukti.** Kita buktikan dengan induksi pada $n$ [pernyataan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-statement) berikut: *untuk setiap $m > n$, tidak ada injeksi $\intint{1}{m} \to \intint{1}{n}$*. Untuk $n = 0$ sasarannya kosong sedangkan $m \geq 1$: tidak ada [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) sama sekali. Andaikan [pernyataan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-statement) itu berlaku untuk $n$, dan andaikan $f \colon
\intint{1}{m} \to \intint{1}{n+1}$ sebuah injeksi dengan $m > n + 1$. Bila nilai $n + 1$ tidak tercapai, $f$ adalah injeksi ke dalam $\intint{1}{n}$, bertentangan dengan hipotesis induksinya. Bila tercapai, $f(a) = n + 1$ untuk tepat satu $a$; tukarkan $f(a)$ dengan $f(m)$ (secara formal: komposisikan dengan transposisi kedua nilai itu), sehingga injeksi baru $g$ memenuhi $g(m) = n + 1$. Maka pembatasan $g$ pada $\intint{1}{m-1}$ adalah injeksi ke dalam $\intint{1}{n}$ dengan $m - 1 > n$ — kontradiksi lagi. ∎

**Akibat 2.3 (Prinsip sarang merpati).**

Jika $\abs{E} > \abs{F}$, tak ada [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) $f \colon E \to F$ yang [injektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj): ada dua unsur $E$ yang berbagi peta.

**Bukti.** Tulis $\abs E = m$, $\abs F = n$ dengan $m > n$, lalu pilih bijeksi $u \colon \intint1m \to E$ dan $v \colon F \to \intint1n$. Jika $f$ [injektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj), maka $v \circ f \circ u$ akan menjadi injeksi dari $\intint1m$ ke dalam $\intint1n$ (komposisi injeksi, [Proposisi 1.26](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#prop-b1-logic-comp)), bertentangan dengan [Teorema 2.2](#thm-b1-counting-welldef). ∎

**Catatan 2.4 (Selingan: mengapa ada penukaran pada bukti teorema itu?).**

Bukti [Teorema 2.2](#thm-b1-counting-welldef) memuat langkah cerdik pertama bab ini, yang layak diputar ulang perlahan. Rintangannya: untuk memakai hipotesis induksi kita ingin menghapus titik terakhir $m$ pada sumbernya *dan* titik terakhir $n+1$ pada sasarannya, tetapi $f$ mungkin mengirim titik lain $a$ ke $n
+ 1$, dan menghapus titik sasaran itu lalu merusak [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) di tempat lain. Obatnya: komposisikan $f$ dengan transposisi kedua *nilai* $f(a)$ dan $f(m)$ — sebuah bijeksi pada sasarannya, jadi keinjektifan terjaga — setelah itu nilai $n + 1$ yang merepotkan tadi duduk pada posisi $m$ yang tak berbahaya, dan kedua penghapusan menjadi bersih. Pola “normalkan dulu, baru potong” ini berulang: begitulah rekursi [permutasi](#def-b1-counting-objects) kacau mengalihkan $\sigma^{-1}(n+1)$ pada soal akhir pekan bab ini, dan begitulah [permutasi](#def-b1-counting-objects) ditambal di sepanjang soal [Bab 7](https://one-course.com/books/math/3/id/chapter/7-struktur-aljabar#ch-b1-structures) tentang grup simetri.

**Proposisi 2.5 (Injeksi, surjeksi dan kardinalitas).**

Misalkan $E, F$ [himpunan hingga](#def-b1-counting-card) dengan $\abs{E} = \abs{F}$, dan $f \colon E
\to F$. Maka

$$
f \text{ injektif} \iff f \text{ surjektif} \iff f \text{ bijektif}.
$$

**Bukti.** Andaikan $f$ [injektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj). Maka $f$ adalah bijeksi dari $E$ pada $f(E)$, sehingga $\abs{f(E)} = \abs{E} = \abs{F}$. Jika $f(E)$ melewatkan sebuah titik $y_0$ pada $F$, maka $f$ akan menjadi injeksi dari $E$ ke dalam $F \setminus \{y_0\}$, yaitu [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) berkardinalitas $\abs{F} - 1 < \abs{E}$ — mustahil menurut prinsip sarang merpati. Jadi $f(E) = F$: $f$ [surjektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj), sehingga [bijektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj).

Andaikan $f$ [surjektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj). Pilih untuk setiap $y \in F$ satu [prapeta](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) $s(y)
\in E$; maka $f \circ s = \mathrm{id}_F$, jadi $s$ [injektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj) ([Proposisi 1.26](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#prop-b1-logic-comp)). Menurut paragraf sebelumnya yang diterapkan pada $s$ ([kardinalitas](#def-b1-counting-card) keduanya sama), $s$ [bijektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj). Dari $f \circ s =
\mathrm{id}_F$ kita peroleh $f = \mathrm{id}_F \circ s^{-1} = s^{-1}$, jadi $f$ [bijektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj). Akhirnya, [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) [bijektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj) menurut definisinya sekaligus [injektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj) dan [surjektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj), dan itu menutup daur implikasinya. ∎

**Contoh 2.6 (Kehinggaan itu penting).**

Pada [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) yang *[hingga](#def-b1-counting-card)*, [Proposisi 2.5](#prop-b1-counting-injsur) adalah jalan pintas yang ampuh: setiap [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) [injektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj) dari $E$ ke dirinya sendiri otomatis menjadi [permutasi](#def-b1-counting-objects) $E$ — separuh dari kebijektifan datang cuma-cuma. Kedua implikasi itu runtuh pada [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) tak [hingga](#def-b1-counting-card): $n \mapsto n + 1$ [injektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj) dari $\N$ ke $\N$ tetapi melewatkan $0$, dan [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) $\N \to \N$ yang mengirim $0 \mapsto 0$ dan $n \mapsto n - 1$ untuk $n \geq 1$ [surjektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj) tetapi tidak [injektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj). Setiap kali proposisi ini dipanggil, hipotesis kehinggaannya sedang bekerja sungguhan — tema yang ditelusuri soal akhir pekan [Bab 1](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#ch-b1-logic) dari sisi yang berlawanan, tempat [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) tak [hingga](#def-b1-counting-card) persis adalah [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) yang punya pemetaan-diri semacam itu.

**Contoh 2.7 (Separuh pekerjaan, cuma-cuma).**

Tinjau [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) $f$ pada $\{0, 1, \dots, 6\}$ yang mengirim $k$ ke sisa pembagian $3k$ oleh $7$; tabel nilainya adalah

$$
0,\ 3,\ 6,\ 2,\ 5,\ 1,\ 4 .
$$

Apakah $f$ sebuah bijeksi? Keinjektifan saja sudah cukup ([Proposisi 2.5](#prop-b1-counting-injsur)): jika $3k$ dan $3k'$ bersisa sama, maka $7$ membagi $3(k - k')$, dan karena $7$ prima serta tidak membagi $3$, ia membagi $k - k'$ (lema Euclid, yang di sini dipakai pada taraf sekolah menengah dan dibuktikan pada [Bab 6](https://one-course.com/books/math/3/id/chapter/6-aritmetika-bilangan-bulat#ch-b1-arith)); dengan $\abs{k - k'} \leq 6$ hal ini memaksa $k = k'$. Kesurjektifan datang cuma-cuma — tak perlu menyelesaikan $3k \equiv c$ untuk setiap $c$, meskipun tabelnya membenarkan bahwa setiap nilai muncul tepat sekali. Jalan pintas itu adalah kuda beban: ia membuktikan keterbalikan perkalian modular ([Bab 6](https://one-course.com/books/math/3/id/chapter/6-aritmetika-bilangan-bulat#ch-b1-arith)), menggerakkan pemasangan pada teorema Wilson, dan kembali dalam aljabar linear sebagai “endomorfisma ruang berdimensi [hingga](#def-b1-counting-card) bersifat [injektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj) jika dan hanya jika [surjektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj)” ([Bab 19](https://one-course.com/books/math/3/id/chapter/19-dimensi-hingga#ch-b1-findim)).

## 2.2 Asas pencacahan

**Proposisi 2.8 (Kaidah jumlah dan kaidah hasil kali).**

Misalkan $E, F$ [himpunan hingga](#def-b1-counting-card).

1. Jika $E \cap F = \emptyset$ , maka $\abs{E \cup F} = \abs{E} +  \abs{F}$ ; lebih umum, untuk [partisi](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#thm-b1-logic-partition) $E$ atas potongan $E_1, \dots, E_k$ berlaku $\abs{E} = \sum_i \abs{E_i}$ .
2. Secara umum, $\abs{E \cup F} = \abs{E} + \abs{F} - \abs{E \cap  F}$ .
3. $\abs{E \times F} = \abs{E} \times \abs{F}$ .
4. [Himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) $F^E$ berisi semua [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) dari $E$ ke $F$ memenuhi $\abs{F^E} = \abs{F}^{\abs{E}}$ .
5. $\abs{\mathcal{P}(E)} = 2^{\abs{E}}$ .

**Bukti.** (1) Sambungkan pencacahannya: jika $E = \{x_1, \dots, x_m\}$ dan $F =
\{y_1, \dots, y_n\}$ tanpa pengulangan, maka $x_1, \dots, x_m, y_1,
\dots, y_n$ mencacah $E \cup F$ tanpa pengulangan (karena saling lepas). Induksi memperluasnya ke $k$ potongan.

(2) $E \cup F$ adalah gabungan saling lepas dari $E$ dan $F \setminus E$, dan $F$ adalah gabungan saling lepas dari $F \cap E$ dan $F \setminus E$; jadi $\abs{E \cup F} = \abs{E} + \abs{F \setminus E} = \abs{E} + \abs{F} -
\abs{E \cap F}$.

(3) $E \times F$ adalah gabungan saling lepas, atas $x \in E$, dari [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) $\{x\} \times F$, yang masing-masing berkardinalitas $\abs{F}$; terapkan (1).

(4) Sebuah [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) dari $E = \{x_1, \dots, x_m\}$ ke $F$ persis sama dengan pemilihan tupel-$m$ $(f(x_1), \dots, f(x_m)) \in F^m$; padanan ini adalah bijeksi, dan $\abs{F^m} = \abs{F}^m$ menurut (3) beserta induksi.

(5) [Himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian $E$ berpadanan secara [bijektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj) dengan [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) $E \to \{0, 1\}$ (kirim $A$ ke fungsi indikatornya); terapkan (4). ∎

**Contoh 2.9 (Mencacah lewat komplemen).**

Berapa banyak kode PIN $4$ angka (angka $0$–$9$, urutan penting, pengulangan dibolehkan) yang memuat *sekurang-kurangnya satu* angka berulang? Mencacahnya secara langsung berarti kita harus menjungkirkan kasus “tepat satu pasang, dua pasang, kembar tiga, kembar empat” — lima konfigurasi yang saling bertindihan. Cacah komplemennya saja: seluruh kode berjumlah $10^4 = 10\,000$ (kaidah hasil kali), sedangkan kode dengan empat angka berbeda berjumlah $10 \times 9 \times 8 \times 7 = 5\,040$ (susunan-$4$), jadi jawabannya adalah

$$
10^4 - 10 \cdot 9 \cdot 8 \cdot 7 = 10\,000 - 5\,040 = 4\,960 .
$$

Hampir separuh dari semua PIN mengulang sebuah angka. Inti gagasannya: setiap kali sebuah cacahan dirumuskan dengan “sekurang-kurangnya” atau “tidak semua”, cobalah komplemennya lebih dulu — kaidah jumlah menjamin $\abs{A} = \abs{E} - \abs{\overline A}$, dan komplemennya sering berupa satu konfigurasi yang bersih.

**Contoh 2.10 (Lintasan pada kisi).**

Cacah lintasan terpendek dari sudut $(0,0)$ ke sudut $(4, 3)$ sebuah kisi, dengan hanya boleh melangkah satu petak ke kanan (K) atau satu petak ke atas (A) setiap kali. Setiap lintasan semacam itu menempuh tepat $7$ langkah, yang $4$ di antaranya K dan $3$ di antaranya A; sebaliknya, setiap kata sepanjang $7$ atas huruf K, A dengan empat huruf K menggambarkan tepat satu lintasan. Jadi lintasan berpadanan secara [bijektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj) dengan pilihan posisi huruf K:

$$
\binom{7}{4} = 35 .
$$

Inti gagasannya ada pada *penyandiannya*: cacahan itu menjadi sepele begitu setiap lintasan diterjemahkan menjadi sebuah kata, yakni sebuah [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian posisi — satu lagi contoh dari semboyan bahwa cacahan yang benar adalah bijeksi yang menyamar ([Metode 2.19](#met-b1-counting-which)).

![Salah satu dari 74 = 35 lintasan terpendek dari (0,0) ke (4,3): lintasan yang digambar menyandikan kata KAKKAKA, yakni pilihan posisi \1,3,4,6\ bagi huruf K di antara ketujuh langkahnya.](https://one-course.com/images/onecourse/chapters/math-3/b1-counting/fig-3b2801348791.svg)

*Salah satu dari $\binom74 = 35$ lintasan terpendek dari $(0,0)$ ke $(4,3)$: lintasan yang digambar menyandikan kata KAKKAKA, yakni pilihan posisi $\{1,3,4,6\}$ bagi huruf K di antara ketujuh langkahnya.*

## 2.3 Daftar, permutasi, himpunan bagian

**Definisi 2.11 (Susunan, permutasi, kombinasi).**

Misalkan $E$ [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) dengan $\abs{E} = n$ dan $0 \leq k \leq n$.

- *Susunan-$k$* dari $E$ adalah tupel- $k$ [injektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj) berisi unsur $E$ (pemilihan terurut tanpa pengulangan);
- *permutasi* dari $E$ adalah bijeksi dari $E$ ke dirinya sendiri — setara dengan susunan- $n$ ;
- *kombinasi-$k$* adalah [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian $E$ beranggota $k$ unsur (pemilihan tak terurut tanpa pengulangan). Banyaknya ditulis $\binom{n}{k}$ , dibaca “ $n$ pilih $k$ ” .

**Teorema 2.12 (Ketiga cacahan itu).**

Dengan $n = \abs{E}$ dan $0 \leq k \leq n$:

1. banyaknya susunan- $k$ dari $E$ adalah $n (n-1) \cdots  (n-k+1) = \dfrac{n!}{(n-k)!}$ ;
2. banyaknya [permutasi](#def-b1-counting-objects) $E$ adalah $n!$ ;
3. $\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$ .

**Bukti.** (1) Pilih koordinat pertama ($n$ cara), lalu yang kedua ($n - 1$ pilihan tersisa), …, lalu yang ke-$k$ ($n - k + 1$ pilihan). Secara formal, berinduksilah pada $k$. Untuk $k = 1$ ada $n$ tupel [injektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj) bersuku satu. Andaikan cacahannya berlaku untuk $k - 1$. Setiap susunan-$k$ $(x_1, \dots, x_k)$ diperoleh dari tepat satu susunan-$(k-1)$ — yaitu pemenggalannya $(x_1, \dots, x_{k-1})$ — dengan menambahkan koordinat terakhir di luar $\{x_1, \dots,
x_{k-1}\}$, yang untuknya tepat $n - (k - 1)$ nilai tersedia. Jadi susunan-$k$ terpartisi, lewat pemenggalan, atas kelas-kelas berukuran sama $n - k + 1$ yang terindeks oleh susunan-$(k-1)$, dan kaidah jumlah memberikan

$$
\frac{n!}{(n-k+1)!}\;(n - k + 1) = \frac{n!}{(n-k)!} .
$$

(2) adalah (1) dengan $k = n$.

(3) Setiap [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian beranggota $k$ terurutkan menjadi $k!$ susunan-$k$ yang berbeda, dan setiap susunan-$k$ muncul dari tepat satu [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian: jadi $\frac{n!}{(n-k)!} = \binom nk \cdot k!$. ∎

**Contoh 2.13 (Meja bundar: membagi habis simetrinya).**

Dengan berapa cara $n$ tamu dapat duduk mengelilingi meja bundar, bila dua susunan dianggap sama ketika setiap tamu mempunyai tetangga kiri dan kanan yang sama — yakni sampai rotasi? Setiap susunan melingkar berpadanan dengan tepat $n$ susunan lurus (potong lingkarannya di salah satu dari $n$ tempat), jadi $n!$ urutan lurus itu melebur dalam kelompok beranggota $n$:

$$
\frac{n!}{n} = (n-1)! \quad\text{susunan melingkar.}
$$

Setara dengan itu: dudukkan satu tamu istimewa di mana saja (mematikan kebebasan rotasinya), lalu urutkan $n - 1$ tamu sisanya searah jarum jam. Untuk $n = 6$: ada $120$ meja. Kedua penyelesaian itu memperlihatkan dua obat baku bagi pencacahan berlebih: bagilah dengan banyaknya pengulangan yang persis, atau *patahkan simetrinya* dengan memaku satu objek. Keduanya menuntut ukuran kelompok pengulangan itu sama bagi setiap konfigurasi — syarat yang juga dipakai bukti rumus $\binom nk = \frac{n!}{k!\,(n-k)!}$ di atas, dengan $k!$ menggantikan $n$.

**Contoh 2.14 (Menambahkan satu kendala).**

Melanjutkan meja bundar tadi: di antara $(n-1)!$ meja berisi $n \geq
3$ tamu, berapa banyak yang mendudukkan dua tamu tertentu $A$ dan $B$ *terpisah* (tidak berdampingan)? Cacah komplemennya. Meja yang $A$ dan $B$-nya duduk bersama: rekatkan keduanya menjadi satu blok — $n - 1$ objek mengelilingi meja, yakni $(n-2)!$ susunan melingkar — lalu urutkan pasangan itu di dalam bloknya ($2$ cara): ada $2\,(n-2)!$ meja yang berdampingan. Jadi

$$
(n-1)! - 2\,(n-2)! = (n-2)!\,\bigl((n - 1) - 2\bigr)
= (n-3)\,(n-2)!
$$

meja membuat keduanya terpisah. Pemeriksaan kewajaran: $n = 3$ memberikan $0$ (mengelilingi segitiga, semua orang bersentuhan) dan $n = 4$ memberikan $2$, yang mudah didaftar dengan tangan. Kiat perekatan — perlakukan blok yang dipaksakan sebagai satu objek, lalu cacah susunan di dalamnya — adalah obat baku bagi kendala kebersebelahan, baik lurus maupun melingkar.

**Proposisi 2.15 (Kesamaan dasar).**

Untuk $0 \leq k \leq n$:

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

**Bukti.** Kesamaan pertama: $A \mapsto E \setminus A$ adalah bijeksi antara [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian beranggota $k$ dan [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian beranggota $(n-k)$. Kaidah Pascal: tetapkan sebuah unsur $a \in E$; [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian beranggota $k$ terbelah atas yang memuat $a$ (pilih $k - 1$ unsur lainnya: $\binom{n-1}{k-1}$) dan yang menghindari $a$ ($\binom{n-1}{k}$). Kesamaan ketiga: kedua ruasnya mencacah semua [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian $E$, dan di ruas kiri cacahan itu dipilah menurut ukurannya ([Proposisi 2.8](#prop-b1-counting-rules) (1) dan (5)). ∎

**Teorema 2.16 (Teorema binomial).**

Untuk setiap $a, b$ dalam sebuah ring komutatif (misalnya $\R$ atau $\C$) dan $n \in \N$:

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

**Bukti.** Menjabarkan $(a+b)(a+b)\cdots(a+b)$ secara distributif menghasilkan satu suku bagi setiap pilihan, pada masing-masing faktor, antara $a$ atau $b$: suku $a^k b^{n-k}$ muncul sekali untuk setiap cara memilih $k$ faktor mana di antara $n$ faktor itu yang menyumbang $a$ — yaitu sebanyak $\binom nk$ kali. (Cara lain: berinduksi pada $n$ memakai kaidah Pascal.) ∎

**Contoh 2.17.**

Dua pengkhususan klasik: $a = b = 1$ memulihkan $\sum_k \binom nk
= 2^n$; $a = -1$, $b = 1$ memberikan $\sum_{k} (-1)^k \binom nk = 0$ untuk $n \geq 1$: di antara [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian sebuah [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) tak kosong, tepat separuhnya berkardinalitas genap.

**Contoh 2.18 (Satu kesamaan, dua bukti).**

Pengkhususan $a = 2$, $b = 1$ pada teorema binomial berbunyi

$$
\sum_{k=0}^{n} \binom nk\,2^k = 3^n .
$$

Berikut kesamaan yang sama tanpa aljabar sama sekali. Ruas kanan mencacah kata sepanjang $n$ atas abjad $\{0, 1, 2\}$ (kaidah hasil kali). Golongkan setiap kata menurut [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) $K$ berisi posisi yang memuat huruf tak nol: memilih $K$ dengan $\abs K = k$ menelan biaya $\binom nk$, lalu masing-masing posisi $K$ secara bebas memuat $1$ atau $2$: ada $2^k$ cara. Kaidah jumlah atas $k$ memberikan ruas kiri. Selain kenikmatan melihat keduanya cocok, kedua bukti itu punya keutamaan yang berbeda: yang aljabar dapat diperluas ke sebarang nilai $a$, sedangkan yang kombinatorial *menjelaskan* rumusnya dan menyesuaikan diri pada kendala (larang huruf $2$ pada posisi terakhir, misalnya) yang tak tertangkap oleh substitusi apa pun. Menjaga kedua teknik itu tetap hidup adalah keterampilan praktis yang dilatih bab ini.

**Metode 2.19 (Cacahan mana yang berlaku?).**

Sebelum menghitung, jawablah dua pertanyaan tentang pemilihannya: apakah *urutan* penting, dan apakah *pengulangan* dibolehkan?

|  | urutan penting | urutan tidak penting |
| --- | --- | --- |
| tanpa pengulangan | $\dfrac{n!}{(n-k)!}$ | $\dbinom{n}{k}$ |
| [6pt] pengulangan dibolehkan | $n^k$ | ([Latihan 2.10](#exo-b1-counting-10)) |

Lalu carilah bijeksi atau [partisi](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#thm-b1-logic-partition) yang menyusutkan masalahnya menjadi cacahan model itu; cacahan yang benar adalah bijeksi yang menyamar.

**Catatan 2.20 (Jebakan yang lazim dalam pencacahan).**

1. *Menjumlahkan kasus yang tidak saling lepas.* Kaidah jumlah menuntut sebuah [partisi](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#thm-b1-logic-partition) ; jika sebuah konfigurasi dapat memenuhi dua kasus sekaligus, ia tercacah dua kali — obatnya adalah inklusi–eksklusi ( [Teorema 2.24](#thm-b1-counting-inclexcl) ) atau pemilahan kasus yang lebih halus.
2. *Terurut lawan tak terurut.* Memilih “panitia beranggota dua” adalah $\binom n2$ , bukan $n(n-1)$ : putuskan *sebelum menghitung* apakah pemilihannya membawa urutan, dan bila cacahan terurut lebih mudah, bagilah dengan banyaknya pengurutan pada akhirnya — tetapi hanya bila setiap objek tak terurut muncul dari *sama* banyak objek terurut.
3. *Pilihan bertahap yang tidak saling bebas.* Kaidah hasil kali menuntut banyaknya pilihan pada setiap tahap tidak bergantung pada pilihan sebelumnya. “Pilih seorang kapten, lalu seorang wakil kapten yang berbeda” aman ( $n(n-1)$ ); “pilih dua pemain yang cocok satu sama lain” sama sekali bukan hasil kali dua tahap.
4. *Pencacahan ganda karena konstruksinya.* Membangun setiap objek dua kali — misalnya mencacah tangan berisi *sekurang-kurangnya* satu raja sebagai (pilih satu raja) $\times$ (pilih $4$ kartu lagi) — melebihkan cacahan tangan yang memuat dua raja. “Sekurang-kurangnya” hampir selalu menuntut komplemen ( [Contoh 2.9](#ex-b1-counting-complement) ).

**Contoh 2.21 (Cacahan bergaya poker).**

Dari setumpuk $52$ kartu, banyaknya tangan berisi $5$ kartu adalah $\binom{52}{5} = 2\,598\,960$. Tangan yang memuat tepat satu raja: pilih rajanya ($4$ cara) lalu $4$ kartu di antara $48$ kartu bukan raja: $4 \binom{48}{4} = 778\,320$. Kaidah hasil kali berlaku karena pilihannya terbelah atas tahap-tahap yang saling bebas.

**Metode 2.22 (Pencacahan ganda).**

Untuk membuktikan kesamaan antara dua ungkapan cacahan, carilah satu [himpunan hingga](#def-b1-counting-card) yang dicacah oleh kedua ruasnya — lazimnya [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) *pasangan* — lalu hitung kardinalitasnya dengan dua urutan yang berbeda. Prototipenya adalah *lema jabat tangan*: pada sebuah pesta, cacah pasangan (orang, tangan yang dijabat). Menjumlahkan atas orang memberikan $\sum_p d_p$ (banyaknya jabat tangan tiap orang $p$); menjumlahkan atas jabat tangan memberikan dua kali banyaknya jabat tangan (masing-masing melibatkan dua orang). Jadi $\sum_p d_p$ genap — sehingga banyaknya orang yang menjabat tangan sejumlah ganjil selalu genap, kesimpulan tak sepele yang diperoleh tanpa rumus sama sekali. Mesin yang sama menggerakkan [Latihan 2.12](#exo-b1-counting-12) dan beberapa pertanyaan pada soal akhir pekan di bawah.

**Contoh 2.23 (Himpunan bagian rata-rata).**

Berapa [kardinalitas](#def-b1-counting-card) rata-rata sebuah [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian dari [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) beranggota $n$ unsur, katakanlah $E$, bila semua $2^n$ [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagiannya sama-sama mungkin? Cacah ganda pasangan $(A, a)$ dengan $a \in A$: menjumlahkan atas [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian memberikan $\sum_A \abs A$, yaitu total yang kita cari; menjumlahkan atas unsur memberikan $n \cdot 2^{n-1}$ (masing-masing dari $n$ unsur itu terletak tepat di separuh [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagiannya — pasangkan setiap $A$ yang memuat $a$ dengan $A
\setminus \{a\}$). Jadi

$$
\frac{1}{2^n}\sum_{A \subseteq E} \abs A
= \frac{n\,2^{n-1}}{2^n} = \frac n2 :
$$

[himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian, rata-rata, terisi separuh — sebagaimana juga diramalkan simetri $A
\leftrightarrow \overline A$ (yang memasangkan ukuran $k$ dengan $n - k$). Dua bukti, satu jawaban, dan keduanya menghindari perhitungan langsung $\sum_k k\binom nk$ pada [Latihan 2.5](#exo-b1-counting-5): pemasangan yang dipilih dengan baik sering menggantikan sebuah kesamaan.

## 2.4 Inklusi–eksklusi

**Teorema 2.24 (Inklusi–eksklusi).**

Untuk [himpunan hingga](#def-b1-counting-card) $A_1, \dots, A_p$:

$$
\Bigl|\, \bigcup_{i=1}^{p} A_i \,\Bigr|
= \sum_{\emptyset \neq I \subseteq \intint{1}{p}}
(-1)^{\abs{I}+1} \Bigl|\, \bigcap_{i \in I} A_i \,\Bigr| .
$$

Untuk $p = 3$: $\abs{A \cup B \cup C} = \abs A + \abs B + \abs C - \abs{A \cap B} -
\abs{A \cap C} - \abs{B \cap C} + \abs{A \cap B \cap C}$.

**Bukti.** Tetapkan sebuah unsur $x$ pada gabungannya lalu cacah sumbangannya pada ruas kanan. Misalkan $J = \{i : x \in A_i\}$, berkardinalitas $m \geq
1$. Unsur $x$ tercacah sekali pada $\abs{\bigcap_{i \in I} A_i}$ tepat ketika $\emptyset \neq I \subseteq J$, dengan tanda $(-1)^{\abs I + 1}$; sumbangan totalnya adalah

$$
\sum_{k=1}^{m} \binom{m}{k} (-1)^{k+1}
= 1 - \sum_{k=0}^{m} \binom mk (-1)^k = 1 - 0 = 1
$$

menurut [Contoh 2.17](#ex-b1-counting-binomial). Jadi setiap unsur gabungan itu tercacah tepat sekali. ∎

**Contoh 2.25 (Mencacah bilangan bulat yang saling prima).**

Berapa banyak bilangan bulat di $\intint1{120}$ yang saling prima dengan $120 = 2^3
\times 3 \times 5$? Sebuah bilangan bulat berbagi faktor dengan $120$ tepat ketika ia habis dibagi $2$, $3$ atau $5$, jadi cacahlah komplemen $A_2 \cup A_3 \cup A_5$, dengan $A_d$ mengumpulkan kelipatan $d$. Di dalam $\intint1{120}$, kelipatan $d$ berjumlah $120/d$ setiap kali $d$ membagi $120$ — tanpa perlu fungsi lantai — dan $A_2 \cap A_3 = A_6$, dan seterusnya. Inklusi–eksklusi:

$$
\abs{A_2 \cup A_3 \cup A_5}
= 60 + 40 + 24 - 20 - 12 - 8 + 4 = 88 ,
$$

jadi ada $120 - 88 = 32$ bilangan bulat yang saling prima dengan $120$. Menarik untuk mengelompokkan ulang perhitungan itu sebagai hasil kali:

$$
120 - 88 = 120\Bigl(1 - \frac12\Bigr)\Bigl(1 -
\frac13\Bigr)\Bigl(1 - \frac15\Bigr) = 120 \cdot \frac12 \cdot
\frac23 \cdot \frac45 = 32 :
$$

menjabarkan ketiga kurung itu mereproduksi persis kedelapan suku bertanda pada inklusi–eksklusi, satu untuk setiap [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian $\{2, 3,
5\}$. Bentuk hasil kali ini mendefinisikan fungsi totien Euler, yang peran aritmetikanya muncul bersama kekongruenan [Bab 6](https://one-course.com/books/math/3/id/chapter/6-aritmetika-bilangan-bulat#ch-b1-arith) dan dikembangkan pada jilid Tahun ke-2.

**Contoh 2.26 (Permutasi kacau).**

*[Permutasi](#def-b1-counting-objects) kacau* adalah [permutasi](#def-b1-counting-objects) tanpa titik tetap. Misalkan $A_i$ [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) [permutasi](#def-b1-counting-objects) $\intint{1}{n}$ yang menetapkan $i$; maka $\abs{\bigcap_{i \in I} A_i} = (n - \abs I)!$, dan inklusi–eksklusi mencacah [permutasi](#def-b1-counting-objects) yang mempunyai sekurang-kurangnya satu titik tetap; [permutasi](#def-b1-counting-objects) kacau berjumlah

$$
D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} .
$$

Karena $\sum (-1)^k / k! \to \eu^{-1}$ (lihat [Bab 17](https://one-course.com/books/math/3/id/chapter/17-deret-numerik#ch-b1-series)), sekitar $37\%$ dari semua [permutasi](#def-b1-counting-objects) adalah [permutasi](#def-b1-counting-objects) kacau, berapa pun $n$ itu.

**Catatan 2.27 (Di mana bab ini dipakai).**

[Koefisien binomial](#def-b1-counting-objects) adalah objek bab ini yang paling banyak dipakai ulang: ia menggerakkan teorema binomial pada [Bab 8](https://one-course.com/books/math/3/id/chapter/8-polinomial#ch-b1-poly) (penjabaran $(X + a)^n$), rumus Leibniz bagi turunan ke-$n$ sebuah hasil kali pada [Bab 14](https://one-course.com/books/math/3/id/chapter/14-pendiferensialan#ch-b1-derivative), dan koefisien ekspansi Taylor pada [Bab 16](https://one-course.com/books/math/3/id/chapter/16-rumus-taylor-dan-ekspansi-asimtotik#ch-b1-taylor). [Permutasi](#def-b1-counting-objects) kembali sebagai grup — dengan tanda yang dibangun dari pencacahan inversi — pada [Bab 7](https://one-course.com/books/math/3/id/chapter/7-struktur-aljabar#ch-b1-structures), dan tanda itu pada gilirannya mendefinisikan determinan pada [Bab 22](https://one-course.com/books/math/3/id/chapter/22-determinan-dan-sistem-linear#ch-b1-det). Inklusi–eksklusi dan asas pencacahan adalah tulang punggung [hingga](#def-b1-counting-card) bagi peluang diskret, yang dikembangkan pada jilid Tahun ke-2; bilangan [permutasi](#def-b1-counting-objects) kacau pada [Contoh 2.26](#ex-b1-counting-derangement) dipelajari secara mendalam pada soal akhir pekan di bawah.

## 2.5 Latihan

**Latihan 2.1 ★.**

Sebuah pelat nomor terdiri atas dua huruf (A–Z), lalu tiga angka, lalu dua huruf lagi. Berapa banyak pelat yang mungkin? Berapa banyak yang tidak mempunyai huruf berulang di antara keempat hurufnya?

**Solusi Latihan 2.1.**

Tahap yang saling bebas dan kaidah hasil kali: ada $26^2 \times 10^3 \times 26^2
= 26^4 \times 1000 = 456\,976\,000$ pelat. Bila keempat hurufnya berbeda dua-dua, tahap hurufnya membentuk susunan-$4$ atas abjad: $26 \times 25 \times 24 \times 23 = 358\,800$ cara, jadi ada $358\,800 \times 1000 = 358\,800\,000$ pelat.

**Latihan 2.2 ★.**

Berapa banyak anagram (penyusunan ulang huruf, bermakna atau tidak) yang dimiliki kata sepatu ? Dan ananas ?

**Solusi Latihan 2.2.**

sepatu mempunyai $6$ huruf yang berbeda: $6! = 720$ anagram. ananas mempunyai $6$ huruf dengan pengulangan ($3$ huruf a, $2$ huruf n, $1$ huruf s): setiap anagram ditentukan oleh posisi huruf a ($\binom 63$ pilihan), lalu posisi huruf n di antara $3$ tempat sisanya ($\binom 32$), sedangkan huruf s menempati tempat terakhir: $\binom{6}{3}\binom{3}{2} = 20 \times 3 = 60$ anagram (setara dengan $6!/(3!\,2!\,1!) = 60$).

**Latihan 2.3 ★.**

Sebuah panitia beranggota $4$ orang dipilih dari $7$ perempuan dan $5$ laki-laki. Berapa banyak panitia: seluruhnya? yang beranggota tepat $2$ perempuan? yang beranggota sekurang-kurangnya satu laki-laki?

**Solusi Latihan 2.3.**

Seluruhnya: $\binom{12}{4} = 495$. Tepat $2$ perempuan: pilih mereka ($\binom 72 = 21$) lalu $2$ laki-laki ($\binom 52 = 10$): ada $210$ panitia. Sekurang-kurangnya satu laki-laki: komplemen dari “tanpa laki-laki”, $\binom{12}{4} - \binom{7}{4} = 495 - 35 = 460$.

**Latihan 2.4 ★.**

Buktikan bahwa pada sebarang kelompok berisi $13$ orang, ada dua orang yang sama bulan lahirnya; dan bahwa di antara sebarang $n + 1$ bilangan bulat yang dipilih dari $\intint{1}{2n}$, ada dua yang berurutan. *(Sarang merpati dua-duanya: sebutkan kotaknya.)*

**Solusi Latihan 2.4.**

*Bulan lahir:* kotaknya adalah $12$ bulan; $13$ orang ke dalam $12$ kotak memaksa dua orang berada pada kotak yang sama ([Akibat 2.3](#cor-b1-counting-pigeonhole)).

*Bilangan bulat berurutan:* kotaknya adalah $n$ pasangan $\{1,2\},
\{3,4\}, \dots, \{2n-1, 2n\}$, yang mempartisi $\intint{1}{2n}$. Memilih $n + 1$ bilangan bulat menempatkan dua di antaranya pada pasangan yang sama, dan kedua unsur sebuah pasangan itu berurutan.

**Latihan 2.5 ★.**

Hitung $\sum_{k=0}^{n} k \binom{n}{k}$. *Petunjuk: turunkan $(1 + x)^n$, atau pakai $k \binom nk = n \binom{n-1}{k-1}$ (buktikan dulu).*

**Solusi Latihan 2.5.**

Untuk $1 \leq k \leq n$,

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

Dengan menjumlahkan lalu mengindeks ulang memakai $j = k - 1$:

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

menurut [Proposisi 2.15](#prop-b1-counting-identities). (Cara lain: turunkan $(1+x)^n = \sum_k \binom nk x^k$ lalu ambil $x = 1$.)

**Latihan 2.6 ★★.**

Ada berapa banyak [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) naik tegas dari $\intint{1}{k}$ ke $\intint{1}{n}$? Simpulkan banyaknya [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) naik (tidak harus tegas). *Petunjuk untuk cacahan kedua: $f$ naik $\mapsto$ $g(i) = f(i) + i - 1$.*

**Solusi Latihan 2.6.**

[Pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) naik tegas $f \colon \intint{1}{k} \to \intint{1}{n}$ ditentukan oleh petanya, yaitu [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian beranggota $k$ dari $\intint{1}{n}$ (daftarkan [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian itu dalam urutan naik); sebaliknya setiap [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian beranggota $k$ memberi tepat satu [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) semacam itu. Jadi ada $\binom nk$ [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) naik tegas.

Jika $f$ hanya naik, tulis $g(i) = f(i) + i - 1$. Maka $g$ naik tegas (di antara dua argumen berurutan, $f$ bertambah $\geq 0$ sedangkan $i - 1$ bertambah $1$) dengan nilai di $\intint{1}{n + k - 1}$; dan $f(i) = g(i) - i + 1$ memulihkan $f$ dari sebarang $g$ yang naik tegas ke dalam $\intint{1}{n+k-1}$. Ini sebuah bijeksi, jadi ada $\binom{n + k - 1}{k}$ [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) naik.

**Latihan 2.7 ★★.**

(Vandermonde) Buktikan, dengan mencacah [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian beranggota $k$ dari sebuah [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) yang terbelah atas dua blok berukuran $m$ dan $n$:

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

Simpulkan $\sum_{j=0}^{n} \binom nj^2 = \binom{2n}{n}$.

**Solusi Latihan 2.7.**

Belah [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) $E$ beranggota $m + n$ unsur atas blok $M$ ($m$ unsur) dan $N$ ($n$ unsur). [Himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian beranggota $k$ dari $E$ memuat sejumlah $j$ unsur $M$ ($0 \leq j \leq k$) dan $k - j$ unsur $N$; untuk $j$ yang tetap ada $\binom mj \binom{n}{k-j}$ [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian semacam itu, dan kasus $j = 0, \dots,
k$ mempartisi [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian beranggota $k$ tadi. Kaidah jumlah memberikan kesamaan 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$, memakai $\binom{n}{n-j} =
\binom nj$.

**Latihan 2.8 ★★.**

Berapa banyak bilangan bulat di $\intint{1}{1000}$ yang habis dibagi $2$ atau $3$ atau $5$? (Inklusi–eksklusi; $\lfloor 1000/6 \rfloor$ mencacah kelipatan $6$, dan seterusnya.)

**Solusi Latihan 2.8.**

Misalkan $A_d$ [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) kelipatan $d$ di $\intint{1}{1000}$, sehingga $\abs{A_d} = \lfloor 1000/d \rfloor$. Inklusi–eksklusi ([Teorema 2.24](#thm-b1-counting-inclexcl)) dengan $A_2, A_3, A_5$, sambil memperhatikan $A_2 \cap A_3 = A_6$ dan seterusnya:

$$
500 + 333 + 200 - 166 - 100 - 66 + 33 = 734 .
$$

Jadi ada $734$ bilangan bulat yang habis dibagi $2$, $3$ atau $5$.

**Latihan 2.9 ★★.**

Cacah surjeksi dari [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) beranggota $4$ unsur pada [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) beranggota $2$ unsur; lalu pada [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) beranggota $3$ unsur. *Petunjuk: cacah [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) yang tak [surjektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj) dengan inklusi–eksklusi atas nilai yang terlewat.*

**Solusi Latihan 2.9.**

Pada $2$ unsur: seluruh $2^4 = 16$ [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) kecuali $2$ [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) konstan: ada $14$ surjeksi.

Pada $3$ unsur: dengan inklusi–eksklusi atas nilai yang terlewat, banyaknya [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) dari [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) beranggota $4$ ke [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) beranggota $3$ yang melewatkan sekurang-kurangnya satu nilai adalah $\binom 31 2^4 - \binom 32 1^4 = 48 - 3 = 45$; seluruh [pemetaan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) berjumlah $3^4 =
81$; jadi surjeksinya: $81 - 45 = 36$. (Periksa: surjeksi dari $4$ pada $3$ unsur menggandakan tepat satu nilai: pilih nilai yang digandakan ($3$), pasangan yang terpetakan ke sana ($\binom 42 = 6$), lalu bijeksi bagi sisanya ($2$): $3 \times 6 \times 2 = 36$.)

**Latihan 2.10 ★★.**

(Bintang dan sekat) Buktikan bahwa banyaknya pemilihan-$k$ dari $n$ objek *dengan* pengulangan dan urutan diabaikan — setara dengan banyaknya $(x_1, \dots, x_n) \in \N^n$ yang memenuhi $x_1 + \dots + x_n = k$ — adalah $\binom{n + k - 1}{k}$. *Petunjuk: sandikan sebuah penyelesaian sebagai sebaris $k$ bintang dan $n - 1$ sekat.*

**Solusi Latihan 2.10.**

Sebuah penyelesaian $x_1 + \dots + x_n = k$ di $\N^n$ tersandikan sebagai sebaris $k$ bintang dan $n - 1$ sekat: tulis $x_1$ bintang, sebuah sekat, $x_2$ bintang, sebuah sekat, …, lalu diakhiri $x_n$ bintang. Ini bijeksi pada kata sepanjang $k + n - 1$ yang memakai $k$ bintang dan $n - 1$ sekat, dan kata semacam itu ditentukan oleh posisi bintangnya: $\binom{n + k - 1}{k}$. Pemilihan dengan pengulangan berpadanan dengan penyelesaian persamaan itu ($x_i$ = banyaknya salinan objek $i$), jadi cacahannya sama.

**Latihan 2.11 ★★★.**

Buktikan rumus [Contoh 2.26](#ex-b1-counting-derangement) untuk $D_n$ secara terperinci, lalu simpulkan $n! = \sum_{k=0}^{n} \binom{n}{k} D_{n-k}$ (buktikan pula kesamaan ini secara langsung dengan menggolongkan [permutasi](#def-b1-counting-objects) menurut [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) titik tetapnya).

**Solusi Latihan 2.11.**

Dengan $A_i = \{\sigma : \sigma(i) = i\}$, sebuah [permutasi](#def-b1-counting-objects) di $\bigcap_{i \in I} A_i$ menetapkan setiap $i \in I$ dan mempermutasikan $n - \abs I$ titik lainnya secara bebas: $\abs{\bigcap_{i \in I} A_i} =
(n - \abs I)!$. Inklusi–eksklusi:

$$
\Bigl|\bigcup_i A_i\Bigr|
= \sum_{k=1}^{n} (-1)^{k+1} \binom nk (n-k)!
= \sum_{k=1}^{n} (-1)^{k+1} \frac{n!}{k!} ,
$$

karena ada $\binom nk$ [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian $I$ berukuran $k$. Jadi

$$
D_n = n! - \Bigl|\bigcup_i A_i\Bigr|
= n!\Bigl(1 - \sum_{k=1}^{n} \frac{(-1)^{k+1}}{k!}\Bigr)
= n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} .
$$

Untuk kesamaan kedua: golongkan [permutasi](#def-b1-counting-objects) $\sigma$ dari $\intint{1}{n}$ menurut [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) titik tetapnya $F(\sigma)$. Untuk [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian beranggota $k$ yang tetap, katakanlah $F$, [permutasi](#def-b1-counting-objects) dengan $F(\sigma) = F$ tepat adalah [permutasi](#def-b1-counting-objects) kacau pada komplemennya: ada $D_{n-k}$ buah. Menjumlahkan atas $\binom nk$ pilihan $F$ untuk setiap $k$ memberikan $n! = \sum_{k=0}^{n} \binom nk D_{n-k}$.

**Latihan 2.12 ★★★.**

Untuk $n \in \N^*$, buktikan dengan pencacahan ganda pasangan ([himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian, unsur bertanda):

$$
\sum_{k=1}^{n} k \binom{n}{k} = n\, 2^{n-1},
\qquad\text{lalu}\qquad
\sum_{k=1}^{n} k^2 \binom{n}{k} = n(n+1)\, 2^{n-2} .
$$

*Untuk yang kedua: cacah pasangan unsur bertanda, sama atau tidak.*

**Solusi Latihan 2.12.**

*Kesamaan pertama.* Cacah pasangan $(A, a)$ dengan $A \subseteq E$ ($\abs E = n$) dan $a \in A$. Menurut ukuran $A$: ada $\sum_k \binom nk k$ pasangan. Dengan memilih unsur bertanda lebih dulu: ada $n$ pilihan bagi $a$, lalu sebarang [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian dari $n - 1$ unsur sisanya untuk melengkapi $A$: ada $n\,2^{n-1}$ pasangan.

*Kesamaan kedua.* Cacah tripel $(A, a, b)$ dengan $a, b \in
A$ (boleh $a = b$). Menurut ukurannya: $\sum_k k^2 \binom nk$. Secara langsung: entah $a = b$ (ada $n\,2^{n-1}$ tripel, cacahan sebelumnya) atau $a \neq b$ (ada $n(n-1)$ pilihan terurut, lalu sebarang [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) bagian dari $n - 2$ unsur lainnya: $n(n-1)\,2^{n-2}$). Totalnya

$$
n\,2^{n-1} + n(n-1)\,2^{n-2} = n\,2^{n-2}\,(2 + n - 1)
= n(n+1)\,2^{n-2} .
$$

## 2.6 Soal: Permutasi kacau, atau surat yang salah alamat

**Soal 2.1.**

Seorang sekretaris memasukkan $n$ surat ke dalam $n$ amplop beralamat secara acak: berapa peluang bahwa *tak seorang pun* menerima surat yang benar? Pertanyaan klasik ini (Montmort, 1708) mengantar ke bilangan [permutasi](#def-b1-counting-objects) kacau $D_n$ pada [Contoh 2.26](#ex-b1-counting-derangement). Rumus inklusi–eksklusi hanyalah langkah pembuka: soal ini mengembangkan rekursi yang menghitung $D_n$, dua bukti mandiri lain bagi rumus itu, teorema mencengangkan bahwa $D_n$ adalah bilangan bulat terdekat dengan $n!/\eu$, distribusi lengkap titik tetap sebuah [permutasi](#def-b1-counting-objects) acak, serta aritmetika ganjil barisan $(D_n)$. Di sepanjang soal ini, $D_n$ menyatakan banyaknya [permutasi](#def-b1-counting-objects) kacau ([permutasi](#def-b1-counting-objects) tanpa titik tetap) dari $\intint1n$, dengan kesepakatan $D_0 = 1$ ([permutasi](#def-b1-counting-objects) kosong tidak mempunyai titik tetap).

**Bagian I — Kasus kecil dan sensus titik tetap.**

1. Hitung $D_1, D_2, D_3$ secara langsung, dan $D_4$ dengan mendaftar [permutasi](#def-b1-counting-objects) kacau $\{1, 2, 3, 4\}$ yang dikelompokkan menurut nilai $\sigma(1)$ . (Anda semestinya memperoleh $D_4 = 9$ .)
2. Untuk $0 \leq k \leq n$ , tunjukkan bahwa banyaknya $P_k(n)$ [permutasi](#def-b1-counting-objects) $\intint1n$ yang mempunyai *tepat* $k$ titik tetap adalah $\binom nk D_{n-k}$ .
3. Periksa sensusnya untuk $n = 4$ : hitung $P_0(4), \dots,  P_4(4)$ lalu periksa bahwa jumlahnya $4! = 24$ . Mana yang lebih mungkin untuk empat surat: tak ada yang cocok, atau tepat satu yang cocok?
4. Dengan pencacahan ganda ([Metode 2.22](#met-b1-counting-doublecount)) pasangan $(\sigma, i)$ yang memenuhi $\sigma(i) = i$, tunjukkan bahwa $$\sum_{\sigma} \abs{\mathrm{Fix}(\sigma)} = n! :$$ rata-rata, sebuah [permutasi](#def-b1-counting-objects) acak mempunyai *tepat satu* titik tetap, berapa pun $n \geq 1$ itu.

**Bagian II — Dua rekursi dan dua bukti baru bagi rumus itu.**

5. Buktikan secara kombinatorial, untuk $n \geq 1$: $$D_{n+1} = n\,(D_n + D_{n-1}) .$$ (Golongkan [permutasi](#def-b1-counting-objects) kacau $\sigma$ dari $\intint1{n+1}$ menurut $j = \sigma(n+1)$, lalu menurut apakah $\sigma(j) = n + 1$; pada kasus $\sigma(j) \neq n+1$, bangunlah bijeksi dengan [permutasi](#def-b1-counting-objects) kacau $\intint1n$ dengan mengalihkan [prapeta](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) $n + 1$ ke $j$.) Periksa rekursi itu secara numerik sampai $D_6$.
6. Dengan menulis $u_n = D_n - n D_{n-1}$, simpulkan dari pertanyaan 5 bahwa $u_{n+1} = -u_n$, lalu simpulkan rekursi kedua: $$D_n = n D_{n-1} + (-1)^n \qquad (n \geq 1).$$
7. Dari pertanyaan 6, buktikan dengan induksi rumus pada [Contoh 2.26](#ex-b1-counting-derangement), $$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!},$$ — sebuah bukti yang sama sekali tak bergantung pada inklusi–eksklusi.
8. (Inversi binomial) Misalkan $(a_n)$ dan $(b_n)$ dua barisan sedemikian sehingga $a_n = \sum_{k=0}^n \binom nk b_k$ untuk setiap $n$. Buktikan bahwa $$b_n = \sum_{k=0}^{n} (-1)^{n-k} \binom nk a_k  \qquad (n \in \N).$$ (Tegakkan lebih dulu *revisi trinomial* $\binom nk \binom kj = \binom nj \binom{n-j}{k-j}$, lalu pakai jumlah baris berselang-seling pada [Contoh 2.17](#ex-b1-counting-binomial).)
9. Terapkan pertanyaan 8 pada kesamaan $n! = \sum_k \binom nk  D_{n-k}$ dari [Latihan 2.11](#exo-b1-counting-11) untuk memperoleh bukti *ketiga* bagi rumus $D_n$ .

**Bagian III — Bilangan bulat terdekat dengan $n!/\eu$.** Terima untuk bagian ini — teorinya dibangun pada [Bab 17](https://one-course.com/books/math/3/id/chapter/17-deret-numerik#ch-b1-series) — bahwa $\eu^{-1} = \lim_{n \to \infty} s_n$ dengan $s_n = \sum_{k=0}^{n}
\frac{(-1)^k}{k!}$, beserta batas deret berselang-seling yang tegas $\abs{\eu^{-1} - s_n} < \frac1{(n+1)!}$ untuk setiap $n$.

10. Tunjukkan bahwa $\bigl| D_n - n!/\eu \bigr| < \frac1{n+1}$ untuk setiap $n \in \N$ .
11. Simpulkan teorema utamanya: *untuk setiap $n \geq 1$, $D_n$ adalah bilangan bulat terdekat dengan $n!/\eu$* . Mengapa argumen itu memerlukan $n \geq 1$ ?
12. Tentukan tanda galatnya: tunjukkan bahwa $D_n > n!/\eu$ tepat ketika $n$ genap. (Cari suku pertama yang diabaikan pada deret berselang-seling itu.)
13. Hitung $D_7$ sampai $D_{10}$ dengan rekursi pertanyaan 5, lalu cocokkan $D_{10}$ dengan $10!/\eu$ ( $10! = 3\,628\,800$ , $\eu \approx 2.718281828$ ).
14. (Peluang penitipan topi) Misalkan $p_n = D_n/n!$ peluang bahwa sebuah [permutasi](#def-b1-counting-objects) acak seragam merupakan [permutasi](#def-b1-counting-objects) kacau. Tunjukkan $\abs{p_n - \eu^{-1}} < \frac1{(n+1)!}$ lalu hitung $p_6$ sampai lima angka desimal. Beri komentar: mengapa jawaban atas pertanyaan Montmort pada dasarnya tidak bergantung pada $n$ — bahkan sudah untuk selusin surat?

**Bagian IV — Distribusi titik tetap.**

15. Tetapkan $k \in \N$. Tunjukkan bahwa proporsi [permutasi](#def-b1-counting-objects) $\intint1n$ yang mempunyai tepat $k$ titik tetap memenuhi $$\frac{P_k(n)}{n!} = \frac{s_{n-k}}{k!}  \;\xrightarrow[n \to \infty]{}\; \frac{\eu^{-1}}{k!} .$$ (Nilai limit ini, yang berjumlah $1$, membentuk *distribusi Poisson* berparameter $1$, objek pusat pada mata kuliah peluang di jilid Tahun ke-2.)
16. Dengan mencacah ganda tripel $(\sigma, i, j)$ yang $i  \neq j$ -nya sama-sama ditetapkan oleh $\sigma$ , tunjukkan bahwa $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}\,  (\abs{\mathrm{Fix}(\sigma)} - 1) = n!$ untuk $n \geq 2$ . Digabungkan dengan pertanyaan 4: rata-rata $\abs{\mathrm{Fix}}^2$ adalah $2$ , jadi “sebaran” (ragam) banyaknya titik tetap sama dengan $1$ — sekali lagi tak bergantung pada $n$ , dan sekali lagi cocok dengan hukum Poisson.
17. Hitung proporsi [permutasi](#def-b1-counting-objects) yang mempunyai sekurang-kurangnya satu titik tetap untuk $n = 4, 5, 6$ (sebagai pecahan dan sampai empat angka desimal), lalu bandingkan dengan $1 - \eu^{-1} \approx  0.6321$ .
18. Tunjukkan secara langsung — tanpa perlu limit — bahwa $s_{n+2} - s_n  = (-1)^{n+1}\bigl(\frac1{(n+1)!} - \frac1{(n+2)!}\bigr)$ , lalu simpulkan bahwa peluang $p_n = s_n$ pada pertanyaan 14 berayun: $p_0 > p_2 > p_4 > \dots$ dan $p_1 < p_3 < p_5 < \dots$ , dengan nilai yang genap menurun dan nilai yang ganjil menaik menuju limit bersama $\eu^{-1}$ .
19. (Tukar kado rahasia) $n$ orang masing-masing menarik satu nama dari sebuah topi; jika ada yang menarik namanya sendiri, *seluruh* penarikan diulang dari awal. Dengan memakai fakta baku bahwa sebuah kejadian berpeluang $p$ rata-rata menuntut $1/p$ percobaan, taksirlah rata-rata banyaknya penarikan lengkap yang diperlukan, lalu simpulkan bahwa prosedur itu menelan sekitar $\eu \approx  2.72$ penarikan secara rata-rata, pada dasarnya tak bergantung pada $n$ .

**Bagian V — Aritmetika $D_n$, dan sebuah sintesis.**

20. Perhalus pertanyaan 5: tunjukkan bahwa untuk $j \in  \intint2n$ yang tetap, [permutasi](#def-b1-counting-objects) kacau $\intint1n$ dengan $\sigma(1) = j$ berjumlah tepat $D_{n-1} + D_{n-2}$ , tak bergantung pada $j$ . Simpulkan bahwa $n - 1$ membagi $D_n$ untuk setiap $n \geq 2$ .
21. Buktikan bahwa $D_n$ ganjil jika dan hanya jika $n$ genap. (Bekerjalah modulo $2$ pada rekursi pertanyaan 6.)
22. Buktikan bahwa $D_n \equiv (-1)^n \pmod n$ untuk $n \geq 1$ , lalu periksa kekongruenan itu pada angka terakhir $D_{10}$ .
23. Tunjukkan dari pertanyaan 6 bahwa $\dfrac{D_n}{D_{n-1}} = n +  \dfrac{(-1)^n}{D_{n-1}}$ untuk $n \geq 3$ , jadi rasio dua bilangan [permutasi](#def-b1-counting-objects) kacau yang berurutan *hampir persis* $n$ ; jelaskan dalam satu kalimat mengapa hal ini sejalan dengan $D_n \approx n!/\eu$ .
24. Di mana persisnya soal ini memakai: (i) kaidah hasil kali dan kaidah jumlah; (ii) pencacahan ganda; (iii) teorema binomial; (iv) batas deret berselang-seling yang diterima tanpa bukti? Satu kalimat untuk masing-masing.
25. Sintesis. Rumus untuk $D_n$ kini mempunyai tiga bukti (inklusi–eksklusi, rekursi beserta induksi, inversi binomial). Dalam satu paragraf pendek, bandingkan apa yang *dijelaskan* masing-masing bukti: mana yang menghitung paling cepat, mana yang dapat diperluas ke cacahan titik tetap yang lain, dan mana yang mengungkap mengapa $\eu$ muncul pada soal tentang amplop.

**Solusi Soal 2.1.**

**1.** $D_1 = 0$ (satu-satunya [permutasi](#def-b1-counting-objects) menetapkan $1$), $D_2 = 1$ (pertukarannya), $D_3 = 2$ (dalam notasi satu baris: $231$ dan $312$). Untuk $n = 4$, kelompokkan menurut $\sigma(1)$: dengan $\sigma(1) = 2$ [permutasi](#def-b1-counting-objects) kacaunya adalah $2143$, $2341$, $2413$; dengan $\sigma(1) = 3$: $3142$, $3412$, $3421$; dengan $\sigma(1) = 4$: $4123$, $4312$, $4321$. Tiga buah pada masing-masing kelompok: $D_4 = 9$.

**2.** Sebuah [permutasi](#def-b1-counting-objects) dengan tepat $k$ titik tetap ditentukan oleh pilihan [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) titik tetapnya $F$ ($\binom nk$ cara) beserta pembatasannya pada komplemen, yang haruslah [permutasi](#def-b1-counting-objects) $n - k$ titik *tanpa* titik tetap ($D_{n-k}$ cara). Kedua pilihan itu saling bebas dan padanannya [bijektif](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-inj): $P_k(n) = \binom nk D_{n-k}$.

**3.** $P_0(4) = D_4 = 9$; $P_1(4) = \binom41 D_3 = 4 \times 2
= 8$; $P_2(4) = \binom42 D_2 = 6$; $P_3(4) = \binom43 D_1 = 0$ (tiga titik tetap memaksa adanya titik tetap yang keempat); $P_4(4) = 1$. Jumlahnya: $9 + 8 + 6
+ 0 + 1 = 24 = 4!$. Tak ada yang cocok ($9$ kasus) mengungguli tepat satu yang cocok ($8$ kasus) — tipis saja.

**4.** Cacah pasangan $(\sigma, i)$ dengan $\sigma(i) = i$. Untuk $i$ yang tetap, [permutasi](#def-b1-counting-objects) yang menetapkan $i$ adalah [permutasi](#def-b1-counting-objects) $n - 1$ titik lainnya: ada $(n-1)!$ buah. Jadi banyaknya pasangan adalah $n \cdot (n-1)! = n!$, dan bilangan itu juga sama dengan $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}$. Dengan membaginya dengan banyaknya [permutasi](#def-b1-counting-objects), yaitu $n!$: rata-rata banyaknya titik tetap adalah tepat $1$, untuk setiap $n \geq 1$.

**5.** Misalkan $\sigma$ [permutasi](#def-b1-counting-objects) kacau $\intint1{n+1}$ dan $j = \sigma(n+1) \in \intint1n$: ada $n$ nilai yang mungkin. *Kasus $\sigma(j) = n+1$:* titik $j$ dan $n+1$ bertukar, sedangkan $\sigma$ yang dibatasi pada $n - 1$ titik sisanya adalah [permutasi](#def-b1-counting-objects) kacau sembarang atas titik-titik itu: ada $D_{n-1}$ kemungkinan. *Kasus $\sigma(j)
\neq n+1$:* tulis $i_0 = \sigma^{-1}(n+1)$; di sini $i_0 \neq j$ dan $i_0 \leq n$. Definisikan $\tau$ pada $\intint1n$ dengan $\tau(i) = \sigma(i)$ untuk $i \neq i_0$ dan $\tau(i_0) = j$. Maka $\tau$ adalah [permutasi](#def-b1-counting-objects) $\intint1n$ (nilai $n+1$ telah digantikan oleh nilai $j$ yang hilang), dan ia [permutasi](#def-b1-counting-objects) kacau: $\tau(i_0) = j \neq i_0$, dan $\tau(i) = \sigma(i) \neq i$ di tempat lain. Sebaliknya, dari sebuah [permutasi](#def-b1-counting-objects) kacau $\tau$ atas $\intint1n$ dan nilai $j$, kita pulihkan $\sigma$ dengan menetapkan $\sigma(n+1) = j$, $\sigma(\tau^{-1}(j)) = n+1$ dan $\sigma = \tau$ di tempat lain: sebuah bijeksi, yang memberikan $D_n$ kemungkinan. Dengan menjumlahkan atas $j$: $D_{n+1} = n(D_n + D_{n-1})$. Secara numerik: $D_5 = 4(9 + 2) = 44$, $D_6 = 5(44 + 9) = 265$.

**6.** Dari pertanyaan 5, $D_{n+1} = nD_n + nD_{n-1}$, jadi

$$
u_{n+1} = D_{n+1} - (n+1)D_n = nD_n + nD_{n-1} - (n+1)D_n
= -(D_n - nD_{n-1}) = -u_n .
$$

Karena $u_1 = D_1 - 1 \cdot D_0 = -1$, induksi memberikan $u_n =
(-1)^n$, yakni $D_n = nD_{n-1} + (-1)^n$ untuk $n \geq 1$.

**7.** Induksi pada $n$. Basis: $D_0 = 1 = 0!\,s_0$. Langkah: dengan mengandaikan $D_{n-1} = (n-1)!\,s_{n-1}$,

$$
D_n = nD_{n-1} + (-1)^n = n!\,s_{n-1} + (-1)^n
= n!\Bigl(s_{n-1} + \frac{(-1)^n}{n!}\Bigr) = n!\,s_n ,
$$

yang tepat merupakan rumus itu. Tak ada inklusi–eksklusi yang dipakai: hanya rekursi kombinatorial pertanyaan 5.

**8.** Revisi trinomial, lewat faktorial:

$$
\binom nk \binom kj
= \frac{n!}{k!\,(n-k)!} \cdot \frac{k!}{j!\,(k-j)!}
= \frac{n!}{j!\,(n-j)!} \cdot \frac{(n-j)!}{(k-j)!\,(n-k)!}
= \binom nj \binom{n-j}{k-j} .
$$

Sekarang substitusikan $a_k = \sum_j \binom kj b_j$ lalu tukarkan kedua jumlah [hingga](#def-b1-counting-card) itu:

$$
\sum_{k=0}^{n} (-1)^{n-k} \binom nk a_k
= \sum_{j=0}^{n} b_j \binom nj
\sum_{k=j}^{n} (-1)^{n-k} \binom{n-j}{k-j}
= \sum_{j=0}^{n} b_j \binom nj
\sum_{i=0}^{n-j} (-1)^{(n-j)-i} \binom{n-j}{i} .
$$

Jumlah bagian dalamnya adalah penjabaran $(1 + (-1))^{n-j} = 0^{n-j}$ (teorema binomial, [Teorema 2.16](#thm-b1-counting-binomial)): ia lenyap untuk $j < n$ dan bernilai $1$ untuk $j = n$. Hanya $j = n$ yang bertahan, dan ruas kanannya adalah $b_n$, sesuai yang diklaim.

**9.** Menurut simetri $\binom nk = \binom n{n-k}$, kesamaan pada [Latihan 2.11](#exo-b1-counting-11) dapat ditulis ulang sebagai $n! =
\sum_{k=0}^n \binom nk D_k$. Terapkan pertanyaan 8 dengan $a_n = n!$ dan $b_k = D_k$:

$$
D_n = \sum_{k=0}^{n} (-1)^{n-k} \binom nk k!
= \sum_{k=0}^{n} (-1)^{n-k} \frac{n!}{(n-k)!}
= n! \sum_{j=0}^{n} \frac{(-1)^j}{j!} ,
$$

dengan mengindeks ulang lewat $j = n - k$: rumus itu untuk ketiga kalinya.

**10.** $D_n = n!\,s_n$ (pertanyaan 7), jadi

$$
\Bigl| D_n - \frac{n!}{\eu} \Bigr|
= n!\,\abs{s_n - \eu^{-1}} < \frac{n!}{(n+1)!} = \frac1{n+1} .
$$

**11.** Untuk $n \geq 1$ berlaku $\frac1{n+1} \leq \frac12$, dan ketaksamaan pertanyaan 10 bersifat tegas: $D_n$ terletak pada jarak $< \frac12$ dari $n!/\eu$, jadi ia satu-satunya bilangan bulat terdekat. Untuk $n = 0$ batas itu hanya memberikan jarak $< 1$, dan klaimnya memang gagal di situ: $0!/\eu \approx 0.368$ mempunyai bilangan bulat terdekat $0$, sedangkan $D_0 = 1$.

**12.** $\eu^{-1} - s_n = \sum_{k \geq n+1} (-1)^k/k!$ adalah deret berselang-seling dengan suku yang menurun tegas, jadi tandanya sama dengan tanda suku pertamanya $(-1)^{n+1}/(n+1)!$. Jadi $s_n -
\eu^{-1}$ bertanda $(-1)^n$: untuk $n$ genap, $s_n > \eu^{-1}$ dan $D_n = n!\,s_n > n!/\eu$; untuk $n$ ganjil, $D_n < n!/\eu$.

**13.** $D_7 = 6(265 + 44) = 6 \times 309 = 1854$; $D_8 =
7(1854 + 265) = 7 \times 2119 = 14\,833$; $D_9 = 8(14\,833 + 1854)
= 8 \times 16\,687 = 133\,496$; $D_{10} = 9(133\,496 + 14\,833) =
9 \times 148\,329 = 1\,334\,961$. Periksa: $10!/\eu = 3\,628\,800 /
2.718281828 \approx 1\,334\,960.92$, yang bilangan bulat terdekatnya adalah $1\,334\,961$ — dan $D_{10} > 10!/\eu$, sebagaimana diramalkan pertanyaan 12 untuk $n$ genap.

**14.** $\abs{p_n - \eu^{-1}} = \abs{s_n - \eu^{-1}} <
\frac1{(n+1)!}$. Untuk $n = 6$: $p_6 = 265/720 = 0.36806$ (lima angka desimal), berbanding $\eu^{-1} = 0.36788$; selisihnya di bawah $1/7! =
1/5040 < 2 \times 10^{-4}$. Batas $1/(n+1)!$ runtuh demikian cepat sehingga peluangnya sudah terpaku sampai banyak angka desimal bahkan untuk selusin surat: jawaban “sekitar $36.8\%$” itu, untuk setiap keperluan praktis, tak bergantung pada $n$ — kejutan yang termasyhur dari soal ini.

**15.** Menurut pertanyaan 2 dan $D_m = m!\,s_m$:

$$
\frac{P_k(n)}{n!} = \frac{\binom nk D_{n-k}}{n!}
= \frac{D_{n-k}}{k!\,(n-k)!} = \frac{s_{n-k}}{k!}
\;\longrightarrow\; \frac{\eu^{-1}}{k!}
$$

ketika $n \to \infty$ dengan $k$ yang tetap, karena $s_{n-k} \to \eu^{-1}$. Nilai limit $\eu^{-1}/k!$ ($k \in \N$) adalah bobot distribusi Poisson berparameter $1$.

**16.** Cacah tripel $(\sigma, i, j)$ dengan $i \neq j$, $\sigma(i) = i$, $\sigma(j) = j$. Dengan memilih pasangan terurutnya lebih dulu: ada $n(n-1)$ cara; [permutasi](#def-b1-counting-objects) yang menetapkan $i$ sekaligus $j$ adalah [permutasi](#def-b1-counting-objects) $n - 2$ titik sisanya: ada $(n-2)!$ buah. Totalnya: $n(n-1)(n-2)! = n!$. Sebaliknya, menjumlahkan atas $\sigma$ lebih dulu mencacah, untuk setiap $\sigma$, pasangan terurut titik tetap yang berbeda: $\abs{\mathrm{Fix}(\sigma)}(\abs{\mathrm{Fix}(\sigma)}-1)$. Jadi kesamaan yang dinyatakan itu berlaku; dengan membaginya dengan $n!$, rata-rata $\abs{\mathrm{Fix}}(\abs{\mathrm{Fix}} - 1)$ adalah $1$, sehingga rata-rata $\abs{\mathrm{Fix}}^2$ adalah $1 + 1 = 2$ dan ragamnya $2 -
1^2 = 1$.

**17.** Proporsi $1 - p_n$: untuk $n = 4$, $1 - \frac
9{24} = \frac{15}{24} = 0.6250$; untuk $n = 5$, $1 - \frac{44}{120} =
\frac{76}{120} = 0.6333$; untuk $n = 6$, $1 - \frac{265}{720} =
\frac{455}{720} = 0.6319$. Semuanya dalam jarak satu persen dari $1 - \eu^{-1}
\approx 0.6321$, dan berayun di sekitarnya.

**18.** Secara langsung:

$$
s_{n+2} - s_n = \frac{(-1)^{n+1}}{(n+1)!} +
\frac{(-1)^{n+2}}{(n+2)!}
= (-1)^{n+1}\Bigl(\frac1{(n+1)!} - \frac1{(n+2)!}\Bigr),
$$

sedangkan kurungnya bernilai $> 0$. Untuk $n$ genap selisihnya negatif: $s_{n+2} < s_n$, jadi $p_0 > p_2 > p_4 > \dots$; untuk $n$ ganjil ia positif: $p_1 < p_3 < p_5 < \dots$ Digabungkan dengan pertanyaan 12 (yang genap di atas $\eu^{-1}$, yang ganjil di bawah) dan pertanyaan 14 (jarak ke $\eu^{-1}$ menuju $0$): kedua tangga itu menjepit $\eu^{-1}$ di antara keduanya.

**19.** Satu penarikan lengkap adalah [permutasi](#def-b1-counting-objects) acak seragam, yang sah bila ia [permutasi](#def-b1-counting-objects) kacau: peluangnya $p_n \approx \eu^{-1}$. Menurut fakta yang dikutip tadi, rata-rata banyaknya penarikan sampai berhasil adalah $1/p_n$, dan pertanyaan 14 memberikan $1/p_n \approx \eu$ dengan galat yang sudah dapat diabaikan bahkan untuk $n$ yang kecil. Jadi tukar kado rahasia dengan pengulangan menelan rata-rata sekitar $\eu \approx 2.72$ penarikan lengkap — entah kantornya berisi $6$ orang atau $600$.

**20.** Tetapkan $j \geq 2$ lalu jalankan penggolongan pertanyaan 5 pada nilai $\sigma(1) = j$. Jika $\sigma(j) = 1$: sisa $n - 2$ titik memikul [permutasi](#def-b1-counting-objects) kacau sembarang, ada $D_{n-2}$ cara. Jika $\sigma(j) \neq 1$: alihkan [prapeta](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-map) $i_0 = \sigma^{-1}(1)$ ke $j$ persis seperti pada pertanyaan 5; ini bijeksi dengan [permutasi](#def-b1-counting-objects) kacau atas $n - 1$ titik $\{2, \dots, n\}$: ada $D_{n-1}$ cara. Totalnya $D_{n-1} + D_{n-2}$, sama untuk setiap $j$. Dengan menjumlahkan atas $n - 1$ nilai $j$: $D_n = (n-1)(D_{n-1} + D_{n-2})$, yang memperlihatkan faktor $n - 1$: $(n-1) \mid D_n$.

**21.** Klaimnya: $D_n$ ganjil jika dan hanya jika $n$ genap. Induksi memakai $D_n = nD_{n-1} + (-1)^n$, yakni $D_n \equiv nD_{n-1} + 1 \pmod 2$. Basis: $D_1 = 0$ genap sedangkan $n = 1$ ganjil: klaimnya berlaku. Jika $n$ genap, $nD_{n-1}$ genap dan $D_n \equiv 1$: ganjil, sesuai klaim. Jika $n$ ganjil, maka $n - 1$ genap, sehingga $D_{n-1}$ ganjil menurut hipotesis, dan $D_n \equiv D_{n-1} + 1 \equiv 0$: genap. Induksinya pun tertutup.

**22.** Mereduksi $D_n = nD_{n-1} + (-1)^n$ modulo $n$ mematikan suku pertamanya: $D_n \equiv (-1)^n \pmod n$. Untuk $n = 10$: $(-1)^{10} = 1$, dan memang $D_{10} = 1\,334\,961$ berakhir pada angka $1$.

**23.** Untuk $n \geq 3$ berlaku $D_{n-1} \geq 1$, dan membagi rekursi pertanyaan 6 dengan $D_{n-1}$ memberikan $D_n/D_{n-1} = n +
(-1)^n/D_{n-1}$, dengan $\abs{(-1)^n/D_{n-1}} \leq 1$ dan menuju $0$ dengan cepat. Kesejalanannya: jika $D_n \approx n!/\eu$, maka $D_n/D_{n-1} \approx n!/(n-1)! = n$ — faktor $\eu$ saling hapus pada rasionya, dan rekursi itu membenarkannya sampai ketelitian $1/D_{n-1}$.

**24.** (i) Kaidah hasil kali dan kaidah jumlah melandasi setiap cacahan: pertanyaan 2 dan 5 mempartisi [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) [permutasi](#def-b1-counting-objects) atas tahap-tahap yang saling bebas. (ii) Pencacahan ganda memberikan rata-rata (pertanyaan 4) dan ragam (pertanyaan 16) banyaknya titik tetap tanpa rumus $D_n$ sama sekali. (iii) Teorema binomial menghitung jumlah dalam yang berselang-seling $(1-1)^{n-j}$, yang membuat inversi binomial berjalan (pertanyaan 8). (iv) Batas deret berselang-seling mengubah jumlah $n!\,s_n$ yang eksak tetapi buram menjadi [pernyataan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-statement) yang bening, yaitu “bilangan bulat terdekat dengan $n!/\eu$” (pertanyaan 10–14).

**25.** Inklusi–eksklusi ([Contoh 2.26](#ex-b1-counting-derangement) dan [Latihan 2.11](#exo-b1-counting-11)) adalah bukti yang konseptual: ia menjelaskan jumlah berselang-seling itu sebagai koreksi atas pencacahan yang berlebih, dan ia dapat diperluas kata demi kata ke pencacahan unsur yang menghindari sebarang keluarga [himpunan](https://one-course.com/books/math/3/id/chapter/1-logika-himpunan-dan-pemetaan#def-b1-logic-sets) “buruk”. Jalur rekursi (pertanyaan 5–7) menghitung paling cepat — waktu linear, aritmetika bilangan bulat yang eksak, tanpa faktorial — dan menjadi sumber fakta aritmetika pada Bagian V. Inversi binomial (pertanyaan 8–9) menempatkan rumus itu di dalam transformasi umum yang akan muncul kembali di mana pun dua sistem kesamaan segitiga saling berhadapan. Dan munculnya $\eu$ paling baik dijelaskan oleh rumus itu sendiri: proporsi [permutasi](#def-b1-counting-objects) kacau adalah jumlah parsial $s_n$ dari deret untuk $\eu^{-1}$, jadi amplop Montmort itu, tiga dasawarsa sebelum notasi Euler, sudah menghitung bilangan $\eu$.