1 kombinatorial(3)

M a t e m a t i k a D i s k r i t

K o m b i n a t o r i a l 1

KOMBINATORIAL

Kombinatorial merupakan cabang matematika yang mempelajari pengaturan objek-

objek. Dengan analisis kombinatorial, memungkinkan kita dapat menentukan

pengaturan objek-objek tanpa dihitung satu per satu (enumerasi).

A. TEKNIK PERHITUNGAN

Dalam kombinatorial dikembangkan teknik-teknik menghitung jumlah kemungkinan

munculnya suatu kejadian tertentu atau jumlah elemen dalam suatu himpunan.

Contoh 1.

Pada semester ini, mahasiswa semester IV jurusan PMT, memperoleh tawaran 4 mata

kuliah bidang ilmu matematika yang berbeda, 3 mata kuliah bidang ilmu kependidikan

yang berbeda, dan 2 mata kuliah bidang ilmu agama yang berbeda. Berapa banyak cara

seorang mahasiswa semester IV tersebut jika:

a) harus memilih satu mata kuliah dari setiap bidang ilmu yang ditawarkan ?

b) hanya perlu memilih satu mata kuliah dari seluruh mata kuliah yang ditawarkan ?

Jawab:

a) Jumlah cara mahasiswa harus memilih satu mata kuliah dari setiap bidang ilmu

yang ditawarkan adalah:

b) Jumlah cara mahasiswa hanya memilih satu mata kuliah dari seluruh mata kuliah

yang ditawarkan adalah:

Seperti pada ilustrasi Contoh 1, pada permasalahan perhitungan sesungguhnya

terdapat dua prinsip dasar perhitungan, yaitu:

1. Prinsip Perkalian.

2. Prinsip Penjumlahan.

Dua prinsip ini akan menjadi pondasi dari hampir seluruh teknik perhitungan dalam

penyelesaian masalah perhitungan.



1. PRINSIP PERKALIAN

Pada langkah pertama terdapat cara dan pada langkah kedua terdapat cara, maka

jika harus memilih satu pilihan dari langkah pertama dan langkah kedua, maka jumlah

seluruh kemungkin akan terdapat cara.

Jika prinsip perkalian ini diperluas dengan sejumlah langkah, yaitu

langkah 1, terdapat cara,



:

langkah , terdapat cara,

Maka banyaknya aktivitas berbeda yang dilakukan secara bersamaan yang mungkin

adalah cara.

Dalam masalah pada Contoh 1, perhitungan banyaknya cara mahasiswa memilih satu

mata kuliah dari setiap bidang ilmu yang ditawarkan, dilakukan sebagai berikut:

langkah pertama adalah memilih satu mata kuliah dari bidang ilmu matematika

yang terdapat pilihan, kemudian

langkah kedua adalah memilih satu mata kuliah dari bidang ilmu kependidikan yang

terdapat pilihan, dan

langkah ketiga adalah memilih satu mata kuliah dari bidang ilmu agama yang

terdapat pilihan,

Jadi dengan prinsip perkalian diperoleh cara.

Interpretasi teori himpunan dalam prinsip perkalian ini, misalkan sebagai

produk Kartesian dari himpunan-himpunan dan , serta notasi jumlah elemen

pada himpunan , maka

Contoh 2.

Suatu sistem komputer menetapkan password bagi pengguna terdiri dari 4 digit

bilangan. Ada berapa banyak password yang mungkin ?

Jawab:

Untuk menempatkan 4 digit sebagai password maka dapat dilakukan:

langkah 1, mempunyai 10 cara (memilih satu bilangan dari 0, 1, 2, , 9),

langkah 2, mempunyai 10 cara,





Jadi akan diperoleh password.

2. PRINSIP PENJUMLAHAN

Pada langkah pertama terdapat cara dan pada langkah kedua terdapat cara, maka

jika harus memilih satu pilihan dari langkah pertama atau langkah kedua, maka jumlah

seluruh kemungkin akan terdapat cara.

Jika prinsip penjumlahan ini diperluas dengan sejumlah langkah, yaitu




:

langkah , terdapat cara,

Maka banyaknya aktivitas berbeda namun tidak dapat dilakukan secara bersamaan

adalah cara.

Dalam masalah pada Contoh 1, perhitungan banyaknya cara mahasiswa memilih satu

mata kuliah dari seluruh mata kuliah yang ditawarkan, dilakukan sebagai berikut:

langkah pertama adalah memilih satu mata kuliah dari bidang ilmu matematika

yang terdapat pilihan, atau

langkah kedua adalah memilih satu mata kuliah dari bidang ilmu kependidikan yang

terdapat pilihan, atau

langkah ketiga adalah memilih satu mata kuliah dari bidang ilmu agama yang

terdapat pilihan,

Jadi dengan prinsip penjumlahan diperoleh cara.

Interpretasi teori himpunan dalam prinsip penjumlahan ini, misalkan adalah

himpunan-himpunan saling lepas, maka

Contoh 3.

Di jurusan PMT pada suatu perguruan tinggi akan dilakukan pemilihan ketua himpunan

mahasiswa. Data seluruh mahasiswanya diperoleh sebagai berikut. Pada semester 2

terdapat 99 mahasiswa, semester 4 terdapat 103 mahasiswa, semester 6 terdapat 112



mahasiswa, dan pada semester 8 terdapat 120 mahasiswa, Berapa banyak pilihan yang

mungkin untuk pemilihan ketua himpunan mahasiswa tersebut, jika peraturan

menetapkan bahwa hanya mahasiswa semester 4 dan 6 yang boleh dipilih ?

Jawab:

Untuk memilih satu ketua himpunan mahasiswa maka dapat dilakukan:

langkah 1, jika memilih mahasiswa dari semester 4, dimiliki 103 cara, atau

langkah 2, jika memilih mahasiswa dari semester 6, dimiliki 112 cara,

Jadi akan diperoleh mahasiswa yang dapat dipilih.

B. DIAGRAM POHON

Diagram pohon adalah alat bantu untuk menghitung semua kemungkinan yang

dihasilkan oleh suatu barisan kejadian dalam sejumlah terhingga cara.

Contoh 4.

A B C dimana A = {1,2}, B = {a,b}, dan C = {x,y}.

Maka diagram pohonnya diilustrasikan sebagai berikut.

C. PRINSIP SARANG MERPATI

Prinsip Sarang Merpati (Pigeon hole): Jika sarang merpati terisi oleh atau

lebih merpati, maka paling tidak satu sarang terisi oleh lebih dari satu ekor merpati.

Contoh 5.

Dari 13 orang mahasiswa, maka akan ada minimal dua dari mahasiswa tersebut lahir

pada bulan yang sama.



Prinsip Sarang Merpati secara Umum: Jika sarang merpati terisi oleh

merpati, dimana bilangan bulat positif, maka paling tidak satu sarang merpati terisi

oleh atau lebih merpati.

atau

Jika objek ditempatkan ke lokasi, maka terdapat paling sedikit satu lokasi yang

memuat sedikitnya objek.

Contoh 6.

Tentukan jumlah minimum mahasiswa di suatu kelas untuk memastikan bahwa 3 orang

diantaranya lahir pada bulan yang sama.

Jawab:

Di sini bulan sebagai sarang merpati. Memastikan minimal 3 orang lahir pada

bulan yang sama maka Jadi jumlah minimum mahasiswa di

dalam kelas itu adalah orang.

Latihan 1.

1. Suatu kelas terdiri dari 18 mahasiswa laki-laki dan 14 mahasiswa perempuan. Ada

berapa cara memilih :

a. 1 orang perwakilan kelas ?

b. 2 orang perwakilan kelas sebagai ketua kelas dan wakilnya ?

c. 2 orang perwakilan kelas dengan memperhatikan 1 orang laki-laki dan 1 orang

perempuan ?

2. Sebuah sandi-lewat (password) panjangnya 6 sampai 8 karakter. Karakter boleh

berupa huruf atau angka. Berapa banyak kemungkinan sandi-lewat yang dapat

dibuat ?

3. Berapa banyak plat nomor kendaraan di Jakarta dengan memuat satu huruf di

depan, kemudian diikuti 4 digit angka, dan diakhiri dengan 2 digit huruf ?

4. Untuk nomor telepon dengan 7 digit, berapa banyak nomor telepon yang berbeda,

jika tidak diperbolehkan angka 0 pada digit pertama ?

5. Berapa jumlah pengambilan minimum dari himpunan agar dua

bilangan yang dipilih berjumlah 10 ?

6. Terdapat selusin kaus kaki warna coklat dan selusin kaus kaki warna hitam di dalam

laci. Jika anda mengambil kaus kaki tanpa melihat, berapa kaus kaki yang harus anda

ambil dari laci agar memastikan bahwa anda akan memperoleh sepasang kaus kaki

sewarna ?



Sekilas Fungsi Faktorial

Hasil kali semua bilangan bulat positif dari 1 hingga n dinotasikan oleh n! (n faktorial)

Maka,

Didapat juga

dan .

Untuk besar, digunakan pendekatan Stirling:

Dalam perhitungan banyaknya cara pengaturan objek-objek, sering kali kita perlu

memperhatikan dua hal yaitu pengaturan dengan urutan dan pengaturan tanpa

memperhatikan urutan. Dua hal ini dikenal dengan Permutasi dan Kombinasi.

Perhatikan contoh soal berikut.

Contoh 7.

Misalkan terdapat 4 objek huruf A, B, C, dan D.

a. Berapa banyak cara kita mengambil 3 huruf dari antara 4 huruf tersebut ?

b. Berapa banyak cara kita menyusun 3 huruf (berbeda) dari antara 4 huruf tersebut ?

Jawab:

a. Mengambil 3 huruf dari 4 huruf A, B, C, dan D dapat dilakukan sebagai berikut :

ABC, ABD, ACD, dan BCD, jadi terdapat 4 cara.

Langkah ini hanya meminta pengambilan dengan memperhatikan perbedaan huruf-

huruf saja, tidak memperhatikan urutan penempatan huruf-huruf tersebut. Pada

penulisan ABC misalnya, itu dianggap sama dengan ACB, BAC, BCA, CAB, maupun

CBA karena semua terdiri dari huruf yang sama yaitu A, B, dan C.

b. Menyusun 3 huruf (berbeda) dari 4 huruf A, B, C, dan D dengan cara enumerasi

diperoleh hasil berikut:

ABC, ACB, BAC, BCA, CAB, CBA (Ini penyusunan dari 3 huruf A, B, C)

ABD, ADB, BAD, BDA, DAB, DBA (Ini penyusunan dari 3 huruf A, B, D)

ACD, ADC, CAD, CDA, DAC, DCA (Ini penyusunan dari 3 huruf A, C, D)

BCD, BDC, CBD, CDB, DBC, DCB (Ini penyusunan dari 3 huruf B, C, D)

Pada langkah ini, urutan huruf menjadi perhatian. Jadi semua terdapat 24 cara

penyusunan.



Contoh 7 di atas memperlihatkan perbedaan cara pengaturan objek-objek yang

memperhatikan pengurutan dan tanpa pengurutan. Pada Contoh 7a diperlihatkan

contoh pengaturan objek huruf dengan aplikasi kombinasi, sedangkan pada Contoh 7b

diperlihatkan contoh pengaturan objek huruf dengan aplikasi permutasi. Selanjutnya,

Permutasi dan Kombinasi akan dibahas berikut.

D. PERMUTASI

Permutasi dari suatu himpunan objek adalah pengaturan yang memperhatikan urutan

dari objek-objek tersebut. Beberapa definisi tentang permutasi dinyatakan sebagai

berikut.

Definisi 1.1. Permutasi adalah jumlah urutan berbeda dari pengaturan objek-objek.

Definisi 1.2. Permutasi dari objek (berbeda), dinotasikan dengan , adalah

jumlah kemungkinan urutan objek yang dipilih dari objek dengan .

Jika mengulas pada Contoh 7b, kasus menyusun 3 huruf dari 4 huruf yang tersedia,

maka perhitungan permutasinya dilakukan sebagai berikut:

Langkah 1, penempatan huruf pertama dapat memilih dari 4 huruf,

Langkah 2, penempatan huruf kedua dapat memilih dari 3 huruf (karena 1 huruf

sudah digunakan),

Langkah 3, penempatan huruf ketiga dapat memilih dari 2 huruf tersisa.

Jadi permutasinya: cara.

Penyelesaian tersebut menunjukkan permutasi merupakan aplikasi dari prinsip

perkalian.

Teorema 1.1 Banyaknya tanpa pengulangan objek adalah

Bukti.

Langkah ke-1 didapat cara.



:

Langkah ke- didapat atau cara.

Dengan aturan perkalian diperoleh:



Contoh 8.

Merujuk pada soal Contoh 7,

a. Berapa banyak cara kita menyusun 4 huruf (berbeda) dari 4 huruf tersebut ?

b. Berapa banyak cara kita menyusun 3 huruf dari 4 huruf tersebut jika diperbolehkan

ada huruf yang sama atau penggunaan huruf berulang ?

Jawab:

a. Penyusunan 4 huruf (berbeda) tersebut dengan cara enumerasi diperoleh hasil

berikut:

ABCD, ABDC, ACBD,ACDB, ADBC, ADCB, BACD, BADC, BCAD, BCDA, BDAC, BDCA,

CABD, CADB, CBAD, CBDA, CDAB, CDBA, DABC, DACB, DBAC, DBCA, DCAB, DCBA.

Jumlah 24 cara.

Jika menggunakan Teorema 1.1 maka permutasi dengan nilai dan maka

cara.

b. Penyusunan 3 huruf (boleh terdapat huruf yang sama) dari 4 huruf, dengan prinsip

perkalian maka akan diperoleh:

Langkah 1, menempatkan huruf pertama dapat memilih 4 huruf,

Langkah 2, menempatkan huruf kedua dapat memilih 4 huruf,

Langkah 3, menempatkan huruf ketiga dapat memilih 4 huruf,

Jadi permutasinya: cara.

Contoh penyusunan antara lain : AAA, AAB, ABA, BAA, dan seterusnya.

Pada Contoh 8 memperlihatkan bentuk lain dari permutasi. Pada kasus 8a, kita masih

dapat menggunakan Teorema 1.1 dengan kasus khusus yaitu yang

kemudian dinyatakan menjadi sebuah akibat berikut.

Akibat 1.1 Banyaknya tanpa pengulangan objek adalah

Untuk kasus 8b, jika dibahas secara umum yaitu penyusunan objek dari objek,

serta diperbolehkan adanya pengulangan objek yang dipilih, maka diperoleh teorema

berikut.

Teorema 1.2 Banyaknya dengan pengulangan objek adalah

Bukti.






:

Langkah ke- didapat cara.


.

Permutasi dapat juga diaplikasikan pada bentuk melingkar. Contoh 9.

Berapa banyak cara mengatur 6 orang untuk duduk pada kursi

yang mengelilingi meja berbentuk lingkaran ?

Jawab :

Satu orang dapat duduk pada kursi mana saja. Lima orang lainnya dapat duduk dalam

cara.

Jika menggunakan Akibat 1.1, maka perhitungan permutasi seharusnya .

Namun demikian jika diperhatikan lebih seksama, jika orang pertama duduk di kursi

nomor 1, 2, 3, , atau 6, keterkaitan posisi duduk lima orang lainnya akan menghasilkan

tetap sama. Dengan demikian, permutasi melingkar dinyatakan dengan akibat berikut.

Akibat 1.2 Permutasi n objek yang mengelilingi bentuk melingkar (atau kurva tertutup

sederhana) adalah

Bukti.

Langkah ke-1 didapat cara (penempatan objek dimana saja pada lingkaran).



:

Langkah ke- didapat cara.


E. KOMBINASI

Kombinasi adalah bentuk khusus dari permutasi. Jika pada permutasi urutan hasil

pemilihan diperhitungkan, maka pada kombinasi, urutan diabaikan.

Definisi 2.1. Kombinasi dari objek (berbeda), dinotasikan dengan , adalah

jumlah pemilihan yang tidak terurut objek yang diambil dari objek dengan .



Pada Contoh 7a, misalnya pengambilan diperoleh ABC, ACB, BAC, BCA, CAB, atau CBA

itu akan dianggap sama dan dihitung hanya satu kali. Sedangkan pada permutasi,

urutan tersebut diperhatikan dengan jumlah pengurutan cara. Sehingga

perhitungan kombinasi pada kasus ini adalah

cara.

Secara umum teorema kombinasi dinyatakan sebagai berikut.

Teorema 2.1 Banyaknya adalah

Contoh 10.

Berapa banyak cara menyusun menu nasi goreng tiga kali seminggu untuk sarapan ?

Jawab:

Untuk menyusun agar nasi goreng ada dalam menu sarapan sebanyak tiga kali dalam

seminggu pada masalah ini tidak mempersoalkan urutan harinya. Sehingga pengaturan

dapat diperoleh dengan menghitung kombinasi 3 hari dari 7 hari dalam seminggu, yaitu

sebanyak

cara.

Seperti juga pada permasalahan dalam permutasi, ada kalanya objek-objek yang sama

atau adanya objek yang berulang merupakan permasalahan dalam kombinasi. Misalkan

permasalahan memasukkan bola dengan semua berwarna sama ke dalam kotak.

(i) Jika masing-masing kotak hanya boleh diisi paling banyak satu bola, maka jumlah

cara memasukkan bola ke dalam kotak adalah

(ii) Jika masing-masing kotak boleh lebih dari satu bola atau tidak ada pembatasan

jumlah bola, maka jumlah cara memasukkan bola ke dalam kotak adalah

adalah jumlah kombinasi yang membolehkan adanya pengulangan

elemen, yaitu dari objek kita akan mengambil buah objek, dengan pengulangan

diperbolehkan.

Teorema 2.2 Banyaknya kombinasi dengan pengulangan objek adalah

.

Contoh 11.

Misalkan sebuah persamaan , .

Berapa jumlah kemungkinan solusinya ?



Jawab:

Analogikan jumlah persamaan adalah 12 buah bola akan dimasukkan kedalam 4 kotak

yaitu empat variabel . Dalam hal ini maka Bagilah keduabelas bola

tersebut ke dalam tiap kotak. Sebuah kotak mungkin dapat diisi 1 bola, 2 bola, ., atau

12 bola, namun demikian dapat jug sebuah atau beberapa kotak tidak diisi bola sama

sekali, yang penting jumlah seluruh bola pada seluruh kotak ada 12. Misalnya,

Kotak 1 diisi 3 bola (




.

Banyak sekali jumlah susunan yang mungkin, namun seluruhnya dapat diperoleh

kemungkinan solusi.

Contoh 12.

Toko roti Enak menjual 8 jenis roti. Berapa jumlah cara mengambil 1 lusin roti ?

Jawab:

Diketahui terdapat 8 jenis roti maka dan pengambilan 1 lusin = 12 roti maka

. Sehingga jumlah cara pembagian 12 roti dari 8 jenis roti diperoleh dengan

menggunakan Teorema 2.2, yaitu

= 50.338 cara.

F. PERMUTASI DAN KOMBINASI BENTUK UMUM

Jika kita mempunyai buah bola dengan warna ada yang berbeda dan ada juga yang

sama. Misalkan

bola warna 1 jumlahnya bola,

bola warna 2 jumlahnya bola,

:

bola warna ke- terdapat bola,

maka bola.

Bila terdapat kotak dan kita diminta meletakkan masing-masing 1 bola didalamnya,

berapa banyak cara pengaturan bola tersebut ?

Dengan menggunakan permutasi dasar, akan diperoleh Namun demikian

karena warna bola tidak berbeda semuanya (ada yang berwarna sama), maka perlu

memperhatikan bahwa untuk



bola warna 1 terdapat cara,

bola warna 2 terdapat cara,

:

bola warna ke- terdapat cara,

maka permutasinya

Masih pada kasus yang sama, dapat juga diselesaikan dengan konsep kombinasi. Untuk

menempatkan bola warna 1 ke dalam kotak berarti kita dapat memilih dari bola,

maka kita peroleh cara. Setelah bola warna 1 ditempatkan pada kotak,

sekarang menempatkan bola pada kotak untuk bola warna 2, maka kini kita

peroleh cara. Masih dengan cara yang sama, kini kita tempatkan bola

warna 3 sehingga diperoleh cara. Demikian seterusnya, sehingga

akhirnya didapat cara untuk menempatkan bola warna .

Jumlah cara pengaturan seluruh bola dalam kotak adalah:

Penyelesaian cara permutasi dan kombinasi seperti kasus di atas disebut permutasi

dan kombinasi bentuk umum.

Teorema 3.1. Apabila merupakan himpunan ganda dengan objek yang didalamnya

terdiri atas objek berbeda dan tiap objek memiliki jumlah (jumlah objek

seluruhnya ), maka jumlah cara menyusun seluruh objek tersebut

adalah:

Contoh 13.

Berapa banyak string yang dapat dibentuk dari huruf-huruf pada kata MISSISSIPPI ?

Jawab:

Untuk huruf M, banyaknya , Untuk huruf I, banyaknya , Untuk huruf S, banyaknya , Untuk huruf P, banyaknya ,



Jumlah

Penyelesaian perhitungan banyaknya string yang dapat dibentuk dapat dalam 2 cara:

1. Dengan permutasi umum:

string.

2. Dengan kombinasi:

string.

Pada tabel berikut, dimuat ringkasan formula permutasi dan kombinasi :

Tabel 2.1 Pengaturan objek dari suatu himpunan beranggota objek.

Dengan urutan Tanpa urutan

Tanpa pengulangan

Dengan pengulangan

Bentuk umum

LATIHAN 2.

1. a. b.

c. d.

2. Ada berapa banyak pengurutan A, B, C, D, E, F, G, H, jika pengurutan terdiri dari :

a. 7 huruf ? b. 5 huruf dengan pengulangan ?

3. Dari kata PERMUTASI, berapa banyak string yang dapat dibentuk jika harus memuat

a. string ASI ? b. string ASI dan ER ?

4. Suatu laci berisi 8 kaos kaki biru dan 6 kaos kaki merah. Tentukan jumlah cara dua

kaos kaki dapat diambil dari laci tersebut jika:

a. warnanya boleh sebarang !

b. warnanya harus sama sepasang !

5. Di dalam sebuah keranjang terdapat 5 buah apel dan 6 buah jeruk. Buah-buahan

tersebut akan diambil 6 buah. Berapa cara pemilihan buah tersebut jika komposisi

ditentukan sebaga berikut:

a. Terdiri dari 2 apel dan 4 jeruk ?

b. Minimal ada 4 apel ?

6. Berapa cara menyusun huruf-huruf dari kata MATEMATIKA ?



KOEFISIEN BINOMIAL

Menyatakan kombinasi dari objek, selain dinotasikan dengan terdapat notasi

lain juga yang umum digunakan untuk menyatakannya, yaitu .

Akibat 2.1 Misalkan adalah bilangan bulat non-negatif dengan

Bukti.

Namun demikian, bilangan ini lebih sering disebut koefisien binomial, karena

bilangan tersebut merupakan koefisien-koefisien dari ekspansi ekspresi binomial yaitu

. Koefisien-koefisien binomial ini merupakan koefisien-koefisien yang menjadi

bagian penting pada beberapa teorema antara lain Pascal, Vandermonde, dan

(Teorema) Binomial. Berikut pembahasannya.

Teorema 4.1 (Teorema Pascal)

Misalkan adalah bilangan bulat non-negatif dengan

Bukti.

Misalkan adalah sebuah himpunan yang memuat elemen dengan sebagai salah

satu elemennya, serta terdapat himpunan . Perlu diingat bahwa terdapat

himpunan bagian dari yang memuat elemen. Sehingga pada suatu himpunan

bagian dari dengan elemen, kemungkinan elemen-elemennya adalah elemen

dari serta memuat atau memuat elemen dari tapi tidak memuat . Jadi jika

terdapat

himpunan bagian dengan elemen dari , terdapat

himpunan

bagian dengan elemen dari termasuk sebagai elemennya. Maka terdapat

himpunan bagian dengan elemen dari tanpa , jika terdapat himpunan bagian

dengan elemen dari Akibatnya

Teorema Pascal merupakan dasar untuk koefisien-koefisien binomial dari suatu

pengaturan geometri dalam segitiga pascal seperti dapat dilihat pada Gambar 3.1. Pada

baris kedalam segitiga memuat koefisien-koefisien binomial



Segitiga ini dikenal sebagai Segitiga Pascal. Teorema Pascal menunjukkan bahwa ketika

dua koefisien binomial yang bertetangga dalam segitiga dijumlahkan, koefisien binomial

pada baris berikutnya antara dua koefisien binomial tersebut adalah hasil

penjumlahannnya.

Gambar 3.1 Segitiga Pascal

Teorema 4.2 Misalkan adalah bilangan bulat non-negatif, maka

Bukti.

Suatu himpunan dengan elemen mempunyai jumlah total himpunan bagian yang

berbeda. Masing-masing himpunan bagian ada yang mempunyai nol elemen, satu

elemen, dua elemen, , atau elemen. Maka terdapat himpunan bagian dengan nol

elemen, himpunan bagian dengan satu elemen,

himpunan bagian dengan dua

elemen, , dan himpunan bagian dengan elemen. Sehingga jumlah seluruh

himpunan bagian dari himpunan dengan elemen adalah

.

Teorema 4.3 (Teorema Vandermonde)

Misalkan adalah bilangan bulat non-negatif, dengan maka

Bukti.

Misalkan terdapat dua himpunan yang masing-masing memiliki dan elemen. Jumlah

cara untuk mengambil elemen dari gabungan dua himpunan tersebut adalah



Cara lain untuk mengambil elemen dari gabungan adalah mengambil elemen dari

himpunan pertama dan mengambil elemen dari himpunan kedua, dimana

, maka diperoleh

menggunakan aturan perkalian. Sehingga jumlah

cara mengambil elemen dari gabungan dua himpunan adalah

Teorema Binomial menunjukkan koefisien-koefisien sebagai ekspansi dari kekuatan

ekspresi binomial. Ekspresi binomial sederhananya adalah penjumlahan dua suku yaitu

(Suku bisa merupakan hasil kali dari konstanta dan variabel, namun pada

pembahasan ini tidak memperhatikan hal itu). Contoh berikut memberi ilustrasi

bagaimana teorema tersebut akan digunakan.

Contoh 14.

Tentukan ekspansi dari !

Jawab:

Ekspansi dapat diperoleh dengan melakukan perkalian suku sebanyak tiga kali.

.

Teorema Binomial memberikan cara untuk menjabarkan bentuk perpangkatan

dengan adalah bilangan bulat non-negatif, sebagai berikut.

1. Suku pertama adalah , sedangkan suku terakhir adalah .

2. Pada setiap suku berikutnya, pangkat berkurang satu sedangkan pangkat

bertambah satu. Untuk setiap suku, jumlah pangkat dan adalah .

3. Koefisien untuk , yaitu suku ke-( ), adalah

Dari aturan tersebut maka diperoleh:

Teorema 4.4 (Teorema Binomial)

Misalkan adalah variabel, dan adalah bilangan bulat non-negatif, maka



Aplikasi Teorema Binomial ini, dapat digunakan sebagai alternatif bagi penggunaan

segitiga Pascal, contohnya yaitu:

Contoh 15.

Tentukan suku ke-4 dari penjabaran perpangkatan !

Jawab:

Suku ke-4 maka : , karena maka

.

Contoh 16.

Jabarkan .

Jawab:

Penjabaran:

Untuk

LATIHAN 3.

1. Pada konsep Segitiga Pascal, tentukan barisan bilangan pada:

a. Baris ke-8

b. Baris ke-9

2. Gunakan Teorema Binomial untuk ekspansi :

a.

b.

3. Tentukan koefisien :

a. pada ekspansi

b. pada ekspansi

4. Tentukan koefisien :

a. pada ekspansi

b. pada ekspansi

1 kombinatorial(3)

Documents