Permutasi Linear Tanpa Perulangan Objek

Kita mulai bagian ini dengan mendefinisikan konsep permutasi atas sekumpulan objek.

Andaikan $r$ dan $n$ adalah bilangan bulat tak negatif sehingga $0 \le r \le n$. Sebuah $r$-permutasi atas sebuah himpunan dengan $n$ objek adalah penyusunan $r$ objek atas $n$ objek dengan memperhatikan urutan. Banyaknya $r$-permutasi atas himpunan dengan $n$ objek dinotasikan dengan $P(n,~r)$.

Contoh:
Misalkan $S =$ {a, b, c}, maka 1-permutasi dari $S$ adalah
$a,~b,~c$ Sehingga $P(3,~1)=3$.
Semua 2-permutasi atas $S$ adalah
$ab$, $ba$, $ac$, $ca$, $bc$, $cb$. Sehingga $P(3,~2)=6$.
Selanjutnya semua 3-permutasi dari $S$ adalah
$abc$, $acb$, $bac$, $bca$, $cab$, $cba$. Sehingga $P(3,~3)=6$.
Secara umum banyaknya $r$-permutasi atas himpunan dengan $n$ objek dinyatakan oleh teorema berikut ini:

Untuk bilangan bulat positif $n$ dan $r$ dengan $r \le n$, maka $P(n,~r)=$ $n \times (n -1) \times (n - 2) \times · · · $ $\times (n -r + 1)$.

Bukti. Dalam membentuk $r$-permutasi atas himpunan dengan $n$ objek, objek pertama dapat dipilih dalam $n$ cara. Objek kedua dapat dipilih dalam $(n -1)$ cara dan seterusnya hingga objek ke $r$ dapat dipilih dalam $(n−r+1)$ cara. Dengan menggunakan prinsip perkalian diperoleh $P(n,~r) =$ $n \times (n -1) \times (n - 2) \times ... \times (n -r + 1)$.

Perlu kita catat bahwa oleh definisi bila $r > n$, maka $P(n,~r) = 0$. Selanjutnya untuk bilangan bulat tak negatif $n$, kita definisikan $n!$ ( dibaca $n$ faktorial) sebagai $n! =$ $n \times (n -1) \times (n - 2) \times ... \times 2 \times 1$ dengan catatan bahwa $0! = 1$. Sehingga kita dapat menyatakan secara ringkas bahwa $$P(n,~r) = \frac{n!}{(n − r)!}$$ Selanjutnya untuk $n \ge 0$, kita definisikan $P(n, 0) = 1$. Definisi ini bersesuaian dengan formula di atas bila $r = 0$.
Contoh-1:
Password komputer dengan panjang 36 karakter dibentuk dengan menggunakan angka 0, 1, . . . , 9 dan huruf kecil $a$, $b$, . . . , $z$. Password mempunyai persyaratan bahwa tidak terdapat dua angka muncul secara berurutan. Tentukan banyaknya password yang dapat dibentuk.
Jawab:
Perhatikan bahwa password dapat dibentuk dengan meng gunakan dua tahap berikut ini.
- Pertama, kita urutkan ke dua puluh enam huruf dalam sem barang urutan. Hal ini dapat dilakukan dalam $P(26,~26) = 26!$ cara.
- Kemudian, agar dua angka tidak muncul secara berurutan kita sisipkan ke sepuluh angka pada dua puluh tujuh posisi sebelum huruf pertama, di antara dua huruf, atau setelah huruf ter akhir. Hal ini dapat dilakukan dalam $P(27, 10)$.
Sehingga oleh prinsip perkalian banyaknya password yang dapat diben tuk adalah sebanyak 26! × $P(27,~10)$.

Contoh-2
Tentukan banyaknya bilangan 7-digit yang dapat dibentuk dari bi langan pada himpunan {1, 2, . . . , 9} sehingga angka 5 dan 6 tidak muncul secara berurutan baik urutan 6 kemudian 5 maupun urutan 5 kemudian 6.
Solusi 1. Kita partisi persoalan menjadi empat bagian yang saling asing.
1. Digit 5 dan 6 tidak muncul. Pada kasus ini bilangan yang ter jadi merupakan 7-permutasi atas {1, 2, 3, 4, 7, 8, 9}. Sehingga banyaknya bilangan yang dapat dibentuk adalah $P(7,~7)$.
2. Digit 5 muncul tetapi digit 6 tidak muncul. Pada kasus ini bilangan dapat dibentuk dengan dua tahap. Pertama, pilih posisi untuk digit 5. Hal ini dapat dilakukan dalam 7 cara. Kemudian, sisanya dapat dilakukan dengan 6-permutasi atas {1, 2, 3, 4, 7, 8, 9}. Sehingga tahap kedua dapat dilakukan dalam $P(7,~6)$ cara. Oleh prinsip perkalian banyaknya bilangan yang dapat dibentuk adalah 7 × $P(7,~6)$.
3. Digit 6 muncul tetapi digit 5 tidak muncul. Banyaknya bi langan yang dapat dibentuk adalah sama seperti pada kasus sebelumnya, yakni sebanyak 7 × $P(7,~6)$.
4. Digit 5 dan 6 muncul secara bersama. Kasus ini akan dibagi menjadi 3 bagian.
(a) Angka 5 muncul sebagai digit pertama, maka 6 bukan digit kedua. Sehingga terdapat lima posisi untuk untuk digit 6. Sisanya adalah 5-permutasi atas {1, 2, 3, 4, 7, 8, 9}. Sehingga banyaknya bilangan yang dapat dibentuk adalah 5 × $P(7,~5)$.
(b) Angka 5 muncul sebagai digit terakhir, maka 6 bukan pada digit ke enam. Ada 5 posisi bagi 6, dan sisanya adalah 5-permutasi dari {1, 2, 3, 4, 7, 8, 9}. Banyaknya bilangan yang terbentuk adalah 5 × $P(7,~5)$.
(c) Angka 5 tidak muncul sebagai digit pertama atau digit terakhir. Maka ada lima posisi yang mungkin bagi angka 5. Karena 6 tidak berurutan dengan 5, maka ada 4 posisi bagi 6. Sisanya adalah 5-permutasi dari {1, 2, 3, 4, 7, 8, 9}. Sehingga banyaknya bilangan yang terbentuk adalah 5 × 4 × $P(7,~5)$.
Sehingga oleh prinsip penjumlahan banyaknya bilangan yang terben tuk adalah
$P$(7, 7) + 2 × 7 × $P$(7, 6) + 2 × 5 × $P$(7, 5) + 5 × 4 × $P$(7, 5) = 151200.

Solusi 2. Kita gunakan prinsip pengurangan. Misalkan $S$ adalah himpunan semua bilangan 7-digit yang dapat dibentuk dari {1, 2, . . . , 9}. Maka $|S| = P(9,~7)$. Misalkan $A$ adalah himpunan bilangan 7-digit yang dapat dibentuk dari {1, 2, . . . , 9} dengan persyaratan 5 dan 6 muncul secara berurutan. Kita partisi $A$ menjadi dua bagian - Digit 5 muncul diikuti digit 6. Terdapat 6 posisi dimana digit 5 diikuti oleh digit 6, sisanya 5-permutasi atas {1, 2, 3, 4, 7, 8, 9}
sehingga banyaknya bilangan terbentuk adalah 6 × $P$(7, 5). - Digit 6 muncul dikuti digit 5. Terdapat 6 posisi dimana digit 6 diikuti oleh digit 5, sisanya 5-permutasi atas {1, 2, 3, 4, 7, 8, 9} sehingga banyaknya bilangan terbentuk adalah 6 × $P$(7, 5). Sehingga $|A| = 12.P(7,~5)$. Jadi banyaknya bilangan 7-digit dengan 5 dan 6 tidak muncul secara berurutan adalah sebanyak $|S| -|A| =P(9,~7) -12 \times P(7,~5)$ = 151200.

Demikianlah ulasan materi Permutasi Linear Tanpa Perulangan Objek. Sampai jumpa dan semoga bermanfaat.