KOMBINATORIKA

Erwin Harahap

Disampaikan pada acara SosialisasiOLIMPIADE MATEMATIKA, FISIKA, DAN KIMIA 2011

KOPERTIS WILAYAH IV JAWA BARATJatinangor- Bandung, 22 Maret 2011

1

2

KEMENTRIAN PENDIDIKAN NASIONALDIREKTORAT JENDERAL PENDIDIKAN TINGGI

DIREKTORAT PEMBELAJARAN DAN KEMAHASISWAAN2011

3

4

Materi Olimpiade Matematika

5

Jenis Tes/Soal

6

Content

• Koefisien Binomial

• Pohon

• The Marriage Theorem

• Pigeonhole Principle

• Inklusi-Eksklusi

• Paritas

• Eulerian / Hamiltonian

• Rekuren

7

Koefisien Binomial

Jika a dan b adalah bilangan real dan n adalahbilangan bulat positif, maka :

Materi terkait:

Prinsip penjumlahan, perkalian, Permutasi, kombinasi, permutasi dan kombinasi denganpengulangan

8

kknn

k

n baknCba0

),()(

Pohon (tree)

• Pohon (tree) adalah Suatu graf terhubung yang setiap pasangan simpulnya hanya dapat dihubungkan oleh satu lintasan tertentu

• Pohon merupakan graf tak-berarah yang terhubung dan tidak memiliki siklus maupun sirkuit.

9

The Marriage Theorem

• Jika S adalah suatu himpunan simpul di G, misal d(S) adalah sejumlah titik di G yang berpasangan dengan paling sedikit satuanggota S

• Pengertian tentang teorema ini lebihmengarah kepada graf bipartisi (bipartite)

10

The Marriage Theorem (lanjutan)

• Graf bipartisi (bipartite graph) adalah graf yang himpunan titiknya dapat dipisahkan menjadi duahimpunan tak kosong X dan Y sehingga masing-masing sisi di graf tersebut menghubungkan satutitik di X dan satu titik di Y

11

Pigeonhole Principle

• Jika k buah benda ditempatkan pada k buahkotak, maka akan terdapat paling sedikit 2 buah benda pada satu kotak

• Akan terdapat paling sedikit 2 sarung tanganpada tangan yang sama dari 3 buah sarungtangan

12

Pigeonhole Principle (lanjutan)

Jika n merpati (pigeon) dimasukkan kedalam m kandang(hole) dimana n>m , maka akan terdapat paling sedikitsatu kandang berisi lebih dari satu merpati

13

Pigeonhole Principle : Soal 1

Paling sedikit dalam berapa kali pelemparan darisebuah dadu agar dapat dijamin angka yang sama akan muncul 2 kali ?

14

Pigeonhole Principle : Jawab 1

Paling sedikit 7 kali pelemparan

15

Pigeonhole Principle : Soal 2

Misalkan P1, P2, P3, P4, P5 adalah lima titik latisberbeda pada suatu bidang cartesius.

Buktikan bahwa terdapat sepasang titik (Pi, Pj), i ≠ j, sedemikian sehingga ruas garis Pi Pj akanmemuat titik latis selain Pi dan Pj.

16

Pigeonhole Principle : Jawab 2

Misalkan 2 titik yang merupakan bagian dari Pn

titik tersebut adalah

Maka koordinat titik tengahnya adalah :

17

),(),( 2211 yxdanyx

))(),((2

12121 yyxx

Pigeonhole Principle : Jawab 2 (lanjutan)

Dikarenakan koordinat titik tengah tersebutmerupakan bilangan bulat maka

adalah genap jika dan hanya jika paritas x1 danx2 sama, serta paritas y1 dan y2 sama.

18

)()( 2121 yydanxx

Pigeonhole Principle : Jawab 2 (lanjutan)

4 Paritas titik yang mungkin :

(genap, genap), (genap, ganjil)

(ganjil, genap), (ganjil, ganjil)

Maka menurut pigeonhole principle, jikaterdapat 5 titik latis berbeda (P1, P2, P3, P4, P5 ), maka dua titik diantaranya memiliki paritas yang sama, dan memuat titik latis selain Pn

19

Prinsip Inklusi-Eksklusi

Untuk mencacah banyaknya unsur di dalam A∪B, kitadapat melakukannya dengan mencacah banyaknya unsurhimpunan A dan himpunan B − A dan kemudianmenjumlahkannya

20

|A B| =|A| + |B| -|A B|

Inklusi Eksklusi : Soal 1

Tentukan banyaknya bilangan bulat dari 1 s/d 1000 yang habis dibagi 3 atau 5

21

Inklusi Eksklusi : Jawab 1

|A| habis dibagi 3 333

|B| habis dibagi 5 200

|A B| habis dibagi 3*5 66

Total :

22

|A B| =|A| + |B| -|A B|

= 333 + 200 - 66

= 467

Inklusi Eksklusi : Soal 2

Tentukan banyaknya bilangan bulat dari 1 s/d 1000 yang tidak habis dibagi 3 dan tidak habis dibagi 5

23

Inklusi Eksklusi : Jawab 1 (lanjutan)

Hukum de Morgan :

24

(A’ B’)= (A B)’

|(A B)’| =|S| -|A B|

= 1000 - 467

= 533

Eulerian / Hamiltonian

• Misal G suatu graf. LIntasan Euler pada Gadalah lintasan yang memuat setiap sisi di G.

• Graf G di sebut graf Euler (Eulerian) jika Gmemuat lintasan Euler yang tertutup

• Sirkuit Hamilton G adalah sirkuit yang memuatsetiap titik di G

• Graf G di sebut Graph Hamilton (Hamiltonian) jika G memuat sirkuit Hamilton

25

Eulerian / Hamiltonian (lanjutan)

26

Rekuren

• Persamaan rekurensi adalah persamaan yang menentukan nilai suku xn dalam fungsi dari suku-suku sebelumnya, yaitu xn-1 , xn-2 , ...

• Persamaan rekurensi berbentuk

• Fungsi karakteristik

27

Rekuren : Soal 1

Barisan a1, a2, . . . didefinisikan dengan

a1 = 1, a2 = 1,

Dan

Tentukan bentuk eksplisit dari an

28

Rekuren : Jawab Soal 1

Barisan

Persamaan karakteristik :

Difaktorkan menjadi :

Bentuk umum :

29

Rekuren : Jawab Soal 1 (lanjutan)

a1 = 1

a2 = 1

Dengan demikian, bentuk umum an :

30

1)1(2 1

2

1

1 cc

1)1(2 2

2

2

1 cc

12 21 cc

14 21 ccEliminasi

Untuk n = 1,2,3, …

Rekuren : Soal 2

Barisan a1, a2, . . .

dimana

Tentukan bentuk umum

31

12 nn aa

11a

na

Rekuren : Jawab Soal 2

Persamaan karakteristik :

Bentuk umum :

maka

Dgn demikian : untuk n = 1,2,3, …

32

12 nn aa 02x

n

n ca 2

11a 21c

12n

na

Sekian dan Terima kasih

erwin2h@yahoo.com

http://erwin2h.wordpress.com

33