I I/

Dlselenqqarakan oleh.Ilmpunan Matematika Indonesia (IndoMS)ekerjasama dengan -\f.'1.\"....• ~-

, Jniversitas Sriwijaya .: ~...Jl;>~ .',_

'ogram Studi Magister Pendidikan Matematika, .; •• 7 L - d ~'-.... 4t '"P . ...J __ __.'-'ogram ascasar)ana e- ,__. _ •.. .~.., . --: ..:.'~

• ";n-'I... .

Kombinatorik

On thef-coloring of the corona product of K. with K", <or P,.Adiwijaya • AN.M. Salman, E.T. Baskoro, and D. Suprijanto

Struktur Titik Selfrepeat dan Nonselfrepeat Pada Digraf Hampir MooreCahyono, H dan Y.M. Cholily

Masalah Diameter Dan Center pada Subgraf-Subgraf Bentukan Dari HypercubeEmastuti, Haryanto, Widaningrum, Dan H. Sutedjo

On The Ramsey Numbers For Star Union Cycle Versus Wheel On Seven VerticesI Wayan Sudarsana; Edy Tri Baskoro, Saladin Uttunggadewa, clan Hilda Assiyatun

Pelabelan Berurutan Sisi Ajaib Total dari Suatu GrafKik.iAriyanti Sugeng

The Total Vertex-Irregular Labellings of The Complete Binary and 3-ary TreesN.N. Gaos. Nurdin. E.T. Baskoro. A.N.M. Salman

The Total Vertex-Irregular Labellings of The Olive and Its CopiesNurdin, E.T. Baskoro, A.N.M. Salman, N.N. Gaos

Earliest Start Tune Schedule Generation Algorithm for the Job Shop Scheduling P-roblemOpim Salim Sitompul

2-Eksponen Digraph Dwi-wama Asimetrik Memuat Sikel PrimitifSaib Suwilo, Opim Salim dan Mardiningsih

Graf Grup Diagram Dari Semigrup [a,b.clab=ba.ac=ca,bc=cb]Sri Gemawati Dan Abd. Ghafur Bin Ahmad

Pembangkitan Permutation dengan SiklusSulistyo Puspitodjati dan Djati Kerami

On Ph-supermagic labelings of «PnT. K. Maryati, A. N. M. Salman, E. T. Baskoro, Irawati

Operasi Penyisipan Dan Reposisi Simpul dalam Menyelesaikan Masalah Desain Tata LetakMesin dan RobotYaya S. Kusumah clan Mieke Yolanda

Statistika

Pengujian Hipotesis Rata-Rata Berurut untuk Membandingan Tingkat Kebocoran di DaerahDinding Gingival Menggunakan Tiga ~acam Bahan Tambalan SementaraBemik Maskun

Analisa Survival Bayesian dalam Model Resiko yang Sebanding dengan Resiko Logisticyang RelativeDaeng Idris Muhyidin

Program Stulfi Mapistu poufU£i{an ?fatmratikaProgram PQSCasaryana'Universitas Sriwijaga

211

215

221

229

233

239

245

253

. 261

267

275

281

287

2Y5

307

XII!

PEMBM GKITAl"l PERMUTATION DENGAN SIKLUS ""

Sulistyo Puspitodjati I dan Djati Kerami2

IJmusan Siste:m lnforrnasi FILKOM Universitas GunadarmaE-mail: sulistyo@staff.gunadarma.acjd

2Jurusan.1arematika FMlPA Universitas IndonesiaE-mail: djatikr@uLedu

Abstrak. Makalah ini membahas pembangkitan leng\c:ap objek kombinatorial pennutasi khususnyapennutasi n dengan satu siklus dengan panjang n. Metode yang akan digunakan dalam pembangkitanpennutasi dengan memperharikan siklus tersebut menggunakan pendekatan pohon pembangkit ataumetode ECO (enumerating combinatorial objects). Dalam metode ini setiap objek diperoleh dati objekyang lebih kecil dengan melakukan ekspansi lokal, Seringkali ekspansi lokal tersebut sangat teratur dandapat dijelaskan dalamamran suksesi, Metode ECO ini telah ditunjukkan efektif untuk beberapa strukturkombinatorik. Efekrif dalam pembangkitan kombinatorik berarti: waktu untuk menghasilkan (runningrime) sebanding dengan banyaknya objek yang dihasilkan, yang merupakan syarat penring dalammerancang algoritma pembangkitan obiek kombinatorial.

Kala kuncl: engbangkitan lengkap, permutasi dengan siklus, po/u)n pembangkit. metode ECo.

1. Pendahulean

Salah sani bidang utama dati kombinatorik adalah membangkitkan objek dati kelas tertenru untukparameter tertentu, baik secara lengkap (exhaustive generation) atau secara acak (random generation).Maksud dari membangkitan secara lengkap tersebut adalah mencari cara atau metode atau algoritmauntuk mencacah (list. enumerate) semua objek dalam urutan tertentu tanpa pengulangan dan tidakmelewatkan satu objek pun. Algorinna-algoritma tersebut berguna pada banyak bidang seperti ujiperangkat keras maupun perangkat hmak, biokimia, biologi dan termodinamika ({Bet{J7), (Duc07)).. .,.Pembangkitan lengkap sering juga digunakan untuk memecahkan masalah-masalah NP-complete, danmenganalisa atau membukrikan suatu program. ([Vaj06]).

Salah satu pendekatan untuk membangkitkan objek kombinatorial adalah dengan yang disebut pohonpembangkit atau sering diidentikkan dengan nama metode ECO (enumerating combinatorial objects)([Ban07]). Dalam metode ECO setiap objek diperoleh dati objek yang lebih kecil yang diekspansikandengan rumusan yang disebut aturan suksesi. Aturan suksesi ini dapatdirepresentasikan dalam suatupobon dan disebut pobon pembangkit ([Fer05]). Pobon pembangkit 1ni telah ditunjukkan efisien dalamkonteks 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 patternavoidance) 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 pemanfaatan yang penting dalam kcmbinatorial, yaitu bijeksidan pembangkitan acak ({Duc07).

Karena itu makalah ini akan membahas pembangkitan perrnutasi siklUS Mtiiggu.nalGm pendekatan pohonpembangkit ataudikenaI juga sebagaimetode ECO

2. 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 adalahhimpunan bagian dari suatu himpunan yang elemen-elemeaava rnasuk dalam satu orbit. Atau siklus

lProgram Stwfi 'M4f!i...ttLr(P,1Il411fiI~g.n :Mntematif,g.<Program CPascasarjana Vniversitas Sriwijaya

275

It•• , •••••••• 1•••••• 11., •••• 1 11.1 ••• 1111. XIV I [2008]------------------------------

dengan panjang 1dari 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 1tberikut:

(1\12 34 2

4 5-8 :>

7 8)6 3/

dapat diwakili oleh diagram berikut:

Permutasi tersebut mempuyai 4 siklus (1), (248 3), (~), and (6 7). (2483) adalah siklus dengan panjangI = 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 nnikuntuk menyatakan permutasi menggunakan notasi siklus, yang disebut sebagai norasi siklus kanonikal.Cara ini adalah menulis elemen terbesar pada setiap siklus terlebih dahufu, kemudian mengurutkan setiapsiklus dari kecil ke besar berdasarkan elemen-elemen pertama pada siklus. Dengan demikian 1t =(1)(2483)(5)(67) dalam notasi siklus kanonikal adalah n = (1)(5)(76)(8324).

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 disebutsebagai permutasi n dengan sikius. Banyaknya permutasi n dengan siklus menurut formula (1) diatasadalah (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\!<lh S<\tu bi~ng dl\!~ KQmbimltc)fik adalah pembangkitan obiekseca; Iengkap, Pembangkitan iniberarti membangkitkan (menghadirkan) semua anggota dari kelas kombinatorial tertentu secara efisienyang sedemikian sehingga setiap anggota muneul tepat seka:li.Salah satu peneekatan untuk pembanzkitanlengkap adalah dengan yang disebut pohon pembangkit, Pohon pembangkit adalah- pohon - yangmenggambarkan ke\uarga tertentu dari objek kombinatorial; tiap simpul berhubungan dengan satu objek,dan cabangnya mennjn simpul yang mengkudekan altematif yang dipilih dalam mengkonstruksikanobjek. Pehen pembangkit menjanjikatt kemputasi yang ccpat dalam mengenumerasi barisan objek .

. . Metode pohon pembangkit ini disistematisasikan oleh Barcucci, Del lungo, Pergola, and Pinzani, dengannama sistem ECO (enumerating combinatorial objects) «(Ban07]). Da:lam metode ECO ini setiap objekdiperoleh tiariobjek ynng lebih kecil dcngan mclaknkanekspansi lokal. seringkati ekspansi lokal tersebntsangat teramr dan dapat dijelaskan dalam aturan suksesi. Metode ECO ini telah ditunjukkan efektifuntukbeberapa struktur kombinatorik, seperti: objek Catalan dalam [Ber07J dan [Fer05], untuk permutasipenghindaran pola umum (generelazid pattern avoidance) dalam [Eli071, convex polyominoespan dalam[LunG3], dan untuk struktur Gray dalam [Ber207]. Namun penelitian-penelitian tcrsebut belum memhahaspembangkitarr permutasi siklus dengan, pohorr pembangkit atau metode ECO tersehnt. Snbhab berikutakan menjelaskan metode ECO secara lebih rinei.

3".r Metode KCO, aturan suksesi, dan pohon pembangkit

Bagaimana m~tQ<JeECO b~k~rja dij~laskan dalam [B~r(H). (O\lc07J. dan [BanOif. sebagaimana berikut.

276tpyo9~mSt.wf~agi.>ur1'~u!i~an.!Ma!e!M.~ili.!z

trrt~'lr(!fT! (;a.~ca!;t!!Jt!~.:: ·i../nsuersuas ~ ~!~~Y.'1

P••••••••••• f•••••• N•••••• _ •• 'e._"•• XIV [2008]

/

Operator ECO ,!Misalkan 0 adalah kelas objek kombinatorial dan p: °~N adalah parameter yang hingga pada 0,yaituparameter 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 sehingga O' E 'II, dan2. untuk setiap 0.0' EOn, akan menggambarkan'll(O) () '11(0')= 0 kapanpun 0 ~ 0', maka famili

himpunan JO+I = { \"(0): 0 E On} adalah partisi dati 00+1.

Operator "yang memenuhi kondisi ) dan 2 tersebut di atas, dikatakan sebagai operator ECO. Jadioperator ECO membangkitkan semua objek 0 sedemikian sehingga setiap objek O' E 0a+1diperolehsecara unik dari 0 E On . Operator ECO yang sedang melakukan ekspansi lokal pada objek yag disebutsitus aktif dari objek. Operator ECO dapat digambarlam dengan pohon pembangkit, yaitu: pohon berakaryang 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 yangsamadan anak dari objek O. adalah yang dihasilkan dari 0 melalui ". Jib {IOn nn adalah urutan yangditentukan oleh banyaknya objek berukuran n, makal Jx) = ~ IOn I x!' adalah fungsi pembangkitnya.

Aturan suksesi

Aturan suksesi a adalah sistem «a), 1'), mengandung aksioma (a) dan himpunan produksi atau aturanpenulisan Vdidefinisikan pada hirapunan label M c N••:

dimana a E Madalah nilai tertentu dan e; adalah :fimgsi M~ M.

Salah satu sifat utama dari aturan suksesi adalah prinsip konsistensi, yaitu setiap label (k) harusmemproduksi tepat k elemen.. Aturan suksesi adalah sesuai dengan representasi pohon yang akarnyaberlabel aksioma (a), dan simpul berlabel (Ie) menghasilkan level seianjutnya k anak-anak yang masing-masing 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 operator ~ dikodelam dengan aturan suksesi n, yang berarti, objek dengan ukuran minimum

mempunyai a anak dan k objek 0;, ..., ~,dihasilkan oleh objek 0 yang sedemikian sehingga 0;akaa menghasilkan anak elk) oleh e, yaitu !,,(O;)!=e;(k), l~ i ~ k. Berarti terdapat isomorfuna antara

pohon pembangkit dari operator £co dan aturan suksesinya yang bersesuaian. Maka I jx) = x'" lo(x),atauf jx) =x., Jo(X) ketika m = 0:

3.2, Contoh : Permutasi

Pohon pembangkit untuk permutasi (secara umum) dapat dibangun berdasarkan algoritma pembangkitanpermutasi 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, ditaIiib3hkani..e permutasi 1 dengan cara meletakkan 2 pada sebelah kiri 1, atau ke sebelah kanan 1, sehingga diperoleh12 dan 21. Dua elemen dari masing-masing pemrutasi ini mendefinisikan 3 posisi untuk elemen k.etiga 3dengan meletakkan 3 pada paling lciri, tengah, dan paling kanan: 312, 132, 123, dan 321, 231, 213. Secaraumum, terdapat N cara untuk mempeduas permutasi 31 32 ... 3n_! dengarr panjang N-l ke permutasidengan panjang N:

277tProgram Studt 9idgisurtPefl(tufik.gt! 9.tt1t~lPmoram llli~:::sr1rja::aVniv:rsit..sSriWijayu

\.

P••••••••••• t•••••••• ,1••• 1 •••••••• IIt. XIV [2008]

N al a2 ... an·1ll'lNa2 ••• 3,..1

a, a2 N... au-I

al a~ Nan_Ia, a1 lI,,-lN

1

12~21

A\ ffi231 213 i134

~~

4213 2413 2143Gambar-l: Pohon pembangkit untuk permutasi

Melalui pohon pembangkit, pembangkitan permutasi dapat digambarkan sebagaimana tcrlihat padagambar-l. Jika simpul dari pohon sebelah kiri pada gambar-l diberi label sesuai dengan banyaknya anakcabang, maka diperoleh pobon sebelah kanan pada gambar-l. Dengan demikian pobon pembangkit untukpennutasi dapat ditulis dalam aturan suksesi berikut:

4312 312 132 123

~~3412 3142 3124

321~

n_{(l)(k) H (k+l)k

(3.)

,~Berdasarkan aturan suksesi (3) maka fungsi pembangkit untuk aturan suksesi tersebut adalah

. fn = L:1nx. = 1+ Zx + 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 logikapembangkitan permutasi Johnson -Trotter. Misa\kan S" c adalah himpunan semua anggota permutasi ndengan siklus yang ditulis secara kanonik, dan IS,,_c Iadalah 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 lainsiklus-siklus anggota Sn,S adalah (na2 ...a.) dengan semua kemungkinan permutasi [11-1] untuk ~ ...a".Berarti Is., I= (n-I)!

S; c dapat dibangun dari S("'/I e dengan menambahkan n didepan semua anggota S'._I) c sehingga diperolehsebanyak IS'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.. Dengandemikian pohon pembangkit untuk permutasi n dengan siklus adalah sebagaimana pada gambar-2.

278<ProgramStudt ?ttagister <Pl!luiitfW~ ~atik(l

iProgram lPasSa.(IIrj(ltUl VnweTsl/.as.:>mv9aJa

•••••••••••• ' ••••• 111•••••• 1 •• , ••••••• X.9 f2002}--------------------------------------

(321 )

~

(1)

I(21).r:-.

(312)

~

,I"

(4321) (4231) (4213) (4312) (4132) (4123)

Gambar-2 Pohon Pembangkit untuk pennutasi 4 dengan siklus

Jika simpul dari pohon pembangkit gambar-2 diberi label sesuai dengan banyaknya anak cabang, makapohon pembangkit untuk pennutasi n dengan siklus dapat ditulis dalam aturan suksesi berikut:

{

O)

Q= (1) H (2)(k) H (k+l)k

(4)

Berdasarlcan aturan suksesi (4) maka fungsi pembangkit untuk aturan suksesi tersebut adalah

I« = Lf.x. =1+x+2.xl +2.3x3 + ... +n!x"n~ .

5. Simpulan

Pohon pembangkit permutasi n dengan satu siklus panjang n pada makalah ini menunjukkankekonsistensian dengan enumerasi tanpa pohon pembangkitan, yang menunjukkan bahwa pohon dapatdigunakan untuk membangkitkan semua pennutasi n dengan siklus.

Langkah selanjutnya yang perlu dikembangkan dari basil pada makalah ini adalah analisa algoritmapembangkitan dengan pohon pembangkit ini untuk mengetahui apakah tahapan-pembangkitan cu......upefektif, 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 untuk menunuskan pohon pembangkitpennutasi untuk sembarang m siklus.

Acknowledgment

Terimakasih saya ucapkan pada Prof. Vajnovszki yang memberikan ide penelitian, dan tak Iupa padaPimpinan Universitas Gunadarma yang memungkinkan makalah ini dihadirkanpada KonferensiMatematika Nasional XIV 2008 Palembang.

Daftar Pustaka

[1] [Ban07] C. Banderier, dkk, Generating Functions for Generating Trees, arXiv:math.CO/_ 0702753vl, 25 Feb 2007

I [2J [Ber07] A. Bernini, I. Fanti, E Grazzini, An exhaustive generation algorithm for Catalan objectsand 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. An Introduction to Enumeration and GraphTheory. New Jersey, War Scientific, 2002.

279Cftngr •• Sttufi 9Jl.tJAisfer(pnu['ufiftan ~M4tnnatik.atPrOlJrdm CPluCilsorjann 'Universitas Srr-..I!ijay!

ti [5] [Duc07] E. Duchi, ECO method and Object Grammars: two methods for tire enumeration ofcombinatorial objects. Dottorato di Ricerea in Ingegneria Informatica e deU'Automazione, XVCiclo, Universit_a Degli 8tudi di Firenze, htto:/Iwww.dsi.unifi-itIDRIIA/RaccoltaTesilDuchLdiunduh: 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, Catalan like numbers and succession rules,arXiv:math.CO/0507210vI, 11 July 2005.

[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 LyndonWords Case. Lecture Notes. Jakarta, 26 January 2006.

[11] [Wes96] J. West, Generating Trees and Forbidden Subsequenceshtto:llciteseerx.ist.psu.edulshQwciting;jsessionid= 1CEE9AO113F2F48EF4334245C6A5~BED?cid=1531l4.1996

280lJ>roaram Studi 9rt.agister fJ>m4ufi~n901.atemati~,g.

tProgram tJ?a...(;(;Q...w.Yjtu!~ ,,-1;;£:;::'!i~!!S.5~'..t~