Lewati ke konten utama
Gambar logo

Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Oscar Levin

Subbab 3.4 Kombinasi dan Permutasi

Subbagian Pratinjau Bagian

Selidiki!
Anda memutuskan untuk menghias tongkat sihir dengan pita perekat berbagai warna. Tersedia 10 warna berbeda, dan Anda akan menggunakan lima di antaranya untuk membuat lima garis warna yang berbeda. Berapa banyak desain tongkat berbeda yang mungkin?
🔗
🔗
Prinsip perkalian memberi kita cara untuk menghitung banyaknya hasil ketika setiap hasil dibentuk dengan menggabungkan bagian-bagian yang lebih kecil. Contoh umum adalah menghitung banyaknya “kata” tiga huruf; setiap hasil (kata) yang kita hitung tersusun dari gabungan tiga bagian yang lebih kecil (huruf). Karena terdapat 26 pilihan untuk setiap bagian yang lebih kecil, terdapat \(26\cdot 26\cdot 26 = 26^3\) hasil yang mungkin.
🔗
Prinsip perkalian tidak mensyaratkan bahwa setiap bagian yang digabungkan harus dipilih dari himpunan berukuran sama. Kita akan menggunakan pengamatan ini untuk membuat cara baku menghitung hasil ketika bagian-bagiannya dipilih dari suatu himpunan tetap, tetapi tanpa memperbolehkan bagian mana pun digunakan lebih dari sekali. Sebagai contoh, kita dapat menanyakan berapa banyak kata 3 huruf yang memuat huruf-huruf berbeda.
🔗
Susunan-susunan ini disebut permutasi. Kita juga akan membahas teknik pencacahan lain yang menghitung kombinasi, yang berkaitan dengan permutasi tetapi menghitung sesuatu yang berbeda. Kita akan mempelajari hubungan antara kedua teknik pencacahan tersebut dan cara menggunakannya untuk menyelesaikan beragam masalah pencacahan.
🔗

Lembar Kerja Kegiatan Pratinjau

Anda memiliki sekumpulan keping poker dalam lima warna berbeda: merah (R), biru (B), hijau (G), ungu (P), dan kuning (Y).
🔗
1.
Berapa banyak tumpukan dua keping yang mungkin jika keping paling bawah harus berwarna merah atau biru?
🔗
(a)
Daftarkan semua tumpukan dua keping yang mungkin. Sebagai contoh, tumpukan dengan keping merah di bawah dan keping hijau di atas dapat ditulis sebagai “RG”.
🔗
🔗
(b)
Dengan menggunakan prinsip penjumlahan, kita melihat bahwa terdapat tumpukan yang memiliki keping biru di bawah dan tumpukan lain yang memiliki keping merah di bawah, sehingga seluruhnya terdapat tumpukan yang mungkin.
🔗
🔗
(c)
Jika kita menggunakan prinsip perkalian, terdapat pilihan untuk keping paling bawah dan pilihan untuk keping paling atas, sehingga terdapat tumpukan yang mungkin.
🔗
🔗
🔗
2.
Berapa banyak tumpukan tiga keping berbeda yang mungkin jika keping paling bawah harus berwarna merah atau biru dan keping paling atas harus berwarna hijau, ungu, atau kuning?
🔗
Petunjuk.
Bagaimana pertanyaan ini berkaitan dengan pertanyaan sebelumnya? Adakah sesuatu yang dapat kita lakukan pada 10 tumpukan dua keping untuk mengubahnya menjadi tumpukan tiga keping?
🔗
🔗
🔗
3.
Berapa banyak tumpukan tiga keping berbeda yang tidak mengulang warna apa pun?
🔗
(a)
Pertama, berapa banyak tumpukan tiga keping tanpa warna berulang yang memiliki keping biru di bawah dan keping hijau di tengah?
🔗
Lalu, berapa banyak tumpukan tiga keping tanpa warna berulang yang memiliki keping biru di bawah dan keping kuning di tengah?
🔗
Bahkan, untuk sembarang tumpukan dengan keping biru di bawah dan suatu warna lain di tengah, terdapat tumpukan yang mungkin.
🔗
🔗
(b)
Jika kita mensyaratkan keping biru berada di bawah, berapa banyak pilihan warna untuk keping tengah?
🔗
Dengan menggabungkan hasil ini dengan jawaban pertanyaan sebelumnya, berapa banyak tumpukan tiga keping tanpa warna berulang yang memiliki keping biru di bawah?
🔗
🔗
(c)
Tentu saja, kita tidak harus memulai dengan keping biru di bawah. Berapa banyak pilihan warna untuk keping paling bawah?
🔗
Jadi, berapa banyak tumpukan tiga keping tanpa warna berulang yang ada?
🔗
🔗
(d)
Berapa banyak tumpukan empat keping tanpa warna berulang yang ada?
🔗
🔗
🔗
4.
Misalkan Anda ingin mengambil tiga keping dengan warna berbeda dan memasukkannya ke dalam saku.
🔗
(a)
Salah satu hasilnya adalah mengambil keping biru, hijau, dan ungu. Berapa banyak tumpukan tiga keping berwarna berbeda yang bersesuaian dengan satu isi saku ini?
🔗
Petunjuk.
Dengan ketiga warna ini, berapa banyak pilihan untuk keping yang berada di bawah? Di tengah? Di atas?
🔗
🔗
🔗
(b)
Berapa banyak tumpukan keping berbeda yang dapat terbentuk dengan mengambil keping merah, kuning, dan hijau?
🔗
🔗
(c)
Jadi, dari tumpukan tiga keping yang mungkin, kita dapat mengelompokkannya ke dalam kelompok berukuran , dengan setiap kelompok bersesuaian dengan isi saku yang sama. Berapa banyak isi saku berbeda yang ada?
🔗
🔗
(d)
Berapa banyak isi saku berbeda yang ada jika Anda mengambil empat keping?
🔗
🔗
🔗
🔗
🔗

Subbagian Mencacah Barisan

Suatu permutasi adalah salah satu susunan ulang yang mungkin dari sejumlah objek. Sebagai contoh, terdapat 6 permutasi huruf a, b, c:
\begin{equation*} abc, ~~ acb, ~~ bac, ~~bca, ~~ cab, ~~ cba\text{.} \end{equation*}
Dalam konteks struktur diskret kita, setiap permutasi sebenarnya merupakan barisan atau tupel dengan panjang tetap.
🔗
Kita mengetahui bahwa semua permutasi telah didaftarkan di atas —terdapat 3 pilihan huruf yang ditempatkan pertama, lalu 2 pilihan untuk huruf berikutnya, sehingga tersisa hanya 1 pilihan untuk huruf terakhir. Prinsip perkalian menyatakan bahwa kita mengalikan \(3\cdot 2 \cdot 1\text{.}\)
🔗

Contoh 3.4.1.

Berapa banyak barisan (permutasi) yang dapat dibentuk dari huruf a, b, c, d, e, f?
🔗
Penyelesaian.
Kita TIDAK ingin mencoba mendaftarkan semua barisan panjang 6 dari huruf-huruf tersebut. Namun, jika kita melakukannya, mula-mula kita perlu memilih huruf yang akan ditulis pertama. Terdapat 6 pilihan untuk huruf tersebut. Untuk setiap pilihan huruf pertama, terdapat 5 pilihan untuk huruf kedua (kita tidak dapat mengulang huruf pertama; kita sedang menyusun ulang huruf dan hanya memiliki satu dari setiap huruf), dan untuk setiap pilihan itu terdapat 4 pilihan untuk huruf ketiga, 3 pilihan untuk huruf keempat, 2 pilihan untuk huruf kelima, dan akhirnya hanya 1 pilihan untuk huruf terakhir. Jadi, terdapat \(6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720\) permutasi dari 6 huruf tersebut.
🔗
🔗
🔗
Sebuah notasi berguna di sini: \(n!\text{,}\) dibaca “\(n\) faktorial”, adalah hasil kali semua bilangan bulat positif yang kurang dari atau sama dengan \(n\) (demi kemudahan, kita juga mendefinisikan 0! sebagai 1). Jadi, banyaknya permutasi 6 huruf, seperti yang terlihat dalam contoh sebelumnya, adalah \(6! = 6\cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1\text{.}\) Hal ini dapat diperumum:
🔗

Contoh 3.4.3. Mencacah Fungsi Bijektif.

Berapa banyak fungsi \(f:\{1,2,\ldots,8\} \to \{1,2,\ldots, 8\}\) yang bijektif?
🔗
Penyelesaian.
Ingat kembali arti fungsi bijektif: Setiap elemen dalam kodomain harus menjadi citra dari tepat satu elemen domain. Dengan menggunakan notasi dua baris, kita dapat menuliskan salah satu bijeksi ini sebagai
\begin{equation*} f = \twoline{1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \amp 7 \amp 8} {3 \amp 1 \amp 5 \amp 8 \amp 7 \amp 6 \amp 2 \amp 4}\text{.} \end{equation*}
Yang sebenarnya kita lakukan hanyalah menyusun ulang elemen-elemen kodomain, sehingga kita membentuk suatu permutasi 8 elemen. Bahkan, “permutasi” merupakan istilah lain yang digunakan untuk menyebut fungsi bijektif dari suatu himpunan hingga ke dirinya sendiri.
🔗
Jika Anda menerima penalaran ini, maka Anda melihat bahwa jawabannya haruslah \(8! = 8 \cdot 7 \cdot\cdots\cdot 1 = 40320\text{.}\) Kita juga dapat melihatnya secara langsung: untuk setiap elemen domain, kita harus memilih elemen kodomain yang berbeda sebagai petanya. Terdapat 8 pilihan untuk memetakan 1, lalu 7 pilihan untuk memetakan 2, dan seterusnya. Kita mengalikannya dengan menggunakan prinsip perkalian.
🔗
🔗
🔗
Kadang-kadang kita tidak ingin mempermutasikan semua huruf/bilangan/elemen yang diberikan.
🔗

Contoh 3.4.4.

Berapa banyak “kata” empat huruf yang dapat Anda bentuk dari huruf a sampai g, tanpa huruf berulang?
🔗
Penyelesaian.
Masalah ini serupa dengan mempermutasikan empat huruf, hanya saja sekarang kita memiliki lebih banyak pilihan untuk setiap huruf. Untuk huruf pertama, terdapat 7 pilihan. Untuk setiap pilihan itu, terdapat 6 pilihan untuk huruf kedua. Kemudian terdapat 5 pilihan untuk huruf ketiga dan 4 pilihan untuk huruf terakhir. Jumlah seluruh kata adalah \(7\cdot 6\cdot 5 \cdot 4 = 840\text{.}\)
🔗
Nilai ini bukan \(7!\) karena kita tidak pernah mengalikan dengan 3, 2, atau 1. Meskipun demikian, kita dapat menuliskannya menggunakan \(7!\) jika kita mencoret 3, 2, dan 1. Jadi, kita dapat menuliskan jawabannya sebagai
\begin{equation*} \frac{7!}{3!} = \frac{7\cdot 6\cdot 5\cdot 4 \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}}{\cancel{3} \cdot \cancel{2} \cdot \cancel{1}} = 7 \cdot 6 \cdot 5 \cdot 4\text{.} \end{equation*}
🔗
🔗
🔗
Secara umum, kita dapat menanyakan berapa banyak permutasi dari \(k\) objek yang dipilih dari kumpulan lebih besar berisi \(n\) objek. (Dalam contoh di atas, \(k = 4\text{,}\) dan \(n = 7\text{.}\)) Bilangan ini kita tulis \(P(n,k)\) dan kadang-kadang kita sebut sebagai permutasi-\(k\) dari \(n\) elemen.
🔗
Dari contoh di atas, kita melihat bahwa untuk menghitung \(P(n,k)\text{,}\) kita harus menerapkan prinsip perkalian pada \(k\) bilangan, dimulai dari \(n\) lalu menghitung mundur. Sebagai contoh,
\begin{equation*} P(10, 4) = 10\cdot 9 \cdot 8 \cdot 7\text{.} \end{equation*}
🔗
Perhatikan bahwa \(P(10,4)\) pada awalnya tampak seperti \(10!\text{,}\) tetapi kita berhenti setelah 7. Secara formal, kita dapat menjelaskan “penghentian” ini dengan membagi bagian faktorial yang tidak kita inginkan:
\begin{equation*} P(10,4) = \frac{10\cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = \frac{10!}{6!}\text{.} \end{equation*}
🔗
Hati-hati: Faktorial dalam penyebut bukan \(4!\text{,}\) melainkan \((10-4)!\text{.}\)
🔗

Definisi 3.4.5. Permutasi-\(k\) dari \(n\) Elemen.

\(P(n,k)\) adalah banyaknya permutasi-\(k\) dari \(n\) elemen, yaitu banyaknya cara untuk menyusun \(k\) objek yang dipilih dari \(n\) objek berbeda.
🔗
🔗
Perhatikan bahwa ketika \(n = k\text{,}\) kita memperoleh \(P(n,n) = \frac{n!}{(n-n)!} = n!\) (karena kita mendefinisikan \(0!\) sebagai 1). Hal ini masuk akal —kita telah mengetahui bahwa \(n!\) menyatakan banyaknya permutasi dari seluruh \(n\) objek.
🔗

Contoh 3.4.7. Mencacah Fungsi Injektif.

Berapa banyak fungsi \(f:\{1,2,3\} \to \{1,2,3,4,5,6,7,8\}\) yang injektif?
🔗
Penyelesaian.
Perhatikan bahwa tidak masuk akal untuk menanyakan banyaknya bijeksi di sini, karena memang tidak ada (karena kodomain lebih besar daripada domain, tidak ada surjeksi). Namun, agar suatu fungsi bersifat injektif, kita hanya tidak boleh menggunakan suatu elemen kodomain lebih dari sekali.
🔗
Kita perlu memilih suatu elemen dari kodomain sebagai citra 1. Terdapat 8 pilihan. Kemudian, kita perlu memilih salah satu dari 7 elemen yang tersisa sebagai citra 2. Akhirnya, salah satu dari 6 elemen yang tersisa harus menjadi citra 3. Jadi, jumlah seluruh fungsi adalah \(8\cdot 7 \cdot 6 = P(8,3)\text{.}\)
🔗
Secara umum, hal ini menunjukkan bahwa banyaknya injeksi \(f:A \to B\text{,}\) dengan \(\card{A} = k\) dan \(\card{B} = n\text{,}\) adalah \(P(n,k)\text{.}\)
🔗
🔗
🔗
🔗

Subbagian Mencacah Himpunan

Mari kita pertimbangkan cara lain untuk mencacah barisan: pertama cacah himpunannya, lalu susun elemen-elemennya.
🔗

Contoh 3.4.8.

Tim bola basket Anda memiliki 12 pemain. Dengan menganggap setiap pemain dapat bermain di setiap posisi, ada berapa cara untuk memilih 5 pemain yang berada di lapangan pada saat yang sama?
🔗
Penyelesaian.
Pertanyaan ini sebenarnya terlalu samar. Apakah yang dimaksud adalah banyaknya cara memilih lima pemain? Ataukah banyaknya cara memilih lima pemain untuk mengisi lima posisi?
 2 
Konon, kelima posisi itu disebut pengatur serangan, bek penembak, penyerang kecil, penyerang kuat, dan pemain tengah. Siapa sangka?
Mari kita jawab kedua pertanyaan tersebut.
🔗
Pertama, jika kita hanya ingin memilih lima dari 12 pemain, hal itu sama seperti memilih lima dari 12 taburan piza (meskipun kurang lezat). Kita mengetahui bahwa terdapat \(\binom{12}{5}\) cara untuk melakukannya, dan dari segitiga Pascal kita mengetahui bahwa nilainya 792.
🔗
Di sisi lain, jika kita ingin memilih lima pemain untuk lima posisi berbeda,... kita dapat memulai dengan memilih salah satu dari 792 himpunan berbeda yang masing-masing terdiri atas lima pemain, lalu mempermutasikan mereka ke dalam lima posisi. Dari lima pemain di lapangan, kita memilih satu sebagai pengatur serangan, lalu satu dari empat pemain yang tersisa sebagai bek penembak, dan seterusnya. Ini memberi kita \(5\cdot 4\cdot 3\cdot 2\cdot 1 = 5!\) cara untuk menyusun para pemain. Jadi, jumlah seluruh cara memilih lima pemain untuk lima posisi adalah
\begin{equation*} \binom{12}{5}\cdot 5! = 792\cdot 120 = 95,040\text{.} \end{equation*}
🔗
Tunggu. Kita sebenarnya dapat memperoleh bilangan tersebut secara langsung. Tanpa memilih kelima pemain terlebih dahulu, kita memiliki 12 pilihan untuk pengatur serangan, lalu 11 pilihan untuk bek penembak, dan seterusnya. Jadi, jumlah seluruh cara memilih lima pemain untuk lima posisi hanyalah permutasi
\begin{equation*} P(12,5) = 12\cdot 11\cdot 10\cdot 9\cdot 8 = 95,040\text{.} \end{equation*}
Syukurlah jawabannya sama!
🔗
🔗
🔗
Contoh di atas menggambarkan cara kedua untuk menghitung banyaknya permutasi-\(k\) dari \(n\) elemen: pertama pilih \(k\) elemen yang akan berada dalam permutasi, lalu hitung banyaknya cara menyusunnya. Setelah memilih himpunan yang terdiri atas \(k\) objek, kita mengetahui bahwa terdapat \(k!\) cara untuk menyusun (mempermutasikan) objek-objek tersebut. Namun, bagaimana cara memilih \(k\) objek dari \(n\) objek? Anda memiliki \(n\) objek dan perlu memilih \(k\) di antaranya. Anda dapat melakukannya dengan \(\binom{n}{k}\) cara.
🔗
Dengan menggunakan prinsip perkalian untuk menggabungkan kedua langkah tersebut, kita memperoleh rumus lain untuk \(P(n,k)\text{:}\)
\begin{equation*} P(n,k) = \binom{n }{ k}\cdot k!\text{.} \end{equation*}
🔗
Ini hasil yang SANGAT PENTING!
🔗
Kita sudah memiliki rumus tertutup untuk \(P(n,k)\text{.}\) Kita dapat menyubstitusikannya:
\begin{equation*} \frac{n!}{(n-k)!} = \binom{n}{k} \cdot k!\text{.} \end{equation*}
🔗
Jika kemudian kita membagi kedua ruas dengan \(k!\text{,}\) kita memperoleh rumus tertutup untuk \(\binom{n}{k}\text{.}\)
🔗
Nama lain untuk kumpulan objek yang dicacah oleh \(\binom{n}{k}\) adalah kombinasi. Kita mengatakan bahwa \(\binom{n}{k}\) menghitung banyaknya kombinasi \(k\) elemen dari \(n\) elemen. Kadang-kadang kita bahkan menggunakan notasi \(C(n,k)\) sebagai pengganti \(\binom{n}{k}\text{.}\)
🔗
Jelas bahwa kombinasi dan permutasi berkaitan sangat erat. Rumus untuk menghitung keduanya sangat mirip; hanya terdapat faktor tambahan \(k!\) dalam penyebut \(\binom{n}{k}\text{.}\) Faktor tambahan \(k!\) ini memperhitungkan fakta bahwa \(\binom{n}{k}\) tidak membedakan berbagai urutan kemunculan \(k\) objek tersebut. Kita hanya memilih \(k\) objek, bukan menyusunnya.
🔗

Contoh 3.4.10.

Anda memutuskan untuk mengadakan jamuan makan malam. Meskipun Anda sangat populer dan memiliki 14 teman berbeda, kursi yang tersedia hanya cukup untuk mengundang 6 di antaranya.
🔗
  1. Berapa banyak pilihan untuk menentukan 6 teman yang akan diundang?
    🔗
    🔗
  2. Bagaimana jika Anda tidak hanya perlu menentukan teman-teman yang akan diundang, tetapi juga tempat duduk mereka di sepanjang meja panjang? Berapa banyak pilihan yang Anda miliki sekarang?
    🔗
    🔗
🔗
Penyelesaian.
  1. Anda cukup memilih 6 teman dari kelompok berisi 14 orang. Ini dapat dilakukan dengan \(\binom{14}{6}\) cara. Kita dapat memperoleh bilangan ini menggunakan segitiga Pascal atau rumus tertutup: \(\frac{14!}{8!\cdot 6!} = 3003\text{.}\)
    🔗
    🔗
  2. Di sini Anda harus menghitung semua cara mempermutasikan 6 teman yang dipilih dari kelompok berisi 14 orang. Jadi, jawabannya adalah \(P(14, 6)\text{,}\) yang dapat dihitung sebagai \(\frac{14!}{8!} = 2162160\text{.}\)
    🔗
    Perhatikan bahwa kita dapat memandang masalah pencacahan ini sebagai pertanyaan tentang pencacahan fungsi: Berapa banyak fungsi injektif dari himpunan 6 kursi ke himpunan 14 teman Anda (fungsi-fungsi tersebut injektif karena satu kursi tidak dapat diberikan kepada dua teman sekaligus).
    🔗
    🔗
🔗
Bagaimana hubungan antara bilangan-bilangan ini? Perhatikan bahwa \(P(14,6)\) jauh lebih besar daripada \(\binom{14}{6}\text{.}\) Hal ini masuk akal. \(\binom{14}{6}\) memilih 6 teman, sedangkan \(P(14,6)\) memilih sekaligus menyusun keenam teman tersebut. Bahkan, kita dapat mengatakan secara tepat seberapa besar \(P(14,6)\) dibandingkan dengan banyaknya kombinasi. Dalam kedua masalah pencacahan, kita memilih 6 dari 14 teman. Untuk masalah pertama, kita berhenti di sana, pada 3003 cara. Namun, untuk masalah pencacahan kedua, masing-masing dari 3003 pilihan 6 teman dapat disusun dengan tepat \(6!\) cara. Jadi, sekarang kita memiliki \(3003\cdot 6!\) pilihan, dan nilainya tepat \(2162160\text{.}\)
🔗
Sebagai alternatif, pandanglah masalah pertama dengan cara lain. Kita ingin memilih 6 dari 14 teman, tetapi kita tidak memedulikan urutan pemilihannya. Untuk memilih 6 dari 14 teman, kita mungkin mencoba perhitungan berikut:
\begin{equation*} 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \text{.} \end{equation*}
🔗
Dugaan ini wajar, karena kita memiliki 14 pilihan untuk tamu pertama, lalu 13 untuk tamu kedua, dan seterusnya. Namun, dugaan ini salah (sebenarnya, hasil kali tersebut tepat sama dengan \(2162160 = P(14,6)\)). Perhitungan itu membedakan urutan-urutan berbeda dalam mengundang para tamu. Untuk memperbaikinya, kita dapat membagi dengan banyaknya susunan berbeda dari 6 tamu (sehingga semua susunan ini dihitung sebagai satu hasil saja). Terdapat tepat \(6!\) cara untuk menyusun 6 tamu, sehingga jawaban yang benar untuk pertanyaan pertama adalah
\begin{equation*} \frac{14 \cdot 13 \cdot 12 \cdot 11\cdot 10 \cdot 9}{6!} \text{.} \end{equation*}
🔗
Perhatikan bahwa cara lain untuk menuliskannya adalah
\begin{equation*} \frac{14!}{8!\cdot 6!}\text{.} \end{equation*}
yang sama dengan hasil awal kita.
🔗
🔗
🔗
Mungkin istilah “kombinasi” dapat menyesatkan. Yang kita maksud bukan seperti kombinasi pada kunci kombinasi (yang jelas sangat bergantung pada urutan). Perumpamaan yang lebih baik mungkin adalah kombinasi rasa — Anda hanya perlu menentukan rasa mana yang akan dipadukan, bukan urutan memadukannya.
🔗
Jadi, bagaimana Anda mengetahui kapan harus menggunakan kombinasi dan kapan harus menggunakan permutasi?
🔗

Apakah Urutan Berpengaruh?

Hampir setiap sumber tentang kombinasi dan permutasi yang Anda baca akan menyampaikan suatu variasi dari pernyataan berikut.
🔗
Gunakan permutasi ketika urutan berpengaruh, dan gunakan kombinasi ketika urutan tidak berpengaruh.
🔗
🔗
Apa sebenarnya arti pernyataan ini? Dan mengapa pernyataan itu merupakan cara yang sangat buruk untuk membedakan kedua teknik pencacahan tersebut? Mari kita selidiki melalui sebuah contoh.
🔗
Misalkan Anda mengusulkan permainan lotre baru. Dalam permainan ini, lima bola bernomor akan dilontarkan secara acak dari mesin yang memuat bola bernomor 1 sampai 52. Jika seorang pemain memilih dengan benar kelima angka yang keluar, ia memenangkan hadiah utama.
🔗
Tentu saja, kita ingin mengetahui peluang memenangkan permainan lotre ini, yang mengharuskan kita mengetahui berapa banyak hasil berbeda yang ada. Bola-bola keluar dari mesin secara acak, sehingga salah satu hasilnya mungkin berupa bola-bola
\begin{equation*} 26, 5, 42, 17, 33\text{.} \end{equation*}
Jika Anda memegang tiket dengan angka \(5, 17, 26, 33, 42\text{,}\) apakah Anda berharap telah menang? Kebanyakan permainan lotre akan menyatakan bahwa Anda menang, karena Anda memiliki angka-angka yang sama, hanya dalam urutan berbeda.
🔗
Dalam pengertian ini, urutan angka tidak berpengaruh. Cara yang lebih baik untuk mengatakannya adalah bahwa sembarang urutan dari angka-angka yang sama dianggap sebagai hasil yang sama dan hanya dihitung sekali. Jadi, sebenarnya kita menghitung himpunan yang terdiri atas lima angka, bukan barisan lima angka. Setiap hasil merupakan suatu kombinasi, sehingga banyaknya hasil seharusnya \(C(52,5) = \binom{52}{5}\text{.}\)
🔗
Di sisi lain, jika kita harus memilih angka dalam urutan yang sama dengan urutan keluarnya dari mesin, sebenarnya kita mencocokkan suatu barisan angka dengan barisan angka lainnya. Banyaknya barisan adalah \(P(52,5)\text{.}\) Dalam kasus ini, kita akan mengatakan bahwa urutan berpengaruh.
🔗
Baik, sejauh ini semuanya berjalan lancar. Namun, bagaimana dengan contoh berikut?
🔗
Contoh 3.4.11.
Berapa banyak “kata” tiga huruf yang memenuhi ketentuan berikut?
  1. huruf-hurufnya muncul dalam urutan alfabet?
    🔗
    🔗
  2. huruf-huruf dalam kata dapat muncul dalam urutan apa pun?
    🔗
    🔗
🔗
Penyelesaian.
Apakah “urutan berpengaruh” untuk pertanyaan pertama? Dalam satu pengertian, tentu saja! Kita hanya ingin menghitung kata yang huruf-hurufnya berada dalam urutan yang benar. Namun, menurut pengertian baku urutan berpengaruh dalam kombinasi/permutasi, urutan tidak berpengaruh.
🔗
Akan jauh lebih baik jika kita bertanya apakah setiap hasil seharusnya direpresentasikan sebagai himpunan huruf atau barisan huruf. Memang benar bahwa kata merupakan barisan huruf, tetapi apakah kita menghitung semua barisan yang mungkin? Tidak, hanya satu barisan untuk setiap himpunan huruf. Nah, tepat, himpunan huruf. Setiap hasil bersesuaian tepat dengan satu himpunan yang terdiri atas tiga huruf. Kita mencacah himpunan, sehingga kita menghitung kombinasi. Banyaknya hasil adalah \(C(26,3) = \binom{26}{3}\text{.}\)
🔗
Untuk pertanyaan kedua, tampaknya urutan seharusnya tidak berpengaruh. Memang, urutan tidak berpengaruh bagi mesin yang mengeluarkan huruf-huruf tersebut, tetapi akan berpengaruh jika kita mencoba mencocokkan huruf-hurufnya. Sebaiknya kita berpikir seperti ini: Apakah kita menghitung setiap barisan huruf yang mungkin? Ya! Jadi, hasil-hasil ini merupakan permutasi, dan banyaknya hasil adalah \(P(26,3)\text{.}\)
🔗
🔗
🔗
Penggunaan urutan lain yang dapat menyesatkan muncul ketika mencacah string bit. Ingatlah bahwa string bit berpanjang \(n\) dan berbobot \(k\) adalah string yang terdiri atas \(n\) bit (0 dan 1), dengan \(k\) bit bernilai 1. Sebagai contoh, string bit berpanjang 4 dan berbobot 2 adalah
\begin{equation*} 1100, ~~ 1010, ~~ 1001, ~~ 0110, ~~ 0101, ~~ 0011\text{.} \end{equation*}
Apakah urutan berpengaruh untuk string bit? Tentu saja! Urutan adalah satu-satunya hal yang berpengaruh. Semua string di atas memuat banyaknya 0 dan 1 yang tepat sama; string-string tersebut hanya dibedakan oleh urutan bitnya.
🔗
Meskipun demikian, banyaknya string bit berpanjang \(n\) dan berbobot \(k\) adalah \(\binom{n}{k}\) dan BUKAN permutasi. Apa yang terjadi di sini?
🔗
Tidak ada yang keliru; kita hanya belum memikirkan objek yang tepat untuk mempertimbangkan urutannya. Ketika kita memilih \(k\) dari \(n\) hal untuk suatu string bit, yang kita pilih adalah posisi (untuk diisi dengan 1, misalnya). Urutan pemilihan posisi-posisi itu tidak berpengaruh; yang berpengaruh hanyalah himpunan posisi yang kita pilih. Artinya, string bit 1001 merupakan hasil memilih posisi 1 dan 4 untuk diisi dengan 1. Jika kita memilih posisi 4 lalu 1, kita akan memperoleh string bit yang sama.
🔗
Sebagai rangkuman, pertanyaan apakah urutan berpengaruh dapat menyesatkan kita ketika memutuskan antara kombinasi dan permutasi. Sebagai gantinya, kita harus menentukan apakah hasil yang kita cacah merupakan himpunan atau barisan. Jika kita mencacah himpunan, pikirkan kombinasi. Jika kita mencacah barisan, pikirkan permutasi.
🔗
🔗
🔗

Subbagian Prinsip Hasil Bagi

Kita memiliki dua cara untuk menuliskan hubungan numerik antara banyaknya kombinasi dan permutasi. Dengan menggunakan prinsip perkalian, kita memperoleh,
\begin{equation*} P(n,k) = \binom{n}{k} \cdot k! \end{equation*}
yang dapat ditulis ulang sebagai,
\begin{equation*} \binom{n}{k} = \frac{P(n,k)}{k!}\text{.} \end{equation*}
Rumus kedua ini menunjukkan bahwa mungkin ada suatu prinsip hasil bagi yang dapat kita gunakan untuk membenarkannya.
🔗
Mari kita pikirkan arti pembagian. Salah satu cara memandang soal pembagian \(24 \div 6 = 4\text{,}\) misalnya, adalah dengan mengatakan bahwa jika Anda memiliki 24 objek yang dibagi ke dalam kelompok berukuran 6, banyaknya kelompok adalah 4.
 3 
Cara lain menafsirkan pernyataan ini adalah bahwa jika Anda membagi 24 objek ke dalam enam kelompok, setiap kelompok akan berukuran 4, tetapi penafsiran ini kurang berguna bagi apa yang akan kita lakukan.
🔗
Sekarang mari kita lihat semua permutasi-3 dari himpunan berukuran 4: sebagai contoh, semua cara untuk membuat kata 3 huruf menggunakan huruf \(a, b, c, d\text{.}\) Kita mengetahui bahwa banyaknya kata semacam itu adalah \(P(4,3) = 4\cdot 3 \cdot 2 = 24\text{.}\) Akan membantu jika kita benar-benar mendaftarkan semuanya.
🔗
\(abc\) \(acb\) \(bac\) \(bca\) \(cab\) \(cba\)
\(abd\) \(adb\) \(bad\) \(bda\) \(dab\) \(dba\)
\(acd\) \(adc\) \(cad\) \(cda\) \(dac\) \(dca\)
\(bcd\) \(bdc\) \(cbd\) \(cdb\) \(dbc\) \(dcb\)
Perhatikan baris pertama. Apa kesamaan semua permutasi ini? Permutasi-permutasi tersebut tepat merupakan permutasi yang menggunakan huruf \(a, b, c\) dalam urutan berbeda. Tidak mengherankan bahwa terdapat 6 permutasi semacam ini, karena banyaknya cara menyusun tiga elemen adalah \(3! = 6\text{.}\) Dengan cara serupa, baris kedua memuat 6 permutasi yang menggunakan huruf \(a, b, d\) dalam urutan berbeda, dan seterusnya.
🔗
Intinya, jika kita hanya ingin menghitung banyaknya himpunan yang terdiri atas tiga dari empat huruf tersebut, setiap himpunan bersesuaian tepat dengan satu baris dalam tabel. Terdapat 24 elemen dalam tabel dan 6 elemen dalam setiap baris, sehingga harus ada \(24 \div 6 = 4\) baris. Tentu saja, hal ini tidak mengejutkan karena \(\binom{4}{3} = 4\text{.}\)
🔗
Penjelasan yang lebih ketat secara matematis untuk fenomena ini menggunakan bahasa relasi ekuivalensi dan partisi dari Subbab 2.6. Kita mulai dengan permutasi, lalu mendefinisikan suatu relasi ekuivalensi pada permutasi-permutasi tersebut dengan menyatakan bahwa dua permutasi ekuivalen jika keduanya memuat tepat elemen-elemen yang sama. Dari relasi ekuivalensi tersebut, kita memperoleh suatu partisi atas himpunan permutasi menjadi kelas-kelas ekuivalensi. Kombinasi yang ingin kita cacah tepat merupakan kelas-kelas ekuivalensi tersebut. Karena setiap kelas ekuivalensi berukuran sama, kita dapat menentukan banyaknya kelas dengan membagi banyaknya permutasi dengan ukuran setiap kelas.
🔗
Prinsip hasil bagi semacam ini juga berguna untuk menyelesaikan pertanyaan yang jawabannya tidak jelas berupa permutasi ataupun kombinasi.
🔗

Contoh 3.4.12.

Anda memutuskan untuk menghias tongkat sihir dengan pita perekat berbagai warna. Tersedia 10 warna berbeda, dan Anda akan menggunakan lima di antaranya untuk membuat lima garis warna yang berbeda. Berapa banyak desain tongkat berbeda yang mungkin?
🔗
Penyelesaian.
Upaya pertama untuk menyelesaikan masalah ini mungkin adalah memandang setiap hasil yang hendak kita cacah sebagai permutasi-5 dari 10 warna. Ini akan memberi kita jawaban \(P(10,5) = 10\cdot 9\cdot 8\cdot 7\cdot 6 = 30,240\text{.}\) Lalu mengapa jawaban ini tidak benar? Mari mulai membuat daftar hasil-hasil yang mungkin.
  1. Merah, biru, hijau, kuning, jingga.
    🔗
    🔗
  2. Merah, biru, hijau, kuning, ungu.
    🔗
    🔗
  3. Biru, hijau, merah, kuning, jingga.
    🔗
    🔗
  4. Jingga, kuning, hijau, biru, merah.
    🔗
    🔗
  5. dan seterusnya.
    🔗
    🔗
Saat mulai membuat daftar ini, mungkin kita bertanya apakah merah, merah, biru, biru, merah seharusnya masuk dalam daftar, lalu menyadari bahwa susunan tersebut tidak boleh masuk. Hal lain yang mungkin kita pertimbangkan adalah apakah butir 1 dan 3 benar-benar berbeda. Keduanya memang berbeda, karena satu tongkat memiliki merah sebagai warna terluar, sedangkan yang lain tidak.
🔗
Namun, bagaimana dengan butir 1 dan 4? Keduanya memiliki lima warna yang sama, tetapi dalam urutan berbeda. Namun, jika Anda memutar tongkat sihir seperti yang lazim dilakukan pesulap, tongkat 1 dapat dengan mudah tampak seperti tongkat 4. Aha! Kita melihat bahwa setiap tongkat dihitung tepat dua kali dalam daftar permutasi kita: dua permutasi ekuivalen jika keduanya hanya merupakan kebalikan urutan satu sama lain.
🔗
Karena kita dapat mengelompokkan permutasi ke dalam kelompok berukuran 2 dan setiap kelompok bersesuaian dengan satu tongkat, kita melihat bahwa jawaban yang benar adalah,
\begin{equation*} \frac{P(10,5)}{2} = \frac{10\cdot 9\cdot 8\cdot 7\cdot 6}{2} = 15,120\text{.} \end{equation*}
Tara!
🔗
🔗
🔗
🔗

Pertanyaan Bacaan Pertanyaan Bacaan

1.

Benar atau salah: Banyaknya barisan dua digit berbeda dari 0–9 adalah dua kali banyaknya himpunan dua digit berbeda dari 0–9. Jelaskan secara singkat.
🔗
🔗

2.

Benar atau salah: Banyaknya barisan tiga digit berbeda dari 0–9 adalah 3 kali banyaknya himpunan tiga digit berbeda dari 0–9. Jelaskan secara singkat.
🔗
🔗

3.

Pertanyaan apa yang Anda miliki setelah membaca bagian ini? Tuliskan sedikitnya satu pertanyaan tentang isi bagian ini yang membuat Anda ingin tahu lebih lanjut.
🔗
🔗
🔗

Latihan Soal Latihan

1.

Sebuah kedai piza menawarkan 8 jenis topping.
  1. Ada berapa piza dengan 4 jenis topping yang dapat dicantumkan pada menunya? Anggap bahwa satu jenis topping tidak boleh digunakan dua kali.
    🔗
    🔗
  2. Ada berapa piza yang mungkin dibuat jika boleh memakai antara nol dan 8 jenis topping, tanpa menggunakan satu jenis topping dua kali?
    🔗
    🔗
  3. Kedai piza itu akan mencantumkan 8 jenis topping dalam dua kolom berukuran sama pada menunya. Ada berapa cara untuk menyusun topping pada kolom kiri?
    🔗
    🔗
🔗
🔗

2.

Sebuah kunci kombinasi memiliki cakram putar dengan 45 angka. Untuk membukanya, Anda memutar cakram ke kanan hingga mencapai angka pertama, lalu ke kiri hingga mencapai angka kedua, kemudian ke kanan lagi hingga mencapai angka ketiga. Ketiga angka harus berbeda. Ada berapa kombinasi berbeda yang mungkin?
🔗
🔗

3.

Dengan menggunakan digit 2 hingga 9, tentukan banyak bilangan 3 digit yang berbeda dengan ketentuan berikut:
  1. Digit boleh digunakan lebih dari sekali.
    🔗
    🔗
  2. Digit tidak boleh berulang, tetapi dapat muncul dalam urutan apa pun.
    🔗
    🔗
  3. Digit tidak boleh berulang dan harus ditulis dalam urutan menaik.
    🔗
    🔗
🔗
🔗

4.

Untuk merapikan kamar, Anda membeli rak dinding baru guna menaruh sebagian dari 18 buku yang bertumpuk di sudut. Semua buku tersebut ditulis oleh penulis yang berbeda. Rak baru itu cukup besar untuk menampung 14 buku. Hati-hati: sebelum menjawab dua pertanyaan berikut, pikirkan jawaban mana yang seharusnya lebih besar.
  1. Ada berapa cara untuk memilih dan menyusun 14 dari 18 buku pada rak? Perhatikan bahwa buku-buku tersebut boleh tersusun dalam urutan apa pun.
    🔗
    🔗
  2. Ada berapa cara untuk menyusun 14 dari 18 buku pada rak jika buku-buku itu harus diurutkan menurut abjad nama penulis?
    🔗
    🔗
🔗
🔗

5.

Sebuah anagram dari suatu kata adalah penyusunan ulang huruf-hurufnya. Ada berapa anagram berbeda dari “troublemakings”?
🔗
🔗

6.

Ada berapa anagram dari kata “voodoo” yang diawali huruf “v”?
🔗
🔗

7.

Ada berapa anagram dari “academia”?
🔗
🔗

8.

Dalam sebuah acara retret perusahaan, 24 orang dari perusahaan Anda pergi bermain golf.
  1. Anda perlu membagi mereka menjadi kelompok berempat (kelompok berisi 4 orang): kelompok pertama, kelompok kedua, dan seterusnya. Ada berapa cara untuk melakukannya?
    🔗
    🔗
  2. Setelah bekerja keras, Anda menyadari bahwa sebenarnya setiap kelompok berempat harus memuat satu dari 6 anggota dewan (yang sudah termasuk di antara 24 pegolf tersebut). Ada berapa cara untuk melakukannya?
    🔗
    🔗
🔗
🔗

9.

Ada berapa susunan tempat duduk berbeda yang mungkin bagi Raja Arthur dan 16 kesatrianya di sekeliling meja bundar mereka?
🔗
🔗

10.

Perhatikan himpunan \(A\) dan \(B\) dengan \(|A| = 14\) dan \(|B| = 21\text{.}\)
  1. Ada berapa fungsi \(f: A \to B\text{?}\)
    🔗
    🔗
  2. Ada berapa fungsi \(f: A \to B\) yang injektif?
    🔗
    🔗
🔗
🔗

11.

Perhatikan fungsi-fungsi \(f: {\left\{1,2,3,4,5,6\right\}}\to {\left\{1,2,3,4,5,6,7\right\}}\text{.}\)
  1. Ada berapa fungsi seluruhnya?
    🔗
    🔗
  2. Ada berapa fungsi yang injektif?
    🔗
    🔗
  3. Di antara fungsi-fungsi injektif tersebut, ada berapa yang naik? Fungsi disebut naik jika \(\renewcommand{\v}{\vtx{above}{}}a \lt b\) mengakibatkan \(\renewcommand{\v}{\vtx{above}{}}f(a) \lt f(b)\text{,}\text{;}\) dengan kata lain, nilai keluaran membesar ketika nilai masukan membesar.
    🔗
    🔗
🔗
🔗
🔗

Latihan Latihan Tambahan

1.

Berapa banyak segitiga yang titik-titik sudutnya dipilih dari titik-titik yang ditunjukkan di bawah ini? Perhatikan bahwa kita tidak memperbolehkan segitiga degenerat – yaitu segitiga yang ketiga titik sudutnya berada pada garis yang sama – tetapi kita memperbolehkan segitiga yang bukan segitiga siku-siku. Jelaskan mengapa jawaban Anda benar.
🔗
Lima titik berjarak sama pada sebuah garis vertikal dan enam titik tambahan berjarak sama yang membentang ke kanan pada garis horizontal dari titik terbawah (membentuk sudut siku-siku).
Petunjuk.
Jika Anda memilih sembarang tiga titik, Anda dapat membentuk sebuah segitiga, kecuali jika ketiga titik itu semuanya berada pada sumbu \(x\) atau sumbu \(y\text{.}\) Ada pula cara lain untuk memulai penyelesaian ini, dan setiap metode yang benar seharusnya memberikan jawaban yang sama.
🔗
🔗
🔗

2.

Kita telah melihat bahwa rumus untuk \(P(n,k)\) adalah \(\dfrac{n!}{(n-k)!}\text{.}\) Tugas Anda di sini adalah menjelaskan mengapa rumus ini benar.
  1. Misalkan Anda memiliki 12 keping, masing-masing dengan warna berbeda. Berapa banyak tumpukan berbeda yang terdiri atas 5 keping yang dapat Anda buat? Jelaskan jawaban Anda dan mengapa hasilnya sama dengan menggunakan rumus untuk \(P(12,5)\text{.}\)
    🔗
    🔗
  2. Dengan kembali menggunakan skenario 12 keping, apa yang dihitung oleh \(12!\text{?}\) Apa yang dihitung oleh \(7!\text{?}\) Jelaskan.
    🔗
    🔗
  3. Jelaskan mengapa masuk akal untuk membagi \(12!\) dengan \(7!\) ketika menghitung \(P(12,5)\) (dalam konteks keping-keping tersebut).
    🔗
    🔗
  4. Apakah penjelasan Anda berlaku untuk bilangan selain 12 dan 5? Jelaskan rumus \(P(n,k) = \frac{n!}{(n-k)!}\) menggunakan variabel \(n\) dan \(k\text{.}\)
    🔗
    🔗
🔗
🔗
🔗
🔗
SblmTopLnjt
Umpan Balik