Matematika Sekolah Menengah Atas · Grades 10–12

27Kombinatorika dan Pencacahan

Kombinatorika adalah seni mencacah tanpa mendaftar. Dua asasnya yang paling dasar — jumlahkan ukuran pilihan yang saling lepas, kalikan banyaknya pilihan yang saling bebas — sudah cukup untuk mencacah susunan, permutasi dan himpunan bagian suatu himpunan berhingga, dan berpuncak pada teorema binomial.

27.1 Dua asas pencacahan

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

Proposisi 27.1 (Asas penjumlahan)

Jika himpunan berhingga $E$ dipartisi menjadi himpunan bagian $A_1, \dots, A_k$ (saling lepas sepasang demi sepasang, dengan gabungan $E$ ), maka

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

Proposisi 27.2 (Asas perkalian)

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

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

Contoh 27.3

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

27.2 Tupel, permutasi, faktorial

Definisi 27.4 (Tupel- $k$ )

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

Proposisi 27.5

Misalkan $\abs E = n$ . Banyaknya tupel- $k$ dari $E$ adalah $n^k$ . Banyaknya susunan $k$ anggota $E$ ( $0 \leq k \leq n$ ) adalah

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

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

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

Definisi 27.6 (Permutasi)

Suatu permutasi dari $E$ adalah susunan seluruh $n$ anggota $E$ , yaitu pengurutan $E$ . Menurut Proposisi 27.5 (kasus $k = n$ ), banyaknya permutasi suatu himpunan beranggota $n$ adalah $n!$ .

Contoh 27.7

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

27.3 Kombinasi dan koefisien binomial

Definisi 27.8 (Kombinasi)

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

Teorema 27.9

Untuk $0 \leq k \leq n$ :

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

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

Proposisi 27.10 (Identitas dasar)

Untuk $0 \leq k \leq n$ :

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

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

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

Bukti. Kesetangkupan $\binom nk = \binom{n}{n-k}$ berlaku sebab pengambilan komplemennya memasangkan himpunan bagian beranggota $k$ dengan yang beranggota $(n-k)$ , satu lawan satu. Untuk kaidah Pascal, tetapkan satu anggota $a \in E$ lalu pilahlah himpunan bagian beranggota $k$ itu menjadi yang memuat $a$ — yang diperoleh dengan menambahkan $a$ pada himpunan bagian beranggota $(k-1)$ dari $E \setminus \{a\}$ , dan banyaknya $\binom{n-1}{k-1}$ — serta yang tidak memuat $a$ , yaitu himpunan bagian beranggota $k$ dari $E \setminus \{a\}$ , yang banyaknya $\binom{n-1}{k}$ . Simpulkan dengan asas penjumlahannya. ∎

Kaidah Pascal membangkitkan koefisiennya baris demi baris, dan itulah yang disebut segitiga Pascal: setiap isian adalah jumlah dua isian di atasnya.

Segitiga Pascal, baris n = 0 sampai 5: kaidah Pascal 41 + 42 = 52 sedang beraksi. — Segitiga Pascal, baris $n = 0$ sampai $5$ : kaidah Pascal $\binom{4}{1} + \binom{4}{2} = \binom{5}{2}$ sedang beraksi.

Teorema 27.11 (Teorema binomial)

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

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

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

Akibat 27.12

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

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

Metode 27.13 (Memilih model yang tepat)

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

	urutan penting	urutan tak penting
pengulangan boleh	$n^k$ (tupel)	(universitas)
tanpa pengulangan	$\frac{n!}{(n-k)!}$ (susunan)	$\binom nk$ (himpunan bagian)

Mengambil bola dari sebuah guci: dengan pengembalian, berurutan $\to$ tupel; tanpa pengembalian, berurutan $\to$ susunan; segenggam sekaligus $\to$ himpunan bagian.

27.4 Latihan

Latihan 27.1 ★

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

Solusi

Solusi Latihan 27.1.

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

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

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

Latihan 27.2 ★

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

Solusi

Solusi Latihan 27.2.

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

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

Latihan 27.3 ★

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

Solusi

Solusi Latihan 27.3.

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

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

Latihan 27.4 ★

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

Solusi

Solusi Latihan 27.4.

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

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

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

Latihan 27.5 ★★

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

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

Solusi

Solusi Latihan 27.5.

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

2. Tepat satu kartu raja: pilihlah kartunya ( $4$ cara) lalu lengkapi dengan $4$ kartu bukan raja: $4 \times \binom{48}{4} = 4 \times 194\,580 = 778\,320$ . Sekurang-kurangnya satu kartu raja, lewat pencacahan komplemennya: $\binom{52}{5} - \binom{48}{5} = 2\,598\,960 - 1\,712\,304 = 886\,656$ .

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

Latihan 27.6 ★★

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

Solusi

Solusi Latihan 27.6.

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

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

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

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

Latihan 27.7 ★★

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

Solusi

Solusi Latihan 27.7.

Secara aljabar:

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

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

Latihan 27.8 ★★

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

Solusi

Solusi Latihan 27.8.

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

Latihan 27.9 ★★★

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

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

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

Solusi

Solusi Latihan 27.9.

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

Dengan $m = n = k$ :

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

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

Latihan 27.10 ★★★

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

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

(Petunjuk: turunkan $(1+x)^n$ , atau pakailah Latihan 27.7.)

Solusi

Solusi Latihan 27.10.

Lewat Latihan 27.7:

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

menurut Akibat 27.12. Lewat penurunan: menurunkan $(1+x)^n = \sum_k \binom nk x^k$ memberi $n(1+x)^{n-1} = \sum_k k \binom nk x^{k-1}$ ; lalu hitung nilainya di $x = 1$ .

27.5 Soal: Seni mencacah dua kali

Soal 27.1

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

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

Bagian I — Memilih modelnya.

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

Bagian II — Bintang dan batang.

Sebuah kedai es krim menjual $4$ rasa; kamu memesan $10$ sendok (rasanya boleh berulang, urutan di dalam cangkirnya tidak penting). Sandikan pesanannya sebagai deretan $10$ bintang (sendoknya) yang dipisahkan oleh $3$ batang (pergantian rasanya), lalu cacahlah pesanannya.
Cacahlah tripel bilangan bulat tak negatif dengan $x + y + z = 12$ .
Cacahlah tripel bilangan bulat positif dengan $x + y + z = 12$ (substitusikan $x = 1 + x'$ , dan seterusnya).
Ada berapa monomial berbeda yang muncul pada penjabaran $(a + b + c)^5$ ?
Ujilah kewarasan caranya: cacahlah pesanan $3$ sendok dari $2$ rasa dengan rumusnya, lalu daftarkan semuanya dan bandingkan.
Sebutkan dengan tepat di mana “sendoknya identik” masuk ke dalam penyandiannya — lalu cacahlah apa yang terjadi jika sebaliknya sendoknya dimakan berurutan (kedudukannya berbeda), dengan daftar periksa pada Metode 27.13.

Bagian III — Topi yang tertukar semua. Suatu permutasi kacau adalah pembagian ulang $n$ topi kepada $n$ pemiliknya yang membuat tak seorang pun menerima topinya sendiri; misalkan $D_n$ mencacahnya. (Soal 18.1 menunjukkan bahwa satu tamu rata-rata memperoleh kembali topinya sendiri — kini kita mencacah pesta yang sepenuhnya sial itu secara eksak.)

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

Bagian IV — Mencacah dua kali, menang dua kali.

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

Solusi

Solusi Soal 27.1.

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

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

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

4. $(1+x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4$ . Di $x = 1$ : $\sum_k \binom nk = 2^n$ ; di $x = -1$ : $\sum_k (-1)^k \binom nk = 0$ — yaitu jumlah barisnya dan jumlah baris berselang-seling pada segitiga Pascal.

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

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

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

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

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

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

11. “Identik” masuk ketika sebuah pesanan dinyatakan tak lebih daripada cacah tiap rasanya — bintangnya tidak membawa nama. Jika sendoknya dimakan berurutan, masing-masing dari $10$ kedudukan yang berbeda itu memilih rasanya secara bebas, sehingga ada $4^{10} = 1\,048\,576$ barisan — model yang lain dan dunia yang lain (Metode 27.13: selalu tanyakan berurutan? berbeda? boleh berulang?).

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

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

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

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

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

17. Setiap jabat tangan menyumbang $2$ pada cacah derajat seluruhnya, sehingga jumlah bilangan jabat tangan semua tamu bernilai genap. Jumlah bilangan bulat bernilai genap hanya jika banyaknya suku ganjil itu genap: jadi penjabat ganjil selalu berpasangan. (Pada pesta bertiga: profil jabat tangan yang mungkin tak pernah punya tepat satu atau tiga isian ganjil — periksalah keempat graf yang mungkin.)

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

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

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

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

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

Istilah yang didefinisikan dalam bab ini

Lihat semua 395 istilah di glosarium