Lewati ke konten utama

Subbab 2.2 Permutasi

Pada bagian sebelumnya, kita membahas string yang mengizinkan pengulangan simbol. Sebagai contoh, “\(01110000\)” merupakan string bit yang sah dengan panjang delapan. Namun, dalam banyak situasi terapan yang sesuai dimodelkan dengan string, setiap simbol hanya boleh digunakan pada paling banyak satu posisi.

Contoh 2.5.

Bayangkan kita memasukkan \(26\) huruf alfabet Inggris ke dalam sebuah kantong, lalu mengambilnya satu per satu (tanpa mengembalikan huruf yang telah diambil) untuk membentuk string enam karakter. Kita tahu bahwa ada \(26^6\) string dengan panjang enam yang dapat dibentuk dari alfabet Inggris. Namun, jika cara pembentukan string dibatasi, tidak semua string dapat terbentuk. String “yellow” terdiri atas enam karakter, tetapi menggunakan huruf “l” dua kali sehingga tidak dapat dibentuk dengan mengambil huruf dari kantong. Sebaliknya, “jacket” dapat dibentuk dengan cara ini. Jika pada awalnya kantong berisi semua huruf, terdapat \(26\) pilihan untuk huruf pertama. Setelah huruf itu diambil, tersisa \(25\) huruf di dalam kantong. Setelah huruf kedua diambil, tersisa \(24\) huruf. Dengan melanjutkan proses ini, tepat sebelum huruf keenam diambil, terdapat \(21\) huruf di dalam kantong. Jadi, dengan mengambil huruf dari kantong, kita dapat membentuk \(26\cdot 25\cdot 24\cdot 23\cdot 22\cdot 21\) string enam karakter dari alfabet Inggris, sedikit lebih dari setengah jumlah seluruh string enam karakter yang dapat dibentuk dari alfabet tersebut.
Untuk menggeneralisasi contoh sebelumnya, sekarang kita memperkenalkan permutasi. Misalkan \(X\) merupakan himpunan berhingga dan \(n\) merupakan bilangan bulat positif. String atas \(X\text{,}\) yaitu \(s=x_1x_2\dots x_n\text{,}\) disebut permutasi jika semua \(n\) karakter yang digunakan dalam \(s\) berbeda. Jelas bahwa keberadaan permutasi atas \(X\) dengan panjang \(n\) mensyaratkan \(|X|\ge n\text{.}\)
Jika \(n\) merupakan bilangan bulat positif, kita mendefinisikan \(n!\) (dibaca “\(n\) faktorial”) dengan
\begin{equation*} n! = n\cdot (n-1)\cdot (n-2)\cdot \cdots\cdot 3\cdot 2\cdot 1. \end{equation*}
Berdasarkan konvensi, kita menetapkan \(0!=1\text{.}\) Sebagai contoh, \(7!=7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2 \cdot 1=5040\text{.}\) Selanjutnya, untuk bilangan bulat \(m,n\) dengan \(m\ge n\ge0\text{,}\) definisikan \(P(m,n)\) dengan
\begin{equation*} P(m,n) = \frac{m!}{(m-n)!} = m(m-1)\cdots(m-n+1). \end{equation*}
Sebagai contoh, \(P(9,3)=9\cdot 8\cdot 7=504\) dan \(P(8,4)=8\cdot 7\cdot 6\cdot5 =1680\text{.}\) Selain itu, sistem aljabar komputer akan segera memberikan hasil bahwa
\begin{equation*} P(68,23) = 20732231223375515741894286164203929600000. \end{equation*}

Bukti.
Proposisi ini benar karena, ketika menyusun permutasi \(s=x_1x_2\dots x_n\) dari himpunan dengan \(m\) elemen, terdapat \(m\) pilihan untuk \(x_1\text{.}\) Setelah menetapkan \(x_1\text{,}\) untuk \(x_2\) terdapat \(m-1\) pilihan, karena kita dapat menggunakan sembarang elemen dari \(X-\{x_1\}\text{.}\) Untuk \(x_3\text{,}\) terdapat \(m-2\) pilihan, karena kita dapat menggunakan sembarang elemen dari \(X-\{x_1,x_2\}\text{.}\) Untuk \(x_n\text{,}\) terdapat \(m-n+1\) pilihan, karena kita dapat menggunakan sembarang elemen \(X\) selain \(x_1,x_2,\dots x_{n-1}\text{.}\) Dengan memperhatikan bahwa
\begin{equation*} P(m,n)=\frac{m!}{(m-n)!} = m(m-1)(m-2)\dots(m-n+1), \end{equation*}
bukti selesai.
Perhatikan bahwa jawaban yang kita peroleh dalam Contoh 2.5 tidak lain adalah \(P(26,6)\text{,}\) sebagaimana yang kita harapkan berdasarkan Proposisi 2.6.

Contoh 2.7.

Sekarang saatnya memilih jajaran empat pengurus kelas (Ketua, Wakil Ketua, Sekretaris, dan Bendahara) dari \(80\) mahasiswa yang mengikuti Kombinatorika Terapan. Jika setiap mahasiswa yang berminat dapat dipilih untuk jabatan mana pun (Alice menekankan kata “jika” karena Bob ikut mencalonkan diri), berapa banyak susunan pengurus berbeda yang dapat dipilih?
Penyelesaian.
Untuk menghitung semua susunan pengurus yang mungkin, gunakan himpunan \(X\) yang memuat nama \(80\) mahasiswa yang berminat (ya, termasuk Bob yang malang). Setiap permutasi panjang empat yang dipilih dari \(X\) menjadi satu susunan pengurus jika nama pertama dalam permutasi dianggap sebagai Ketua, nama kedua sebagai Wakil Ketua, nama ketiga sebagai Sekretaris, dan nama keempat sebagai Bendahara. Jadi, banyaknya susunan pengurus adalah \(P(80,4)=37957920\text{.}\)

Contoh 2.8.

Mari kembali ke soal pelat nomor dalam Contoh 2.1. Misalkan negara bagian Georgia mensyaratkan ketiga huruf saling berbeda. Dengan demikian, alih-alih memiliki \(26^3=17\,576\) cara untuk mengisi tiga posisi terakhir pada pelat nomor, kita memiliki \(P(26,3) = 26\times 25\times 24 = 15\,600\) pilihan, sehingga seluruhnya terdapat \(140\,400\,000\) pelat nomor.
Sebagai contoh lain, misalkan pengulangan huruf diizinkan, tetapi ketiga digit pada posisi kedua hingga keempat harus saling berbeda (meskipun salah satunya boleh sama dengan digit pertama, yang tetap harus bukan nol). Masih terdapat \(9\) pilihan untuk posisi pertama dan \(26^3\) pilihan untuk huruf, tetapi tiga digit sisanya dapat diisi dengan \(P(10,3)\) cara. Dengan demikian, jumlah seluruh pelat nomor adalah \(9\times P(10,3)\times 26^3\text{.}\) Jika kita juga ingin melarang pengulangan digit pada posisi pertama, diperlukan sedikit pemikiran tambahan. Mula-mula, terdapat \(9\) pilihan untuk digit pertama tersebut. Kemudian, untuk mengisi tiga posisi berikutnya dengan digit, kita memerlukan permutasi panjang \(3\) yang dipilih dari \(9\) digit tersisa. Jadi, terdapat \(9\times P(9,3)\) cara untuk melengkapi bagian digit, sehingga seluruhnya terdapat \(9\times P(9,3)\times 26^3\) pelat nomor.
SblmKe AtasLnjt