matematika diskrit PDF

Preview

Summary

BAB 1 METODE FUNDAMENTAL PENCACAHAN Dalam bab ini diperkenalkan konsep dasar dari permutasi dan kombinasi, serta perhitungan atau numerasi (pencacahan) menyangkut permutasi maupun kombinasi. Diawali bab ini dengan dua prinsip utama dalam numerasi. 1.1 Prinsip Dasar dan Pencacahan Terdapat dua prinsi...

Description

BAB 1 METODE FUNDAMENTAL PENCACAHAN

Dalam bab ini diperkenalkan konsep dasar dari permutasi dan kombinasi, serta perhitungan atau numerasi (pencacahan) menyangkut permutasi maupun kombinasi. Diawali bab ini dengan dua prinsip utama dalam numerasi.

1.1

Prinsip Dasar dan Pencacahan Terdapat dua prinsip atau aturan utama dalam pencacahan yaitu aturan perkalian ( Multiplication Rule ) dan aturan penambahan ( Addition Rule )

1.1.1 Aturan Perkalian ( Multiplication Rule ) Bunyi aturan perkalian : Jika kejadian pertama dapat terjadi dalam n1 cara, dan setiap kejadian pertama diikuti oleh kejadian kedua dengan n2 cara, dan setiap kejadian kedua diikuti oleh kejadian

ketiga

dengan

n3

cara,

dan

seterusnya,

dan

setiap

kejadian

ke-(p-1) diikuti oleh kejadian ke-p yang terjadi dalam np cara, maka kejadian pertama, kedua, ketiga, … , ke-p. Secara bersama-sama terjadi dalam n1 x n2 x n3 x … x np cara.

CONTOH : 1. Berapa macam menu makan siang yang terdiri atas sup, sandwich, desert dan minuman yang dapat dipilih dari 4 macam sup, 3 jenis sandwich , 5 desert dan 4 minuman ? Penyelesaian : Banyaknya cara untuk memilih sup ada 4 cara Banyaknya cara untuk memilih sandwich ada 3 cara Banyaknya cara untuk memilih desert ada 5 cara, dan Banyaknya cara untuk memilih minuman ada 4 cara Jadi banyaknya macam menu makan siang adalah 4 x 3 x 5 x 4 = 240

1

2. Berapa banyak bilangan 4 digit yang tidak mengandung angka yang berulang ? Penyelesaian : Digit pertama ada 10 kemungkinan angka Digit kedua ada 9 kemungkinan angka Digit ketiga ada 8 kemungkinan angka Digit keempat ada 7 kemungkinan angka Jadi banyaknya bilangan 4 digit yang tidak mengandung angka yang berulang adalah sebanyak 10 x 9 x 8 x 7 = 4536

SOAL LATIHAN 1.1.2 1. Sebuah

sandi-lewat

(password)

panjangnya

6

sampai

8

karakter.

Karakter boleh berupa huruf atau angka. Berapa banyak kemungkinan sandi-lewat yang dapat dibuat? 2. Bit biner hanya 0 dan 1. Berapa banyak string biner yang dapat dibentuk jika : a. Panjang string 5 bit b. Panjang string 8 bit

1.1.2 Aturan Penambahan ( Addition Rule ) Bunyi aturan penambahan : Jika kejadian pertama dapat terjadi dalam n1 cara, kejadian kedua secara terpisah dapat terjadi dalam n2 cara, dan seterusnya, kejadian ke-p secara terpisah terjadi dalam np cara maka kejadian pertama atau kedua, …, atau kejadian ke-p. Dapat terjadi dalam n1 + n2 + … + np cara.

CONTOH : 1. Seseorang mahasiswa ingin memebeli sebuah motor. Ia dihadapkan untuk memilih pada setu jenis dari tiga merek motor, honda 3 pilihan, susuki 2 pilihan, dan yamaha 2 pilihan. Berapa cara yang dapat dilakukan ? Penyelesaian : Dengan demikian, mahasiswa tersebut mempunyai pilihan sebanyak 3+2+2=7 pilihan

2

2. Seorang Guru SMA di daerah, mengajar murid kelas X, kelas XI, dan kelas XII. Jika jumlah murid kelas X adalah 25 orang dan jumlah murid kelas XI adalah 27 orang serta jumlah murid kelas XII adalah 20 orang. Berapa banyak jumlah murid yang diajar guru ? Penyelesaian : Maka Guru SMA tersebut adalah mengajar 25+27+20= 72 murid

SOAL LATIHAN 1.1.2 1. Dalam Perpustakaan terdapat 10 buku Matematika, 25 buku Statistik dan 5 buku social. Berapa cara yang dapat dilakukan untuk mengambil 1 buku ? 2. Sekelompok mahasiswa terdiri dari 4 orang pria dan 3 orang wanita. Berapa cara memilih 1 orang yang mewakili kelompok tersebut (tidak perduli pria atau wanita)?

1.2

Permutasi Permutasi

adalah penyusunan beberapa objek dari suatu grup dengan

memperhatikan urutan. Didalam permutasi urutan diperhatikan. Rumus Permutasi : P ( n , r ) =

𝒏! ( 𝒏−𝒓 )!

Syarat : n  r atau n = r

Notasi : nPr atau P𝑟𝑛 atau P (n, r) CONTOH : 1. Sebuah dalam tim olahraga ada 10 orang siswa yang dicalonkan untuk menjadi pemain. Namun hanya 5 orang boleh menjadi pemain utama. Tentukan banyak cara yang bisa dipakai untuk memilih para pemain utama tersebut? Penyelesaian: Diketahui n = 10 dan r = 5 P(n,r)=

𝑛! ( 𝑛−𝑟 )!

P ( 10 , 5 ) =

10! ( 10−5 )!

=

10! 4!

=

10× 9 × 8 × 7× 6× 5 × 4! 4!

= 151.200 cara

3

SOAL LATIHAN 1.2 1. Menjelang Pergantian kepengurusan BEM FKIP UHAMKA akan dibentuk panitia inti sebanyak 2 orang (terdiri dari ketua dan wakil ketua), calon panitia tersebut ada 6 orang yaitu: a, b, c, d, e, dan f. Ada berapa pasang calon yang dapat duduk sebagai panitia inti tersebut? 2. Sebuah bilangan 5 angka dibentuk dari angka 1,2,3,4,5,6,7 berapakah banyak bilangan yang mungkin jika angka-angka dalam bilangan tersebut tidak ada yang sama? 1.2.1 Permutasi Siklik Biasa Dapat dikatakan permutasi siklik jika beberapa objek yang dijajar melingkar (pada suatu lingkaran) dengan memperhatikan arah melingkarnya, misalnya searah putaran jarum jam.

CONTOH : 1. Ada Empat kubus yang diberi label A, B, C, dan D yang akan dijajar melingkar searah dengan putaran jarum jam ? Penyelesaian : Maka dari 4 objek itu akan didapat enam buah permutasi siklik yaitu, (ABCD), (ABDC), (ACBD), (ACDB), (ADBC), dan (ADCB). Perhatikanlah bahwa dari setiap permutasi-4 siklik tersebut terdapat 4 permutasi linear. Sehingga seluruhnya terdapat 6 × 4 = 24 permutasi linear.

Jika pengulangan tidak diperkenankan, maka hubungan antara banyaknya permutasi siklik dan banyaknya permutasi linear disajikan dalam teorema berikut. 

Teorema 1.1 𝐽𝑖𝑘𝑎 𝑛 𝑑𝑎𝑛 𝑘 𝑑𝑢𝑎 𝑏𝑖𝑙𝑎𝑛𝑔𝑎𝑛 𝑏𝑢𝑙𝑎𝑡 𝑝𝑜𝑠𝑖𝑡𝑖𝑓, 𝑚𝑎𝑘𝑎 𝑛!

𝑃 ∗ (𝑛, 𝑘) = 𝑛𝑘 ; dan 𝑃(𝑛, 𝑘) = 𝑛−𝑘, untuk 𝑘 ≤ 𝑛

4



Teorema 1.2 Jika 𝑃𝑆(𝑛, 𝑘) menyatakan banyaknya permutasi-k siklik dari n objek berbeda, maka 𝑃𝑆(𝑛, 𝑘) =

𝑃(𝑛, 𝑘) 𝑛! = 𝑘! 𝑘(𝑛 − 𝑘)!

Khususnya, 𝑃𝑆(𝑛, 𝑛) = (𝑛 − 1)! Bukti; Karena dari setiap permutasi-k siklik terdapat k buah permutasi-k linear, maka berdasarkan aturan perkalian diperoleh 𝑃𝑆(𝑛, 𝑘) × 𝑘 = 𝑃(𝑛, 𝑘) Ekuivalen dengan 𝑃𝑆(𝑛, 𝑘) × 𝑘 =

𝑃(𝑛, 𝑘) 𝑘

;

Jika 𝑘 = 𝑛 diperoleh

Berdasarkan teorema 1.1 𝑛!

diperoleh, 𝑃𝑆(𝑛, 𝑘) = 𝑛−𝑘

𝑃𝑆(𝑛, 𝑛) =

𝑛! 𝑛(𝑛 − 1)! = = (𝑛 − 1)! 𝑛. 0! 𝑛

Sehingga teorema 1.2 terbukti. Catatan: Jika arah putaran tidak dibedakan, artinya memutar searah ataupun berlawanan arah dengan arah putaran jarum jam tidak dibedakan, maka permutasi siklik (ABCD) ekuivalen dengan permutasi siklik (ADBC). CONTOH : 1. Sekelompok mahasiswa yang terdiri dari 10 orang akan mengadakan rapat dan duduk mengelilingi sebuah meja, ada berapa carakah kelima mahasiswa tersebut dapat diatur pada sekeliling meja tersebut ? Penyelesaian: 𝑃𝑆(𝑛, 𝑘) = (𝑛 − 1)! 𝑃𝑆(10 , 5) = (10 − 1)!

5

= 9! =9×8×7×6×5×4×3×2×1 = 362880 cara 2. Dalam sebuah keluarga yang terdiri dari seorang ayah, seorang ibu, dan 3 orang anaknya makan bersama dan mengelilingi sebuah meja makan. Berapa banyaknya cara yang berlainan saat mereka dapat duduk, jika: a. Mereka berpindah-pindah tempat ? b. Ayah dan ibu selalu berdekatan ? Penyelesaian: a. Banyaknya anggota keluarga adalah 5 orang (seorang ayah, seorang ibu, dan 3 orang anak). Sehingga, banyaknya cara yang berlainan saat mereka duduk berpindah-pindah tempat adalah (5 – 1)! = 4! = 24 cara. Perhatikan gambar berikut.

b. Ayah dan ibu selalu berdampingan, sehingga pasangan ini dapat kita anggap satu. Sehingga terdapat 4 objek yang akan disusun secara siklis. Akan tetapi pasangan ayah dan ibu dapat disusun kembali menjadi 2P2 cara. Sehingga banyaknya susunan agar ayah dan ibu selalu berdekatan adalah (4 – 1)! × 2P2 = 3! × 2! = 12 cara

SOAL LATIHAN 1.2.1 1. Dalam suatu pesta terdapat 7 orang yang duduk mengelilingi sebuah meja makan berbentuk lingkaran. Maka ada berapa cara yang mungkin dapat dibuat untuk menempati posisi yang berlainan? 2. 5 orang direktur suatu perusahaan sedang melakukan pertemuan disebuah restoran dan mereka menempati meja lingkaran yang tidak jauh dari pintu masuk. Maka ada berapa cara untuk menyusun kursi para direktur tersebut?

6

3. Tentukan banyaknya permutasi siklik dari 4 unsur! 4. Ada berapa cara jika 8 gelas warna yang mengitari meja bundar, dapat menempati kedelapan tempat dengan urutan yang berlainan? 5. Dengan berapa cara potongan 6 kue yang berbeda dapat disusun melingkar diatas sebuah meja? 1.2.2 Permutasi Siklik (PS*) Jika

PS* (n,k) menyatakan banyak permutasi-k siklik dari n objek tanpa

memperhatikan arah putaran, maka : 𝑃𝑆 ∗ (𝑛, 𝑘) =

𝑃𝑆(𝑛,𝑘) 2

𝑛!

= 2𝑘(𝑛−𝑘)!

Jika arah putaran tidak dibedakan, artinya memutar searah ataupun berlawanan arah dengan arah putara jarum jam tidak dibedakan, maka permutasi siklik (12345) ekuivalen dengan permutasi siklik (15432), ditulis permutasi siklik (12345), seperti terlihat pada diagram berikut : 1

1

5

2

4

3

12345

5

2

4

3

15432

CONTOH : 1.

Terdapat 4 orang, ada berapa susunan duduk. Jika, arah putaran tidak dibedakan ? Penyelesaian : 4! 2(4)(4−4)!

=

4×3×2×1 2×4

=3

SOAL LATIHAN 1.2.2 1.

Empat orang siswa masuk perpustakaan sekolah. Mereka membaca di meja bundar. Berapa cara agar keempat siswa dapat duduk melingkar dengan urutan yang sama ?

2.

Berapa banyaknya permutasi dari cara duduk dapat terjadi jika 8 orang disediakan 4 kursi pada meja bundar dengan arah tempat duduk tidak dibedakan ?

7

3.

Dari 50 manik-manik berlabel 1, 2, 3, 4, …20 akan dibuat gelang yang terdiri dari 10 manik-manik berbeda. Maka banyaknya gelang yang mungkin terbentuk adalah …

4.

Sekelompok mahasiswa yang terdiri dari 10 orang akan mengadakan rapat dan duduk mengelilingi sebuah meja, ada berapa carakah kelima mahasiswa tersebut dapat diatur jika arah putaran tidak dibedakan .

5.

Jika kita mempunyai 75 permata , berlebel 1,2,3,4, … 30 dan ingin digunakan 25 permata untuk membuat kalung, maka ada berapa kemungkinan gelang yang dapat dibuat ?

1.3

Kombinasi Istilah kombinasi dalam matematika yaitu kombinatorik yang berarti himpunan objek yang tidak mementingkan urutan. Kombinasi berbeda dengan permutasi yang mementingkan urutan. Sehingga kombinasi r objek yang dipilih dari n objek adalah susunan r objek tanpa memperhatikan urutan atau posisi. Kombinasi biasa dirumuskan dengan:

n!

Crn = r!(n−r)!

Contoh : 1. Dari 40 nomor rekening akan diundi untuk memenangkan 3 hadiah yang sama. Berapa banyaknya susunan pemenang yang mungkin terbentuk ? Penyelesaian : 40!

40!

C340 = 3!(40−3)! = 3!37! =

40 . 39 . 38 . 37! 3!37!

=

40 . 39 . 38 3. 2. 1

= 9880

2. Saat akan menjamu Bayern Munchen di Allianz arena, Antonio Conte (Pelatih Juventus) punya 20 pemain yang akan dipilih 11 diantaranya untuk jadi starter. Berapa banyak cara pemilihan starter tim juventus? (tidak memperhatikan posisi pemain). Penyelesaian :

8

20!

20!

20 C11 = 11!(20−11)! = 11!9! =

=

20 . 19 . 18 . 17 . 16 . 15 . 14 . 13 . 12 . 11!

20 . 19 . 18 . 17 . 16 . 15 . 14 . 13 . 12 9. 8. 7. 6. 5. 4. 3. 2. 1

11!9!

= 167.960

3. Banyaknya segitiga yang dapat dibuat dari 7 titik tanpa ada tiga titik yang terletak segaris adalah ? Penyelesaian : Membuat segitiga dengan memilih 3 titik dari 7 titik yang tersedia adalah masalah 7!

7. 6 . 5

kombinasi C(7, 3). Jadi, banyaknya segitiga C(7,3) 3!4! = 3 .

2. 1

= 35

SOAL LATIHAN 1.3 1.

Tentukan kombinasi 5 dari 8 huruf yang berbeda missalnya ABCDEFGH ?

2.

Bayu membawa 16 pemain saat Persita melawan Persija di GBK Stadium. 11 orang diantaranya akan dipilih untuk bermain pada babak pertama. jika kita tidak memperhatikan posisi pemain, berapakah banyaknya cara yang dapat diambil oleh pelatih untuk memilih pemain ?

3.

Siswa di minta mengerjakan 9 dari 10 soal ulangan, tetapi soal 1-5 harus di kerjakan. Banyaknya pilihan yang dapat diambil murid adalah ?

4.

Dalam suatu pertemuan terdapat 10 orang yang belum saling kenal. Agar mereka saling kenal maka mereka saling berjabat tangan. Berapa banyaknya jabat tangan yang terjadi ?

5.

Sebuah perusahaan membutuhkan karyawan yg terdiri dari 5 putra dan 3 putri. Jika terdapat 15 pelamar, 9 diantaranya putra. Tentukan banyaknya cara menyeleksi karyawan!

6.

Sebuah kotak berisikan 5 bola merah dan 10 bola putih. Ada berapa cara mengambil 6 bola sedemikian hingga dari bola-bola yang terambil tersebut terdapat : a. Tepat 2 bola merah b. Paling banyak 2 bola merah

7.

Sebuah kantong berisi 6 kelereng putih dan 4 kelereng merah.Dari kantong itu diambil 3 kelereng sekaligus secara acak.Ada berapa cara pengambilan,jika kelereng yang diambil adalah:

9

a. 2 kelereng berwarna putih dan 1 kelereng berwarna merah? b. Ketiganya bebas warnanya? 8.

Dalam sebuah ruangan terdapat 15 orang. Jika mereka saling bersalaman maka berapa banyak salaman yang akan terjadi?

9.

Terdapat 5 mawar merah , 10 mawar putih ditoko bunga. Dipilih 4 mawar secara acak dari toko. Berapa banyak kemungkinan dari : a.

Tepat 2 mawar merah

b.

Paling sedikit 3 mawar putih

10. Seorang penjahit akan membeli 3 benang hitam dan 2 benang biru dari seorang pedagang yang memiliki 6 benang hitam dan 4 benang biru. Dengan berapa cara penjahit tersebut dapat memilih benang-benang yang di inginkannya?

1.3.1

Kombinasi dengan Pengulangan Kombinasi dengan pengulangan berukuran r dari n obyek adalah seleksi (pengambilan) berukuran r dari kumpulan beranggota n obyek dengan urutan tidak diperhatikan dan pengulangan (pengembalian) dibolehkan.

Teorema : Banyaknya kombinasi dengan pengulangan berukuran r dari n obyek adalah

(𝑛+𝑟−1)! 𝑟!(𝑛−1)!

𝑛+𝑟−1 𝑛+𝑟−1 )=( ) 𝑛−1 𝑟

=(

Untuk memperoleh dari mana bilangan dalam teorema tersebut diperoleh, berikut ini diberikan contoh sebagai ilustrasi untuk menuju ke suatu generalisasi.

CONTOH : 1. Untuk memenuhi syarat kelulusan, 7 orang mahasiwa yang terancam DO (drop out) diwajibkan mengambil 1 mata kuliah pilihan yang dipilih dari 4 mata kuliah pilihan yang ditawarkan: Kriptologi, Teori Pengkodean, Matematika Finansial, dan Optimisasi Kombinatorial. Ada berapa cara pemilihan 4 mata kuliah oleh ketujuh mahasiswa yang bersangkutan? Penyelesaian : Misalkan K, T, M, dan O menyatakan Kriptologi, Teori Pengkodean, Matematika Finansial, dan Optimisasi Kombinatorial. Sebagai gambaran, suatu contoh cara

10

pemilihan yang mungkin adalah K dipilih oleh 2 mahasiswa, T oleh 2 mahasiswa, M oleh 2 mahasiswa, dan O oleh 1 mahasiswa, kemudian dinotasikan dengan K,K,T,T,M,M,O dan ditulis sebagai xx|xx|xx|x.

Agar lebih jelas beberapa cara pemilihan yang mungkin lainnya diberikan dalam tabel berikut ini. Cara pemilihan yang mungkin

Ditulis sebagai

K,K,K,K,T,M,O

xxxx|x|x|x

K,K,K,K,O,O,O

xxxx|||xxx

T,T,M,M,M,M,O

|xx|xxxx|x

K,T,T,T,T,T,T

x|xxxxxx||

O,O,O,O,O,O,O

|||xxxxxxx

K,K,K,T,M,O,O

xxx|x|x|xx

M,M,M,M,M,M,M

||xxxxxxx|

Beberapa contoh dalam tabel di atas mengarahkan kita pada suatu kesimpulan bahwa masalah menentukan jumlah semua cara pemilihan yang mungkin dapat dibawa ke masalah mencari banyaknya permutasi berukuran 10 dengan 2 jenis, yaitu 7 obyek berjenis "x"dan tiga obyek berjenis "|". Dengan demikian ada

10! 3!7!

10 ) cara ketujuh mahasiswa tersebut 7

=(

memilih 4 mata kuliah yang ditawarkan.

2. Ada berapa cara apabila 13 kelereng yang identik didistribusikan ke dalam 5 lubang yang berbeda? Penyelesaian : Dengan argumen yang sama dengan jawaban Contoh 1 diperoleh jawaban 17! 17 =( ) 13 4! 3! 3. Tentukan banyaknya semua penyelesaian intejer dari persamaan x1 + x2 + x3 + x4 + x5 + x6 = 20 ; dimana xi ≥ 0 untuk setiap 1 ≤ i ≤ 6. Penyelesaian : Dengan argumen yang sama dengan jawaban Contoh 1 diperoleh jawaban

11

25! 25 =( ) 20 5! 20!

Catatan Dari ketiga contoh terakhir di atas, kita sampai pada kesimpulan bahwa ketiga pernyataan berikut adalah ekuivalen: 1.

Banyaknya pemilihan berukuran r dari koleksi beranggota n obyek dengan urutan tidak diperhatikan dan pengulang dibolehkan.

2.

Banyaknya solusi intejer dari persamaan x1 + x2 + … + xn = r, dimana xi ≥ 0 untuk setiap 1 ≤ i ≤ n.

3.

Banyaknya cara pendistribusian apabila r obyek yang identik didistribusikan ke dalam n wadah yang berbeda.

SOAL LATIHAN 1.3.1 1. Tulislah semua kombinasi-3 dari {a, b, c, d} sedemikian sehingga pengulangan

diperbolehkan. 2. Jika n adalah bilangan bulat positif, berapa banyaknya (i, j, k) yang mungkin

apabila 1 ≤ i ≤j ≤ k ≤ n?

Perhatikan kisi-kisi berukuran 3 x 4 berikut:

12

Jika kita ingin melintas dari titik P (pojok kiri bawah) ke titik Q (pojok kanan atas) dengan syarat hanya boleh bergerak kekanan (K) dan keatas (A). salah satu lintasan yang mungkin diperlihatkan oleh lintasan-1. Lintasan ini dapat dinyatakan dengan barisan KKAKKAA (2 langkah kekanan, dilanjutkan 1 langkah keatas, dilanjutkan 2 langkah ke kanan dan 2 langkah keatas). Lintasan yang lain Lintasan-2 yang dapat dinyatakan dengan barisan AAKKKAK. Perhatikan bahwa dalam setiap barisan terdapat empat K dan tiga A. Dai setiap barisan yang demikian, diperoleh sebuah lintasan dari P dan Q. Jadi, banyak lintasan yang mungkin sama dengan banyaknya binair 7 huruf yang memuat empat huruf K dan tiga huruf A. Barisan yang dimaksud sama dengan banyaknya cara memilih 4 posisi dari 7 posisi yang ada untuk meletakkan huruf K, yaitu C (7, 4) = C (4+3, 4) = 35. Sama saja dengan banyak cara memilih 3 posisi dari 7 posisi untuk meletakkan huruf A, yaitu C (7, 3) = C (4+3, 3) = 35. Dengan demikian terdapat 35 lintasan yang mungkin dari Titik P ke titik Q pada kisi-kisi tersebut. Theorema : C* (n, k) = C (n+k-1, k) = C (n+k-1, n-1)

CONTOH : 1. S = {a,b,c} Penyelesaian : 1. {𝑎, 𝑎, 𝑎, 𝑏, 𝑐}|{0,0,0,1,0,1,0} 2. {𝑎, 𝑎, 𝑏, 𝑏, 𝑐}|{0,0,1,0,0,1,0} 3. {𝑎, 𝑏, 𝑏, 𝑏, 𝑐}|{0,1,0,0,0,1,0} . . . 𝑑𝑙𝑙 C*(3, 5) = C (7, 5) = C (7, 2) C* (n, k) = C (n+k-1, k) = C (n+k-1, n-1) 4.

B 3X2

A 13

Penyelesaian : C (n+m, n) / C (n+m, m) C (5, 2) =

5! 5.4 20 = = = 10 Cara 3! 2! 2 2

1. KKAAA

6. AAKKA

2. KAAAK

7. AAKAK

3. AAAKK

8. AKAKA

4. AKKAA

9. KAAKA

5. AKAAK

10. KAKAA

LINTASAN CANTIK ADALAH SUATU LINTASAN YANG MENYENTUH DAN DIBAWAH DIAGONAL UTAMA RUMUS: Lintasan Cantik pada kisi-kisi n x n: 𝐶 (𝑛 + 𝑛, 𝑛) – 𝐶 (2𝑛, 𝑛 − 1) 𝐶 (2𝑛, 𝑛) – 𝐶 (2𝑛, 𝑛 − 1) (2𝑛)! (2𝑛)! = 𝑛! 𝑛! (𝑛 − 1)! (𝑛 + 1)! (2𝑛)! (2𝑛)! = 𝑛! 𝑛! 𝑛! (𝑛 + 1)𝑛! 𝑛 (2𝑛)! (2𝑛)! 𝑛 = 𝑛! 𝑛! 𝑛! 𝑛! (𝑛 + 1) (2𝑛)! 𝑛 = (1 − ) 𝑛! 𝑛! 𝑛+1 Lintasan Cantik (n x n ) adalah Bilangan Catalan 𝐑𝐔𝐌𝐔𝐒 𝐋𝐈𝐍𝐓𝐀𝐒𝐀𝐍 𝐂𝐀𝐍𝐓𝐈𝐊 (𝐧𝐱𝐦) ⇒ 𝐂(𝐧 + 𝐦, 𝐧 ) 𝐀𝐓𝐀𝐔 𝐂(𝐧 + 𝐦, 𝐧)

14

Soal Latihan : 1. Berapa banyak lintasan cantik...