Lewati ke konten utama
Gambar logo

Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Oscar Levin

Subbab 3.8 Pencacahan Lanjut dengan Prinsip Inklusi–Eksklusi

Subbagian Pratinjau Bagian

Selidiki!
Anda memiliki 11 pai jeruk nipis mini yang identik untuk diberikan kepada 4 anak. Namun, Anda tidak ingin seorang anak pun menerima lebih dari 3 pai. Dengan berapa banyak cara pai tersebut dapat dibagikan?
🔗
🔗
Metode batang dan batu memungkinkan kita, misalnya, mencacah banyaknya cara membagikan 10 kue kering kepada 3 anak dan banyaknya solusi bilangan asli untuk \(x+y+z = 10\text{.}\) Dengan modifikasi yang relatif mudah, kita dapat memberlakukan batas bawah pada masalah-masalah ini: mungkin setiap anak harus menerima sedikitnya dua kue kering, atau \(x,y,z \ge 2\text{.}\) Caranya ialah terlebih dahulu memberikan 2 kue kering (atau satuan) kepada setiap anak (atau variabel), kemudian membagikan sisanya dengan metode batang dan batu.
🔗
Bagaimana jika kita menginginkan batas atas? Sebagai contoh, kita mungkin mensyaratkan bahwa tidak ada anak yang menerima lebih dari 4 kue kering atau bahwa \(x, y, z \le 4\text{.}\) Ternyata masalah ini jauh lebih sulit.
🔗
Perhatikan bahwa jika kita mempertimbangkan kejadian komplemen, yaitu pembagian kue kering yang menyebabkan anak-anak menerima lebih dari 4 kue kering, kita kembali pada masalah batang dan batu dengan batas bawah. Jika kita dapat mencacahnya, mengurangkan hasil tersebut dari seluruh kemungkinan pembagian seharusnya memberikan jawaban yang diinginkan. Namun, masalahnya adalah bahwa komplemen dari “tidak ada anak yang menerima lebih dari 4 kue kering” ialah “sedikitnya satu anak menerima lebih dari 4 kue kering”. Kita tahu cara menangani syarat bahwa semua anak menerima sedikitnya 5 kue kering, tetapi bagaimana menangani kasus ketika satu atau lebih anak menerima sedikitnya 5 kue kering? Kita harus menggunakan prinsip inklusi–eksklusi.
🔗

Lembar Kerja Kegiatan Pratinjau

Pertama, mari kita tinjau kembali beberapa pertanyaan bertipe batang dan batu yang telah kita pelajari dalam Subbab 3.5.
🔗
Kemudian kita akan memodifikasinya dan menerapkan prinsip inklusi–eksklusi dari Subbab 3.3.
🔗
1.
Misalkan kita memiliki 10 kue kering untuk diberikan kepada tiga anak: Albie, Bertie, dan Charlie.
🔗
(a)
Dengan berapa banyak cara kita dapat membagikan kue kering tersebut tanpa pembatasan?
🔗
🔗
(b)
Dengan berapa banyak cara kita dapat membagikan kue kering jika setiap anak harus menerima sedikitnya dua kue kering?
🔗
Petunjuk.
Berikan terlebih dahulu jumlah minimum kue kering kepada setiap anak. Dengan berapa banyak cara sisa kue kering dapat dibagikan?
🔗
🔗
🔗
(c)
Dengan berapa banyak cara Anda dapat membagikan kue kering jika Albie menerima sedikitnya 3 kue kering dan Bertie menerima sedikitnya 2 kue kering (sedangkan Charlie tidak memiliki pembatasan)?
🔗
🔗
🔗
2.
Mari kita kembali mempertimbangkan 10 kue kering yang ingin kita bagikan kepada Albie, Bertie, dan Charlie. Kali ini, kita akan memberlakukan beberapa batas atas.
🔗
(a)
Dengan berapa banyak cara kita dapat membagikan kue kering jika Albie memang menerima lebih dari 3 kue kering (jadi sedikitnya 4)?
🔗
Dengan berapa banyak cara kita dapat membagikan kue kering jika Albie tidak menerima lebih dari 3 kue kering?
🔗
🔗
(b)
Dengan berapa banyak cara kita dapat membagikan kue kering jika Bertie memang menerima lebih dari 3 kue kering?
🔗
🔗
(c)
Dengan berapa banyak cara kita dapat membagikan kue kering jika Albie dan Bertie sama-sama menerima lebih dari 3 kue kering?
🔗
🔗
(d)
Dengan menggunakan prinsip inklusi–eksklusi untuk dua himpunan, dengan berapa banyak cara kita dapat membagikan kue kering jika sedikitnya salah satu dari Albie atau Bertie menerima lebih dari 3 kue kering? Jadi, Albie menerima lebih dari 3 kue kering, Bertie menerima lebih dari 3 kue kering, atau keduanya menerima lebih dari 3 kue kering.
🔗
🔗
(e)
Dengan berapa banyak cara kita dapat membagikan kue kering jika baik Albie maupun Bertie tidak menerima lebih dari 3 kue kering?
🔗
🔗
🔗
🔗
🔗

Subbagian Prinsip Inklusi–Eksklusi untuk Multihimpunan

Prinsip inklusi–eksklusi memberikan metode untuk menentukan kardinalitas gabungan himpunan-himpunan yang tidak harus saling lepas. Dalam Subbab 3.3, kita telah melihat cara kerjanya untuk tiga himpunan. Untuk menentukan berapa banyak objek yang berada dalam satu atau lebih di antara himpunan \(A\text{,}\) \(B\text{,}\) dan \(C\text{,}\) kita mula-mula menjumlahkan banyaknya anggota setiap himpunan. Namun, jika himpunan-himpunan tersebut bertumpang tindih, sejumlah anggota terhitung beberapa kali. Karena itu, kita mengurangkan anggota dalam setiap irisan sepasang himpunan. Akan tetapi, tindakan ini menghapus anggota yang berada dalam ketiga himpunan satu kali terlalu banyak, sehingga kita harus menambahkannya kembali. Dalam kardinalitas himpunan, kita memperoleh
\begin{equation*} |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A\cap B \cap C| \text{.} \end{equation*}
🔗

Contoh 3.8.1.

Tiga anak, Alberto, Bernadette, dan Carlos, memutuskan untuk berbagi 11 kue kering. Mereka bertanya-tanya dengan berapa banyak cara kue tersebut dapat dibagi jika tidak seorang pun menerima lebih dari 4 kue kering (entah mengapa, ketiga anak itu tidak keberatan jika seseorang tidak menerima kue sama sekali).
🔗
Penyelesaian.
Tanpa batasan “tidak lebih dari 4”, jawabannya adalah \({13 \choose 2}\text{,}\) dengan menggunakan 11 batu dan 2 batang (untuk memisahkan bagian ketiga anak). Sekarang, cacahlah banyaknya cara satu atau lebih anak melanggar syarat tersebut, yaitu menerima sedikitnya 5 kue kering.
🔗
Misalkan \(A\) adalah himpunan hasil ketika Alberto menerima lebih dari 4 kue kering. Misalkan \(B\) adalah himpunan hasil ketika Bernadette menerima lebih dari 4 kue kering. Misalkan \(C\) adalah himpunan hasil ketika Carlos menerima lebih dari 4 kue kering. Untuk melakukan pengurangan, kita mencari banyaknya anggota himpunan \(A \cup B \cup C\text{.}\) Dengan prinsip inklusi–eksklusi, kita harus menentukan \(|A|\text{,}\) \(|B|\text{,}\) \(|C|\text{,}\) \(|A\cap B|\text{,}\) dan seterusnya. Hasilnya sebagai berikut.
🔗
  • \(|A| = {8 \choose 2}\text{.}\) Berikan terlebih dahulu 5 kue kering kepada Alberto, lalu bagikan 6 kue yang tersisa kepada ketiga anak tanpa pembatasan dengan menggunakan 6 batu dan 2 batang.
    🔗
  • \(|B| = {8 \choose 2}\text{.}\) Sama seperti di atas, tetapi kali ini Bernadette menerima 5 kue kering terlebih dahulu.
    🔗
  • \(|C| = {8 \choose 2}\text{.}\) Carlos menerima 5 kue kering terlebih dahulu.
    🔗
  • \(|A \cap B| = {3 \choose 2}\text{.}\) Berikan masing-masing 5 kue kering kepada Alberto dan Bernadette, sehingga tersisa 1 kue (batu) untuk dibagikan kepada ketiga anak (2 batang).
    🔗
  • \(|A \cap C| = {3 \choose 2}\text{.}\) Alberto dan Carlos masing-masing menerima 5 kue kering terlebih dahulu.
    🔗
  • \(|B \cap C| = {3 \choose 2}\text{.}\) Bernadette dan Carlos masing-masing menerima 5 kue kering terlebih dahulu.
    🔗
  • \(|A \cap B \cap C| = 0\text{.}\) Ketiga anak tidak mungkin masing-masing menerima 5 kue kering atau lebih.
    🔗
🔗
Dengan menggabungkan semuanya, kita memperoleh
\begin{equation*} |A \cup B \cup C| = {8 \choose 2} + {8 \choose 2} + {8 \choose 2} - {3 \choose 2} - {3 \choose 2} - {3 \choose 2} + 0 = 75 \text{.} \end{equation*}
🔗
Jadi, jawaban atas pertanyaan semula adalah \({13 \choose 2} - 75 = 78 - 75 = 3\text{.}\) Setelah melihatnya, hasil ini masuk akal. Satu-satunya cara memastikan bahwa tidak ada anak yang menerima lebih dari 4 kue kering adalah memberikan 4 kue kepada dua anak dan 3 kue kepada satu anak; terdapat tiga pilihan untuk anak yang menerima 3 kue. Pengamatan ini sebenarnya dapat memberi jawaban jauh lebih cepat, tetapi tujuan contoh ini adalah menunjukkan bahwa prinsip inklusi–eksklusi bekerja!
🔗
🔗
🔗
Untuk empat himpunan atau lebih, kita tidak menuliskan sebuah rumus panjang bagi prinsip inklusi–eksklusi. Sebaliknya, kita memikirkan prinsipnya: jumlahkan semua anggota dalam setiap himpunan tunggal, lalu kurangkan objek yang terhitung dua kali (anggota dalam irisan setiap pasangan himpunan); tambahkan kembali anggota yang terhapus terlalu sering (anggota dalam irisan kelompok tiga himpunan); kurangkan lagi anggota yang ditambahkan kembali terlalu sering (anggota dalam irisan kelompok empat himpunan); lalu tambahkan kembali, kurangkan lagi, tambahkan kembali, dan seterusnya. Hal ini akan sangat sulit seandainya dalam masalah-masalah ini kardinalitas setiap himpunan tunggal tidak sama, kardinalitas setiap irisan dua himpunan tidak sama, dan begitu pula untuk irisan tiga himpunan dan seterusnya. Karena semuanya sama menurut ukurannya, kita dapat mengelompokkannya dan mengalikan dengan banyaknya kombinasi berbeda dari 1, 2, 3, … himpunan.
🔗

Contoh 3.8.2.

Dengan berapa banyak cara Anda dapat membagikan 10 kue kering kepada 4 anak sehingga tidak ada anak yang menerima lebih dari 2 kue kering?
🔗
Penyelesaian.
Terdapat \({13 \choose 3}\) cara untuk membagikan 10 kue kering kepada 4 anak (menggunakan 10 batu dan 3 batang). Kita akan mengurangkan semua hasil ketika seorang anak menerima 3 kue kering atau lebih. Berapa banyak hasil semacam itu? Kita dapat memastikan bahwa anak A memakan 3 kue kering atau lebih dengan memberinya 3 kue sebelum pembagian dimulai. Hal ini mengubah masalah menjadi pembagian 7 kue kering kepada 4 anak tanpa pembatasan. Dalam kasus tersebut, terdapat 7 batu (7 kue yang tersisa) dan 3 batang (satu kurang dari banyaknya anak), sehingga kue dapat dibagikan dengan \({10 \choose 3}\) cara. Tentu saja, kita dapat memilih salah satu dari 4 anak untuk menerima terlalu banyak kue, sehingga tampaknya terdapat \({4 \choose 1}{10 \choose 3}\) pembagian yang memberi terlalu banyak kue kepada satu anak. Namun, sebenarnya kita telah mencacah beberapa hasil terlalu banyak.
🔗
Kita harus menghilangkan hasil ketika dua anak menerima terlalu banyak kue. Terdapat \({4 \choose 2}\) cara memilih 2 anak yang akan diberi kue tambahan. Diperlukan 6 kue untuk melakukannya, sehingga hanya tersisa 4 kue. Jadi, kita mempunyai 4 batu dan tetap 3 batang. Dengan demikian, 4 kue yang tersisa dapat dibagikan dengan \({7 \choose 3}\) cara untuk setiap satu dari \({4 \choose 2}\) pilihan pasangan anak yang diberi terlalu banyak kue.
🔗
Namun, sekarang kita telah menghapus terlalu banyak. Kita harus menambahkan kembali semua cara memberi terlalu banyak kue kepada tiga anak. Hal ini menggunakan 9 kue, sehingga hanya tersisa 1 kue untuk dibagikan kepada 4 anak dengan metode batang dan batu, yang dapat dilakukan dengan \({4 \choose 3}\) cara. Kita harus memperhitungkan hasil ini untuk setiap kemungkinan pilihan tiga anak yang menerima terlalu banyak kue, dan terdapat \({4 \choose 3}\) cara memilih himpunan 3 anak tersebut.
🔗
Berikutnya, kita akan mengurangkan semua cara memberi terlalu banyak kue kepada keempat anak, tetapi dalam kasus ini jumlahnya 0.
🔗
Secara keseluruhan, banyaknya cara membagikan 10 kue kering kepada 4 anak tanpa memberi seorang anak pun lebih dari 2 kue adalah
\begin{equation*} {13 \choose 3} - \left[{4 \choose 1}{10 \choose 3} - {4 \choose 2}{7 \choose 3} + {4\choose 3}{4\choose 3}\right] \end{equation*}
yaitu
\begin{equation*} 286 - [480 - 210 + 16] = 0 \text{.} \end{equation*}
🔗
Hasil ini masuk akal: TIDAK ADA cara membagikan 10 kue kering kepada 4 anak sambil memastikan bahwa tidak seorang pun menerima lebih dari 2 kue. Agak mengejutkan bahwa
\begin{equation*} {13 \choose 3} = \left[{4 \choose 1}{10 \choose 3} - {4 \choose 2}{7 \choose 3} + {4\choose 3}{4\choose 3}\right] \text{,} \end{equation*}
tetapi karena prinsip inklusi–eksklusi bekerja, kesetaraan ini harus berlaku.
🔗
🔗
🔗
Agar Anda tidak mengira bahwa masalah semacam ini selalu memiliki penyelesaian yang lebih mudah, perhatikan contoh berikut.
🔗

Contoh 3.8.3.

Sebelumnya, dalam Contoh 3.5.6, kita mencacah banyaknya solusi persamaan
\begin{equation*} x_1 + x_2 + x_3 + x_4 + x_5 = 13 \text{,} \end{equation*}
dengan \(x_i \ge 0\) untuk setiap \(x_i\text{.}\)
🔗
Berapa banyak di antara solusi tersebut yang memenuhi \(0 \le x_i \le 3\) untuk setiap \(x_i\text{?}\)
🔗
Penyelesaian.
Kita harus mengurangkan banyaknya solusi ketika satu atau lebih variabel bernilai lebih besar dari 3. Kita perlu menggunakan prinsip inklusi–eksklusi karena pencacahan solusi untuk setiap variabel yang secara terpisah lebih besar dari 3 akan mencacah beberapa solusi berkali-kali. Hasilnya sebagai berikut.
🔗
  • Seluruh solusi: \({17 \choose 4}\text{.}\)
    🔗
    🔗
  • Solusi dengan \(x_1 > 3\text{:}\) \({13 \choose 4}\text{.}\) Berikan 4 satuan terlebih dahulu kepada \(x_1\text{,}\) lalu bagikan 9 satuan yang tersisa kepada 5 variabel.
    🔗
    🔗
  • Solusi dengan \(x_1 > 3\) dan \(x_2 > 3\text{:}\) \({9 \choose 4}\text{.}\) Setelah memberikan 4 satuan kepada \(x_1\) dan 4 satuan lagi kepada \(x_2\text{,}\) hanya tersisa 5 satuan untuk dibagikan.
    🔗
    🔗
  • Solusi dengan \(x_1 > 3\text{,}\) \(x_2 > 3\text{,}\) dan \(x_3 > 3\text{:}\) \({5 \choose 4}\text{.}\)
    🔗
    🔗
  • Solusi dengan \(x_1 > 3\text{,}\) \(x_2 > 3\text{,}\) \(x_3 > 3\text{,}\) dan \(x_4 > 3\text{:}\) 0.
    🔗
    🔗
🔗
Kita juga harus memperhitungkan bahwa salah satu dari kelima variabel dapat dipilih menggantikan \(x_1\) di atas (sehingga terdapat \({5 \choose 1}\) hasil semacam ini), sembarang pasangan variabel dapat menggantikan \(x_1\) dan \(x_2\) (sebanyak \({5 \choose 2}\) hasil), dan seterusnya. Inilah penyebab pencacahan ganda, sehingga kita perlu menggunakan prinsip inklusi–eksklusi. Secara keseluruhan, banyaknya solusi dengan \(0 \le x_i \le 3\) adalah
\begin{equation*} {17 \choose 4} - \left[{5\choose 1}{13 \choose 4} - {5 \choose 2}{9 \choose 4} + {5 \choose 3}{5 \choose 4}\right] = 15 \text{.} \end{equation*}
🔗
🔗
🔗
🔗

Subbagian Mencacah Permutasi Tanpa Titik Tetap

Selidiki!
Sebagai lelucon menjelang kelulusan, Anda memutuskan untuk menukar papan nama pada pintu lima dosen favorit Anda. Agar tidak ada yang merasa dilupakan, Anda ingin memastikan bahwa setiap papan nama berakhir pada pintu yang salah. Dengan berapa banyak cara hal ini dapat dilakukan?
🔗
🔗
Penggunaan lanjut prinsip inklusi–eksklusi memiliki penerapan di luar metode batang dan batu. Sebuah permutasi tanpa titik tetap dari \(n\) anggota \(\{1,2,3,\ldots, n\}\) adalah permutasi yang tidak menetapkan anggota mana pun pada posisi semula. Sebagai contoh, terdapat \(6\) permutasi dari tiga anggota \(\{1,2,3\}\text{:}\)
\begin{equation*} 123 ~~ 132 ~~ 213 ~~ 231 ~~ 312 ~~ 321 \text{.} \end{equation*}
Namun, sebagian besar permutasi tersebut memiliki satu atau lebih anggota yang tetap: \(123\) menetapkan ketiga anggota karena semuanya berada pada posisi semula, \(132\) menetapkan anggota pertama (1 berada pada posisi pertama semula), dan seterusnya. Sebenarnya, satu-satunya permutasi tanpa titik tetap dari tiga anggota adalah
\begin{equation*} 231 \text{ dan } 312 \text{.} \end{equation*}
🔗
Jika kita beralih ke 4 anggota, terdapat 24 permutasi (karena ada 4 pilihan untuk anggota pertama, 3 pilihan untuk anggota kedua, dan 2 pilihan untuk anggota ketiga, sehingga hanya tersisa 1 pilihan untuk anggota terakhir). Berapa banyak di antaranya yang merupakan permutasi tanpa titik tetap? Jika Anda mendaftarkan semua 24 permutasi dan menghapus yang memiliki titik tetap, hanya tersisa 9 permutasi tanpa titik tetap. Mari kita lihat cara memperoleh bilangan itu dengan prinsip inklusi–eksklusi.
🔗

Contoh 3.8.4.

Berapa banyak permutasi tanpa titik tetap dari 4 anggota?
🔗
Penyelesaian.
Kita mencacah semua permutasi lalu mengurangkan permutasi yang memiliki titik tetap. Terdapat \(4! = 24\) permutasi dari 4 anggota. Agar suatu permutasi bukan permutasi tanpa titik tetap, sedikitnya satu dari 4 anggota harus berada pada posisi semula. Terdapat \({4 \choose 1}\) pilihan untuk satu anggota yang ditetapkan. Setelah anggota itu ditetapkan, kita perlu membentuk permutasi dari tiga anggota lainnya. Terdapat \(3!\) permutasi dari 3 anggota.
🔗
Namun, sekarang kita telah mencacah terlalu banyak permutasi yang memiliki titik tetap, sehingga kita harus mengurangkan permutasi yang menetapkan dua anggota. Terdapat \({4 \choose 2}\) pilihan untuk kedua anggota tersebut dan, untuk setiap pasangan, terdapat \(2!\) permutasi dari anggota yang tersisa. Pengurangan ini terlalu banyak, sehingga kita menambahkan kembali semua \({4 \choose 3}1!\) permutasi yang menetapkan 3 anggota. Terakhir, kurangkan \({4 \choose 4}0!\) permutasi (ingat bahwa \(0! = 1\)) yang menetapkan keempat anggota. Secara keseluruhan, banyaknya permutasi tanpa titik tetap dari 4 anggota adalah
\begin{equation*} 4! - \left[{4 \choose 1}3! - {4 \choose 2}2! + {4 \choose 3} 1! - {4 \choose 4}0!\right] = 24 - 15 = 9 \text{.} \end{equation*}
🔗
🔗
🔗
Tentu saja, kita dapat menggunakan rumus serupa untuk mencacah permutasi tanpa titik tetap dari berapa pun banyak anggota. Namun, semakin banyak anggotanya, semakin panjang rumusnya. Berikut contoh lain.
🔗

Contoh 3.8.5.

Lima pria menghadiri sebuah pesta dan menitipkan topi mereka di dekat pintu. Pada akhir pesta, mereka mengambil topi dengan tergesa-gesa ketika keluar. Dengan berapa banyak cara hal ini dapat terjadi sehingga tidak seorang pun membawa pulang topinya sendiri?
🔗
Penyelesaian.
Kita mencacah permutasi tanpa titik tetap dari 5 anggota. Terdapat \(5!\) cara kelima pria mengambil topi dalam sembarang urutan—tetapi dalam banyak permutasi tersebut seseorang akan memperoleh topinya sendiri. Jadi, kita mengurangkan semua cara ketika satu atau lebih pria memperoleh topi sendiri. Dengan kata lain, kita mengurangkan permutasi yang memiliki titik tetap. Hal ini memerlukan prinsip inklusi–eksklusi. Jadi, jawabannya adalah
\begin{equation*} 5! - \left[{5 \choose 1}4! - {5 \choose 2}3! + {5 \choose 3}2! - {5 \choose 4}1! + {5 \choose 5}0!\right] \text{.} \end{equation*}
🔗
🔗
🔗
🔗

Subbagian Mencacah Fungsi

Selidiki!
  1. Perhatikan semua fungsi \(f: \{1,2,3,4,5\} \to \{1,2,3,4,5\}\text{.}\) Berapa banyak fungsi seluruhnya? Berapa banyak di antaranya yang injektif? Ingat, suatu fungsi merupakan injeksi jika setiap masukan dipetakan ke keluaran yang berbeda.
    🔗
    🔗
  2. Perhatikan semua fungsi \(f: \{1,2,3,4,5\} \to \{1,2,3,4,5\}\text{.}\) Berapa banyak injeksi yang memenuhi \(f(x) \ne x\) untuk setiap \(x \in \{1,2,3,4,5\}\text{?}\)
    🔗
    Teman Anda menyatakan bahwa jawabannya adalah
    \begin{equation*} 5! - \left[ {5\choose 1}4! - {5 \choose 2}3! + {5\choose 3}2! - {5 \choose 4}1! + {5\choose 5}0! \right] \text{.} \end{equation*}
    🔗
    Jelaskan mengapa jawaban ini benar.
    🔗
    🔗
  3. Ingat bahwa surjeksi adalah fungsi yang setiap anggota kodomainnya berada dalam daerah hasil. Berapa banyak fungsi \(f: \{1,2,3,4,5\} \to \{1,2,3,4,5\}\) yang surjektif? Gunakan prinsip inklusi–eksklusi!
    🔗
    🔗
🔗
🔗
Di seluruh bab ini, kita telah melihat bahwa banyak pertanyaan pencacahan dapat dirumuskan kembali sebagai pertanyaan tentang pencacahan fungsi dengan sifat tertentu. Hal ini masuk akal karena banyak pertanyaan pencacahan dapat dipandang sebagai pencacahan banyaknya cara memasangkan anggota suatu himpunan dengan anggota himpunan lain.
🔗

Contoh 3.8.6.

Anda memutuskan untuk memberikan koleksi gim video Anda agar dapat menggunakan waktu dengan lebih baik untuk mempelajari matematika lanjut. Dengan berapa banyak cara hal ini dapat dilakukan jika:
  1. Anda ingin membagikan 3 gim PS4 yang berbeda kepada 5 teman sehingga tidak ada teman yang menerima lebih dari satu gim?
    🔗
  2. Anda ingin membagikan 8 gim 3DS yang berbeda kepada 5 teman?
    🔗
  3. Anda ingin membagikan 8 gim SNES yang berbeda kepada 5 teman sehingga setiap teman menerima sedikitnya satu gim?
    🔗
Dalam setiap kasus, modelkan pertanyaan pencacahan sebagai pertanyaan pencacahan fungsi.
🔗
Penyelesaian.
  1. Kita harus menggunakan ketiga gim (sebut saja 1, 2, 3) sebagai domain dan kelima teman (a,b,c,d,e) sebagai kodomain; jika perannya dibalik, fungsi tidak akan terdefinisi pada seluruh domain ketika seorang teman tidak menerima gim. Jadi, berapa banyak fungsi berdomain \(\{1,2,3\}\) dan berkodomain \(\{a,b,c,d,e\}\text{?}\) Jawabannya \(5^3=125\text{,}\) karena salah satu dari 5 anggota dapat menjadi citra 1, salah satu dari 5 anggota dapat menjadi citra 2, dan salah satu dari 5 anggota dapat menjadi citra 3.
    🔗
    Namun, ini bukan jawaban yang tepat bagi masalah pencacahan kita, karena salah satu fungsi tersebut adalah \(f= \twoline{1\amp 2\amp 3}{a\amp a\amp a}\text{;}\) satu teman dapat menerima lebih dari satu gim. Yang sebenarnya perlu kita cacah ialah fungsi injektif. Hal ini menghasilkan \(P(5,3) = 60\) fungsi, yang merupakan jawaban bagi pertanyaan pencacahan kita.
    🔗
    🔗
  2. Sekali lagi, kita harus menggunakan 8 gim sebagai domain dan 5 teman sebagai kodomain. Kita mencacah semua fungsi, sehingga banyaknya cara membagikan gim adalah \(5^8\text{.}\)
    🔗
    🔗
  3. Pertanyaan ini lebih sulit. Gunakan gim sebagai domain dan teman sebagai kodomain; pembalikan peran keduanya tidak menghasilkan fungsi. Syarat bahwa setiap teman menerima sedikitnya satu gim berarti bahwa setiap anggota kodomain berada dalam daerah hasil. Dengan kata lain, kita mencari fungsi surjektif. Bagaimana cara mencacahnya?
    🔗
    🔗
🔗
🔗
🔗
Dalam Contoh 3.2.13, kita melihat cara mencacah semua fungsi (menggunakan prinsip perkalian), dan dalam Contoh 3.4.7, kita mempelajari cara mencacah fungsi injektif (menggunakan permutasi). Fungsi surjektif tidak semudah itu dicacah, kecuali jika banyaknya anggota domain lebih kecil daripada banyaknya anggota kodomain; dalam kasus tersebut tidak ada fungsi surjektif.
🔗
Gagasannya adalah mencacah fungsi yang tidak surjektif, lalu mengurangkan hasilnya dari seluruh fungsi. Cara ini bekerja sangat baik ketika kodomain memiliki dua anggota.
🔗

Contoh 3.8.7.

Berapa banyak fungsi \(f: \{1,2,3,4,5\} \to \{a,b\}\) yang surjektif?
🔗
Penyelesaian.
Terdapat \(2^5\) fungsi seluruhnya karena tersedia dua pilihan citra bagi masing-masing dari 5 anggota domain. Di antara fungsi-fungsi tersebut, fungsi yang tidak surjektif harus mengecualikan satu atau lebih anggota kodomain dari daerah hasil. Pertama, perhatikan fungsi yang daerah hasilnya tidak memuat \(a\text{.}\) Hal ini hanya dapat terjadi dengan satu cara: semua anggota dipetakan ke \(b\text{.}\) Sebagai alternatif, kita dapat mengecualikan \(b\) dari daerah hasil. Dalam hal itu, semua anggota dipetakan ke \(a\text{,}\) sehingga hanya ada satu fungsi semacam ini. Inilah satu-satunya cara suatu fungsi dapat tidak surjektif; tidak ada fungsi yang mengecualikan \(a\) dan \(b\) sekaligus dari daerah hasil. Jadi, tepat terdapat \(2^5 - 2\) fungsi surjektif.
🔗
🔗
🔗
Ketika kodomain memiliki tiga anggota, terdapat tiga pilihan anggota tunggal yang dapat dikecualikan dari daerah hasil. Selain itu, kita dapat memilih pasangan dua anggota untuk dikecualikan dari daerah hasil dan harus memastikan bahwa kita tidak mencacahnya terlalu banyak. Saatnya menggunakan prinsip inklusi–eksklusi!
🔗

Contoh 3.8.8.

Berapa banyak fungsi \(f: \{1,2,3,4,5\} \to \{a,b,c\}\) yang surjektif?
🔗
Penyelesaian.
Sekali lagi, mulailah dari seluruh fungsi, yaitu \(3^5\text{,}\) karena setiap satu dari lima anggota domain dapat dipetakan ke salah satu dari tiga anggota kodomain. Sekarang kita mencacah fungsi yang tidak surjektif.
🔗
Mulailah dengan mengecualikan \(a\) dari daerah hasil. Kemudian tersedia dua pilihan, \(b\) atau \(c\text{,}\) sebagai citra setiap satu dari lima anggota domain. Jadi, terdapat \(2^5\) fungsi yang mengecualikan \(a\) dari daerah hasil. Demikian pula, terdapat \(2^5\) fungsi yang mengecualikan \(b\) dan \(2^5\) fungsi lain yang mengecualikan \(c\text{.}\) Apakah kita sekarang telah mencacah semua fungsi yang tidak surjektif? Ya, tetapi sebenarnya beberapa di antaranya telah dicacah berkali-kali. Sebagai contoh, fungsi yang memetakan semuanya ke \(c\) termasuk salah satu dari \(2^5\) fungsi yang kita cacah ketika mengecualikan \(a\text{,}\) sekaligus salah satu dari \(2^5\) fungsi yang kita cacah ketika mengecualikan \(b\text{.}\) Kita harus mengurangkan semua fungsi yang secara khusus mengecualikan dua anggota dari daerah hasil. Terdapat 1 fungsi ketika kita mengecualikan \(a\) dan \(b\) (semuanya dipetakan ke \(c\)), satu fungsi ketika kita mengecualikan \(a\) dan \(c\text{,}\) serta satu fungsi ketika kita mengecualikan \(b\) dan \(c\text{.}\)
🔗
Kita sedang menggunakan prinsip inklusi–eksklusi. Untuk mencacah fungsi yang tidak surjektif, kita menjumlahkan secara terpisah fungsi yang mengecualikan \(a\text{,}\) \(b\text{,}\) dan \(c\text{,}\) lalu mengurangkan fungsi yang mengecualikan pasangan anggota. Berikutnya, kita seharusnya menambahkan kembali fungsi yang mengecualikan kelompok tiga anggota, tetapi tidak ada fungsi semacam itu. Jadi, banyaknya fungsi yang tidak surjektif adalah
\begin{equation*} 2^5 + 2^5 + 2^5 - 1 - 1 - 1 + 0 \text{.} \end{equation*}
🔗
Cara yang mungkin lebih deskriptif untuk menuliskannya adalah
\begin{equation*} {3 \choose 1}2^5 - {3 \choose 2}1^5 + {3 \choose 3}0^5 \text{,} \end{equation*}
karena setiap suku \(2^5\) diperoleh dengan memilih 1 dari 3 anggota kodomain untuk dikecualikan dari daerah hasil, sedangkan setiap satu dari tiga suku \(1^5\) diperoleh dengan memilih 2 dari 3 anggota kodomain untuk dikecualikan. Menulis \(1^5\) alih-alih 1 juga masuk akal: kita mempunyai 1 pilihan citra bagi setiap satu dari 5 anggota domain.
🔗
Sekarang kita akhirnya dapat mencacah banyaknya fungsi surjektif:
\begin{equation*} 3^5 - \left[{3 \choose 1}2^5 - {3 \choose 2}1^5\right] = 150 \text{.} \end{equation*}
🔗
🔗
🔗
Anda mungkin khawatir bahwa mencacah fungsi surjektif ketika kodomain memiliki lebih dari 3 anggota akan terlalu melelahkan. Kita perlu menggunakan prinsip inklusi–eksklusi, tetapi untuk lebih dari 3 himpunan rumusnya sangat panjang. Untungnya, kita mendapat kemudahan. Seperti yang terlihat dalam contoh di atas, banyaknya fungsi yang mengecualikan satu anggota dari daerah hasil selalu sama, apa pun anggota tunggal yang dikecualikan. Demikian pula, banyaknya fungsi yang mengecualikan sepasang anggota sama untuk setiap pasangan. Untuk kodomain yang lebih besar, pola yang sama muncul ketika kelompok 3, 4, atau lebih anggota dikecualikan. Jadi, alih-alih menambah atau mengurangkan setiap kelompok satu per satu, kita dapat menambah atau mengurangkan semuanya sekaligus asalkan mengetahui banyaknya kelompok. Cara ini bekerja seperti pada jenis pertanyaan pencacahan lain dalam bagian ini, hanya saja sekarang ukuran berbagai kombinasi himpunan berupa bilangan berpangkat, bukan koefisien binomial atau faktorial. Berikut yang terjadi ketika kodomain memiliki \(4\) dan \(5\) anggota.
🔗

Contoh 3.8.9.

  1. Berapa banyak fungsi \(f: \{1,2,3,4,5\} \to \{a,b,c,d\}\) yang surjektif?
    🔗
    🔗
  2. Berapa banyak fungsi \(f: \{1,2,3,4,5\} \to \{a,b,c,d,e\}\) yang surjektif?
    🔗
    🔗
🔗
Penyelesaian.
  1. Terdapat \(4^5\) fungsi seluruhnya; kita akan mengurangkan fungsi yang tidak surjektif. Kita dapat mengecualikan salah satu dari empat anggota kodomain, dan untuk setiap anggota yang dikecualikan tersisa \(3^5\) fungsi. Hal ini mencacah terlalu banyak, sehingga kita mengurangkan fungsi yang mengecualikan dua dari empat anggota kodomain; setiap pasangan menghasilkan \(2^5\) fungsi. Namun, pengurangan ini terlalu banyak, sehingga kita menambahkan kembali fungsi yang mengecualikan tiga dari empat anggota kodomain; setiap rangkap tiga menghasilkan \(1^5\) fungsi. Terdapat \({4 \choose 1}\) kelompok fungsi yang mengecualikan satu anggota, \({4 \choose 2}\) kelompok fungsi yang mengecualikan sepasang anggota, dan \({4 \choose 3}\) kelompok fungsi yang mengecualikan tiga anggota. Jadi, banyaknya fungsi yang tidak surjektif adalah
    \begin{equation*} {4 \choose 1}3^5 - {4 \choose 2}2^5 + {4 \choose 3}1^5 \text{.} \end{equation*}
    Dengan demikian, banyaknya fungsi yang surjektif adalah
    \begin{equation*} 4^5 - \left[{4 \choose 1}3^5 - {4 \choose 2}2^5 + {4 \choose 3}1^5\right] \text{.} \end{equation*}
    🔗
    🔗
  2. Banyaknya fungsi surjektif adalah
    \begin{equation*} 5^5 - \left[{5 \choose 1}4^5 - {5 \choose 2}3^5 + {5 \choose 3}2^5 - {5 \choose 4}1^5\right] \text{.} \end{equation*}
    Kita mengambil seluruh \(5^5\) fungsi lalu mengurangkan semua yang tidak surjektif. Terdapat \({5 \choose 1}\) cara memilih satu anggota kodomain untuk dikecualikan dari daerah hasil, dan untuk setiap pilihan terdapat \(4^5\) fungsi. Namun, hal ini mencacah ganda, sehingga dengan prinsip inklusi–eksklusi kita mengurangkan fungsi yang mengecualikan dua anggota dari daerah hasil: terdapat \({5 \choose 2}\) pilihan bagi kedua anggota yang dikecualikan dan, untuk setiap pasangan, terdapat \(3^5\) fungsi. Pengurangan ini menghapus terlalu banyak fungsi, sehingga kita menambahkan kembali fungsi yang mengecualikan 3 anggota dari daerah hasil: terdapat \({5 \choose 3}\) pilihan tiga anggota yang dikecualikan dan \(2^5\) fungsi untuk setiap pilihan. Terakhir, untuk setiap satu dari \({5 \choose 4}\) pilihan 4 anggota, kita mengurangkan kembali 1 fungsi yang mengecualikan keempat anggota tersebut.
    🔗
    Jika Anda menghitung bilangan ini secara tepat, hasilnya 120 surjeksi. Kebetulan, bilangan ini juga sama dengan \(5!\text{.}\) Hal tersebut mungkin tampak sebagai kebetulan yang luar biasa sampai kita menyadari bahwa setiap fungsi surjektif \(f:X \to Y\) dengan nilai \(\card{X} = \card{Y}\) yang berhingga harus merupakan bijeksi. Dalam kasus ini, banyaknya bijeksi selalu \(\card{X}!\text{.}\) Jadi, kita memperoleh pembuktian kombinatorial bagi identitas berikut:
    \begin{equation*} n^n - \left[{n\choose 1}(n-1)^n - {n \choose 2}(n-2)^n + \cdots + {n \choose n-1}1^n \right] = n! \text{.} \end{equation*}
    🔗
    🔗
🔗
🔗
🔗
Kita telah melihat bahwa pencacahan fungsi surjektif merupakan contoh lain yang baik bagi penggunaan lanjut prinsip inklusi–eksklusi. Selain itu, pencacahan fungsi injektif ternyata ekuivalen dengan pencacahan permutasi, sedangkan pencacahan semua fungsi memiliki penyelesaian yang serupa dengan masalah pencacahan ketika urutan penting tetapi pengulangan diperbolehkan, seperti mencacah banyaknya kata yang dapat dibentuk dari suatu himpunan huruf.
🔗
Ini bukan sekadar beberapa contoh tambahan dari teknik yang telah kita kembangkan dalam bab ini. Justru sebaliknya: semua yang telah kita pelajari dalam bab ini merupakan contoh pencacahan fungsi!
🔗

Contoh 3.8.10.

Berapa banyak kata sepanjang 5 huruf yang dapat Anda bentuk menggunakan delapan huruf \(a\) sampai \(h\text{?}\) Berapa banyak yang tidak memuat huruf berulang?
🔗
Penyelesaian.
Sekarang seharusnya tidak mengejutkan bahwa terdapat \(8^5\) kata dan \(P(8,5)\) kata tanpa huruf berulang. Hal baru di sini adalah bahwa sebenarnya kita sedang mencacah fungsi. Untuk masalah pertama, kita mencacah semua fungsi dari \(\{1,2,\ldots, 5\}\) ke \(\{a,b,\ldots, h\}\text{.}\) Bilangan dalam domain menyatakan posisi huruf dalam kata, sedangkan kodomain memuat huruf yang dapat ditempatkan pada posisi tersebut. Jika kita mensyaratkan tidak ada huruf berulang, kita mencari fungsi injektif.
🔗
Jika \(A\) dan \(B\) adalah sembarang himpunan dengan \(|A| = 5\) dan \(|B| = 8\text{,}\) banyaknya fungsi \(f: A \to B\) adalah \(8^5\) dan banyaknya injeksi adalah \(P(8,5)\text{.}\) Jadi, jika Anda dapat merepresentasikan masalah pencacahan sebagai masalah pencacahan fungsi, sebagian besar pekerjaan telah selesai.
🔗
🔗
🔗

Contoh 3.8.11.

Berapa banyak himpunan bagian dari \(\{1,2,\ldots, 9\}\text{?}\) Berapa banyak string 9-bit (dengan sembarang bobot)?
🔗
Penyelesaian.
Dalam Subbab 3.1, kita melihat bahwa jawaban bagi kedua pertanyaan ini adalah \(2^9\text{,}\) karena kita dapat menjawab ya atau tidak (atau 0 atau 1) untuk setiap satu dari 9 anggota himpunan (posisi dalam string bit). Namun, \(2^9\) juga tampak seperti jawaban yang diperoleh dari pencacahan fungsi. Memang, jika kita mencacah semua fungsi \(f: A \to B\) dengan \(|A| = 9\) dan \(|B| = 2\text{,}\) tepat inilah hasilnya.
🔗
Hal ini masuk akal! Misalkan \(A = \{1,2,\ldots, 9\}\) dan \(B = \{y, t\}\text{.}\) Kita memberi setiap anggota himpunan salah satu jawaban, ya atau tidak. Dalam bahasa string bit, kita menggunakan 9 posisi dalam string bit sebagai domain dan himpunan \(\{0,1\}\) sebagai kodomain.
🔗
🔗
🔗
Sejauh ini, kita belum menggunakan fungsi sebagai model bagi koefisien binomial (kombinasi). Pikirkan sejenak hubungan antara kombinasi dan permutasi, khususnya antara \({9 \choose 3}\) dan \(P(9,3)\text{.}\) Kita memiliki model fungsi bagi \(P(9,3)\text{.}\) Bilangan ini mencacah fungsi injektif dari himpunan beranggota 3, misalnya \(\{1,2,3\}\text{,}\) ke himpunan beranggota 9, misalnya \(\{1,2,\ldots, 9\}\text{.}\) Terdapat 9 pilihan citra bagi anggota pertama domain, kemudian hanya 8 pilihan bagi anggota kedua, dan 7 pilihan bagi anggota ketiga. Sebagai contoh, fungsinya mungkin berbentuk
\begin{equation*} f(1) = 5 \qquad f(2) = 8 \qquad f(3) = 4 \text{.} \end{equation*}
🔗
Fungsi ini berbeda dari
\begin{equation*} f(1) = 4 \qquad f(2) = 5 \qquad f(3) = 8 \text{.} \end{equation*}
🔗
\(P(9,3)\) dengan tepat mencacah kedua fungsi tersebut sebagai hasil yang berbeda, sedangkan \({9\choose 3}\) mencacahnya, bersama fungsi-fungsi lain, sebagai satu hasil saja. Dalam bahasa fungsi, \({9 \choose 3}\) sebenarnya hanya mencacah banyaknya daerah hasil yang mungkin bagi fungsi injektif. Hal ini tidak mengejutkan karena koefisien binomial mencacah himpunan bagian, dan daerah hasil merupakan suatu himpunan bagian yang mungkin dari kodomain.
 5 
Penafsiran kombinasi yang lebih canggih secara matematis ialah mendefinisikan dua fungsi injektif sebagai ekuivalen jika keduanya memiliki daerah hasil yang sama, lalu mencacah banyaknya kelas ekuivalensi menurut relasi ekuivalensi ini.
🔗
Meskipun kombinasi dapat ditafsirkan sebagai fungsi, saran yang lebih baik mungkin ialah menggunakan kombinasi (atau metode batang dan batu) ketika fungsi bukan cara yang tepat untuk menafsirkan pertanyaan pencacahan.
🔗
🔗

Latihan Soal Latihan

1.

Menu satu dolar di restoran cepat saji bebas pajak favorit Anda memuat 7 hidangan. Anda mempunyai $18 untuk dibelanjakan. Ada berapa kombinasi makanan berbeda yang dapat Anda beli jika Anda menghabiskan seluruh uang dan:
  1. Membeli sedikitnya satu dari setiap hidangan.
    🔗
    🔗
  2. Boleh tidak membeli beberapa hidangan.
    🔗
    🔗
  3. Tidak membeli lebih dari 2 porsi dari hidangan mana pun.
    🔗
    🔗
🔗
🔗

2.

Setelah belajar matematika hingga larut malam, Anda dan teman-teman memutuskan untuk pergi ke restoran cepat saji Meksiko bebas pajak favorit Anda, Burrito Chime. Anda memutuskan untuk memesan dari menu satu dolar yang memuat 10 hidangan. Kelompok Anda mempunyai $20 untuk dibelanjakan (dan akan menghabiskan semuanya).
  1. Ada berapa pesanan berbeda yang mungkin? (Urutan saat pesanan disampaikan tidak penting; yang penting hanya jenis dan banyaknya setiap hidangan yang dipesan.)
    🔗
    🔗
  2. Ada berapa pesanan berbeda yang mungkin jika Anda ingin membeli sedikitnya satu dari setiap hidangan?
    🔗
    🔗
  3. Ada berapa pesanan berbeda yang mungkin jika Anda tidak ingin membeli lebih dari 4 porsi dari hidangan mana pun?
    🔗
    🔗
🔗
🔗

3.

Setelah satu pelajaran olahraga lagi, Anda ditugasi menyimpan 14 bola dodgeball yang identik ke dalam 5 wadah. Kali ini, setiap wadah hanya dapat menampung paling banyak 6 bola. Dengan berapa banyak cara Anda dapat membereskannya?
🔗
🔗

4.

Perhatikan persamaan \(x_1 + x_2 + x_3 + x_4 = 18\text{.}\) Ada berapa solusi yang memenuhi \(1 \le x_i \le 6\) untuk semua \(i \in \{1,2,3,4\}\text{?}\)
🔗
🔗

5.

Misalkan Anda hendak memberikan 13 bintang emas kepada beberapa dari 15 siswa berprestasi di kelas Anda. Setiap siswa dapat menerima paling banyak satu bintang. Ada berapa cara untuk melakukannya?
  1. Gunakan segitiga Pascal untuk memperoleh jawaban numeriknya.
    🔗
    🔗
🔗
  1. Gunakan prinsip inklusi–eksklusi.
    🔗
    🔗
🔗
🔗

6.

Berapa banyak permutasi dari \({\left\{1,2,3,4,5,6\right\}}\) yang menetapkan tepat 1 anggota?
🔗
🔗

7.

Sebanyak 11 perempuan menitipkan topi merah mereka di tempat penitipan barang sebuah museum. Ketika mereka hendak pulang, petugas mengembalikan topi-topi itu secara acak. Ada berapa cara agar tepat 6 perempuan menerima topinya sendiri (sedangkan 5 lainnya tidak)?
🔗
🔗

8.

Grinch menyelinap ke sebuah ruangan yang berisi 9 hadiah Natal untuk 9 orang berbeda. Ia lalu menukar label nama pada hadiah-hadiah itu. Ada berapa cara ia dapat melakukannya jika:
  1. Tidak satu pun hadiah boleh mendapatkan kembali label aslinya? Jelaskan arti setiap suku dalam jawaban Anda.
    🔗
    🔗
  2. Tepat 4 hadiah mempertahankan label aslinya? Jelaskan.
    🔗
    🔗
  3. Tepat 8 hadiah mempertahankan label aslinya? Jelaskan.
    🔗
    🔗
🔗
🔗

9.

Perhatikan fungsi-fungsi \(f: {\left\{1,2,3,4,5,6,7,8,9\right\}} \to \{a,b,c,d,e,f\}\text{.}\) Berapa banyak fungsi yang memenuhi \(f(1) \ne c\) atau \(f(2) \ne f\text{,}\) atau keduanya?
🔗
🔗

10.

Perhatikan himpunan \(A\) dan \(B\) dengan \(|A| = 11\) dan \(|B| = 4\text{.}\) Berapa banyak fungsi surjektif \(f: A \to B\text{?}\)
🔗
🔗

11.

Misalkan \(A = {\left\{1,2,3,4,5,6,7,8\right\}}\text{.}\) Berapa banyak fungsi injektif \(f:A \to A\) yang memenuhi \(f(x) \ne x\) untuk setiap \(x \in A\text{?}\)
🔗
🔗
🔗

Latihan Latihan Tambahan

1.

Berdasarkan pertanyaan sebelumnya, berikan pembuktian kombinatorial bagi identitas berikut:
\begin{equation*} {n \choose k} = {n+k-1 \choose k} - \sum_{j=1}^n (-1)^{j+1}{n \choose j}{n+k-(2j+1) \choose k - 2j}\text{.} \end{equation*}
🔗
🔗

2.

Ilustrasikan cara mencacah permutasi tanpa titik tetap dengan menuliskan semua permutasi dari \(\{1,2,3,4\}\text{,}\) lalu coret permutasi yang memiliki titik tetap. Dengan menggunakan prinsip inklusi–eksklusi, catat permutasi yang Anda coret lebih dari sekali.
🔗
🔗

3.

Misalkan \(d_n\) adalah banyaknya permutasi tanpa titik tetap dari \(n\) objek. Sebagai contoh, dengan menggunakan teknik dalam bagian ini, kita memperoleh
\begin{equation*} d_3 = 3!-\left({3 \choose 1}2! - {3 \choose 2}1! + {3 \choose 3}0! \right)\text{.} \end{equation*}
Kita dapat menggunakan rumus \({n \choose k}\) untuk menuliskan semuanya dalam bentuk faktorial. Setelah disederhanakan, untuk \(d_3\) kita memperoleh
\begin{equation*} d_3 = 3!\left(1 - \frac{1}{1} + \frac{1}{2} - \frac{1}{6} \right)\text{.} \end{equation*}
Generalisasikan hasil ini untuk memperoleh rumus yang lebih sederhana bagi \(d_n\text{.}\) Bonus: Untuk \(n\) yang besar, kira-kira berapa proporsi di antara semua permutasi yang tidak memiliki titik tetap? Gunakan pengetahuan Anda tentang deret Taylor dari kalkulus.
🔗
🔗
🔗
🔗
SblmTopLnjt
Umpan Balik