Permutasi 2

Definisi : permutasi dari himpunan A dikatakan cycle berukuran n, jika terdapat

Sehingga

Saat menggunakan notasi siklik, himpunan A harus sudah jelas.

Contoh: jika A = {1,2,3,4,5}, maka

Perhatikan bahwa

(1,3,5,4) = (3,5,4,1) = (5,4,1,3) = (4,1,3,5)

Tentu saja karena cycle juga suatu permutasi, maka cycle juga bisa dikalikan seperti dua buah permutasi.

Akan tetapi, hasil kali dua cycle belum tentu mrupakan cycle lagi.

Contoh: misalkan (1,4,5,6) dan (2,1,5) adalah cycle dari grup S₆ dari semua permutasi di {1,2,3,4,5,6}.

Maka

Atau

Tidak satu pun dari permutasi ini yang cycle.

Beberapa cycle dikatakan disjoint jika tidak ada elemen dari A yang muncul di dua cycle, yang berarti tidak ada elemen dari A yang muncul di dua cycle.

Dalam sudut pandang pemetaan, semua unsur di A dipetakan tetap oleh cycle-cycle, kecuali pada paling banyak satu cycle jika koleksi cycle itu disjoint.

“cycle berukuran 1 senantiasa merupakan identitas permutasi”

Contohnya (1) di S₃ {1,2,3} pada permutasi

Contoh: pandang permutasi

Sekarang coba kita konstruksi cycle yang bisa didapat dari permutasi ini.

Kita mulai dari 1, kita tahu 1 dipetakan jadi 6 dan 6 dipetakan jadi 1,

jadi kita memiliki sebuah cycle, yakni (1,6).

Berikutnya 2 dipetakan menjadi 5, 5 dipetakan jadi 3, lalu 3 dipetakan jadi 2, sehingga kita menemukan cycle-kedua kita, yakni (2,5,3).

Terakhir kita mendapatkan 4 dipetakan menjadi 4, artinya kita punya cycle (4), tapi karena cycle terakhir adalah identitas permutasi, maka bisa kita tidak tampilkan.

Jadi,

Perkalian cycle yang disjoint tentu komutatif.

Oleh karena itu urutan faktor (1,6) dan (2,5,3) tidak menjadi masalah.

Teorema 6.1

“Setiap permutasi dari himpunan hingga A adalah perkalian cycle-cycle yang disjoint.”

Bukti:

Telah dijelaskan sebelumnya bahwa cycle dikatakan disjoint jika tidak ada elemen dari A yang muncul di dua cycle.

Karena himpunan A hingga, berdasarkan definisi pada Permutasi I (link permutasi satu).

Maka grup semua permutasi pada A bisa disimbolkan dengan S_n.

Langkah untuk membuktikan teorema diatas akan dijelaskan mulai dari mencari cycle-cycle yang disjoint dari suatu permutasi dalaM S_n.

Diberikan sebagai permutasi dari S_n,

pemetaan pada permutasi misalkan dituliskan dengan

Karena A himpunan hingga maka barisan elemen-elemen diatas tidak mungkin semuanya berbeda, pasti ada saat dimana elemennya akan sama.

Misalkanmerupakan elemen pertama dari barisan diatas yang muncul untuk kedua kali.

Maksudnya bahwa memiliki nilai yang sama dengan elemen pertama dari barisan diatas.

Misalkan notasi untuk menuliskan cycle pertama dari adalah

Jadi, setelah memperoleh satu cycle yang diberi nama , maka dilanjutkan untuk menentukan cycle selanjutnya dari permutasi .

Misalkan merupakan elemen pertama dari A yang tidak muncul pada notasi siklik .

Maka dengan mengulang prosedur sebelumnya diperoleh barisan

Maka akan terbentuk cycle selanjutnya yang elemennya berbeda dengan elemen cycle yang pertama.

Karena A himpunan hingga, maka proses akan terhenti pada suatu cycle namakan . perkalian

Akan memiliki efek yang sama pada setiap elemen A, sehingga

Permutasi Ganjil dan Genap

Definisi: cycle berukuran 2 dinamakan transposisi.

Setiap cycle dapat dinyatakan sebagai hasil kali transposisi- transposisi dengan aturan:

(a₁, a₂, a₃, …, a_n) = (a₁, a₂)( a₁, a₃),…,( a₁, a_n).

Akibat sebarang permutasi dari himpunan berhingga yang terdiri dari minimal dua elemen adalah perkalian dari beberapa transposisi.

Transposisi tersebut tidak harus disjoint dan representasi untuk permutasi itu tidak mesti unik juga.

Sebagai contoh, kita bisa menyisipkan transposisi (a,b) dua kali karena (a,b)(a,b) adalah identitas permutasi.

Apa yang menarik adalah, jumlah transposisi untuk representasi suatu permutasi selalu genap atau ganjil.

Definisi: Permutasi dari suatu himpunan hingga dikatakan genap atau ganjil berdasarkan apakah permutasi tersebut bisa dituliskan sebagai perkalian sejumlah genap transposisi atau sejumlah ganjil transposisi.

Maksudnya ialah permutasi dari suatu himpunan hingga dikatakan genap jika permutasi tersebut dapat dituliskan sebagai perkalian sejumlah genap transposisi. Dan permutasi dari suatu himpunan hingga dikatakan ganjil jika permutasi tersebut dapat dituliskan sebagai perkalian sejumlah ganjil transposisi.

Teorema 6.2 : Tidak ada permutasi dari himpunan hingga bisa dituliskan sebagai perkalian sejumlah genap transposisi dan sejumlah ganjil transposisi.

Bukti:

Tanpa menghilangkan perumuman, misalkan saja A={1,2,3,…,n} dan n 2 agar transposisi ada.

Kita kerjakan dulu untuk kasus khusus dari identitas permutasi .

Tentu saja dapat direpresentasikan oleh perkalian sejumlah genap transposisi,

contohnya = (1,2)(1,2).

Kita akan tunjukkan jika

dimana adalah transposisi, maka k genap.

Pilih sebarang m yang muncul di salah satu transposisi pada persamaan (1), dan misalkan adalah transposisi pertama, dihitung dari kiri ke kanan, yang memuat m.

Tidak mungkin j=k, karena akan memuat memetakn m tidak tetap.

Sekarang pasti memiliki salah satu bentuk seperti pada ruas kiri dibawah ini:

Jika kita mengganti dipersamaan(1) dengan salah satu ekspresi di persamaan (2),

maka kita akan mengurangi jumlah transposisi sejumlah 2 buah atau mengggeser transposisi yang memuat m ke kanan.

Kita bisa mengulang proses sehingga m hilang dari persamaan (1), ingat bahwa transposisi yang memuat m tidak mungkin terdapat pada urutan terakhir, sehingga situasi pertama di persamaan (2) pasti terjadi sehingga m akan hilang semua. Kemudian kita bisa memilih suatu bilangan lain di A, lalu mereduksi persamaan (1) dengan proses yang sama. Karena proses-proses diatas membuat jumlah transposisi tidak berubah atau berkurang dua pada setiap substitusi dari persamaan (2), maka k haruslah bilangan genap. Kita sudah membuktikan kasus kusus untuk ,

sekarang misalkan sebarang permutasi , tulis Karena setiap transposisi adalah punya balikan dirinya sendiri,

maka kasus khusus kita menunjukkan r+s adalah bilangan genap, jadi r dan s keduanya genap atau keduanya ganjil.         _QED

>>>Untuk contoh soal dan pembahasannya bisa di akses pada link dibawah ini:

Bq. Fevy Shofya Wahyulana

lili hultiani

http://ernagalery2008.wordpress.com/2011/04/24/struktur-aljabar/

yusita marlia G1D008023