I I
/
Dlselenqqarakan oleh. Ilmpunan Matematika Indonesia (IndoMS) ekerjasama dengan
, Jniversitas Sriwijaya 'ogram Studi Magister Pendidikan Matematika,
. 'ogram P ascasar)ana
....•-\f.'1.\" ~-
.: ~ ...
Jl;>~
.;
.',_
•• 7 L - d
'-.... ...J __ e- ,__.
..,-: •
~
4t '" __.'_ •.. .~ .-
";n-'I...
..:.'~ .
Kombinatorik On thef-coloring of the corona product of K. with K",
211
Struktur Titik Selfrepeat dan Nonselfrepeat Pada Digraf Hampir Moore Cahyono, H dan Y.M. Cholily
215
Masalah Diameter Dan Center pada Subgraf-Subgraf Bentukan Dari Hypercube Emastuti, Haryanto, Widaningrum, Dan H. Sutedjo
221
On The Ramsey Numbers For Star Union Cycle Versus Wheel On Seven Vertices
229
I Wayan Sudarsana;
Edy Tri Baskoro, Saladin
Uttunggadewa,
clan Hilda Assiyatun
Pelabelan Berurutan Sisi Ajaib Total dari Suatu Graf Kik.i Ariyanti Sugeng
233
The Total Vertex-Irregular Labellings of The Complete Binary and 3-ary Trees N.N. Gaos. Nurdin. E.T. Baskoro. A.N.M. Salman
239
The Total Vertex-Irregular Labellings of The Olive and Its Copies Nurdin, E.T. Baskoro, A.N.M. Salman, N.N. Gaos
245
Earliest Start Tune Schedule Generation Algorithm for the Job Shop Scheduling P-roblem Opim Salim Sitompul
253
2-Eksponen Digraph Dwi-wama Asimetrik Memuat Sikel Primitif Saib Suwilo, Opim Salim dan Mardiningsih
. 261
Graf Grup Diagram Dari Semigrup [a,b.clab=ba.ac=ca,bc=cb] Sri Gemawati Dan Abd. Ghafur Bin Ahmad
267
Pembangkitan Permutation dengan Siklus Sulistyo Puspitodjati dan Djati Kerami
275
On Ph-supermagic labelings of «Pn T. K. Maryati, A. N. M. Salman, E. T. Baskoro, Irawati
281
Operasi Penyisipan Dan Reposisi Simpul dalam Menyelesaikan Masalah Desain Tata Letak Mesin dan Robot Yaya S. Kusumah clan Mieke Yolanda
287
Statistika Pengujian Hipotesis Rata-Rata Berurut untuk Membandingan Tingkat Kebocoran di Daerah Dinding Gingival Menggunakan Tiga ~acam Bahan Tambalan Sementara Bemik Maskun
2Y5
Analisa Survival Bayesian dalam Model Resiko yang Sebanding dengan Resiko Logistic yang Relative Daeng Idris Muhyidin
307
XII!
Program Stulfi Mapistu poufU£i{an ?fatmratika Program PQSCasaryana'Universitas Sriwijaga
PEMBM GKIT Al"l PERMUTATION DENGAN SIKLUS Sulistyo Puspitodjati
I
""
dan Djati Kerami2
Jmusan Siste:m lnforrnasi FILKOM Universitas Gunadarma E-mail:
[email protected] 2Jurusan.1arematika FMlPA Universitas Indonesia E-mail: djatikr@uLedu
I
Abstrak.
Makalah ini membahas pembangkitan leng\c:ap objek kombinatorial pennutasi khususnya pennutasi n dengan satu siklus dengan panjang n. Metode yang akan digunakan dalam pembangkitan pennutasi dengan memperharikan siklus tersebut menggunakan pendekatan pohon pembangkit atau metode ECO (enumerating combinatorial objects). Dalam metode ini setiap objek diperoleh dati objek yang lebih kecil dengan melakukan ekspansi lokal, Seringkali ekspansi lokal tersebut sangat teratur dan dapat dijelaskan dalamamran suksesi, Metode ECO ini telah ditunjukkan efektif untuk beberapa struktur kombinatorik. Efekrif dalam pembangkitan kombinatorik berarti: waktu untuk menghasilkan (running rime) sebanding dengan banyaknya objek yang dihasilkan, yang merupakan syarat penring dalam merancang algoritma pembangkitan obiek kombinatorial.
Kala kuncl:
1.
engbangkitan
lengkap, permutasi
dengan siklus, po/u)n pembangkit. metode ECo.
Pendahulean
Salah sani bidang utama dati kombinatorik adalah membangkitkan objek dati kelas tertenru untuk parameter tertentu, baik secara lengkap (exhaustive generation) atau secara acak (random generation). Maksud dari membangkitan secara lengkap tersebut adalah mencari cara atau metode atau algoritma untuk mencacah (list. enumerate) semua objek dalam urutan tertentu tanpa pengulangan dan tidak melewatkan satu objek pun. Algorinna-algoritma tersebut berguna pada banyak bidang seperti uji perangkat keras maupun perangkat hmak, biokimia, biologi dan termodinamika ({Bet{J7), (Duc07)).. Pembangkitan lengkap sering juga digunakan untuk memecahkan masalah-masalah NP-complete, dan menganalisa atau membukrikan suatu program. ([Vaj06]).
.,.
Salah satu pendekatan untuk membangkitkan objek kombinatorial adalah dengan yang disebut pohon pembangkit atau sering diidentikkan dengan nama metode ECO (enumerating combinatorial objects) ([Ban07]). Dalam metode ECO setiap objek diperoleh dati objek yang lebih kecil yang diekspansikan dengan rumusan yang disebut aturan suksesi. Aturan suksesi ini dapatdirepresentasikan dalam suatu pobon dan disebut pobon pembangkit ([Fer05]). Pobon pembangkit 1ni telah ditunjukkan efisien dalam konteks pembangkitan kombinatorial, yaitu waktu untuk menghasilkan N objek berukuran n adalah O(l\.l). Objek-objek yang telah ditunjukkan efisien dibangkitkan dengan pohon pembangkit tersebut adalah: objek Catalan dalam [Ber07] dan (Fer05], untuk pennutasi pengbindaran pola umum (generelazid pattern avoidance) dalam [Eli07], convex polyominoespan dalam {Lun03}, dan untuk: struktur Gray dalam [Ber207]. Pobon pembangkit juga secara detail dibahas untuk beberapa objek dalam [Ban07] dan [Wes96]. Selain itu, pohon pembangkit mempunyai dan pembangkitan acak ({Duc07).
pemanfaatan
Karena itu makalah ini akan membahas pembangkitan pembangkit ataudikenaI juga sebagaimetode ECO
2.
yang penting dalam kcmbinatorial,
yaitu bijeksi
perrnutasi siklUS Mtiiggu.nalGm pendekatan
pohon
Permutasi
Perrnutasi adalah pemetaan dati suatu himpunan
ke dirinya sendiri, Atau secara tbnMl:
Dejinisi I: Permutasi dati himpunan S = (n] = {1,2, ..,n} adalab bijeksi n: S ~ S. Salah representasi dari pennutasi adalah dengan perkalian siklusnya. Siklus dari permutasi adalah himpunan bagian dari suatu himpunan yang elemen-elemeaava rnasuk dalam satu orbit. Atau siklus
275 lProgram Stwfi 'M4f!i...ttLr(P,1Il411fiI~g.n :Mntematif,g.
It•• , ••••••••
------------------------------
1••••••
11., •••• 1 11.1 •••
1111. XIV
I [2008]
dengan panjang 1 dari suatu pennutasi adalah urutan at. a2, ... , a, sedemikian sehingga ~ = n:(a;.\)untuk i = 2, 3, ... , I,dan a, = It{a/) atau ~(a;) = a; ([Rus03] dan [8On02]). Contoh, pennutasi 1t berikut:
(1 2 3 4 \1
4
2
8
5-
:>
7 8) 6
3/
dapat diwakili oleh diagram berikut:
Permutasi tersebut mempuyai 4 siklus (1), (248 3), (~), and (6 7). (2483) adalah siklus dengan panjang I = 4, karena n:4(2) = 2. Dengan perkalian siklus, 1t dapat dinyatakan sebagai 1t = (IX2483)(5)(67). Karena siklus (8324) menyatakan siklus yang sama dengan (.2483), nuka sering digunakan earn yang nnik untuk menyatakan permutasi menggunakan notasi siklus, yang disebut sebagai norasi siklus kanonikal. Cara ini adalah menulis elemen terbesar pada setiap siklus terlebih dahufu, kemudian mengurutkan setiap siklus dari kecil ke besar berdasarkan elemen-elemen pertama pada siklus. Dengan demikian (1)(2483)(5)(67) dalam notasi siklus kanonikal adalah n = (1)(5)(76)(8324).
1t
=
Banyaknya permutasi en] dengan m siklus adalah bilangan Stirling tanpa tanda jenis pertama c(n,m) «(Rus03J, (B6n02J). Dimana c(n,n) = 1, c(n,l) = (n-l)! (1) c(n,m) = (n-l).c(n-l.m) + c(n-l,m-l), 1 < m < n. Makalab ini akan membabas permutasi dengan m siklus, khusus m = 1, yang selanjutnya akan disebut sebagai permutasi n dengan sikius. Banyaknya permutasi n dengan siklus menurut formula (1) diatas adalah (n-l)!. Sehingga banyaknya permutasi 4 dengan siklus adalah 3! = 6,yajJft-{(4123), (4312), (4132), (4213), (4231), (4321)}. 3. Pembapgkitan
ObjeR.
kombinatoriar dan Pohon Pembangkit
Sl\!
[BanOif. sebagaimana
berikut.
276 tpyo9~mSt.wf~agi.>ur1'~u!i~an.!Ma!e!M.~ili.!z trrt~'lr(!fT! (;a.~ca!;t!!Jt!~.:: ·i../nsuersuas ~ ~!~~Y.'1
P •••••••••••
N ••••••
f••••••
'e._"•• XIV
_ ••
[2008]
/
Operator ECO ,! Misalkan 0 adalah kelas objek kombinatorial dan p: N adalah parameter yang hingga pada 0, yaitu parameter p sedemikian sebingga OD = {O EO: P(O) = n} dari objek berulcuran n adalah hingga. Misalkan " : ~2° adalah operator yang sedemikian sehingga 'll(On) k 20>+1, Operator "
°~
°
menggambarkan
bagaimana objek keeil mengaasilkan
objek yang lebih besar.
Proposisi 2-1: Jika e memenuhi, untuk setiap n? 0, l. untuk setiap 0' E Oa+hakan terdapat 0 E Onsedemikian
2.
EOn, akan menggambarkan'll(O) = { \"(0): 0 E On} adalah partisi dati
himpunan Operator
JO+I
"yang
memenuhi
kondisi
operator ECO membangkitkan
sehingga O'
dan 0 ~ 0', maka famili
00+1.
) dan 2 tersebut di atas, dikatakan
semua objek 0
E 'II,
() '11(0')= 0 kapanpun
untuk setiap 0.0'
sedemikian
sehingga
sebagai
operator
setiap objek O'
E
ECO. Jadi
0a+1diperoleh
secara unik dari 0 E On . Operator ECO yang sedang melakukan ekspansi lokal pada objek yag disebut situs aktif dari objek. Operator ECO dapat digambarlam dengan pohon pembangkit, yaitu: pohon berakar yang simpu-simpulnya berhubungan dengan objek 0, Akar yang ditempatkan pada level 0 pada pohon, adalah objek dengaa ulomm terkecil. m. Objek-objek dengan ukuran S3IllZ berada pada level yangsama dan anak dari objek O. adalah yang dihasilkan dari 0 melalui ". Jib {IOn nn adalah urutan yang ditentukan
oleh banyaknya
IOn I x!'
objek berukuran n, makal Jx) = ~
adalah fungsi pembangkitnya.
Aturan suksesi Aturan suksesi
a adalah
penulisan
V didefinisikan
dimana a
E
sistem «a),
1'), mengandung
aksioma (a) dan himpunan
produksi
atau aturan
pada hirapunan label M c N••:
M adalah nilai tertentu dan e; adalah :fimgsi M ~ M.
Salah satu sifat utama dari aturan suksesi adalah prinsip konsistensi, yaitu setiap label (k) harus memproduksi tepat k elemen.. Aturan suksesi adalah sesuai dengan representasi pohon yang akarnya berlabel aksioma (a), dan simpul berlabel (Ie) menghasilkan level seianjutnya k anak-anak yang masingmasing berlabel (e/(k), "', e,jlc) (yang nanti akan menghasilkan masing-masing anak berlabel e/(k), •. " e,jlc), dan seterusnya). Aturan suksesi menghasilkan urutan {f"},, dari bilangan bulat positif, dimana /.. adalah banyaknya simpul pada level ke n dari pohon pembangkit dan dinotasikan sebagai 10M = 1:.-
1,,-1'.
Seringkali mempunyai
operator ~ dikodelam
a anak dan k objek
akaa menghasilkan
n, yang
0;, ..., ~,dihasilkan
anak elk) oleh e, yaitu
pohon pembangkit dari operator atauf jx) = x., Jo(X) ketika m = 0: 3.2, Contoh
dengan aturan suksesi
£co
!,,(O;)!=e;(k),
berarti, objek dengan ukuran minimum
oleh objek 0 yang sedemikian
sehingga
l~ i ~ k. Berarti terdapat isomorfuna
dan aturan suksesinya
yang bersesuaian.
0;
antara
Maka I jx) = x'" lo(x),
: Permutasi
Pohon pembangkit untuk permutasi (secara umum) dapat dibangun berdasarkan algoritma pembangkitan permutasi Johnson =Trotter, Algoritma Johnson-Trotter memulai peimutasi dari yang terpendek, yaitu [I], dan ini hanya mempunyai satu permutasi {I}. Kemudiaa untuk [21, elemen tambahan 2, ditaIiib3hkan i..e permutasi 1 dengan cara meletakkan 2 pada sebelah kiri 1, atau ke sebelah kanan 1, sehingga diperoleh 12 dan 21. Dua elemen dari masing-masing pemrutasi ini mendefinisikan 3 posisi untuk elemen k.etiga 3 dengan meletakkan 3 pada paling lciri, tengah, dan paling kanan: 312, 132, 123, dan 321, 231, 213. Secara umum, terdapat N cara untuk mempeduas permutasi 31 32 ... 3n_! dengarr panjang N-l ke permutasi dengan panjang N:
277 Studt
9.tt1t~ lPmoram llli~:::sr1rja::aVniv:rsit..sSriWijayu
tProgram
9idgisurtPefl(tufik.gt!
\.
P •••••••••••
t••••••••
,1••• 1 ••••••••
IIt. XIV
[2008]
N al a2 ... an·1 ll'lNa2
••• 3,..1
a, a2 N... au-I al a~ a, a1
Nan_I lI,,-lN
1
12~21
A\ 4312 312
ffi 321 ~
132 123
231
213
i134
~~
~~ 3412 3142 3124
4213 2413 2143 Gambar-l:
Pohon pembangkit
untuk permutasi
Melalui pohon pembangkit, pembangkitan permutasi dapat digambarkan sebagaimana tcrlihat pada gambar-l. Jika simpul dari pohon sebelah kiri pada gambar-l diberi label sesuai dengan banyaknya anak cabang, maka diperoleh pobon sebelah kanan pada gambar-l. Dengan demikian pobon pembangkit untuk pennutasi dapat ditulis dalam aturan suksesi berikut:
n_{(l) (k)
(3.) H
(k+l)k ,~
Berdasarkan
aturan suksesi (3) maka fungsi pembangkit
. fn
= L:1nx.
= 1 + Zx
untuk aturan suksesi tersebut adalah
+ 2.3x2 + 23Ax3 + '" + (n + l)!x·
w.o
4. Pohon Pembangkit untuk Permutasi dengan siklus Untuk pembangkitan permutasi it: [n]~ In] dengan satu siklus panjang n, penulis mengikuti logika pembangkitan permutasi Johnson -Trotter. Misa\kan S" c adalah himpunan semua anggota permutasi n dengan siklus yang ditulis secara kanonik, dan IS,,_c I adalah banyaknya anggota S,,_c. Maka S,,_c = {(ala2 ...a.)lal = n = 1t(a.), ai = 1t(ai-I), i = 2, 3, ... , n} (4) Dengan demikian, 1t(n) adalah semua kemungkinan angota [n-I], kcmudian n:(a2) adalah semua anggota [n-I] tanpa al. dan seterusnya, tt(a,...I) adalah anggota [n-I] tanpa ai, i = 2, ... , n-2. Dengan kata lain siklus-siklus anggota Sn,S adalah (na2 ...a.) dengan semua kemungkinan permutasi [11-1] untuk ~ ...a". Berarti I I = (n-I)!
s.,
S; c dapat dibangun dari S("'/I e dengan menambahkan n didepan semua anggota S'._I) c sehingga diperoleh sebanyak I S'n-l)_c I eIemen berupa (na2 .•• a.) dengan a2 = n- I. Anggota S"J yang lain- dibentuk dari setiap (na, ...aH) yang ada dengan memindahkan posisi n-I ke posisi ac berturut-turut untuk k = 3, ..., n.. Dengan demikian pohon pembangkit untuk permutasi n dengan siklus adalah sebagaimana pada gambar-2.
278
~atik(l
iProgram lPasSa.(IIrj(ltUl VnweTsl/.as.:>mv9aJa
••••••••••••
' •••••
--------------------------------------
111••••••
1 ••
, •••••••
X.9
f2002}
,I "
(1)
.r:-. I
(21)
(321 )
(312)
~
~ (4231) (4213)
(4321)
Gambar-2 Pohon Pembangkit
(4312)
(4132) (4123)
untuk pennutasi 4 dengan siklus
Jika simpul dari pohon pembangkit gambar-2 diberi label sesuai dengan banyaknya anak cabang, maka pohon pembangkit untuk pennutasi n dengan siklus dapat ditulis dalam aturan suksesi berikut: O) Q= {
(1)
H
(2)
(k)
H
(k+l)k
Berdasarlcan aturan suksesi (4) maka fungsi pembangkit
I«
= Lf.x.
(4)
untuk aturan suksesi tersebut adalah
=1+x+2.xl +2.3x3 + ... +n!x"
n~
5.
.
Simpulan
Pohon pembangkit permutasi n dengan satu siklus panjang n pada makalah ini menunjukkan kekonsistensian dengan enumerasi tanpa pohon pembangkitan, yang menunjukkan bahwa pohon dapat digunakan untuk membangkitkan semua pennutasi n dengan siklus. Langkah selanjutnya yang perlu dikembangkan dari basil pada makalah ini adalah analisa algoritma pembangkitan dengan pohon pembangkit ini untuk mengetahui apakah tahapan-pembangkitan cu...... up efektif, Selain itu perlu diteliti lebih lanjut untuk melihat sifat-sifat yang dapat dihasilkan dari pohon ini, seperti kode gray misalnya. Penelitian ini merupakan langkah sangat awal dalam penelitian pennutasi untuk sembarang m siklus.
untuk menunuskan
pohon pembangkit
Acknowledgment Terimakasih saya ucapkan pada Prof. Vajnovszki yang memberikan Pimpinan Universitas Gunadarma yang memungkinkan makalah Matematika Nasional XIV 2008 Palembang.
ide penelitian, dan tak Iupa pada ini dihadirkanpada Konferensi
Daftar Pustaka [1] [Ban07] C. Banderier, dkk, _ 0702753vl, 25 Feb 2007
I
Generating Functions for Generating Trees, arXiv:math.CO/
[2J [Ber07] A. Bernini, I. Fanti, E Grazzini, An exhaustive generation algorithm for Catalan objects and others, arXiv:math.CO/0612 127v2, 1 Feb 2007, . _ .. __ . _
[j] [Ber207] A. Bernini. dkk, A general exhaustive generation algorithm for Gray structures, arXiv: mathl0703262vl
[math.eOl
,9 March 2007
[4] [B6n02] 'vi. BOna, A Walk through Combinatorics. Theory. New Jersey, War Scientific, 2002.
An Introduction to Enumeration and Graph
279 Sttufi 9Jl.tJAisfer(pnu['ufiftan ~M4tnnatik.a tPrOlJrdm CPluCilsorjann 'Universitas Srr-..I!ijay! Cftngr ••
ti
[5] [Duc07] E. Duchi, ECO method and Object Grammars: two methods for tire enumeration of combinatorial objects. Dottorato di Ricerea in Ingegneria Informatica e deU'Automazione, XV Ciclo, Universit_a Degli 8tudi di Firenze, htto:/Iwww.dsi.unifi-itIDRIIA/RaccoltaTesilDuchL diunduh: Mei, 2007 [6] [Eli07] S. Elizalde, Generating Tree for Permutations Avoiding Generalized Patterns, arXiv: 0707.4633vl [math.CO] ,31 July 2007 [7] [Fer05] L. Ferrari and R. Pinzani, arXiv:math.CO/0507210vI, 11 July 2005.
Catalan
like numbers
and
succession
rules,
[8] [Lun03] A. Del Longo, dkk.,"Enumeration of convex polyominoes using the ECO method". Discrete Malhemathics and Theoretical Computer Science AB(DMCS), 2003, 103-116. [9] [Rus03] F. Ruskey, Combinatorial Generation, http://www.lstworks.comlreflRuskevCombGen.pdf.
2003.
[10]
[Vaj06] V. Vajnovszki, Generating Combinatorial Objects by ECO Method, the Lyndon Words Case. Lecture Notes. Jakarta, 26 January 2006.
[11]
[Wes96] J. West, Generating Trees and Forbidden Subsequences htto:llciteseerx.ist.psu.edulshQwciting;jsessionid= 1CEE9AO113F2F48EF4334245C6A5~BED ?cid=1531l4.1996
280 lJ>roaram Studi 9rt.agister fJ>m4ufi~n901.atemati~,g. tProgram tJ?a...(;(;Q...w.Yjtu!~ ,,-1;;£:;::'!i~!!S.5~'..
t~
