Download - 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
INTERPRETASI KOMBINATORIAL BILANGAN EULER
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
Universitas Sumatera Utara
OlehREKTOR SIANTURI
127021033/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAMUNIVERSITAS SUMATERA UTARA
MEDAN
2014
Universitas Sumatera Utara
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
Universitas Sumatera Utara
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
Universitas Sumatera Utara
PERNYATAAN
INTERPRETASI KOMBINATORIAL BILANGAN EULER
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.
Universitas Sumatera Utara
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.
Universitas Sumatera Utara
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).
4Universitas Sumatera Utara
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.
Universitas Sumatera Utara
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.
6Universitas Sumatera Utara
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.
Universitas Sumatera Utara
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.
Universitas Sumatera Utara
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)
Universitas Sumatera Utara
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.
Universitas Sumatera Utara
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?
Universitas Sumatera Utara
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.
Universitas Sumatera Utara
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.
Universitas Sumatera Utara
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.
Universitas Sumatera Utara
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).
Universitas Sumatera Utara
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)
Universitas Sumatera Utara
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.
Universitas Sumatera Utara
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.
Universitas Sumatera Utara
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:
19Universitas Sumatera Utara
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
Universitas Sumatera Utara
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.
Universitas Sumatera Utara
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.
Universitas Sumatera Utara
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|.
Universitas Sumatera Utara
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
Universitas Sumatera Utara
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)
Universitas Sumatera Utara
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
)
Universitas Sumatera Utara
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 π
Universitas Sumatera Utara
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.
Universitas Sumatera Utara
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.
29Universitas Sumatera Utara
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.
30Universitas Sumatera Utara