Matematika Universitas — Tahun 1 · Bachelor Year 1

2Pencacahan

Mencacah himpunan hingga terdengar sederhana — dan dengan cepat menjadi halus. Bab ini mendefinisikan kardinalitas secara benar (lewat bijeksi, sejalan dengan Bab 1), menegakkan segelintir asas pencacahan yang darinya segala sesuatu mengikut, lalu menurunkan hasil cacah yang klasik: daftar, permutasi, himpunan bagian, koefisien binomial.

2.1 Kardinalitas himpunan hingga

Definisi 2.1 (Himpunan hingga, kardinalitas)

Untuk $n \in \N^*$ , tulis $\intint{1}{n} = \{1, 2, \dots, n\}$ . Himpunan $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) 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 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 sama sekali. Andaikan pernyataan 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 $f \colon E \to F$ yang injektif: 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, maka $v \circ f \circ u$ akan menjadi injeksi dari $\intint1m$ ke dalam $\intint1n$ (komposisi injeksi, Proposisi 1.26), bertentangan dengan Teorema 2.2. ∎

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

Bukti Teorema 2.2 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 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 kacau mengalihkan $\sigma^{-1}(n+1)$ pada soal akhir pekan bab ini, dan begitulah permutasi ditambal di sepanjang soal Bab 7 tentang grup simetri.

Proposisi 2.5 (Injeksi, surjeksi dan kardinalitas)

Misalkan $E, F$ himpunan hingga 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. 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 berkardinalitas $\abs{F} - 1 < \abs{E}$ — mustahil menurut prinsip sarang merpati. Jadi $f(E) = F$ : $f$ surjektif, sehingga bijektif.

Andaikan $f$ surjektif. Pilih untuk setiap $y \in F$ satu prapeta $s(y) \in E$ ; maka $f \circ s = \mathrm{id}_F$ , jadi $s$ injektif (Proposisi 1.26). Menurut paragraf sebelumnya yang diterapkan pada $s$ (kardinalitas keduanya sama), $s$ bijektif. Dari $f \circ s = \mathrm{id}_F$ kita peroleh $f = \mathrm{id}_F \circ s^{-1} = s^{-1}$ , jadi $f$ bijektif. Akhirnya, pemetaan bijektif menurut definisinya sekaligus injektif dan surjektif, dan itu menutup daur implikasinya. ∎

Contoh 2.6 (Kehinggaan itu penting)

Pada himpunan yang hingga, Proposisi 2.5 adalah jalan pintas yang ampuh: setiap pemetaan injektif dari $E$ ke dirinya sendiri otomatis menjadi permutasi $E$ — separuh dari kebijektifan datang cuma-cuma. Kedua implikasi itu runtuh pada himpunan tak hingga: $n \mapsto n + 1$ injektif dari $\N$ ke $\N$ tetapi melewatkan $0$ , dan pemetaan $\N \to \N$ yang mengirim $0 \mapsto 0$ dan $n \mapsto n - 1$ untuk $n \geq 1$ surjektif tetapi tidak injektif. Setiap kali proposisi ini dipanggil, hipotesis kehinggaannya sedang bekerja sungguhan — tema yang ditelusuri soal akhir pekan Bab 1 dari sisi yang berlawanan, tempat himpunan tak hingga persis adalah himpunan yang punya pemetaan-diri semacam itu.

Contoh 2.7 (Separuh pekerjaan, cuma-cuma)

Tinjau pemetaan $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): 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); 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), menggerakkan pemasangan pada teorema Wilson, dan kembali dalam aljabar linear sebagai “endomorfisma ruang berdimensi hingga bersifat injektif jika dan hanya jika surjektif” (Bab 19).

2.2 Asas pencacahan

Proposisi 2.8 (Kaidah jumlah dan kaidah hasil kali)

Misalkan $E, F$ himpunan hingga.

Jika $E \cap F = \emptyset$ , maka $\abs{E \cup F} = \abs{E} + \abs{F}$ ; lebih umum, untuk partisi $E$ atas potongan $E_1, \dots, E_k$ berlaku $\abs{E} = \sum_i \abs{E_i}$ .
Secara umum, $\abs{E \cup F} = \abs{E} + \abs{F} - \abs{E \cap F}$ .
$\abs{E \times F} = \abs{E} \times \abs{F}$ .
Himpunan $F^E$ berisi semua pemetaan dari $E$ ke $F$ memenuhi $\abs{F^E} = \abs{F}^{\abs{E}}$ .
$\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 $\{x\} \times F$ , yang masing-masing berkardinalitas $\abs{F}$ ; terapkan (1).

(4) Sebuah pemetaan 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 bagian $E$ berpadanan secara bijektif dengan pemetaan $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 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 bagian posisi — satu lagi contoh dari semboyan bahwa cacahan yang benar adalah bijeksi yang menyamar (Metode 2.19).

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. — 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 dengan $\abs{E} = n$ dan $0 \leq k \leq n$ .

Susunan- $k$ dari $E$ adalah tupel- $k$ injektif 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 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$ :

banyaknya susunan- $k$ dari $E$ adalah $n (n-1) \cdots (n-k+1) = \dfrac{n!}{(n-k)!}$ ;
banyaknya permutasi $E$ adalah $n!$ ;
$\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 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 bagian beranggota $k$ terurutkan menjadi $k!$ susunan- $k$ yang berbeda, dan setiap susunan- $k$ muncul dari tepat satu himpunan 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 bagian beranggota $k$ dan himpunan bagian beranggota $(n-k)$ . Kaidah Pascal: tetapkan sebuah unsur $a \in E$ ; himpunan 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 bagian $E$ , dan di ruas kiri cacahan itu dipilah menurut ukurannya (Proposisi 2.8 (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 bagian sebuah himpunan 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 $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)

Lalu carilah bijeksi atau partisi yang menyusutkan masalahnya menjadi cacahan model itu; cacahan yang benar adalah bijeksi yang menyamar.

Catatan 2.20 (Jebakan yang lazim dalam pencacahan)

Menjumlahkan kasus yang tidak saling lepas. Kaidah jumlah menuntut sebuah partisi; jika sebuah konfigurasi dapat memenuhi dua kasus sekaligus, ia tercacah dua kali — obatnya adalah inklusi–eksklusi (Teorema 2.24) atau pemilahan kasus yang lebih halus.
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.
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.
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).

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 yang dicacah oleh kedua ruasnya — lazimnya himpunan 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 dan beberapa pertanyaan pada soal akhir pekan di bawah.

Contoh 2.23 (Himpunan bagian rata-rata)

Berapa kardinalitas rata-rata sebuah himpunan bagian dari himpunan beranggota $n$ unsur, katakanlah $E$ , bila semua $2^n$ himpunan bagiannya sama-sama mungkin? Cacah ganda pasangan $(A, a)$ dengan $a \in A$ : menjumlahkan atas himpunan 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 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 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: pemasangan yang dipilih dengan baik sering menggantikan sebuah kesamaan.

2.4 Inklusi–eksklusi

Teorema 2.24 (Inklusi–eksklusi)

Untuk himpunan hingga $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. 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 bagian $\{2, 3, 5\}$ . Bentuk hasil kali ini mendefinisikan fungsi totien Euler, yang peran aritmetikanya muncul bersama kekongruenan Bab 6 dan dikembangkan pada jilid Tahun ke-2.

Contoh 2.26 (Permutasi kacau)

Permutasi kacau adalah permutasi tanpa titik tetap. Misalkan $A_i$ himpunan permutasi $\intint{1}{n}$ yang menetapkan $i$ ; maka $\abs{\bigcap_{i \in I} A_i} = (n - \abs I)!$ , dan inklusi–eksklusi mencacah permutasi yang mempunyai sekurang-kurangnya satu titik tetap; permutasi kacau berjumlah

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

Karena $\sum (-1)^k / k! \to \eu^{-1}$ (lihat Bab 17), sekitar $37\%$ dari semua permutasi adalah permutasi kacau, berapa pun $n$ itu.

Catatan 2.27 (Di mana bab ini dipakai)

Koefisien binomial adalah objek bab ini yang paling banyak dipakai ulang: ia menggerakkan teorema binomial pada Bab 8 (penjabaran $(X + a)^n$ ), rumus Leibniz bagi turunan ke- $n$ sebuah hasil kali pada Bab 14, dan koefisien ekspansi Taylor pada Bab 16. Permutasi kembali sebagai grup — dengan tanda yang dibangun dari pencacahan inversi — pada Bab 7, dan tanda itu pada gilirannya mendefinisikan determinan pada Bab 22. Inklusi–eksklusi dan asas pencacahan adalah tulang punggung hingga bagi peluang diskret, yang dikembangkan pada jilid Tahun ke-2; bilangan permutasi kacau pada Contoh 2.26 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

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

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

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

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

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

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. (Cara lain: turunkan $(1+x)^n = \sum_k \binom nk x^k$ lalu ambil $x = 1$ .)

Latihan 2.6 ★★

Ada berapa banyak pemetaan naik tegas dari $\intint{1}{k}$ ke $\intint{1}{n}$ ? Simpulkan banyaknya pemetaan naik (tidak harus tegas). Petunjuk untuk cacahan kedua: $f$ naik $\mapsto$ $g(i) = f(i) + i - 1$ .

Solusi

Solusi Latihan 2.6.

Pemetaan naik tegas $f \colon \intint{1}{k} \to \intint{1}{n}$ ditentukan oleh petanya, yaitu himpunan bagian beranggota $k$ dari $\intint{1}{n}$ (daftarkan himpunan bagian itu dalam urutan naik); sebaliknya setiap himpunan bagian beranggota $k$ memberi tepat satu pemetaan semacam itu. Jadi ada $\binom nk$ pemetaan 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 naik.

Latihan 2.7 ★★

(Vandermonde) Buktikan, dengan mencacah himpunan bagian beranggota $k$ dari sebuah himpunan 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

Solusi Latihan 2.7.

Belah himpunan $E$ beranggota $m + n$ unsur atas blok $M$ ( $m$ unsur) dan $N$ ( $n$ unsur). Himpunan 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 bagian semacam itu, dan kasus $j = 0, \dots, k$ mempartisi himpunan 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

Solusi Latihan 2.8.

Misalkan $A_d$ himpunan kelipatan $d$ di $\intint{1}{1000}$ , sehingga $\abs{A_d} = \lfloor 1000/d \rfloor$ . Inklusi–eksklusi (Teorema 2.24) 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 beranggota $4$ unsur pada himpunan beranggota $2$ unsur; lalu pada himpunan beranggota $3$ unsur. Petunjuk: cacah pemetaan yang tak surjektif dengan inklusi–eksklusi atas nilai yang terlewat.

Solusi

Solusi Latihan 2.9.

Pada $2$ unsur: seluruh $2^4 = 16$ pemetaan kecuali $2$ pemetaan konstan: ada $14$ surjeksi.

Pada $3$ unsur: dengan inklusi–eksklusi atas nilai yang terlewat, banyaknya pemetaan dari himpunan beranggota $4$ ke himpunan beranggota $3$ yang melewatkan sekurang-kurangnya satu nilai adalah $\binom 31 2^4 - \binom 32 1^4 = 48 - 3 = 45$ ; seluruh pemetaan 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

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 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 menurut himpunan titik tetapnya).

Solusi

Solusi Latihan 2.11.

Dengan $A_i = \{\sigma : \sigma(i) = i\}$ , sebuah permutasi 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 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 $\sigma$ dari $\intint{1}{n}$ menurut himpunan titik tetapnya $F(\sigma)$ . Untuk himpunan bagian beranggota $k$ yang tetap, katakanlah $F$ , permutasi dengan $F(\sigma) = F$ tepat adalah permutasi 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 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

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 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 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 kacau $D_n$ pada Contoh 2.26. 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 acak, serta aritmetika ganjil barisan $(D_n)$ . Di sepanjang soal ini, $D_n$ menyatakan banyaknya permutasi kacau (permutasi tanpa titik tetap) dari $\intint1n$ , dengan kesepakatan $D_0 = 1$ (permutasi kosong tidak mempunyai titik tetap).

Bagian I — Kasus kecil dan sensus titik tetap.

Hitung $D_1, D_2, D_3$ secara langsung, dan $D_4$ dengan mendaftar permutasi kacau $\{1, 2, 3, 4\}$ yang dikelompokkan menurut nilai $\sigma(1)$ . (Anda semestinya memperoleh $D_4 = 9$ .)
Untuk $0 \leq k \leq n$ , tunjukkan bahwa banyaknya $P_k(n)$ permutasi $\intint1n$ yang mempunyai tepat $k$ titik tetap adalah $\binom nk D_{n-k}$ .
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?
Dengan pencacahan ganda (Metode 2.22) pasangan $(\sigma, i)$ yang memenuhi $\sigma(i) = i$ , tunjukkan bahwa

$\sum_{\sigma} \abs{\mathrm{Fix}(\sigma)} = n! :$

rata-rata, sebuah permutasi acak mempunyai tepat satu titik tetap, berapa pun $n \geq 1$ itu.

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

Buktikan secara kombinatorial, untuk $n \geq 1$ :

$D_{n+1} = n\,(D_n + D_{n-1}) .$

(Golongkan permutasi 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 kacau $\intint1n$ dengan mengalihkan prapeta $n + 1$ ke $j$ .) Periksa rekursi itu secara numerik sampai $D_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).$
Dari pertanyaan 6, buktikan dengan induksi rumus pada Contoh 2.26,

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

— sebuah bukti yang sama sekali tak bergantung pada inklusi–eksklusi.
(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.)
Terapkan pertanyaan 8 pada kesamaan $n! = \sum_k \binom nk D_{n-k}$ dari Latihan 2.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 — 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$ .

Tunjukkan bahwa $\bigl| D_n - n!/\eu \bigr| < \frac1{n+1}$ untuk setiap $n \in \N$ .
Simpulkan teorema utamanya: untuk setiap $n \geq 1$ , $D_n$ adalah bilangan bulat terdekat dengan $n!/\eu$ . Mengapa argumen itu memerlukan $n \geq 1$ ?
Tentukan tanda galatnya: tunjukkan bahwa $D_n > n!/\eu$ tepat ketika $n$ genap. (Cari suku pertama yang diabaikan pada deret berselang-seling itu.)
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$ ).
(Peluang penitipan topi) Misalkan $p_n = D_n/n!$ peluang bahwa sebuah permutasi acak seragam merupakan permutasi 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.

Tetapkan $k \in \N$ . Tunjukkan bahwa proporsi permutasi $\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.)
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.
Hitung proporsi permutasi 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$ .
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}$ .
(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.

Perhalus pertanyaan 5: tunjukkan bahwa untuk $j \in \intint2n$ yang tetap, permutasi 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$ .
Buktikan bahwa $D_n$ ganjil jika dan hanya jika $n$ genap. (Bekerjalah modulo $2$ pada rekursi pertanyaan 6.)
Buktikan bahwa $D_n \equiv (-1)^n \pmod n$ untuk $n \geq 1$ , lalu periksa kekongruenan itu pada angka terakhir $D_{10}$ .
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 kacau yang berurutan hampir persis $n$ ; jelaskan dalam satu kalimat mengapa hal ini sejalan dengan $D_n \approx n!/\eu$ .
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.
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

Solusi Soal 2.1.

1. $D_1 = 0$ (satu-satunya permutasi 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 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 dengan tepat $k$ titik tetap ditentukan oleh pilihan himpunan titik tetapnya $F$ ( $\binom nk$ cara) beserta pembatasannya pada komplemen, yang haruslah permutasi $n - k$ titik tanpa titik tetap ( $D_{n-k}$ cara). Kedua pilihan itu saling bebas dan padanannya bijektif: $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 yang menetapkan $i$ adalah permutasi $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, yaitu $n!$ : rata-rata banyaknya titik tetap adalah tepat $1$ , untuk setiap $n \geq 1$ .

5. Misalkan $\sigma$ permutasi 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 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 $\intint1n$ (nilai $n+1$ telah digantikan oleh nilai $j$ yang hilang), dan ia permutasi kacau: $\tau(i_0) = j \neq i_0$ , dan $\tau(i) = \sigma(i) \neq i$ di tempat lain. Sebaliknya, dari sebuah permutasi 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 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): 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 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 yang menetapkan $i$ sekaligus $j$ adalah permutasi $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 acak seragam, yang sah bila ia permutasi 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 kacau sembarang, ada $D_{n-2}$ cara. Jika $\sigma(j) \neq 1$ : alihkan prapeta $i_0 = \sigma^{-1}(1)$ ke $j$ persis seperti pada pertanyaan 5; ini bijeksi dengan permutasi 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 permutasi 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 yang bening, yaitu “bilangan bulat terdekat dengan $n!/\eu$ ” (pertanyaan 10–14).

25. Inklusi–eksklusi (Contoh 2.26 dan Latihan 2.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 “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 kacau adalah jumlah parsial $s_n$ dari deret untuk $\eu^{-1}$ , jadi amplop Montmort itu, tiga dasawarsa sebelum notasi Euler, sudah menghitung bilangan $\eu$ .

Istilah yang didefinisikan dalam bab ini

Lihat semua 395 istilah di glosarium