A. Keamanan Sistem Komputer dalam Bidang Transportasi dengan Algoritma Kriptografi Vigenere Cipher

Hubungan Keamanan Sistem Komputer dengan Algoritma Kriptografi Vigenere Cipher

 

Masalah keamanan data bagi organisasi atau perusahaan merupakan penting pada era informasi. Kerahasiaan data di perusahaan yang bergerak pada produksi, mendapat perhatian dari penulis untuk mengamankan data. Seharusnya data tersebut dapat dirahasiakan, berisi identitas pelanggan, yang didalamnya terdapat harga dan discount yang diberikan untuk pelanggan. Metode algoritma yang digunakan yaitu algoritma vigenere chipper. Keamanan data ini merupakan salah satu aspek yang sangat penting dalam penggunaan computer. Pemilik data tersebut tentunya ingin datanya aman terhadap gangguan dari berbagai tindakan yang tidak di inginkan, baik dari computer pribadi (PC) ataupun jaringan. Dalam kegiatan sehari-hari pelanggan adalah orang-orang yang kegiatannya membeli dan menggunakan suatu produk, baik barang maupun jasa, secara terus-menerus.

 Masalah keamanan komputer merupakan sesuatu yang sangat penting dalam era informasi ini terutama bagi suatu organisasi atau perusahaan. Kerahasiaan data Masalah keamanan komputer merupakan sesuatu yang sangat penting dalam era informasi ini terutama bagi suatu organisasi atau perusahaan. Kerahasiaan data merupakan sesuatu yang penting dalam keamanan data. Data pelanggan menjadi salah satu data yang sangat penting dalam kelangsungan berjalannya perusahaan. Keamanan merupakan bentuk tindakan untuk mempertahankan sesuatu hal dari berbagai macam gangguan dan ancaman. Aspek yang berkaitan dengan suatu keamanan dalam dunia komputer, antara lain: 

- Privacy/Confidentiality yaitu usaha menjaga  - informasi dari orang yang tidak berhak mengakses (menggaransi bahwa data pribadi tetap pribadi). 

- Integrity yaitu usaha untuk menjaga data atau sistem tidak diubah oleh yang tidak berhak. 

- Authentication yaitu usaha atau metoda untuk mengetahui keaslian dari informasi yang dikirim dibuka oleh orang yang benar (asli). 

- Availability berhubungan dengan ketersediaan sistem dan data (informasi) ketika dibutuhkan. Keamanan data ini merupakan salah satu aspek yang sangat penting dalam penggunaan komputer. Pemilik data tersebut tentunya ingin datanya aman terhadap gangguan dari berbagai tindakan yang tidak di inginkan, baik dari komputer pribadi (PC) ataupun jaringan.

 Kode vigènere termasuk kode abjad-majemuk (polyalphabetic substitution cipher). Dipublikasikan oleh diplomat (sekaligus seorang kriptologis) Perancis, Blaise de Vigènere pada abad 16, tahun 1586. Sebenarnya Giovan Batista Belaso telah menggambarkannya untuk pertama kali pada tahun 1533 seperti ditulis di dalam buku La Cifra del Sig. Algoritma ini baru dikenal luas 200 tahun kemudian dan dinamakan kode vigènere. Vigènere merupakan pemicu perang sipil di Amerika dan kode vigènere digunakan oleh Tentara Konfederasi (Confederate Army) pada perang sipil Amerika (American Civil War). Kode vigènere berhasil dipecahkan oleh Babbage dan Kasiski pada pertengahan abad 19. (Ariyus, 2008). Algoritma enkripsi jenis ini sangat dikenal karena mudah dipahami dan diimplementasikan. Teknik untuk menghasilkan ciphertext bisa dilakukan menggunakan substitusi angka maupun bujursangkar vigènere. Teknik susbtitusi vigènere dengan menggunakan angka dilakukan dengan menukarkan huruf dengan angka, hampir sama dengan kode geser. Contoh:

Plaintext: PLAINTEXT 

 Kunci: CIPHER

Dengan metode pertukaran angka dengan huruf di atas, diperoleh bahwa teks asli (PLAINTEXT) memiliki kode angka (15,11, 0, 8, 13, 19, 4, 23, 19), sedangkan kode angka untuk teks kunci (CIPHER) yaitu (2, 8, 15, 7, 4, 17). Setelah dilakukan perhitungan, maka dihasilkan kode angka ciphertext (17, 19, 15, 15, 17, 10, 6, 5, 8). Jika diterjemahkan kembali menjadi huruf sesuai urutan awal, maka menjadi huruf RTPPRKGFI. 

Rumus enkripsi vigenere cipher :

–  Pi = (Ci-Ki) mod 26

–  atau

–  Ci = ( Pi + Ki ) – 26, kalau hasil penjumlahan Pi dan Ki lebih dari 26

Rumus dekripsi vigenere cipher :

–  Pi = (Ci-Ki) mod 26

–  atau

–  Pi = ( Ci – Ki ) + 26, kalau hasil pengurangan Ci dengan Ki minus

–  Keterangan:

–  Ci = nilai desimal karakter ciphertext ke-i

–  Pi = nilai desimal karakter plaintext ke-i

–  Ki = nilai desimal karakter kunci ke-i

–  Nilai desimal karakter: A=0 B=1 C=2 ... Z=25

 

Sedangkan metode lain untuk melakukan proses enkripsi dengan metode vigènere cipher yaitu menggunakan tabula recta (disebut juga bujursangkar vigènere).

Kolom paling kiri dari bujursangkar menyatakan huruf-huruf kunci, sedangkan baris paling atas menyatakan huruf-huruf plaintext. Setiap baris di dalam bujursangkar menyatakan huruf-huruf ciphertert yang diperoleh dengan Caesar cipher, yang mana jumlah pergeseran huruf plaintext ditentukan nilai numerik huruf kunci tersebut (yaitu, a=0, b=1, c=2, …, z=25). 

Bujursangkar vigènere digunakan untuk memperoleh ciphertert dengan menggunakan kunci yang sudah ditentukan. Jika panjang kunci lebih pendek daripada panjang plaintext, maka kunci diulang penggunaannya (sistem periodik). Bila panjang kunci adalah m, maka periodenya dikatakan m. Sebagai contoh, jika plaintext adalah THIS PLAINTEXT dan kunci adalah sony, maka penggunaan kunci secara periodik sebagai berikut:

Plaintext : THIS PLAINTEXT

Kunci     : sony sonysonys

Untuk mendapatkan ciphertext dari teks dan kunci di atas, untuk huruf plaintext pertama T, ditarik garis vertikal dari huruf T dan ditarik garis mendatar dari huruf s, perpotongannya adalah pada kotak yang berisi huruf L. Dengan cara yang sama, ditarik garis vertikal dari huruf H dan ditarik garis mendatar pada huruf o, perpotongannya adalah pada kotak yang juga berisi berisi huruf V. hasil enkripsi seluruhnya adalah sebagai berikut:

Plaintext             : THIS PLAINTEXT

Kunci                 : sony sonysonys

Ciphertext          : LVVQ HZNGFHRVL

Variasi-variasi vigènere cipher pada dasarnya perbedaannya terletak pada cara membentuk tabel atau cara menghasilkan kuncinya, sedangkan enkripsi dan dekripsi tidak berbeda dengan vigènere cipher standar. Beberapa variasi tersebut sebagai berikut:

1.    Full Vigènere Cipher

Pada varian ini, setiap baris di dalam tabel tidak menyatakan pergeseran huruf, tetapi merupakan permutasi huruf-huruf alfabet.

2.    Auto-Key Vigènere cipher

Idealnya kunci tidak digunakan secara berulang. Pada auto-key vigènere cipher, jika panjang kunci lebih kecil dari panjang plaintext, maka kunci disambung dengan plaintext tersebut. Misalnya, untuk mengenkripsi pesan NEGARA PENGHASIL MINYAK dengan kunci INDO, maka kunci tersebut disambung dengan plaintext semula sehingga panjang kunci menjadi sama dengan panjang plaintext:

Plaintext: NEGARA PENGHASIL MINYAK

Kunci: INDONE GARAPENGH ASILMI

3.    Running-Key Vigènere cipher

Pada varian ini, kunci bukan string pendek yang diulang secara periodik seperti pada vigènere cipher standar, tetapi kunci adalah string yang sangat panjang yang diambil dari teks bermakna (misalnya naskah proklamasi, naskah Pembukaan UUD 1945, terjemahan ayat di dalam kitab suci, dan lain-lain). Misalnya untuk mengenkripsi plaintext NEGARA PENGHASIL MINYAK dapat menggunakan kunci berupa sila ke-2 Pancasila: KEMANUSIAAN YANG ADIL DAN BERADAB. Selanjutnya enkripsi dan dekripsi dilakukan seperti biasa. (Munir, 2006)

Berikut flowchartnya :

Study Kasus dalam Bidang Transportasi

Dalam tema yang dibahas kali ini tentang keamanan sistem komputer pada bidang transportasi. Dengam munculnya teknologi sistem diharapkan dapat memudahkan masyarakat untuk melakukan transaksi online untuk mendapatkan transportasi. Kini untuk memesan atau membooking trasportasi bisa dilakukan kapanpun dan dimanapun. Adapun di Indonesia sudah dibuat sebuah aplikasi di bidang transportasi yaitu Go-jek. Aplikasi ini dilengkapi oleh beberapa fitur pendukung seperti Go-food untuk delivery makanan, Go-box untuk mengantar barang, Go-ride untuk pemesanan kendaraan roda dua dan beberapa fitur lainnya yang dapat mendukung kinerja. Sistem ini sengaja dibuat untuk memudahkan masyarakat Indonesia melakukan pekerjaan yang berhubungan dengan transportasi. Sistem ini memiliki banyak manfaat namun dibalik segudang manfaat terdapat suatu masalah dalam keamanan sistem komputer. Keseluruhan sistem belum merupakan sistem yang aman untuk mengolah data dari pengguna. Sistem yang dirancang juga belum sepenuhnya efisien dalam database penggunanya.

Merambahnya bisnis ojek berbasis online Go-Jek yang sangat menjanjikan membuat ribuan orang akhirnya memutuskan untuk menggunakan aplikasi ini. Aplikasi Go-Jek merupakan pengembangan sistem yang dapat membantu efisiensi proses pekerjaan dalam bidang transportasi. Namun, terdapat suatu masalah pada keamanan sistem Go-Jek yaitu perusahaan dapat menyimpan seluruh database yang diinputkan user pada saat pemasukan data seperti nama, nomer telfon, dan lainnya. Seorang hacker bisa saja menyalahgunakan data tersebut demi kepentingan pribadi atau keuntungan perusahaan. Penyalahgunaan tersebut bisa dapat menggunakan algoritma kriptografib Vigenere Cipher.

Dalam studi kasus yang dipilih penjelasan dapat disampaikan seperti berikut:

Algoritma ini memerlukan 4 komponen yaitu

• Plaintext

Merupakan pesan yang dibaca oleh siapapun dalam study kasus. Plaintext yang dimaksud adalah nama pengguna aplikasi Gojek

• Chipertext

Merupakan pesan acak yang tidak dapat dibaca oleh user tetapi dimengerti oleh admin

–  Key

Kunci untuk melakukan teknik komputasi

–  Algoritma

Metode melakukan enkripsi dan deskripsi

 

Berikut merupakan kodingan program C++ metode Algortima Vigenere Cipher

#include <iostream>

#include <string>
         using namespace std;

class Vigenere {

public:

string key;

 Vigenere(string key){
           for(int i = 0; i < key.size();++i){
            if (key[i] >= 'A' && key [i] <= 'Z')
             this->key += key [i];
            else if (key[i] >= 'a' && key[i] <= 'z')
             this->key += key [i] + 'A' - 'a';
             }
             }
       string encrypt(string text){
       string out;
       for (int i = 0, j = 0; i < text.length(); ++i){
       char c = text[i];
       if (c >= 'a' && c<= 'z')
       c += 'A' - 'a';
       else if ( c < 'A' || c> 'Z')
     continue;
   out += (c +key[j] -2 * 'A') %26 +'A';
     j = (j +1) % key.length();
    }
  return out;
 }
 string decrypt(string text)
 {
  string out;
 
  for (int i = 0, j = 0; i < text.length(); ++i)
   {
   char c = text[i];
  
  if (c >= 'a' && c<= 'z')
   c += 'A' - 'a';
  else if ( c < 'A' || c> 'Z')
   continue;
  
  out += (c - key[j] +26 ) %26 +'A';
  j = (j +1) % key.length();
  }
 
  return out;
 }
};
int main(){
string a,b;
cout<<"Masukkan Plaintext : ";
cin>>a;
cout<<"Masukkan Key : ";
cin>>b;
 string original=a;
 Vigenere chiper=b;

 string encrypted = chiper.encrypt(original);
 string decrypted = chiper.decrypt(encrypted);
 cout<<endl;
 cout<<"encrypted :"<<encrypted<<endl;
 cout<<"decrypted :"<<decrypted<<endl;
}

Hasil Output Program :

B. Analisa Algoritma

Sistem informasi akademik merupakan salah satu kebutuhan wajib dan penting yang harus dipenuhi perguruan tinggi. Kemampuan menyediakan dan mengakses informasi secara cepat dan akurat menjadi yang diinginkan bagi perguruan tinggi. Sangat pentingnya informasi tersebut, menyebabkan seringkali informasi yang diinginkan hanya boleh diakses orang-orang tertentu yang memilki wewenang. Jatuhnya informasi kepada pihak lain menimbulkan kerugian baik pihak perguruan tinggi.

Keamanan sistem (Security System) informasi merupakan hal yang sangat penting dalam mengelola sistem informasi, tujuannya adalah untuk mencegah ancaman terhadap sistem serta mendeteksi dan memperbaiki segala kerusakan sistem. Namun,  masih banyak kampus atau instansi tidak terlalu memperhatikan masalah keamanan

Security System atau keamanan sistem informasi merupakan hal yang sangat penting dalam mengelola sistem informasi, tujuannya adalah untuk mencegah ancaman terhadap sistem serta mendeteksi dan memperbaiki segala kerusakan sistem. Namun, masih banyak kampus atau instansi tidak terlalu memperhatikan masalah keamanan ini.

Semisal: Data akademik yang merupakan data yang sangat penting di dalam perguruan tinggi. Dengan data tersebut akan melancarkan berbagai urusan baik mahasiswa, dosen dan pegawai kampus. Jika dirusak oleh orang yang tidak bertanggung jawab, kampus akan kewalahan dalam memulihkan data tersebut. Bisa jadi data itu akan hilang selamanya tidak bisa diperbaiki kembali. 

Algoritma Beaufort Cipher merupakan varian dari algoritma Vignere Cipher                 Algoritma ini ditemukan oleh Laksamana Sir Francis Beaufort,

Royal Navy, yang juga merupakan pencipta skala Beaufort yaitu instrumen ahli meterorologi yang digunakan untuk menunjukkan kecepatan angin. Beaufort Cipher
termasuk algoritma kriptografi klasik kunci simetris Mollin, 2007. Proses enkripsi dan dekripsi pada algoritma Beaufort Cipher menggunakan
sebuah tabel yang disebut dengan tabel Beaufort Tassel, 1969

 Algoritma Vigenere Cipher dan Beaufort Cipher hanya menggunakan Alfabet untuk penjabaran dan penyelesaian algoritmanya. Sedangkan untuk angka atau numerik tidak dapat diselesaikan.

Kedua algoritma ini dapat dibedakan menjadi 3 yaitu : 

Viginère cipher membandingkan baris + kolom = isi tabel

Beaufort cipher membandingkan kolom+ isi tabel = baris

Vigenere cipher memakai rumus sedangkan beaufort cipher hanya melihat tabel\

memakai key yang berbeda.

sedangkan persamaan kedua algoritma ini adalah :

1. Memakai tabel

2. Hanya mengoperasikan alfabet

3. Keamanan cukup lemah

C. Kesimpulan

Pada dasarnya algoritma kriptografi Vigenere Cipher dengan Algoritma Kriptografi Beaufort Cipher memiliki persamaan yaitu pengoperasiannya hanya alfabet, memakai tabel, namun kedua algoritma ini bisa dibilang cukup mudah ditebak karna hanya mengoperasikan beberapa huruf. Namun kedua algoritma ini cukup mudah untuk dipahami oleh pemula.

Link Anggota Kelompok 5 :

https://adelinamarchelia.blogspot.com/

krisyuananjel.blogspot.com

https://nimadeayuastitiwiwekawati-stt-pln.blogspot.com/

wahyuunggul08.wordpress.com

naufal1731.blogspot.com

Link Anggota Kelompok 4 :

http://ksk-algoritma-201731230.blogspot.com/?m=1

https://kskbidangpendidikan.blogspot.com/2018/12/keamanan-sistem-komputer-dalam.html

Https://ksk201731174.blogspot.com/2018/12/nama-saya-nadya-azzahra-nim-201731174.html?m=0

Sumber :

Wikipedia

Artike Implementaasi Vigenere Chiper

KEGELISAHAN HATI - PUISI

KAMU

Karya : Ni Made Ayu Astiti Wiwekawati

Kamu . . .

Yang tiba-tiba perhaian

Mengantar dan menjemputku

Saling bercanda walau itu dalam khayalan

Mencari kesempatan untuk duduk disampingku

Namun aku tak percaya kau benar menyukaiku

Karna perjuanganmu untuk berkorban tak seberapa

Mungkin itu hanya main main belaka

KEGELISAHAN HATI - Puisi

Sengaja Begitu

Karya : Ni Made Ayu Astiti Wwekawati

Malam itu tak pernah datang sebelumnya

Dimana saat ingin beristirahat lebih cepat 

Mata mampu untuk terpejam namun pikiran tak mampu diam di satu tempat

Hai. . . Kau yang disana, apa kau memikirkan ku

Hingga malam berjalan sangat lambat

Kau begitu peduli 

Di tengah malam itu kau peduli

Namun aku tak menghiraukan

Maaf. . . karna sengaja aku begitu

KEGELISAHAN HATI - Puisi

SAKIT SEBELUM PERGI

Karya : Ni Made Ayu Astiti Wiwekawati

Sakit ini datang di saat jauh

Namun hilang saat akan kembali

Ingin kembali ke hari-hari biasa

Sesaat akan pergi, ia datang membawa sakit

Karna baik kau sakit

Jangan salahkan kebaikan karna dia tak bersalah

Mungkin dulu kau salah

Hingga kau tanggung saat baik

Materi MatDis (Matematika Diskrit) : Pohon Part 2

1. Pohon Berakar 

          adalah pohon yang sebuah simpulnya diperlukan sebagai akar dan sisi-sisinya diberi arah menjauh dari akar.

Terminologi pada pohon berakar

Anak(Child atau children) dan Orangtua (parent)

Misalkan Xx adalah sebuah simpul di dalam pohon berakar. Simpul y dkatakan anak simpul x jika ada sisi dari simpul x ke y. Dalam hal demikian, x disebut orangtua (parent)  y. Pada gambar dibawah, b, c dan d adalah anak-anak simpul a, dan a adalah orangtua dari anak-anak itu. e dan f adalah anak-anak simpul b dan b adalah orangtua dari e dan f. g adalah anak simpul d dan d adalah orangtua g. Simpul h,i, j, l dan m tidak mempunyai anak.

2. Pohon Berakar Terurut

    adalah pohon berakar yang urutan anak-anaknya penting.

3. Pohon Ekspresi
   adalah pohon biner dengan daun menyatakan operand dan simpul dalam (termasuk akar) menyatakan operator. Perhatikan bahwa tanda kurang tidak lagi diperlukan bila suatu ekspresi aritmetik diprsentasikan sebagai pohon biner.
contoh :
(a+b) * c/(d+e) Infix
Prefix : *+ ab/c + de
Posfix : ab + cde +/*


INFIX, POSTFIX dan PREFIX

1. Infix
    Digunakan manusia sebagai input di komputer
2. Postfix
    Digunakan komputer sebagai proses
3. Prefix
    Sama Seperti Postfix yaitu digunakan komputer sebagai proses.

• Konversi Infix ke Postfix

ada 3 cara yaitu :
1. Cara Manual
    Caranya adalah dengan menyederhanakan  notasi menjadi dua operand (variabel) da satu operator, seperti A + B

2. Cara Stack
    Stack adalah tumpukan (jadi, memori diibaratkan dengan tumpukan) yang memiliki cara kerja yang pertama masuk ke kotak, maka akan terakhir kali diambil kembali atau first in last out atau sebaliknya, yang terakhir masuk ke kotak akan diambil yang pertama kali, atau last in first out.

3. Cara Binary Tree

• Konversi Infix ke Prefix

Ada 2 cara :
1. Cara Manual
    Sama seperti mengonversi notasi infix ke prefix
2. Cara Binary Tree
    Sama seperti mengonversi notasi infix ke prefix

• Konversi Prefix ke Infix dan/atau Postfix

Bisa dilakukan melalui bantuan manual dan pohon binar.

• Konversi Postfix ke Infix dan/atau Prefix

Sama seperti Konversi Prefix ke Infix dan/atau Postfix

Materi MatDis (Matematika Diskrit) : Pohon

DEFINISI POHON

Pohon adalah graf tak berarah terhubung yang tidak mengandung sirkuit.
Beberapa pohon dapat membentuk hutan. Hutan adalah kumpulan pohon yang saling lepas. Atau hutan adalah graf tak terhubung yang tidak mengandung sirkuit, dalam hal ini setiap komponen graf terhubung adalah pohon.
Pohon juga seringkali didefinisikan sebagai graf tak berarah dengan sifat bahwa hanya terdapat sebuah lintasan unik antara setiap pasang simpul.


POHON MERENTANG

adalah semua simpul pada pohon T sama dengan semua simpul pada graf G.
Pohon merentang didefinisikan hanya untuk graf terhubung, karena pohon selalu terhubung. Pada graf terhubung terdapat setidaknya satu buah pohon merentang.Graf yang tidak mengandung sirkuit adalah pohon merentang itu sendiri. Pada graf yang mengandung sirkuit, pohon merentangnya diperoleh dengan cara memutuskan sirkuit yang ada.
Sisi pada pohon merentang disebut cabang. Sedangkan sisi dari graf yang tidak terdapat di dalam pohon merentang disebut tali hubung.Himpunan tali hubung beserta simpul yang bersisian disebut komplemen pohon. Rumus menghitung jumlah cabang dan jumlah tali hubung :

                                Jumlah cabang = n - 1
                                Jumlah tali hubung = m - n + 1

dan pada graf tidak terhubung dengan k komponen, m buah sisi dan n buah simpul,

                                Jumlah cabang = n - k
                                Jumlah tali hubung = m - n + k

Sirkuit yang terbentuk dengan penambahan sebuah tali hubung pada pohon merentang disebut sirkuit fundamental.


POHON MERENTANG MINIMUM

adalah pohon merentang yang berbobot minimum dimana pohon merentang ini merupakan pohon merentang yang paling penting karena mempunyai terapan yang luas dalam praktik.
Terdapat dua buah algoritma dalam membuat pohon merentang minimum :

1. Algoritma Prim

          Algoritma Prim membentuk pohon merentang minimum langkah per langkah. 

          1. Ambil sisi dari graf G yang berbobot minimum, masukkan ke dalam T

          2. Pilih sisi e yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi e                        tidak  membentuk sirkuit di T. Masukkan e ke dalam T

          3. Ulangi langkah 2 sebanyak n - 2 kali

         Jumlah langkah seluruhnya di dalam algoritma prim adalah 1 + (n - 2) = n - 1, yaitu sebanyak             jumlah sisi di dalam pohon merentang dengan n buah simpul.

     2. Algoritma Kruskal

         Pada algoritma kruskal, sisi-sisi di dalam graf diurut terlebih dahulu berdasarkan bobotnya dari           kecil ke besar. Perbedaan prinsip antara algoritma prim dan algoritma kruskal adalah : jika pada           algoritma prim sisi yang dimasukkan ke dalam T harus bersisian dengan sebuah simpul di T,               maka pada algoritma kruskal sisi yang dipilih tidak perlu bersisian dengan sebuah simpul di T             asalkan penambahan sisi tersebut tidak membentuk sirkuit.

         

         Algoritma Kruskal :

1. T Masih Kosong
2. Pilih sisi e dengan bobot minimum yang tidak membentuk sirkuit di T. Masukkan e ke dalam T
3. Ulangi langkah 2 sebanyak n - 1 kali

Materi MatDis (Matematika Diskrit) : Graf Part 2

GRAF PLANAR dan GRAF BIDANG

Graf planar adalah graf yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling memotong. Reprsentasi dari graf planar disebut dengan graf bidang. Sisi-sisi pada graf graf bidang membagi bidang datar menjadi beberapa wilayah atau muka.

RUMUS EULER

Rumus euler sebagai berikut:

             n - e + f = 2
atau
            f = e - n + 2
keterangan:
e = jumlah sisi
n = jumlah simpul



TEOREMA KURATOWSKI

Sifat graf kuratowski :

1. Kedua graf kuratowski adalah graf teratur
2. Kedua graf kuratowski adalah graf tidak planar
3. Penghapusan sisi atau simpul dari graf kuratowski menyebabkannya menjadi graf planar
4. Graf kuratowski pertama adalah graf tidak planar dengan jumlah simpul minimum dan graf kuratowski kedua adalah graf tidak planar dengan jumlah sisi minimum. Keduanya adalah graf tidak planar paling sederhana

HOMEOMORFIK

adalah jika salah satu dari kedua graf dapat diperoleh dari graf yang lain dengan cara menyisipkan dan/atau membuang secara berulang-ulang simpul berderajat 2.

LINTASAN dan SIRKUIT EULER

Lintasan euler adalah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali. Jika kembali ke simpul asal membentuk lintasan tertutup disebut sirkuit euler.

Graf yang mempunyai sirkuit euler disebut graf euler. Graf yang mempunyai lintasan euler dinamakan graf semi euler.

LINTASAN dan SIRKUIT HAMILTON

Lintasan hamilton adalah lintasan yang melalui tiap simpul di dalam graf tepat satu kali. Jika kembali ke simpul asal membentuk lintasan tertutup disebut sirkuit hamilton.

Graf yang memiliki sirkuit hamilton disebut graf hamilton sedangkan graf yang hanya memiliki lintasan hamilton disbeut graf semi hamilton.

Materi MatDis (Matematika Diskrit) : Graf

1. Definisi Graf
    Graf adalah tidak adanya sisi satu buah pun namun memiliki simpul, minimal adanya simpul satu.

2. Jenis-jenis Graf
    Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka secara urutan graf dapat          digolongkan menjadi dua jenis :

•      Graf Sederhana

               adalah graf yang tidak mengandung gelang maupun sisi-ganda. Pada graf sederhana, sisi                     adalah pasangan terurut. Jadi menuliskan sisi (u, v) sama saja dengan (v, u). Graf sederhana                 dapat juga diartikan himpunan tidak kosong simpul-simpul dan himpunan pasangan tak                       terurut yang disebut sebagai sisi.

• Graf Tak Sederhana

           adalah graf yang mengandung sisi ganda atau gelang. Ada dua macam graf tak sederhana,                   yaitu

1.          Graf Ganda

                   adalah graf yang mengandung sisi ganda. Sisi ganda yang menghubungkan sepasang                           simpul bisa lebih dari dua buah. Sisi ganda dapat diasosiasikan sebagai pasangan tak                           terurut yang sama. Serta dapat juga diartikan yang terdiri dari himpunan tidak kosong                           simpul-simpul dan himpunan ganda yang mengandung sisi ganda. Setiap graf sederhana                       juga adalah graf ganda tetapi tidak setiap graf ganda merupakan graf sederhana.

     

       2.         Graf Semu

               

                   adalah graf yang mengandung gelang. Graf semu lebih umum daripada graf ganda                               karena  sisi pada graf semu dapat terhubung ke dirinya sendiri.

Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis :

1. Graf Tak Berarah 

          adalah graf yang sisinya tidak mempunyai orientasi arah. Pada graf tak berarah, urutan                        pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi (u, v) = (v, u) adalah sisi              yang sama.

  

       2. Graf Berarah

           adalah graf yang setiap sisinya diberikan orientasi arah. Sisi berarah disebut dengan busur.                 Pada graf berarah, (u, v) dan (v, u) menyatakan dua buah busur yang berbeda. Untuk busur (u,             v), simpul v dinamakan simpul asal dan simpul v dinamakan simpul terminal.

TERMINOLOGI DASAR

1. Bertetangga

          Duah buah simpul dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah                  sisi.

       2. Bersisian

           Untuk sembarang sisi e = (u, v), sisi e dikatakan bersisian dengan simpul u dan simpul v.

       3. Simpul Terpencil

           adalah simpul yang tidak mempunyai sisi yang bersisian dengannya ataupun tidak satupun                   bertetangga dengan simpul-simpul lainnya.

        4. Graf Kosong

            adalah graf yang himpunan sisinya merupakan himpunan kosong.

         5. Derajat

             Derajat suatu simpul pada graf tak berarah adalah jumlah sisi yang bersisian dengan simpul                 tersebut.

             Notasi : d(v) menyatakan derajat simpul v
             Simpul yang berderajat satu disebut anting-anting. Dengan kata lain, anting-anting hanya                     bertetangga dengan sebuah simpul.

         6. Lintasan

             adalah barisan berselang-seling simpul-simpul dan sisi-sisi. Istilah lain untuk lintasan adalah               jalur. Simpul dan sisi yang dilalui di dalam lintasan boleh berulang. Sebuah lintasan                           dikatakan lintasan sederhana jika semua simpulnya berbeda. Lintasan yang berawal dan                     berakhir pada simpul yang sama disebut lintasan tertutup sedangkan lintasan yang tidak                     berawal dan berakhir pada simpul yang sama disebut lintasan terbuka. Panjang lintasan                     adalah jumlah sisi dalam lintasan tersebut.

       7. Siklus atau Sirkuit

            adalah lintasan yang berawal dan berakhir pada lintasan yang sama. Panjang sirkuit adalah                  jumlah sisi di dalam sirkuit tersebut.

        8. Terhubung

             Dikatakan terhubung jika terdapat lintasan dari u ke v diantara dua buah simpul u dan simpul               v. Jika dua buah simpul terhubung maka pasti simpul yang pertama dapat dicapai dari simpul               yang kedua. Jika setiap pasang simpul di dalam graf terhubung maka graf tersebut dikatakan               graf terhubung.

          9. Upagraf dan Komplemen Upagraf

          10. Upagraf Merentang

          11. Cut-Set

                Cut-Set atau jembatan adalah himpunan sisi yang apabila dibuang dari graf menyebabkan                    graf tersebut tidak terhubung.

          12. Graf Berbobot

                adalah graf yang setiap sisinya diberi sebuah harga (bobot).

             
BEBERAPA GRAF SEDERHANA KHUSUS

1. Graf Lengkap

          adalah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya.

       2. Graf Lingkaran

           adalah graf sederhana yang setiap simpulnya berderajat dua.

       3. Graf Teratur

            adalah graf yang setiap simpulnya mempunyai derajat yang sama.

        4. Graf Bipartit

            adalah himpunan simpulnya dapat dikelompokkan menjadi dua himpunan bagian.


REPRESENTASI GRAF

1. Matriks Ketetanggaan

          Karena matriks ketetanggaan hanya berisi 0 dan 1, maka matriks tersebut dinamakan matriks              nol-satu. Selain dengan angka 0 dan , elemen matriks dapat juga dinyatakan dengan nilai false            (menyatakan 0) dan true (menyatakan 1). Matriks ketetanggaan untuk graf sederhana dan tidak            berarah selalu simetri sedangkan untuk graf berarah matriks ketetanggaannya belum tentu                    simetri. Selain itu, diagonal utamanya selalu nol karena tidak ada sisi gelang.

      2. Matriks Bersisian

          Matriks bersisian menyatakan kebersisian simpul dengan sisi. Baris menunjukkan label simpul sedangkan kolom menunjukkan label sisinya. Matriks bersisian dapat digunakan untuk mempresentasikan graf yang mengandung sisi ganda atau sisi gelang.

      3. Senarai Ketetanggaan

          Senarai ketetanggaan menganumerasi simpul-simpul yang bertetangga dengan setiap simpul di dalam graf.


GRAF ISOMORFIK

adalah dua buah graf yang sama tetapi secara geometri berbeda. Syarat-syarat dua buah graf isomorfik :

1. Mempunyai jumlah simpul yang sama.
2. Mempunyai jumlah sisi yang sama.
3. Mempunyai jumlah simpul yang sama berderajat tertentu.

           

Materi MatDis (Matematika Diskrit) : Aljabar Boolean

1. Definisi Aljabar Boolean
    Yang disebut aljabar boolean adalah <B, +, ., ',  0, 1>

• Identitas

         (i) a + 0 = a
         (ii) a + 1 = a

• Komutatif

          (i) a + b = b + a
          (ii) a . b = b . a

• Distributif

          (i) a . (b +c) = (a . b) + (a . c)
          (ii) a + (b . c) = (a + b) . (a + c)

• Komplemen

          (i) a + a' = 1
          (ii) a . a' = 0


2. Prinsip Dualitas
    Misalkan S adalah kesamaan (identify) di dalam aljabar boolean yang melibatkan operator +, ., dan komplemen, maka jika pernyataan S* diperoleh dari S dengan cara mengganti
   
     . dengan +
     + dengan .
     0 dengan 1
     1 dengan 0
dan membiarkan operator komplemen tetap apa adanya, maka kesamaan S* juga benar. S* disebut sebagai dual dari S


Hukum-hukum Aljabar Boolean
1. Hukum Identitas:
    (i) a + 0 = a
    (ii) a . 1 = a

2. Hukum Idempoten:
    (i) a + a = a
    (ii) a . a = a

3. Hukum Komplemen:
    (i) a + a' = 1
    (ii) aa' = 0

4. Hukum Dominansi:
    (i) a . 0 = 0
    (ii) a + 1 = 1

5. Hukum Involusi:
    (i) (a')' = a

6. Hukum Penyerapan:
    (i) a + ab = a
    (ii) a(a + b) = a

7. Hukum Komutatif:
    (i) a + b = b + a
    (ii) ab = ba

8. Hukum Asosiatif
    (i) a + (b + c) = (a + b) + c
    (ii) a (b c) = (a b) c

9. Hukum Distributif:
    (i) a + (b c) = (a + b)(a + c)
    (ii) a (b + c) = a b + a c

10. Hukum De Morgan
      (i) (a + b)' = a'b'
      (ii) (ab)' = a' + b'

11. Hukum 0/1
      (i) 0' = 1
      (ii) 1' = 0


Contoh Soal :
1. Bentuk baku SOP dan POS dari f (x, y, z) = xy + x'z

    SOP:
    xy = xy(z + z')
         = xyz + xyz'
    dan
    x'z = x'z (y +y')
          = x'yz + x'y'z
    Jadi f(x, y, z) = xy + x'z
                          = xyz + xyz' + x'yz + x'y'z
   Atau f(x, y, z) = m7 + m6 + m3 + m1
                          = (1, 3, 6, 7)

    POS:
    f(x, y, z) = xy +x'z
                   = (xy + x')(xy + z)
                  = (x + x')(y + x')(x + z)(y + z)
                   = (x' + y)(x + z)(y + z)
   
     x' + y = x' + y + zz' = (x' + y + z)(x' + y + z')
     x + z  = x + z + yy'  = (x + y + z)(x + y' + z)
     y + z   = xx' + y + z  = (x + y +z)(x' + y + z)

     Jadi f(x, y, z) = (x + y + z)(x + y' + z)(x' + y + z)(x' + y + z')

     Atau f(x, y, z) = M0 M2 M4 M5
                            = (0, 2, 4, 5)

2. Bentuk Baku SOP dan POS dari f(x, y, z) = x + yz'
   
     SOP:
     x = x(y + y')
        = xy + xy'
        = xy (z + z') + xy' (z + z')
        = xyz + xyz' + xy'z + xy'z'
    dan
    yz' = yz' (x + x')
          = yz'x + yz'x' = xyz' + x'yz'
 
     Jadi f(x, y, z) = x + yz'
                           = xyz + xyz' + xy'z + xy'z' + x'yz'
                           = x'yz' + xy'z' + xy'z + xyz' + xyz
     
     Atau f(x, y, z) = m2 + m4 + m5 + m6 + m7
                            = (2, 4, 5, 6, 7)


    POS:
    f(x, y, z) = x + yz'
                   = (x + y)(x + z')
 
    x + y = x + y + zz'
             = (x + y + z)(x + y + z')

    x + z' = x + z' + yy'
              = (x + y + z')(x + y' + z')

   Jadi f(x, y, z) = (x + y + z)(x + y + z')(x + y + z')(x + y' + z')
                         = (x + y + z)(x + y + z')(x + y' + z')

   Atau f(x, y, z) = M0 M1 M3
                          = (0, 1, 3)

Materi MatDis (Matematika Diskrit) : Permutasi dan Kombinasi

PERMUTASI Permutasi adalah jumlah urutan berbeda dari pengaturan objek-objek. Permutasi merupakan bentuk khusus aplikasi aturan perkalian. Misalkan jumlah objek adalah n, maka urutan pertama dipilih dari n objek, urutan kedua dipilih dari n – 1 objek, urutan ketiga dipilih dari n – 2 objek, begitu seterusnya dan urutan terakhir dipilih dari 1 objek yang tersisa. Menurut kaidah perkalian, permutasi dari n objek adalah n(n – 1) (n – 2) . . . (2)(1) = n! Menurut kaidah perkalian, ada sebanyak n(n – 1) (n – 2) . . . (n – (r – 1)) buah susunan berbeda dari penyusunan r objek yang dipilih dari n objek. Jumlah susunan berbeda dari pemilihan r objek yang diambil dari n objek disebut permutasi-r, dilambangkan dengan P(n, r), yaitu P(n, r) = n(n – 1)(n – 2). . . (n – (r – 1)) = n!/(n-r)! Menurut persamaan tersebut, jumlah cara memasukkan 6 buah bola yang berbeda warnanya ke dalam 3 buah kotak adalah P(6, 3) = 6!/(6 - 3)! = 120 dan jumlah kemungkinan urutan 2 dari 3 elemen himpunan A = {a, b, c} adalah P(3, 2) = 3!/(3 – 2)! = 6. Permutasi r dari n objek adalah jumlah kemungkinan urutan r buah objek yang dipilih dari n buah objek, dengan r ≤ n, yang dalam hal ini, pada setiap kemungkinan urutan tidak ada objek yang sama. Bila r = n, maka P(n, n) = n!/(n-n)! = n!/0! = n!/1 = n! Contoh : Berapa banyak “kata” yang terbentuk dari kata “BOSAN”? Penyelesaian : Anggap setiap huruf di dalam kata “BOSAN” sebagai bola yang berbeda warnanya dan 5 buah kotak yang akan diisi dengan 1 bola pada setiap kotak. Cara 1 : (5)(4)(3)(2)(1) = 120 buah kata Cara 2 : P(5, 5) = 5! = 120 buah kata Berapa banyak cara mengurutkan nama 25 orang mahasiswa? Penyelesaian : Analogikan dengan mengisi 25 kotak dengan 25 bola huruf berbeda, setiap kotak diisi dengan 1 bola. Jadi, jumlah cara pengurutan nama mahasiswa sama dengan jumlah susunan 25 bola ke dalam 25 kotak, yaitu P(25, 25) = 25! Tiga buah ujian dilakukan dalam suatu periode enam hari (Senin sampai Sabtu). Berapa banyak pengaturan jadwal yang dapat dilakukan sehingga tidak ada dua ujian atau lebih yang dilakukan pada hari yang sama. Penyelesaian : Cara 1 (dengan kaidah perkalian) : sama seperti menempatkan 3 bola (ujian) berbeda ke dalam enam kotak (hari). Ujian pertama dapat ditempatkan pada salah satu dari enam hari; Ujian kedua dapat ditempatkan pada salah satu dari lima hari; Ujian ketiga dapat ditempatkan pada salah satu dari empat hari; Jumlah pengaturan jadwal ujian = (6)(5)(4) = 120 Cara 2 (dengan rumus permutasi) : P(6, 3) = 6! / (6 – 3)! = 120 Sebuah bioskop mempunyai jajaran kursi yang disusun per baris. Tiap baris terdiri dari 6 tempat kursi. Jika dua orang akan duduk, berapa banyak pengaturan tempat duduk yang mungkin pada suatu baris? Penyelesaian : Orang pertama mempunyai 6 pilihan kursi dan orang kedua mempunyai 5 pilihan kursi. Jadi, jumlah pengaturan tempat duduk = (6)(5) = 30 atau P(6, 2) = 6! / 4! = (6)(5) = 30 cara Berapa banyak string yang dapat dibentuk yang terdiri dari 4 huruf berbeda dan diikuti dengan 3 angka yang berbeda pula? Penyelesaian : Ada P(26, 4) cara mengisi posisi 4 huruf dan P(10, 3) cara untuk mengisi posisi 3 buah angka. Karena string disusun oleh 4 huruf dan 3 angka, maka jumlah string yang dapat dibuat adalah P(26, 4) x P(10, 3) = 258.336.000 KOMBINASI Bentuk khusus dari permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan. Urutan acb, bca dan acb dianggap sama dan dihitung sekali. Secara umum, jumlah cara memasukkan r buah bola yang berwarna sama ke dalam n buah kotak adalah (n(n-1)(n-2)...(n-(r-1)))/r! = n!/r!(n-r)! Rumus n!/r!(n-r)! Disebut rumus kombinasi-r dan dilambangkan dengan C(n, r) atau (n¦r). Jadi, C(n, r) = n!/r!(n-r)! C(n, r) sering dibaca “n diambil r”, artinya r objek diambil dari n buah objek. Kombinasi r elemen dari n elemen adalah jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen. Dapat juga dibuktikan dengan cara membentuk permutasi-r dari n elemen. Mula-mula hitung kombinasi-r , yaitu C(n , r), kemudian urutkan elemen-elemen di dalam setiap kombinasi-r. Pengurutan ini dapat dilakukan dengan P(r, r) cara. Dengan demikian, permutasi-r dari n elemen adalah P(n, r) = C(n, r) P(r, r) Dari persamaan di atas kita peroleh C(n, r) = (P(n,r))/(P(r,r)) = (n!/(n-r)!)/r!(r-r)! = n!/r!(n-r)! Contoh : Berapa banyak cara menyusun menu nasi goreng tiga kali seminggu untuk sarapan pagi? Penyelesaian : Bayangkan tiga kali menu nasi goreng sebagai tiga buah bola dan tujuh hari dalam seminggu sebagai 7 buah kotak. Persoalan ini sama dengan menempatkan 3 buah bola ke dalam 7 buah kotak. Banyaknya pengaturan jadwal menu nasi goreng adalah C(7, 3) = 7!/3!4! = 35 cara. String biner yang panjangnya 32 bit disusun oleh angka 1 atau 0. Berapa banyak string biner yang tepat berisi 7 buat bit 1? Penyelesaian : Analogikan 7 bit 1 sebagai 7 buah bola dan 32 posisi bit sebagai 32 buah kotak. Persoalan ini sama dengan memasukkan 7 bola ke dalam 32 kotak, sisanya kosong (0). Banyak string biner yang terbentuk adalah C(32, 7). Sebuah koin yang mempunyai sisi A dan sisi B dilempar ke atas sebanyak empat kali. Berapakah jumlah kemungkinan munculnya sisi A sebanyak tiga kali? Penyelesaian : Ini adalah persoalan dari kombinasi karena kita tidak mementingkan kapan sisi A tersebut muncul. Jadi, jumlah kemungkinan munculnya sisi A sebanyak tiga kali adalah C(4, 3) = 4. Tiga buah apartemen A, B dan C disewakan untuk mahasiswa. Tiap unit apartemen dapat menampung 3 atau 4 orang mahasiswa. Berapa jumlah cara menyewakan apartemen kepada 10 orang mahasiswa? Penyelesaian : Andaikan apartemen A, B, C ditempati masing-masing oleh 4, 3 dan 3 orang mahasiswa. Jumlah cara menyewakan = C(10, 4) x C(6, 3) x C(3, 3) Andaikan apartemen A, B, C ditempati masing-masing oleh 3, 4 dan 3 orang mahasiswa. Jumlah cara menyewakan = C(10, 3) x C(7, 4) x C(3, 3) Andaikan apartemen A, B, C ditempati masing-masing oleh 3, 3 dan 4 orang mahasiswa. Jumlah cara menyewakan = C(10, 3) x C(7, 3) x C(4, 4) Total seluruh cara menyewakan = C(10, 4)C(6, 3) + C(10, 3)C(7, 4) + C(10, 3)C(7, 3) = 3C(10, 4)C(6, 3). PERMUTASI DAN KOMBINASI BENTUK UMUM P(n;n_1,n_2, ... , n_k) = (P(n,n))/(n_1 !n_(2!…n_k !) ) = n!/(n_1 !n_(2!…n_k !) ) Persamaan ini diterapkan untuk menghitung pengaturan (atau pengurutan) n buah objek dari himpunan ganda S (himpunan S terdiri dari n buah objek yang tidak perlu semuanya berbeda). Persamaan tersebut dinamakan permutasi bentuk umum (generalized permutation) terhadap S. C(n;n_1,n_2, ... , n_k) = C(n, n_1) C(n - n_1, n_2) C(n - n_1 - n_2, n_3) . . . C(n - n_1 - n_2 - . . . - n_(k-1), n_k) = n!/(n_(1 ) !(n- n_1 )!) (n-n_(1 ) )!/(n_2 !(n- n_1- n_2 )!) (n- n_1- n_2 )!/(n_3 !(n- n_1- n_2- n_k )!) . . . ((n- n_1- n_2- n_(k-1) )! )/(n_k !(n- n_1- n_2-…- n_(k-1)- n_k )!) = n!/(n_1 !n_(2!…n_k !) ) Persamaan ini dinamakan kombinasi bentuk umum (generalized combination). Kita dapat melihat bahwa tidak ada perbedaan antara permutasi bentuk umum dengan kombinasi bentuk umum. Keduanya dapat dihitung dengan rumus yang sama. Jadi, apabila S adalah himpunan ganda dengan n buah objek yang di dalamnya terdiri atas k jenis objek berbeda dan tiap objek memiliki multiplisitas n_1, n_2, . . ., n_k (jumlah objek seluruhnya n_1 + n_2 + . . . + n_k = n), maka jumlah cara menyusun seluruh objek adalah : P(n;n_1,n_2, ... , n_k) = C(n;n_1,n_2, ... , n_k) = n!/(n_1 !n_(2!…n_k !) ) Contoh : 12 lembar karton akan diwarnai sehingga 3 diantaranya berwarna hijau, 2 berwarna merah, 2 berwarna kuning dan sisanya berwarna biru. Berapa jumlah cara pengecatan? Penyelesaian : Diketahui n_1 = 3, n_2 = 2, n_3 = 2, n_4 = 5 dan n_(1 )+ n_2 + n_3 + n_4 = 3 + 2 + 2 + 5 = 12 Jumlah cara pengecatan = P(12; 3, 2, 2, 5) = (P(12,12))/((3!)(2!)(2!)(5!)) = 12!/((3!)(2!)(2!)(5!)) = 166320 cara 12 buah lampu berwarna (4 merah, 3 putih dan 5 biru) dipasang pada 18 buah soket dalam sebuah baris (sisanya 6 buah soket dibiarkan kosong). Berapa jumlah cara pengaturan lampu? Penyelesaian : Diketahui, n = 18; n_1 = 4, n_2 = 3, n_3 = 5 dan n_(4 )= 6 (socket kosong) Jumlah cara pengaturan lampu = P(18; 4, 3, 5, 6) = 18!/((4!)(3!)(5!)(6!)) cara Berapa banyak cara membagikan delapan buah buku berbeda kepada 3 orang mahasiswa, bila Billy mendapat empat buah buku dan Andi serta Toni masing-masing memperoleh 2 buah buku. Penyelesaian : Diketahui n = 8, n_1 = 4, n_2 = 2, n_3 = 2 dan n_(1 )+ n_2 + n_3 = 4 + 2 + 2 = 8 Jadi, jumlah cara membagi seluruh buku = 8!/((4!)(2!)(2!)) = 420 cara KOMBINASI DENGAN PENGULANGAN Tinjau kembali persoalan memasukkan bola ke dalam kotak. Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak. Jika masing – masing kotak hanya boleh diisi paling banyak satu buah bola, maka jumlah cara memasukkan bola ke dalam kotak adalah C(n, r). Jika masing -masing kotak boleh lebih dari satu buah bola (tidak ada pembatasan jumlah bola), maka jumlah cara memasukkan bola ke dalam kotak adalah C(n + r – 1, r). C(n + r – 1, r) adalah jumlah kombinasi yang membolehkan adanya pengulangan elemen, yaitu dari n buah objek kita akan mengambil r buah objek, dengan pengulangan diperbolehkan. Pembuktian rumus kombinasi dengan pengulangan tidak disertakan di sini. Perhatikan bahwa C(n + r – 1, r) = C(n + r – 1, n – 1). Contoh : Toko roti ”Enak” menjual 8 jenis roti. Berapa jumlah cara mengambil 1 lusin roti (1 lusin = 12 buah) Penyelesaian : Analogikan 8 jenis roti sebagai 8 kotak. Kita akan mendistribusikan 12 roti itu ke dalam 8 kotak. Setiap kotak mungkin berisi lebih dari 1 buah roti. Di sini n = 8 dan r = 12, maka jumlah cara memilih 12 buah roti itu sama dengan jumlah cara memasukkan 12 buah roti ke dalam 8, yaitu sebanyak C(8 + 12 – 1, 12) = C(19, 12) cara. Andaikan terdapat kumpulan bola yang berwarna merah, biru dan hijau. Jumlah bola dari masing – masing warna paling sedikit jumlahnya 8 buah. Berapa banyak cara memilih 8 buah bola (tanda ada batasan warna)? Berapa banyak cara memilih 8 buahbola jika paling sedikit 1 bola dari masing – masing warna terwakili? Penyelesaian : n = 3, r = 8, maka C(n + r – 1, r) = C(3 + 8 – 1, 8) = C(10, 8) = 45 Ambil terlebih dulu 1 bola dari masing – masing warna, kemudian ambil 5 boal sisanya. Jumlah cara seluruhnya adalah C(3 + 5 – 1, 5) = C(7, 5) = 21 cara. Tiga buah dadu dilempar bersamaan. Berapa banyaknya hasil berbeda yang mungkin? Penyelesaian : C(6 + 3 – 1, 3) = C(8, 3) = 56.