interpretasi kombinatorial bilangan euler

INTERPRETASI KOMBINATORIAL BILANGAN EULER

TESIS

Oleh

REKTOR SIANTURI

127021033/MT

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAMUNIVERSITAS SUMATERA UTARA

MEDAN

2014

Universitas Sumatera Utara


T E S I S

Diajukan Sebagai Salah Satu SyaratUntuk Memperoleh Gelar Magister Sains dalam

Program Studi Magister Matematika padaFakultas Matematika dan Ilmu Pengetahuan Alam


OlehREKTOR SIANTURI

127021033/MT

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAMUNIVERSITAS SUMATERA UTARA

MEDAN

2014


Judul Tesis : INTERPRETASI KOMBINATORIAL BILANGANEULER

Nama Mahasiswa : Rektor SianturiNomor Pokok : 127021033Program Studi : Magister Matematika

Menyetujui,Komisi Pembimbing

(Prof. Dr. Saib Suwilo, M.Sc) (Prof. Dr. Opim Salim S, M.Sc)Ketua Anggota

Ketua Program Studi Dekan

(Prof. Dr. Herman Mawengkang) (Dr. Sutarman, M.Sc)

Tanggal lulus: 22 Desember 2014


Telah diuji pada

Tanggal : 22 Desember 2014

PANITIA PENGUJI TESIS

Ketua : Prof. Dr. Saib Suwilo, M.Sc

Anggota : 1. Prof. Dr. Opim Salim S, M.Sc

2. Prof. Dr. Herman Mawengkang

3. Dr. Esther Nababan, M.Sc


PERNYATAAN


T E S I S

Saya mengakui bahwa tesis ini adalah hasil karya sendiri, kecuali beberapa kutipan

dan ringkasan yang masing-masing dituliskan sumbernya.

Medan, Desember 2014

Penulis,

Rektor Sianturi

iUniversitas Sumatera Utara

ABSTRAK

Kombinatorial bilangan Euler ialah suatu proses yang menghitung banyaknya alter-natif permutasi dari himpunan bilangan dengan jumlah genap. Interpretasi kombi-natorial bilangan Euler membutuhkan pemahaman dasar mengenai penurunan (de-scent) dan kenaikan (ascent) dalam permutasi. Beberapa artikel dan buku memba-has tentang bilangan Euler, kombinatorial bilangan Euler, barisan bilangan Euler,bentuk umum bilangan Euler dengan berbagai metode. Dalam penelitian ini akanmembahas lebih lanjut bagaimana bentuk umum interpretasi kombinatorial bila-ngan Euler yang didefinisikan pada progres aritmatika umum a, a + d, a + 2d, . . .kemudian membentuk algoritmanya.

Kata kunci: Bilangan Euler, Kombinatorial, Permutasi.

iiUniversitas Sumatera Utara

ABSTRACT

Combinatorial of Euler numbers is a process that count permutation alternative ofa set which has even numbers. Interpretation of combinatorial Euler numbers needa basic knowledge about descent and ascent in permutation. Some articles had ex-plained about Euler traditional number, Euler number sequence, and general Eulernumber in several method. In this research will explain why general combinatorialEuler number in general aritmethic a, a + d, a + 2d, . . . needed and then make analgorithm of the process.

Keywords: Euler number, Combinatorial, Permutation.

iiiUniversitas Sumatera Utara

KATA PENGANTAR

Puji syukur kepada Tuhan Yang Maha Esa yang selalu memberikan kesem-

patan, kesehatan dan keselamatan yang luar biasa sehingga penulis dapat menyele-

saikan tesis dengan judul: INTERPRETASI KOMBINATORIAL BILANGAN EU-

LER. Penulis menyampaikan terima kasih kepada :

Bapak Prof. Dr. dr. Syahril Pasaribu, DTM&H, M.Sc(CTM), Sp.A(K) selaku

Rektor Universitas Sumatera Utara.

Bapak Dr. Sutarman, M.Sc, Dekan Fakultas Matematika dan Ilmu Pengetahuan

Alam Universitas Sumatera Utara, yang telah memberikan kesempatan kepada penu-

lis untuk mengikuti Program Magister Matematika di FMIPA Universitas Sumatera

Utara.

Bapak Prof. Dr. Herman Mawengkang, Ketua Program Studi Magister Matemati-

ka FMIPA Universitas Sumatera Utara sekaligus sebagai Pembanding I yang telah

memberikan kesempatan serta saran kepada penulis dalam penulisan tesis ini.

Bapak Prof. Dr. Saib Suwilo, M.Sc, selaku Sekretaris Program Studi Magister

Matematika FMIPA Universitas Sumatera Utara sekaligus Pembimbing I yang telah

memberikan bimbingan dan arahan terhadap penulisan tesis ini.

Bapak Prof. Dr. Opim Salim S, M.Sc, Pembimbing-II yang telah memberikan

bimbingan dan arahan terhadap penulisan tesis ini.

Ibu Dr. Esther Nababan, M.Sc selaku Pembanding-II yang memberikan saran dan

kritik dalam penyempurnaan tesis ini.

Seluruh Staf Pengajar pada Program Studi Magister Matematika FMIPA USU yang

telah banyak memberikan ilmu pengetahuan selama masa perkuliahan.

Kak Misiani, S.Si selaku Staf Administrasi Program Studi Magister Matematika

FMIPA USU yang telah banyak memberikan pelayanan yang baik kepada penulis

selama mengikuti perkuliahan.

ivUniversitas Sumatera Utara

Seluruh keluarga, khususnya ibunda tercinta Selma Silitonga yang senantiasa men-

dukung dan mendoakan untuk keberhasilan penulis dalam menyelesaikan pendidikan

ini.

Kepada semua teman teman serta semua pihak yang tidak dapat disebutkan

satu persatu penulis ucapkan terimakasih atas bantuan dan dorongan yang telah

diberikan sehingga penulis dapat menyelesaikan pendidikan tepat waktu.

Penulis menyadari bahwa tesis ini masih jauh dari sempurna, untuk itu penulis

mengharapkan kritik saran untuk penyempurnaan tesis ini. Semoga tesis ini dapat

bermanfaat bagi pembaca dan pihak-pihak lain yang memerlukannya. Terimakasih.

Medan, Desember 2014

Penulis,

Rektor Sianturi

vUniversitas Sumatera Utara

RIWAYAT HIDUP

Penulis dilahirkan di Pansur pada tanggal 26 mei 1981, sebagai anak keenam

dari 7 bersaudara dari ayah almarhum Mustar Sianturi dan ibu Selma Silitonga.

Penulis menamatkan Sekolah Dasar Inpres Pansur pada tahun 1993, Sekolah Me-

nengah Pertama Swasta HKBP Tanah Jawa pada tahun 1996, Sekolah Menengah

Atas Swasta Dharma Bakti pada tahun 1999, dan pada tahun 1999 melanjutkan

pendidikan di Universitas HKBP Nommensen, Fakultas Keguruan dan Ilmu Pen-

didikan Jurusan Pendidikan Matematika dan lulus pada tahun 2004. Dari tahun

2005 sampai dengan sekarang, penulis menjadi staf pengajar di Yayasan Pendidikan

Teladan Pematangsiantar dan pada tahun 2010 sampai sekarang, penulis menjadi

staf pengajar di Sekolah Menengah Atas Negeri 5 Pematangsiantar. Pada tahun

2013 penulis mengikuti pendidikan pada program studi Magister Matematika Seko-

lah Pasca Sarjana Universitas Sumatera Utara.

viUniversitas Sumatera Utara

DAFTAR ISI

Halaman

PERNYATAAN i

ABSTRAK ii

ABSTRACT iii

KATA PENGANTAR iv

RIWAYAT HIDUP vi

DAFTAR ISI vii

BAB 1 PENDAHULUAN 1

1.1 Latar Belakang 1

1.2 Perumusan Masalah 2

1.3 Tujuan Penelitian 3

1.4 Manfaat Penelitian 3

1.5 Metode Penelitian 3

BAB 2 TINJAUAN PUSTAKA 4

BAB 3 KOMBINATORIAL DAN BILANGAN EULER 6

3.1 Teori Kombinatorial 6

3.1.1 Kaidah dasar menghitung kombinatorial 7

3.1.2 Prinsip inklusi-eksklusi 8

3.1.3 Permutasi 9

3.1.4 Kombinasi 10

3.1.5 Interpretasi kombinasi 10

3.1.6 Permutasi dan kombinasi bentuk umum 11

3.1.7 Penurunan (Descent) 11

viiUniversitas Sumatera Utara

3.1.8 Bilangan Euler 13

3.1.9 Fungsi pembangkit dan bilangan Euler 17

3.1.10 Barisan bilangan Euler 17

BAB 4 KOMBINATORIAL BILANGAN EULER DAN INTERPRETASINYA 19

4.1 Kombinatorial Bilangan Euler 19

4.1.1 Interpretasi kombinatorial bilangan Euler umum 20

4.2 Hasil Penelitian 26

4.3 Algoritma Interpretasi Kombinatorial Bilangan Euler 27

BAB 5 KESIMPULAN 29

DAFTAR PUSTAKA 30

viiiUniversitas Sumatera Utara

ABSTRAK

Kombinatorial bilangan Euler ialah suatu proses yang menghitung banyaknya alter-natif permutasi dari himpunan bilangan dengan jumlah genap. Interpretasi kombi-natorial bilangan Euler membutuhkan pemahaman dasar mengenai penurunan (de-scent) dan kenaikan (ascent) dalam permutasi. Beberapa artikel dan buku memba-has tentang bilangan Euler, kombinatorial bilangan Euler, barisan bilangan Euler,bentuk umum bilangan Euler dengan berbagai metode. Dalam penelitian ini akanmembahas lebih lanjut bagaimana bentuk umum interpretasi kombinatorial bila-ngan Euler yang didefinisikan pada progres aritmatika umum a, a + d, a + 2d, . . .kemudian membentuk algoritmanya.

Kata kunci: Bilangan Euler, Kombinatorial, Permutasi.

iiUniversitas Sumatera Utara

ABSTRACT

Combinatorial of Euler numbers is a process that count permutation alternative ofa set which has even numbers. Interpretation of combinatorial Euler numbers needa basic knowledge about descent and ascent in permutation. Some articles had ex-plained about Euler traditional number, Euler number sequence, and general Eulernumber in several method. In this research will explain why general combinatorialEuler number in general aritmethic a, a + d, a + 2d, . . . needed and then make analgorithm of the process.

Keywords: Euler number, Combinatorial, Permutation.

iiiUniversitas Sumatera Utara

BAB 1

PENDAHULUAN

1.1 Latar Belakang

Dalam teori bilangan, bilangan Euler merupakan sebarisan bilangan bulat En yang

didefinisikan melalui ekspansi deret Taylor:

1

cosh t=

2

et + e−t=

∞∑

n=0

En

n!.tn, (1.1)

dengan cosh t adalah kosinus hiperbolik. Bilangan Euler pada umumnya muncul

sebagai suatu nilai khusus dari polinomial Euler. Selain itu, bilangan Euler juga

muncul dalam bentuk kombinatorik.

Kombinatorial (Combinatoric) adalah cabang matematika yang mempelajari

pengaturan objek-objek tanpa harus mengenumerasi terlebih dahulu. Solusi yang

ingin diperoleh adalah jumlah cara pengaturan objek-objek tertentu di dalam him-

punannya. Pengaturan yang dimaksud adalah bagaimana objek-objek dapat di-

kombinasikan dalam bebagai susunan atau urutan yang menghasilkan output yang

berbeda. Konsep kombinatorial yang digunakan dalam penelitian ini salah satunya

adalah permutasi.

Permutasi adalah salah satu bentuk umum dari kombinatorial. Permutasi r

dari n elemen adalah jumlah kemungkinan urutan r buah elemen yang dipilih dari

n buah elemen, dengan r ≤ n, yang dalam hal ini, pada setiap kemungkinan urutan

tidak ada elemen yang sama. Selain itu, terdapat pula bentuk permutasi yang lebih

khusus yaitu kombinasi. Kombinasi r elemen dari n elemen, atau C(n, r), adalah

jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen.

Dalam kaitannya dengan kombinatorik, bilangan Euler muncul khusus ketika

menghitung banyaknya alternatif permutasi dari himpunan bilangan dengan jumlah

genap. Interpretasi kombinatorial bilangan Euler dapat diperoleh setelah memahami

pengertian penurunan (descent) dalam permutasi. Misalkan p = p1, p2, p3, . . . , pn

adalah sebuah permutasi, i dikatakan suatu penurunan (descent) dari p jika pi >

1Universitas Sumatera Utara

2

pi+1, hal yang sama juga berlaku i dikatakan naik (ascent) jika pi < pi+1. Descent

menotasikan posisi p bukan entri dari p (Bona, 2004).

Dalam Xiong et al., 2014, jika diberikan n bilangan bulat positif, Ωn didefinisi-

kan sebagai himpunan semua permutasi [n] = 1, 2, . . . , n. Untuk sebuah permutasi

π = p1p2p3 . . . pn ∈ Ωn, i dikatakan menaik (ascent) dari π jika pi < pi+1; i disebut

terlampau lemah dari π jika pi ≥ i.

Bilangan Euler kuno, An,k telah dikenal sebagai banyaknya permutasi π ∈ Ωn

yang memiliki k lampauan lemah dan An,k memenuhi rekurensi berikut (Xiong et

al., 2014):

An,1 = 1, (n ≥ 1), An,k = 0(k > n),

An,k = kAn−1,k + (n + 1 − k)An−1,k−1 (1.2)

Sejak tahun 1950an, Carlitz [3, 4] dan timnya telah melakukan hasil general-

isasi bilangan Euler ke dalam q-barisan 1, q, q2, q3, . . .. Peneliti bertujuan ingin

mengulas penelitian yang dilakukan oleh Xiong et al., (2014) yang menggeneralisasi

bilangan Euler ke dalam bentuk progres aritmatika

a, a + d, a + 2d, a + 3d, . . . . (1.3)

Berdasarkan persamaan (1.3), penelitian ini mengulas bagaimana bentuk kom-

binatorial bilangan Euler dan cara menginterpretasikannya sesuai penelitian terdahu-

lu yang dilakukan oleh Xiong et al., (2014). Oleh karena penelitian terdahulu masih

sulit untuk dipahami bagaimana proses interpretasi kombinatorial bilangan Euler

secara jelas, peneliti juga mengajukan suatu rangkaian algoritma sebagai solusinya.

1.2 Perumusan Masalah

Pada penelitian terdahulu interpretasi kombinatorial bilangan Euler masih sangat

sulit dipahami, karena itu peneliti mengajukan sebuah algoritma interpertasi kom-

binatorial bilangan Euler.


3

1.3 Tujuan Penelitian

Menguraikan proses dan membentuk algoritma interpretasi kombinatorial bilangan

Euler.

1.4 Manfaat Penelitian

Memperkaya literatur tentang kombinatorial dengan adanya kombinatorial bilangan

Euler. Selain itu, pembaca mampu memahami bagaimana proses dan interpretasi

kombinatorial bilangan Euler.

1.5 Metode Penelitian

Metode penelitian ini bersifat literatur dan kepustakaan dengan mengumpulkan

informasi dari beberapa jurnal. Langkah-langkah yang dilakukan adalah sebagai

berikut:

1. Menguraikan prinsip-prinsip dasar kombinatorial khususnya permutasi.

2. Mengulas proses kombinatorial bilangan Euler.

3. Memberikan interpretasi kombinatorial bilangan Euler.


BAB 2

TINJAUAN PUSTAKA

Bilangan Euler pertama kali diperkenalkan oleh Leonhard Euler yang dimulai dengan

deret geometri∞

∑

k=1

xk =x

1 − x, (2.1)

konvergen untuk semua |x| < 1. Jika dilakukan diferensial berulang dan mengalikan-

nya dengan x maka akan memberikan barisan identitas

∞∑

k=1

k xk =x

(1 − x)2 (1)

∞∑

k=1

k2 xk =x

(1 − x)3 (1 + x)

...

∞∑

k=1

km xk =x

(1 − x)m+1

m−1∑

n=0

E(m, n) xn.

Oleh karena itu, penjabaran rumus tersebut menunjukkan bahwa bilangan Euler

memiliki banyak aplikasi dalam kombinatorial.

Kombinatorial bilangan Euler ialah suatu proses yang menghitung banyak-

nya alternatif permutasi dari himpunan bilangan dengan jumlah genap. Interpretasi

kombinatorial bilangan Euler membutuhkan pemahaman dasar mengenai penurunan

(descent) dan kenaikan (ascent) dalam permutasi. Beberapa artikel dan buku mem-

bahas tentang bilangan Euler, kombinatorial bilangan Euler, barisan bilangan Euler,

bentuk umum bilangan Euler dengan berbagai metode.

Sebelum adanya bilangan Euler, Bernoulli (1713) telah memperkenalkan bila-

ngan Bernoulli B2r(B2r+1 − 0 untuk r ≥ 1) untuk mengevaluasi jumlah pangkat n

dari m bilangan bulat pertama. Dua dekade kemudian, Euler (1736) mempelajari

penjumlahan alternatifm∑

i=1

(−1)iin hingga membentuk suatu polinomial yang disebut

dengan polinomial Euler (Xiong et al., 2013).


5

Penelitian tentang bilangan Euler kemudian dikembangkan oleh Carlitz (1954)

yang mempelajari bilangan Bernoulli dan bilangan Euler. Penelitiannya dilanjutkan

dengan meneliti kombinatorial sifat q-bilangan Euler.

Selanjutnya Stanley (1996) mengeluarkan buku yang berisi tentang prinsip-

prinsip dasar dalam kombinatorik enumerasi yang memiliki kendala pada perhi-

tungan banyaknya himpunan berhingga disusul oleh Bona (2004) yang mengulas

kombinatorial dari permutasi-permutasi. Dalam buku yang ditulis Bona terdapat

penjabaran mengenai descent, permutasi dan bilangan Euler.

Tiga tahun belakangan, Khattri dan Witkowski (2012), (Xiong et al., 2013),

dan (Xiong et al., 2014) masing-masing mengembangkan penelitian tentang bilangan

Euler. Khattri dan Witkowski (2012) melakukan investigasi pada beberapa rata-rata,

interpolasi antara aritmatika, geometrik, dan rata-rata harmonik serta mencari suatu

perubahan konvergen yang terbaik dari bilangan Euler. (Xiong et al., 2013) mencari

bentuk umum bilangan Euler dan polinomial Euler. Setahun kemudian (Xiong et

al.,(2014) menjabarkan bentuk kombiatorial bilangan Euler kemudian memberikan

interpretasi terhadap kombinatorial bilangan Euler tersebut.

Penelitian ini berhubungan dengan penelitian yang dilakukan oleh (Xiong et

al.,(2013, 2014). Penelitian dilakukan dengan mengulas bentuk kombinatorial bila-

ngan Euler terlebih dahulu, bagaimana proses pembentukan kombinatorial bilangan

Euler kemudian mengulas interpretasi bilangan Euler. Oleh karena itu, penelitian ini

juga bertujuan agar pembaca memahami bagaimana kombinatorial bilangan Euler

dan interpretasinya.


BAB 3

KOMBINATORIAL DAN BILANGAN EULER

3.1 Teori Kombinatorial

Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan

objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya. Kombi-

natorial. Solusi yang ingin diperoleh adalah jumlah cara pengaturan objek-objek

tertentu di dalam himpunannya.

Proses enumerasi atau pencacahan pengaturan yang memungkinkan sekumpu-

lan objek merupakan cara untuk mendapatkan jumlah pengaturan yang mungkin

dibuat dari sekumpulan objek tersebut. Cara enumerasi adalah cara yang paling mu-

dah dan sederhana, namun dalam penerapannya, metode enumerasi membutuhkan

banyak waktu dan usaha lebih besar ketika metode ini digunakan untuk menyele-

saikan persoalan-persoalan dengan jumlah objek yang tidak sedikit. Dengan metode

ini juga sulit untuk mendapatkan hasil dengan ketelitian yang tepat. Oleh karena

itu, diperlukan suatu metode yang lebih efektif untuk melakukan penghitungan ke-

mungkinan pengaturan objek yang jumlahnya banyak. Kombinatorial adalah cara

yang tepat untuk mengatasi masalah tersebut.

Dengan penghitungan kombinatorial, banyaknya kemungkinan pengaturan se-

jumlah objek dalam himpunannya yang dapat diperoleh tanpa harus mencacah setiap

kemungkinan jawabannya satu per satu. Meskipun kombinatorial tetap tidak ter-

lepas dari dilakukannya enumerasi atau pencacahan pada setiap kasus, namun kom-

binatorial akan menjadi sangat membantu dalam penyelesaian berbagai persoalan,

khususnya untuk pengaturan sejumlah objek yang banyak.

Kombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan, di-

mana percobaan itu sendiri adalah proses fisik yang hasilnya dapat diamati. Beber-

apa contoh persoalan yang dapat dipecahkan dengan kombinatorial ini diantaranya

adalah menghitung jumlah kemungkinan sandi-lewat (password) yang bisa dicoba

untuk menyusup masuk sebuah sistem komputer dan menghitung peluang terjadinya

suatu kejadian.


7

3.1.1 Kaidah dasar menghitung kombinatorial

Di dalam kombinatorial, hal yang harus dilakukan adalah menghitung semua ke-

mungkinan pengaturan objek. Untuk memudahkan penghitungan tersebut, terdapat

dua kaidah dasar yang digunakan sebagai teknik menghitung dalam kombinatorial.

Dua kaidah tersebut adalah kaidah perkalian (rule of product) dan kaidah penjum-

lahan (rule of sum). Kedua kaidah ini dapat digunakan untuk memecahkan banyak

persoalan menghitung.

1. Kaidah perkalian (rule of product)

Jika percobaan 1 menghasilkan p kemungkinan jawaban, percobaan 2 meng-

hasilkan q kemungkinan jawaban, maka apabila percobaan 1 dan percobaan 2

dilakukan, terdapat p × q hasil percobaan (menghasilkan kemungkinan p × q

jawaban).

2. Kaidah penjumlahan (rule of sum)

Jika percobaan 1 menghasilkan p kemungkinan jawaban, percobaan 2 meng-

hasilkan q kemungkinan jawaban, maka apabila hanya satu percobaan di-

lakukan (percobaan 1 atau percobaan 2), terdapat p+ q kemungkinan jawaban

yang mungkin terjadi.

Kata ’dan’ dan kata ’atau’ adalah kata kunci untuk mengidentifikasikan apakah

suatu persoalan diselesaikan dengan kaidah perkalian atau penjumlahan. Kaidah

perkalian menyatakan bahwa kedua percobaan dilakukan secara simultan atau serem-

pak, sedangkan pada kaidah penjumlahan, kedua percobaan dilakukan secara tidak

simultan. Kaidah perkalian dan kaidah penjumlahan tersebut juga dapat diperluas

sehingga mengandung lebih dari dua buah percobaan. Misalkan ada n percobaan,

masing-masing dengan hasil π, maka hasil yang mungkin adalah:

p1, p2, . . . , pn (3.1)

untuk kaidah perkalian.

p1+p2+ . . . +pn (3.2)

untuk kaidah penjumlahan.


8

Contoh:

Permasalahannya adalah misal terdapat 5 angka 1, 2, 3, 4, 5. Berapa jumlah ke-

mungkinan untuk membentuk 3 angka dari 5 angka tersebut? Penyelesaian dari

persoalan tersebut dapat dibagi menjadi dua. Yang pertama jika dari 5 angka terse-

but tidak boleh ada pengulangan ataukan boleh ada pengulangan. Jika tidak boleh

ada pengulangan maka penyelesaiannya adalah: Dengan kaidah perkalian: (5)(4)(3)

= 120 buah Dengan rumus permutasi P(5, 3) = 5!/(5-3)! = 120 buah.

3.1.2 Prinsip inklusi-eksklusi

Dalam Kombinatorial juga terdapat prinsip inklusi-eksklusi. Prinsip ini juga da-

pat digunakan untuk menyelesaikan persoalan kombinatorial. Prinsip inklusi dan

eksklusi merupakan perluasan ide dalam Diagram Venn beserta operasi irisan dan

gabungan, namun dalam pembahasan kali ini konsep tersebut diperluas dan diperkaya

dengan ilustrasi penerapan yang bervariasi dalam matematika kombinatorik. Ba-

nyaknya anggota himpunan gabungan antara himpunan A dan himpunan B meru-

pakan jumlah banyaknya anggota dalam himpunan tersebut dikurangi banyaknya

anggota di dalam irisannya. Dengan demikian,

|A ∪ B| = |A|+ |B| − |A ∩ B| (3.3)

Informasi terkecil yang dapat disimpan di dalam memori komputer adalah byte. Se-

tiap byte disusun oleh 8-bit. Berapa banyak jumlah byte yang dimulai dengan 11

atau berakhir dengan 11 ? Misalkan :

A = himpunan byte yang dimulai dengan 11

B = himpunan byte yang diakhiri dengan 11

C = himpunan byte yang berawal dan berakhir dengan 11

D = himpunan byte yang berawal dengan 11 atau berakhir dengan 11

Jumlah byte yang dimulai dengan 11 adalah 26 = 64 buah, karena 2 posisi pertama

sudah diisi dengan 11, sehingga cukup mengisi 6 posisi bit sisanya. Jadi |A| = 64 11

- - - - - - 8 bit. Jumlah byte yang diakhiri dengan 11 adalah 26 = 64 buah, Jadi |B|

= 64 - - - - - - 11. Jumlah byte yang berawal dan berakhir dengan 11 ada 24 = 16

buah, karena 2 posisi pertama dan 2 posisi terakhir sudah diisi dengan 11, sehingga

tinggal mengisi 4 posisi bit di tengah saja. Jadi |C| = 16 11 - - - - 11

Dengan menggunakan prinsip inklusi-eksklusi

|D| = |A| + |B| - |C| = 26 + 26 - 24 = 64 + 64 - 16 = 112 buah.


9

3.1.3 Permutasi

Dalam melakukan kaidah perkalian, terhadap perluasan-perluasan sesuai dengan per-

soalan yang dihadapi. Bentuk perluasan tersebut adalah permutasi dan kombinasi.

Permutasi adalah banyaknya urutan cara penempatan suatu objek. Contohnya,

mengurutkan pemain bernomor punggung 7, 8 dan 9. Jika mengenumerasi kemung-

kinan urutannya, maka akan didapat urutan berupa 789, 798, 879, 897, 978 dan 987.

Kemungkinan yang didapat adalah enam urutan.

Kemudian kemungkinan yang didapat jika akan memilih tiga pemain dari lima

pemain bernomor 5,6,7,8 dan 9 adalah terdapat lima kemungkinan untuk pemain

pertama, empat kemungkinan untuk pemain kedua, serta tiga kemungkinan untuk

pemain ketiga. Secara matematis, kemungkinannya dapat ditulis sebagai 5 x 4 x 3

= 60 kemungkinan. Dari persoalan tersebut, didapat suatu pola, yaitu :

Misalkan jumlah objek adalah n

Urutan pertama dipilih dari n objek

Urutan kedua dipilih dari n − 1 objek

Urutan ketiga dipilih dari n − 2 objek

...

Urutan ke r dipilih dari n − (r + 1) objek

Maka selanjutnya persoalan ini disebut permutasi dari n buah objek yang di-

ambil sebanyak r dan dinyatakan sebagai P (n, r) yang dapat direpresentasi secara

matematis sebagai berikut:

P (n, r) = n(n − 1)(n − 2)(n − (r + 1)) (3.4)

Dengan mengalikan kedua sisi terhadap (n − r)!, maka didapat:

P (n, r)(n − r)! = n! (3.5)

Sehingga didapat rumus dari permutasi, yaitu

P (n, r) =n!

(n − r)!(3.6)


10

3.1.4 Kombinasi

Kombinasi adalah merupakan suatu bentuk permutasi yang tidak memperhatikan

urutan. Misalnya dalam pemilihan tiga pemain bernomor punggung 7,8, dan 9,

urutan 789, 798, 879, 897, 978 dan 987 dianggap sama sebagai satu kemungkinan

kejadian.

Sehingga dalam pemilihan tiga pemain bernomor punggung 5,6,7,8 dan 9 terda-

pat 5 x 2 kemungkinan pemilihan pemain. Rumus kombinasi menyerupai permutasi,

hanya saja karena tidaka mempedulikan urutan, maka kejadian dengan anggota yang

sama namun urutan berbeda dianggap sebagai satu kejadian.

Secara matematis, jika terdapat suatu n objek dan dipilih r objek, maka terda-

pat r! kejadian dimana elemen pembentuk kejadian adalah sama, tetapi beda urutan.

Sehingga didapat rumus untuk mencari kombinasi kejadiannya sebagai berikut:

C(n, r) =n!

r!(n − r)!(3.7)

Persoalan kombinasi juga memiliki perluasan tersendiri, yaitu adanya teori kombinasi

dengan pengulangan. Jumlah kombinasi yang memperbolehkan adanya pengulangan

elemen, yaitu dari n buah objek untuk mengambil r buah objek dapat ditulis sebagai

berikut:

C(n + r − 1, r) = C(n + r − 1, n − 1) (3.8)

3.1.5 Interpretasi kombinasi

1. C(n, r) sama dengan menghitung banyaknya himpunan bagian yang terdiri

dari r elemen yang dapat dibentuk dari himpunan dengan n elemen. Dua atau

lebih himpunan bagian dengan elemen-elemen yang sama dianggap sebagai

himpunan yang sama meskipun urutan elemen-elemennya berbeda.

2. Persoalan kombinasi C(n, r) dapat dipandang sebagai cara memilih r buah

elemen dari n buah elemen yang ada, namun urutan elemen di dalam susunan

hasil pemilihan tidak penting.


11

3.1.6 Permutasi dan kombinasi bentuk umum

Misalkan terdapat n buah bola yang tidak seluruhnya berbeda warna (ada beberapa

bola berwarna sama) n1 bola di antaranya berwarna 1, n2 bola di antaranya berwarna

2,nk bola di antaranya berwarna k, dan n1 + n2 + . . . + nk = n. Berapa jumlah cara

pengaturan n buah bola ke dalam kotak-kotak tersebut (tiap kotak maksimal 1

buah bola)? Persoalan ini dapat diselesaikan dengan permutasi maupun kombinasi

menggunakan persamaan bentuk umum sebagai berikut:

P (n, r) = n(n − 1)(n − 2), . . . , (n − (r − 1)) =n!

(n − r)!(3.9)

3.1.7 Penurunan (Descent)

Urutan permutasi terbanyak dari semua n-permutasi ialah permutasi urutan menaik

1,2,3, . . . ,n. Namun, ada permutasi lain memiliki setidaknya beberapa ”gangguan”

didalamnya, misalnya, hal itu terjadi ketika sebuah entri segera diikuti dengan entri

yang lebih kecil didalamnya.

Teorema 3.1 Misalkan p = p1p2 . . .pn menjadi permutasi, maka i adalah penu-

runan dari p jika pi > pi + 1. Demikian pula, untuk i yang naik dari p jika pi < pi

+ 1.

Contoh: Misalkan p = 3412576. Kemudian 2 dan 6 adalah penurunan dari p, sedan-

gkan 1, 3, 4 dan 5 adalah naik dari p.

Perhatikan bahwa penurunan menunjukkan posisi dalam p, dan bukan entri

p. Himpunan semua penurunan dari pis disebut himpunan penurunan dari p dan

dinotasikan dengan D(p). Kardinalitas D(p), yaitu jumlah penurunan dari p, dilam-

bangkan dengan d(p), meskipun penulis tertentu lebih memilih des(p).

Gagasan yang sering muncul tentang penurunan ialah menghitung kombina-

torialnya. berapa banyak n-permutasi yang ada dengan sebuah angka menurun?

Berapa banyak n-permutasi yang ada dengan penurunan himpunan? Jika dua n-

permutasi memiliki himpunan yang sama penurunannya, atau jumlah yang sama

penurunan, apa sifat-sifat lainnya yang dibagi?


12

Jawaban atas pertanyaan-pertanyaan ini tidak selalau mudah, tetapi selalau

menarik. Dapat dimulai dengan masalah menemukan jumlah permutasi dengan

penurunan himpunan S. Ternyata bahwa lenih mudah untuk menemukan jumlah

permutasi penurunan himpunan dalam S.

Lemma 3.1 (Bona, 2004)

S = s1, s2, . . . , sn ⊆ [n-1] dan α(S) menjadi jumlah n-permutasi yang kumpulan

penurunannya terkandung dalam S, maka:

α(S) =(

ns1

) (

n−s1

s2−s1

) (

n−s2

s3−s2

)

. . .(

n−sk

n−sk

)

(3.10)

Bukti: Entri n ke segmen k + 1 sehingga segmen i bersama-sama berada pada en-

tri si untuk setiap i. Kemudian, dalam setiap segmen, ditempatkan entri n dalam

meningkatkan ketertiban. Maka satu-satunya tempat dimana permutasi yang diha-

silkan memiliki kesempatan untuk mendapat penurunan adalah dimana dua segmen

bertemu, yaitu, di s1, s2, . . ., sk. Oleh karena itu, set penurunan dari permutasi yang

dihasilkan terkandung dalam S. Banyak cara yang ada untuk mengatur entri di seg-

men tersebut Segmen pertama harus memiliki panjang s1, dan dapat dipilih dengan

cara(

ns1

)

. Segmen kedua harus panjang s2 − s1, dan harus memisah dari yang perta-

ma. Oleh karena itu, dapat dipilih dengan cara(

n−s1

s2−s1

)

. Secara umum, segmen saya

harus memiliki panjang si − si − 1 jika i < k + 1, dan harus dipilih dari ns tersisa

i−1 entri,(

n−si−1si−si−1

)

cara. Hanya ada satu pilihan bagi segmen terakhir karena semua

sisa entri n − sk harus pergi ke sana. Ini melengkapi bukti (Bona, 2004).

Teorema 3.2 (Bona, 2004)

S ⊆ [n-1] maka jumlah n-permutasi dengan keturunan himpunan S adalah:

β(S) =∑

T6S

(−1)|S−T |α(S) (3.11)

Bukti: Ini adalah kesimpulan langsung dari Prinsip inklusi-eksklusi. Perhatikan

bahwa permutasi jika diberikan h-elemen himpunan penurunan H dihitung dengan

ah =|S−H |∑

i=0

(−1)(

|S−H |i

)

= (1 + (−1))|S−H | di sisi sebelah kanan dari (1.1). Nilai ah

adalah 0 kecuali bila |SH| = 0, yaitu ketika S = H. Jadi jumlah sisi kanan justru

permutasi dengan mengatur penurunan S.


13

3.1.8 Bilangan Euler

Misalkan A(n,k) adalah banyaknya n-permutasi dengan k - 1 penurunan. Jika p

memiliki k - 1 penurunan, maka p merupakan gabungan k subbarisan dengan entri

menaik yang disebut kenaikan berjalan dari p. Dalam beberapa penelitian, A(n,k)

digunakan untuk menunjukkan jumlah permutasi dengan k penurunan.

Contoh: Terdapat tiga kenaikan (ascent) dari p = 2415367 yakni 24, 15, dan 367.

Permutasi k yang menaik sama dengan permutasi dengan k - 1 penurunan dan

dinotasikan dengan A(n,k) atau dengan notasi (nk) untuk A(n,k) dan A(n,k) disebut

bilangan Euler.

Teorema 3.3 (Xiong et al., 2013)

Untuk semua bilangan positif k dan n, (k 6 n) maka:

A(n, k + 1) = (k + 1)A(n − 1, k + 1) + (n − k)A(n − 1, k) (3.12)

Bukti:

Ada dua cara untuk mendapatkan n-permutasi p dengan k penurunan dari (n − 1)-

permutasi p dengan menyisipkan entri n ke p. p memiliki k penurunan dan meny-

isipkan n yang tidak membentuk penurunan baru, atau p memiliki k − 1 penurunan

dan menyisipkan n yang membentuk penurunan baru. Dalam kasus pertama, harus

menempatkan entri n diakhir p, atau harus memasukkan n antara dua entri yang

membentuk salah satu k penurunan dari p. Ini berarti k+1 harus ada pilihan untuk

posisi n. Seperti A(n − 1, k + 1) pilihan untuk p, yang pertama jangka waktu sisi

kanan dijelaskan. Dalam kasus kedua, harus menempatkan entri n di depan p, atau

harus masukkan n antara dua entri yang membentuk salah satu (n−2)−(k−1) yang

naik dari p. Ini berarti bahwa n − k pilihan untuk posisi n. Seperti yang telah kita

A(n− 1, k) pilihan untuk p, bagian kedua dari sisi kanan dijelaskan, dan teorema ini

terbukti.


14

Teorema 3.4 (Xiong et al., 2013) Jika A(0, 0) = 1 dan A(n, 0) = 0 untuk n > 0.

Dimana untuk semua n bilangan bulat yang tidak negatif, dan untuk semua x bilangan

real, maka:

xn =

n∑

k=1

A(n, k)(x+n−kn ) (3.13)

Teorema 3.5 (Xiong et al., 2013)

Untuk semua bilangan bulat non-negatif n dan k memenuhi k = n, diperoleh:

A(n, k) =k

∑

i=0

(−1)i(

n+1i

)

(k − 1)n (3.14)

Bukti (Teorema 3.5)

Misalkan ditulis k − 1 bar antara k bagian. Tempatkan setiap elemen [n] pada

tempatnya. Terdapat kn cara untuk melakukan hal ini, istilah dalam jumlah tersebut

diindeks oleh i = 0. Atur angka dalam setiap kompartemen dalam meningkatkan

ketertiban. Sebagai contoh, jika k=4 dan n = 9, maka salah satu pengaturan yang

237||19|4568 (3.15)

Untuk mendapatkan bar dpat dilakukan dengan mengabaikan (dalam contoh terse-

but, itu adalah 237194568) paling banyak k − 1 penurunan. Mungkin ada bagian

kosong, atau mungkin ada bagian tetangga tanpa penurunan. Menunjukkan bagaimana

untuk saringan keluar permutasi memiliki salah satu dari masalah ini, dan karena

itu, kurang dari k − 1 penurunan, pada saat yang sama.

Dikatakan bahwa bar asing jika:

1. Menghapus susunan legalnya, yaitu susunan yang setiap bagian terdiri dari

bilangan bulat dalam urutan naik,

2. Tidak diikuti oleh bar lain.

Pada persamaan (3.15), bar kedua merupakan bar asing. Tujuannya adalah untuk

menghitung susunan tanpa adanya bar asing, karena ini jelas di bijektif dengan

permutasi dengan penurunan k − 1.


15

Untuk melakukan hal ini, diterapkan prinsip inklusi dan eksklusi. Misalkan Bi

menjadi jumlah susunan dengan paling sedikit i bar asing, dan misalkan B menjadi

jumlah susunan tanpa bar asing. Rumus Prinsip Inklusi dan Eksklusi kemudian

menunjukan:

B = kn − B1 + B2 −B3 + . . . + (−1)nBn (3.16)

Misalkan menentukan B1. Susunan yang memiliki setidaknya satu bar asing

dapat diperoleh sebagai berikut, dengan menulis unsur-unsur [n] dengan k − 2 bar

di antara membentuk bagian k − 1. Kemudian menyisipkan bar asing di sebelah

kiri salah satu entri n, atau di akhir di n + 1. Hal ini menunjukkan bahwa B1 =

(n+11 )(k − 1)n

Satu-satunya perubahan adalah saat dimulai dengan k−3 bar dan pada bagian

k − 2, oleh karena itu harus memasukkan dua bar asing di akhir. Kelanjutan baris

ini diperoleh:

Bi = (n+ii )(k − i)n (3.17)

dan persamaan(3.16) diperoleh setelah mengganti nilai-nilai Bi kedalam persamaan

(3.17).

Lemma 3.2 (Xiong et al., 2013)

Jika Formula barisan Cauchy, misalkan x, y ∈ R, dan z ∈ Z maka diperoleh:

(

x+yz

)

=z

∑

d=0

(xd)

(

yz−d

)

(3.18)

Bukti:

Pertama asumsikan x dan y adalah bilangan bulat positif. Sisi kiri menghi-

tung banyaknya himpunan bagian yang terdiri dari z-elemen dari himpunan [x + y],

sedangkan sisi kanan menyebutkan objek-objek yang sama, berdasarkan ukuran dan

irisan dengan himpunan [x]. Untuk umum x dan y, perhatikan bahwa kedua belah

pihak dapat dipandang sebagai polinomial dalam x dan y, dan mereka setuju untuk

tak terhingga banyaknya nilai-nilai (bilangan bulat positif).


16

Bukti (Teorema 3.6):

Sebagai langkah pertama, pertimbangkan rumus persamaan (3.18) dengan x =

1, maka dengan x = 2, dan kemudian untuk x = i untuk i = k. Sehingga diperoleh:

1 = A(n, 1) (nn) (3.19)

2n = A(n, 2) (nn) + A(n, 1)

(

n+1n

)

(3.20)

dan seterusnya, h persamaan menjadi:

hn =h−1∑

j=0

A (n, k − j)(

n+j−1n

)

(3.21)

dan persamaan terakhir menjadi:

kn =k−1∑

j=0

A (n, k − j)(

n+j−1n

)

(3.22)

Sekarang akan menambahkan kelipatan tertentu ke persamaan yang terakhir, sehing-

ga sisi kiri menjadi sisi kanan rumus persamaan (3.22) untuk membuktikannya.

Untuk memulai, tambahkan (-1)(

n+11

)

kali (k− 1) ke persamaan yang terakhir.

Kemudian tambahkan(

n+12

)

kali persamaan (k−2) dengan yang terakhir. Lanjutkan

dengan cara ini, yaitu, pada langkah i, tambahkan (-1)(

n+11

)

kali persamaan (k − i)

dengan yang terakhir. sehingga diperoleh:

k∑

i=0

(−1)i(

n+1i

)

(k − i)n =k

∑

j=1

A(n, j)k−1∑

j=0

(

n+k−i−jn

) (

n+1i

)

(1)i (3.23)

Sisi kiri persamaan (3.23) sama dengan sisi kanan persamaan (3.23). Oleh

karena itu, persamaan(3.24) akan terbukti jika dapat menunjukkan bahwa koefisien

(n, j) dari A(n, j) di sisi kanan atas adalah 0 untuk j < k. Hal ini jelas bahwa suatu

(n, k)=1 sebagai A(n, k) terjadi pada persamaan terakhir.

Himpunan b = k − j. Kemudian (n, k) dapat diubah sebagai berikut:

a (n, k) =

b∑

i=0

(−1)i (n+1

i

) (

n−1+bn

)

(3.24)


17

Untuk sebarang x positif, (−xa ) = (x+a−1

a ) (−1)a maka (−1)b = (−1)b−2i, sehing-

gah diperoleh:

(−1)ba(n, k) =

b∑

i=0

(−1)−b−i(

n+11

) (

n−1+bn

)

=b

∑

i=0

(

n+11

) (

−1−nb−i

)

=(

0b

)

= 0 (3.25)

di mana langkah terakhir memegang sebagai b = k − j > 0, dan langkah

berikutnya-untuk-terakhir adalah aplikasi langsung dari rumus barisan Cauchy. Hal

ini menunjukkan bahwa sisi kanan (3.25) disederhanakan menjadi A(n, k), dan mem-

buktikan Teorema tersebut.

3.1.9 Fungsi pembangkit dan bilangan Euler

Berbagai fungsi pembangkit dari bilangan Euler memiliki beberapa sifat menarik,

namun akan hanya akan diuraikan yang sifat terbatas saja.

Definisi 3.1 Untuk semua bilangan bulat non-negatif n, polinomial:

An(x) =n

∑

k=1

A(n, k)xk (3.26)

disebut polinomial Euler berderajat n.

Teorema 3.6 Untuk semua bilangan bulat positif n, polinomial Euler berderajat n

memiliki deskripsi alternatif

An(x) = (1 − x)n+1∑

i>0

inxi (3.27)

Perhatikan bahwa Euler pertama kali didefinisikan polinomial An(x) dalam bentuk

seperti yang dituliskan pada persamaan (3.27).

3.1.10 Barisan bilangan Euler

Perhatikan nilai-nilai numerik bilangan Euler untuk n kecil, dan k = 0, 1, . . ., n − 1.

Baris ke-n pada segitiga Pascal berisi nilai-nilai A(n, k), untuk t1 6 k 6 n, sampai

dengan n = 6.

Barisan A(n, k) simetris untuk setiap n tetap. Selain itu, urutan pertama

meningkat terus, kemudian menurun terus. Sifat ini sangat penting dalam kombina-

torika.


18

Definisi 3.2 Urutan positif bilangan real a1, a2, . . ., an adalah unimodus jika ada

indeks k sehingga 1 6 k 6 n, a1 6 a2 6 . . . 6 ak > ak+1 > . . . 6 an

Barisan A(n, k)16k6n menjadi unimodus untuk setiap n tetap, bahkan, memi-

liki sifat yang lebih kuat.

Definisi 3.3 Menyatakan bahwa barisan bilangan real positif a1, a2, . . ., an adalah

log-konkaf ak−ak+1 6 a2k jika berlaku untuk semua indeks k = 1, . . ., n − 1.


BAB 4

KOMBINATORIAL BILANGAN EULER DAN INTERPRETASINYA

Penelitian tesis ini merupakan penelitian studi literatur mengenai kombinatorial dan

bilangan Euler, yang kemudian bilangan Euler dinyatakan dalam suatu kombina-

torial, yang disebut dengan kombinatorial bilangan Euler dan bagaimana interpre-

tasinya.

4.1 Kombinatorial Bilangan Euler

Sejak tahun 1950an, ahli matematika telah berhasil menginterpretasi bilangan-bi-

langan Euler kuno dan q-bilangan Euler secara kombinatorial. Kombinatorial bila-

ngan Euler dapat dipahami melalui tahapan definisi kenaikan (ascent), cara perhi-

tungan kenaikan (ascent) seperti pada Definisi 4.1 dan 4.2.

Definisi 4.1 Diberikan suatu bilangan bulat positif n, dan Ωn didefinisikan sebagai

himpunan semua permutasi dari [n] = 1, 2, 3, . . . , n. Pada suatu permutasi π =

p1p2p3 . . . pn ∈ Ωn, i disebut sebuah kenaikan (ascent) dari π jika pi < pi+1; i disebut

kelebihan yang lemah dari π jika pi ≥ i.

Perlu diketahui bahwa suatu bilangan Euler kuno An,k merupakan banyaknya

permutasi π ∈ Ωn yang mempunyai k buah kelebihan yang lemah (Riordan, 1958)

dan An,k memenuhi pengulangan:

An,1 = 1, (n ≥ 1), An,k = 0, (k > n),

An,k = kAn−1,k + (n + 1 − k)An−1,k−1(1 ≤ k ≤ n). (4.1)

Selain rumus rekursif pada persamaan (4.1), An,k dapat dihitung secara lang-

sung melalui rumus analitik berikut (Bona, 2004):

An,k =k−1∑

i=0

(−1)i(k − i)n

(

n + 1

i

)

(1 ≤ k ≤ n). (4.2)

Dalam setiap permutasi π, definisikan jumlah penurunan (descent) atau kenaikan

(ascent) sebagai:


20

Definisi 4.2 Diberikan suatu permutasi π = p1p2p3 . . . pn ∈ Ωn, definisikan fungsi

maj π =∑

pj>pj+1

j, (4.3)

a(n, k, i) = #π|maj π = i &π memiliki k kenaikan (ascents).

Sejak tahun 1950an, Carlitz (1954, 1975) telah membentuk generalisasi hasil pene-

litian Euler ke q-barisan 1, q, q2, q3, . . . . Berdasarkan definisi Carlitz, q-bilangan

Euler An,k(q) diberikan sebagai

An,k(q) = q(m−k+1)(m−k)/2

k(n−k−1)∑

i=0

a(n, n− k, i)qi, (4.4)

dimana fungsi a(n, k, i) didefinisikan dalam Definisi 4.2.

4.1.1 Interpretasi kombinatorial bilangan Euler umum

Konsep-konsep dan sifat-sifat yang digunakan untuk menginterpretasikan kombina-

torial bilangan Euler adalah sebagai berikut.

Definisi 4.3 Definisikan bahwa Ln,k adalah himpunan n permutasi dengan k kelebi-

han yang lemah. Selanjutnya didefinisikan |Ln,k| = An,k (yakni banyaknya n permu-

tasi dengan k kelebihan yang lemah sama dengan bilangan Euler kuno). Kemudian,

pada sebuah permutasi π = p1p2p3 . . . pn, misalkan Qn(π) = i dimana Pi = n.

Sebuah permutasi π ∈ Ωn, dapat ditulis sebagai sebaris π = p1p2p3 . . . pn, atau π

dapat juga ditulis sebagai gabungan yang saling lepas dari cycle-cycle yang berbe-

da. Jika π ditulis dalam suatu bentuk cycle, maka selanjutnya dapat menggunakan

representasi standar melalui penulisan (Stanley, 1996):

(a) Setiap cycle bermula dari elemen terbesarnya.

(b) Cycle berada dalam urutan naik dari elemen terbesarnya.

Penjelasan lengkapnya, jika diberikan permutasi π ditulis dalam suatu bentuk

cycle representasi standar, definisikan fungsi f sebagai f(π) menjadi permutasi yang


21

diperoleh dari π melalui penghapusan tanda kurung. Kemudian f dikenal sebagai

fungsi bijektif fundamental dari Ωn ke dirinya sendiri (Bona, 2004). Selain itu,

invers pemetaan f−1 dari fungsi bijektif fundamental f juga dikenal dalam ilustrasi

hubungan antara kenaikan (ascent) dan kelebihan lemahnya (Bona, 2004).

Proposisi 4.1 Fungsi f−1 memberikan bijeksi antara himpunan permutasi pada [n]

k kenaikan dan himpunan Ln,k+1 (Xiong et al., 2014).

Contoh: Representasi standard permutasi π = 5243716 adalah (2)(43)(7615) ∈ Ω7

dan f(π) = 2437615; Q7(π) = 5; π = 5243716 mempunyai 3 buah kenaikan, semen-

tara f−1(π) = (5243)(716) = 6453271 ∈ W7,4 mempunyai 3 + 1 = 4 kelebihan yang

lemah karena p1 = 6 > 1, p2 = 4 > 2, p3 = 5 > 3, dan p6 = 7 > 6.

Penjelasan contoh: sesuai dengan penjelasan dalam Stanley(1996), bahwa su-

atu permutasi dapat dituliskan dalam bentuk cycle standar sehingga π = 5243716

mempunyai salah satu permutasi (2)(43)(7615) (berbentuk cycle), masing-masing

cycle bermula dari elemen terbesarnya, perhatikan (43) dan (7615) bermula dari 4

dan 7. Selanjutnya, f(π) = 2437615 mempunyai f−1(π) = (5243)(716)(cycle) =

6453271 (tanda kurung dihapus). Permutasi 6453271 mempunyai 4 penurunan (de-

scent yaitu 6 ke 4, 5 ke 3, 3 ke 2, dan 7 ke 1. Selain itu, memiliki 4 kelebihan yang

lemah karena p1 = 6 > 1, p2 = 4 > 2, p3 = 5 > 3, dan p6 = 7 > 6.

Sekarang andaikan akan dibentuk barisan yang terdiri dari k bar vertikal dan

n bilangan bulat positif. Kemudian k bar vertikal membagi n bilangan bulat positif

tersebut ke dalam k + 1 bagian. Dalam setiap bagian, tidak terdapat satupun bila-

ngan atau terdapat semua bilangan yang didaftar dalam urutan menurun, perhatikan

Definisi 4.4 (Bona, 2004).

Definisi 4.4 Suatu bar disebut asing jika:

(a) Segera diikuti oleh bar yang lain, atau

(b) Setiap bagian sisa baik kosong atau berisi bilangan bulat berada dalam urutan

menurun jika bar ini dihapus.


22

Contoh: Misalkan n = 7, k = 4 maka susunannya sebagai berikut:

32|1||7654|,

bar pertama, kedua dan keempat saling asing.

Sehingga diperoleh interpretasi kombinatorial bilangan Euler An,k(a, d) dengan

catatan pertama bahwa

An,k =k−1∑

i=0

(−1)i[(k + 1 − i)d − a]n(

n + 1

i

)

(4.5)

menyiratkan bahwa An,k(a, d) merupakan polinomial homogen berderajat n yang

berhubungan ke a dan d. Selain itu,

An,k(a, d) =k

∑

i=0

(−1)i[(k + 1 − i)d − a]n

n + 1

i

=k

∑

i=0

(−1)i[(k + 1 − i)(d − a) + (k − i)a]n

n + 1

i

=n

∑

j=0

k∑

i=0

(−1)i(k + 1 − i)n−j(k − i)

n + 1

i

×(

nj

)

(d − a)n−jaj

=k

∑

i=0

Cn,k(j)(

nj

)

(d − a)n−jaj,

(4.6)

dimana

Cn,k(j) =

k∑

i=0

(−1)i[(k + 1 − i)n−j(k − i)j

(

n + 1

i

)

, (0 ≤ j ≤ n). (4.7)

Berikut penjelasan tentang interpretasi kombinatorial untuk koefisien Cn,k(j),(0 ≤

j ≤ n).

Andaikan bilangan Euler An,k(a, d) ditulis seperti pada persamaan (4.7), maka

Cn,k(j) = fπ ∈ Ln,k+1, (j < Qn(π) ≤ n) + fπ ∈ Ln,k, (1 < Qn(π) ≤ j). (4.8)

Persamaan (4.8) dapat dibuktikan untuk dua nilai j = 0 dan j = n adalah benar

sehingga diperoleh:

jika j = 0, Cn,k(0) =∑k

i=0(−1)i(k + 1 − i)n(

n+1i

)

= An,k+1;

jika j = n, Cn,k(n) =∑k

i=0(−1)i(k − i)n(

n+1i

)

= An,k.

Oleh karena itu, persamaan (4.8) benar untuk j = 0 dan j = n.


23

Secara umum, untuk (1 ≤ j ≤ n − 1), tuliskan k bar dengan k + 1 bagian

diantaranya. Tempatkan setiap elemen dari [n] ke dalam suatu bagian. Jika tidak

terdapat k bar asing, maka susunan dipasangkan ke permutasi dengan k kenaikan.

Misalkan B himpunan susunan dengan paling banyak satu bar asing pada bagian

ujung dan tidak terdapat bilangan bulat 1, 2, 3, . . . , j dalam bagian akhir. Akan

ditunjukkan bahwa Cn,k(j)=|B|.

Tujuan dapat tercapai dengan menggunakan Prinsip inklusi eksklusi. Ada

(k + 1)n−jkj cara meletakkan n bilangan ke dalam k + 1 bagian dengan elemen-

elemen 1, 2, 3, . . . , j yang menghindari bagian-bagian akhir.

Misal Bi menotasikan banyaknya susunan bilangan dengan ciri-ciri sebagai

berikut:

(1) Tidak ada 1, 2, 3, . . . , j dalam bagian akhir.

(2) Setiap susunan bilangan Bi paling sedikit memiliki satu bar asing.

(3) Dalam setiap susunan Bi, ada dua bar asing yang diletakkan tidak saling berse-

belahan satu sama lain.

Selanjutnya, Prinsip Inklusi dan Eksklusi menunjukkan bahwa:

|B| = (k + 1)n−jkj − B1 + B2 + . . . + (−1)kBk. (4.9)

Sekarang, pertimbangkan nilai Bi, dengan syarat (1 ≤ i ≤ k). Andaikan bahwa

ada k+1− i bagian dengan k− i bar diantaranya, sehingga ada (k+1− i)n−j (k− i)j

cara untuk memasukkan n bilangan ke dalam k +1− i bagian dengan menghindari j

bilangan bulat pertama masuk ke bagian akhir dan daftar komponen bilangan bulat

yang berada dalam urutan menurun. Kemudian masukkan i bar asing secara ter-

pisah ke dalam n + 1 posisi, sehingga diperoleh:

Bi = (k + 1 − i)n−j(k − i)j

(

n + 1

i

)

. (4.10)

Substitusi persamaan (4.10) ke dalam persamaan (4.9), maka diperoleh Cn,k(j) =

|B|.


24

Diberikan susunan π ∈ B, hapus bar sehingga diperoleh permutasi π ∈ Ω.

Oleh karena itu, hanya gunakan notasi yang sama yaitu π untuk merepresentasi

kedua susunan himpunan B dan permutasi pada [n]. Sekarang untuk π ∈ B, π yang

lain:

1. (Kasus 1) tidak terdapat bar asing dan 1, 2, 3, . . ., j tidak berada pada bagian

akhir atau

2. (Kasus 2) hanya ada satu bar asing di bagian akhir.

Jika π berada dalam kasus 1, maka π mempunyai k buah kenaikan karena setiap

bar tidak saling asing dan pada bagian akhir dari π tidak kosong. Oleh karena itu,

cycle akhir fungsi f−1(π) menjadi (n. . .pg). Dengan kata lain, Qn(f−1(π))= pg >

j karena tidak terdapat (1, 2, . . ., j) pada bagian akhir. Berdasarkan Proposisi 4.1

f−1(π) ∈ Ln,k+1.

Jika π berada dalam kasus 2, maka π mempunyai k− 1 kenaikan karena hanya

bar akhir yang asing. Dengan catatan bahwa dalam kasus ini, susunan dengan

tidak adanya elemen (1, 2, . . ., j) dalam bagian kedua ke bagian akhir atau bagian

akhir yang tidak kosong telah dihapus dengan menggunakan Prinsip inklusi-eksklusi.

Dengan arti yang sama, paling sedikit satu bilangan dari (1, 2, . . ., j) harus berada

dalam bagian kedua ke bagian akhir. Jadi, cycle akhir fungsi f−1(π) menjadi (n. . .pl)

dan Qn (f−1(π)) = pl ≤ j Berdasarkan Proposisi 4.1 f−1(π)∈ Ln,k.

Gabungan semua hasil pada kasus 1 dan 2, membuktikan persamaan (4.8)

benar.

Berikut menjelaskan beberapa sifat penting koefisien Cn,k.

Misal koefisien Cn,k seperti yang dituliskan pada persamaan (4.8), maka:

1.∑n

k=0 Cn,k(j) = n! untuk 0 ≤ j ≤ n

2. Cn,k(j) = Cn,n−k(n − j) untuk semua 0 ≤ j, k ≤ n


25

Koefisien Cn,k membutuhkan lemma persamaan (4.11) sebagai:

Lemma 4.1 (Xiong et al., 2014)

Jika terdapat n bilangan bulat positif maka:

fπ ∈ Ln,k&Qn(π) = j = fπ ∈ Ln,n+1−k&Qn(π) = n + 1 − j, (4.11)

dengan syarat 1 ≤ k, j ≤ n.

Pembuktian. Langkah awal, diberikan n bilangan bulat positif, didefinisikan fungsi

g : Ωn → Ωn sebagai berikut:

untuk π = p1, p2, . . ., pn ∈ Ωn,

g(n) = (n + 1 − p1)(n + 1 − p2). . .(n + 1 − pn) (4.12)

untuk tingkat pertama, π = 13452 ∈ Ω5, g(π) = 53214. g merupakan fungsi bijektif

dari Ωn ke fungsi tersebut.

Sekarang, untuk variabel tetap 1 ≤ k, j ≤ n, anggap Sk,j = π ∈ Wn,k & Qn(π)

= j dan Tk,j = π ∈ Wn,n+1−k & Qn(π) = n+1− j. Untuk sebarang π ∈ Sk,j tulis

π dalam bentuk representasi cycle standard. Jadi π = (pu. . .). . .(n. . .j) dan f(π) =

pu. . .n. . .j mempunyai (k−1) kenaikan (ascent). Sekarang komposisikan fungsi f(π)

dengan fungsi bijektif g terdefinisi. Kemudian g(f(π)) = n + 1 − pu. . .1. . .n + 1 − j

mempunyai (n− k) kenaikan yang mengakibatkan f−1g(f(π)) mempunyai n +1− k

kelebihan yang lemah sehingga f−1g(f(π)) ∈ Ln,n+1−k. Suatu catatan bahwa cycle

akhir f−1g(f(π)) telah menjadi (n. . .n + 1− j). Oleh karena itu, f−1g(f(π)) ∈ Tk,j.

Oleh karena kedua fungsi f dan g adalah fungsi bijektif, f−1gf juga bijektif antara

Sk,j dan Tk,j.

Dengan demikian, koefisien Cn,k yang∑n

k=0 Cn,k(j) = n! untuk 0 ≤ j ≤ n dan

Cn,k(j) = Cn,n−k(n − j) untuk semua 0 ≤ j, k ≤ n dapat dibuktikan dengan cara:

Langkah pertama, melalui persamaan (4.8), diperolehn

∑

k=0

Cn,k(j) =n

∑

k=0

fπ ∈ Ln,k+1, j < Qn(π) ≤ n

+

n∑

k=0

fπ ∈ Ln,k, 1 ≤ Qn(π) ≤ j

=

n∑

k=0

fπ ∈ Ln,k = |Ωn| = n!. (4.13)


26

Langkah kedua,

Cn,k(j) =n

∑

i=j+1

fπ ∈ Ln,k+1, Qn(π) = i +

j∑

m=1

fπ ∈ Ln,k, Qn(π) = m

=n

∑

i=j+1

fπ ∈ Ln,n−k , Qn(π) = n + 1 − i +

j∑

m=1

]π ∈ Ln,n+1−k,

Qn(π) = n + 1 − m

oleh Lemma 4.5 = fπ ∈ Ln,k, 1 ≤ Qn(π) ≤ n − j

+]π ∈ Ln,n+1−k , n − j < Qn(π) ≤ n = Cn,n−k(n − j). (4.14)

4.2 Hasil Penelitian

Berdasarkan ulasan-ulasan bilangan Euler dan kombinatorialnya yang telah dijabarkan

sebelumnya diperoleh bahwa bilangan Euler kuno An,k merupakan banyaknya per-

mutasi π ∈ Ωn yang mempunyai k buah kelebihan yang lemah (Riordan, 1958) dan

An,k memenuhi pengulangan:

An,1 = 1, (n ≥ 1), An,k = 0, (k > n),

An,k = kAn−1,k + (n + 1 − k)An−1,k−1(1 ≤ k ≤ n).

dapat dibentuk ke dalam suatu permutasi kemudian definisikan

maj π =∑

pj>pj+1

j.

Selanjutnya, gunakan representasi standar melalui penulisan setiap cycle bermu-

la dari elemen terbesarnya dan cycle berada dalam urutan naik dari elemen terbe-

sarnya. Perhatikan bar asing dengan aturan bahwa bar tersebut segera diikuti oleh

bar yang lain, atau setiap bagian sisa baik kosong atau berisi bilangan bulat berada

dalam urutan menurun jika bar ini dihapus. Oleh karena itu, diperoleh interpretasi

kombinatorial bilangan Euler umum sebagai:

An,k =k−1∑

i=0

(−1)i[(k + 1 − i)d − a]n(

n + 1

i

)


27

An,k(a, d) =k

∑

i=0

(−1)i[(k + 1 − i)d − a]n

n + 1

i

=k

∑

i=0

(−1)i[(k + 1 − i)(d − a) + (k − i)a]n

n + 1

i

=n

∑

j=0

k∑

i=0

(−1)i(k + 1 − i)n−j(k − i)

n + 1

i

×(

nj

)

(d − a)n−jaj

=k

∑

i=0

Cn,k(j)(

nj

)

(d − a)n−jaj,

dengan

Cn,k(j) =k

∑

i=0

(−1)i[(k + 1 − i)n−j(k − i)j

(

n + 1

i

)

, (0 ≤ j ≤ n).

Koefisien Cn,k mempunyai nilai∑n

k=0 Cn,k(j) = n! untuk 0 ≤ j ≤ n dan Cn,k(j) =

Cn,n−k(n − j) untuk semua 0 ≤ j, k ≤ n.

Hasil penelitian menunjukkan bahwa bilangan Euler dapat direpresentasikan

dalam bentuk kombinatorial, cycle, pemisahan bilangan dengan menggunakan bar

asing sehingga lebih mudah difahami.

4.3 Algoritma Interpretasi Kombinatorial Bilangan Euler

Interpretasi kombinatorial bilangan Euler yang telah dijabarkan sebelumnya, akan

lebih informatif jika dituangkan dalam suatu algoritma. Tujuannya ialah memu-

dahkan pemahaman bagaimana interpretasi kombinatorial bilangan Euler sehingga

algoritmanya ialah sebagai berikut;

Algoritma

Input: Permutasi Ωn = π = p1p2 . . . pn

Output: Interpretasi kombinatorial bilangan Euler

Langkah 1 : Definisikan An,k sebagai banyaknya permutasi π ∈ Ωn yang mempunyai k kelebihan

yang lemah.

Langkah 2 : Hitung maj π sebagai banyaknya penurunan (descent) dalam permutasi π


28

Langkah 3 : Gunakan representasi standar penulisan permutasi dalam bentuk cycle dimana

setiap cycle bermula dari elemen terbesarnya dan cycle berada dalam urutan naik

dari elemen terbesarnya.

Langkah 4 : Perhatikan adanya bar asing dengan aturan bahwa bar tersebut segera diikuti bar

lain, atau setiap bagian sisa baik kosong ataupun berisi, bilangan bulat berada dalam

urutan menurun jika bar ini dihapus

Langkah 5 : Diperoleh interpretasi kombinatorial bilangan Euler secara umum sebagai

An,k =k−1∑

i=0

(−1)i[(k + 1− i)d− a]n(

n + 1

i

)

Langkah 6 : Gunakan prinsip inklusi-eksklusi untuk menjabarkan Langkah 5 sehingga tujuan

akhir diperoleh.

Berdasarkan langkah-langkah algoritma tersebut, untuk mempermudah mema-

hami kombinatorial bilangan Euler dapat digunakan algoritma interpretasi kombi-

natorial bilangan Euler.


BAB 5

KESIMPULAN

Dalam tesis ini, penulis mengulas bentuk kombinatorial bilangan Euler, dimulai dari

pengulasan bilangan Euler kuno yang telah diteliti oleh ilmuwan terdahulu dan men-

uangkan hasil penelitian sebagai berikut:

1. Diperoleh interpretasi kombinatorial bilangan Euler secara umum:

An,k =k−1∑

i=0

(−1)i[(k + 1 − i)d − a]n(

n + 1

i

)

2. Untuk mempermudah memahami kombinatorial bilangan Euler dapat digu-

nakan algoritma interpretasi kombinatorial bilangan Euler.


DAFTAR PUSTAKA

Bona, M. 2004. Combinatorics of Permutations. Discrete Mathematics and its Appli-cations. Boca Raton: Chapman & Hall/CRC.

Carlitz, L. 1954. q-bernoulli and Eulerian Numbers. Transactions of the AmericanMathematical Society, 76: 332-350.

Carlitz, L. 1975. A Combinatorial property of q-Eulerian Numbers. The AmericanMathematical Monthly, 82: 51-54.

Khattri, S. K., dan Witkowski, A. 2012. Euler’s Number and Some Means*. TamsuiOxford Journal of Information and Mathematical Sciences, 28(4): 369-377.

Riordan, J. 1958. An Introduction to Combinatorial Analysis. Wiley Publications inMathematical Statistics. New York: John Wiley & Sons.

Stanley, R. P. 1996. Enumerative Combinatorics. Vol. 1 of Cambridge Studies inAdvanced Mathematics, Cambridge University Press, Cambridge, UK.

Xiong, T., Tsao, H. P., dan Hall, J. I. 2013. General Eulerian Numbers and EulerianPolynomials. Journal of Mathematics, Article ID 629132, 9 pages.

Xiong, T., Tsao, H. P., dan Hall, J. I. 2014. Combinatorial Interpretation of GeneralEulerian Numbers. Journal of Discrete Mathematics, Article ID 870596, 6 pages.


interpretasi kombinatorial bilangan euler

Documents