Susunan, permutasi, kombinasi কী?

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

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.

Contoh 2.18 (Satu kesamaan, dua bukti)

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

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.

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.