Seri berfikir kombinatorik 2011

Sutopo, Fisika UM 1

Banyaknya daerah dalam lingkaran yang dibentuk oleh mengubungkan garis-garis yang n titik pada lingkaran

Oleh: Sutopo Jurusan Fisika FMIPA UM sutopo@fisika.um.ac.id

Problem Apabila n buah titik ditempatkan pada keliling lingkaran kemudian masing-masing titik saling dihubungkan dengan suatu garis lurus, maka lingkaran itu akan terbagi menjadi sejumlah daerah. Apabila tidak ada tiga garis yang berpotongan di satu titik dalam lingkaran itu, berapa banyak daerah yang akan terbentuk?

Pembahasan Langkah 1. Selidiki dulu pengaruh kehadiran sebuah titik baru terhadap formasi yang telah ada (dihasilkan oleh sejumlah titik yang sebelumnya telah dipasang). Misalnya, titik Q ditambahkan pada formasi yang telah dihasilkan oleh 4 titik, seperti pada gambar.

Garis pertama, 푄1, menambah satu daerah baru, tidak memotong garis-garis yang telah ada.

Garis kedua, 푄2, menambah 3 daerah baru, memotong 2 garis yang telah ada, yaitu 13 dan 14.

Garis ketiga, 푄3, menambah 3 daerah baru, memotong 2 garis yang telah ada, yaitu 14 dan 24.

Garis ke-4, 푄4, menambah satu daerah baru, tidak memotong garis-garis yang telah ada. Jadi, banyaknya daerah baru yang diakibatkan oleh titik ke-5 adalah 8 daerah. Maka diperoleh

rumusan 퐷(5) = 퐷(4) + 8, dengan 퐷(푛) menyatakan banyaknya daerah yang dihasilkan oleh 푛 titik.

Ada tiga hal penting yang ditunjukkan oleh percobaan tersebut, yaitu sebagai berikut.

Titik ke 5 menghasilkan 4 potong garis, diperluas: titik ke-푛 menghasilkan (푛 − 1) potong garis. Banyaknya daerah baru akibat masing-masing garis tersebut sama dengan banyaknya perpotongan

(di dalam lingkaran) garis itu dengan garis-garis yang sudah ada ditambah satu. Banyaknya daerah yang dihasilkan oleh 푛 titik, adalah 퐷(푛) = 퐷(푛 − 1) + 푔(푛), dengan 푔(푛)

menyatakan banyaknya daerah baru yang dihasilkan oleh titik ke-푛.

Ditulis pada sekitar bulan April 2011. Diunggah pada 3 Desember 2011

Seri berfikir kombinatorik 2011

Sutopo, Fisika UM 2

Langkah 2: mencari formula banyaknya titik potong

Berpijak pada hasil langkah pertama: (1) banyaknya daerah baru yang dihasilkan titik terakhir sama dengan jumlahan dari banyaknya daerah yang dihasilkan masing-masing garis yang menghubungkan titik itu dengan titik sebelumnya, dan (2) banyaknya daerah baru yang dihasilkan oleh suatu garis ditentukan oleh banyaknya titik potong garis itu dengan garis-garis yang sudah ada, maka analis difokuskan pada menghitung banyaknya titik potong tehadap suatu garis.

Buat (푛 − 1) titik dan labeli secara berurutan dengan bilangan 1 s.d (푛 − 1). Untuk memudahkan analisis, titik-titik tersebut tidak saling dihubungkan terlebih dulu. (Garis-garis hubung akan dibuat secara bertahap pada saatnya nanti). Tambahkan titik Q, sebagai titik ke-푛, di antara titik ke-1 dan titik ke-(푛 − 1). Lihat gambar di samping.

Secara bertahap, titik Q dihubungkan dengan garis lurus ke titik-titik yang sudah ada, sambil didata banyaknya titik potong dan daerah baru yang dihasilkan. Gambar di samping menunjukkan cara menghitung banyaknya titik potong yang dihasilkan garis 푄1 dan 푄2. Terlihat bahwa:

Garis 푄1 tidak memotong garis manapun. Jika 푡(푄퐼)menyatakan banyaknya titik potong, maka 풕(푸ퟏ) = ퟎ.

Garis 푄2 memotong semua garis dari titik 1 ke titik-titik: 3, 4, 5, …, (푛 − 1). Maka banyaknya titik potong adalah (푛 − 1) − 2 = 푛 − 3. Jadi 풕(푸ퟐ) = 풏 − ퟑ.

Jika dilanjutkan ke garis-garis berikutnya, diperoleh data sebagai berikut:

Garis 푄3 memotong: o semua garis dari titik 1 ke titik-titik: 4, 5, 6, …, (푛 − 1); sebanyak (푛 − 4) garis

o dan semua garis dari titik 2 ke titik-titik: 4, 5, 6, …, (푛 − 1); juga sebanyak (푛 − 4) garis. Jadi 풕(푸ퟑ) = ퟐ(풏 − ퟒ).

Garis 푄4 memotong: o semua garis dari titik 1 ke titik-titik: 5, 6, 7,…, (푛 − 1); sebanyak (푛 − 5) garis, o semua garis dari titik 2 ke titik-titik: 5, 6, 7,…, (푛 − 1); sebanyak (푛 − 5) garis, o semua garis dari titik 3 ke titik-titik: 5, 6, 7,…, (푛 − 1); sebanyak (푛 − 5) garis.

Jadi 퐭(퐐ퟒ) = ퟑ(퐧 − ퟓ).

Secara umum diperoleh formula: 풕(푸 ) = (풋 − ퟏ)(풏− ퟏ − 풋); 풋 = ퟏ,ퟐ,ퟑ, … , (풏 − ퟏ).

Untuk 푗 = 푛 − 1, maka 푡 푄(푛 − 1) = 0 seperti yang diharapkan.

Seri berfikir kombinatorik 2011

Sutopo, Fisika UM 3

Langkah 3: mencari formula untuk 푔(푛), yaitu daerah baru yang disumbangkan oleh titik ke-n

Banyaknya daerah baru yang dihasilkan oleh garis 푄횥 adalah

푡(푄횥) + 1 = (푗 − 1)(푛 − 1 − 푗) + 1 = (2 − 푛) + 푛푗 − 푗 .

Maka banyaknya daerah baru yang diakibatkan oleh kehadiran titik Q (sebagai titik ke-푛) adalah:

푔(푛) = {(2 − 푛) + 푛푗 − 푗 } = (2− 푛) + 푛푗 − 푗

Dengan menggunakan formula:

푖 =푚(푚 + 1)

2 dan 푖 =

푚(푚 + 1)(2푚 + 1)6

Maka

푔(푛) = (푛 − 1)(2 − 푛) + 푛 ( ) + ( )( )[ ( ) ]

= (푛 − 1)(2 − 푛) + (푛−1)[3푛−2푛+2−1]6 = ( )( ) + (푛−1)[푛+1]

6

= ( )[ +푛−6푛+12]6 = ( )[( −5푛+6)+6]

6 = (푛 − 1) + (푛−1)(푛−2)(푛−3)

= ( )!( )!

+ ( )!!( )!

= 푛 − 11 + 푛 − 1

3

Langkah 4: mencari formula untuk 퐷(푛), rumus Rekursi

Langkah pertama telah menghasilkan formula 퐷(푛) = 퐷(푛 − 1) + 푔(푛), dan langkah ke-3 telah menghasilkan formula untuk 푔(푛). Berdasarkan kedua formula tersebut, secara iteratif dapat ditemukan 퐷(푛) untuk setiap 푛 jika 퐷(푛 − 1) telah diketahui. Karena 퐷(1) = 1, maka 퐷(푛) dapat ditentukan dengan rumus rekursi berikut: Beberapa contoh: G(2) = 1 + 1 + 0 = 2 G(5) = 8 + 4 + 4 = 16 G(3) = 2 + 2 + 0 = 4 G(6) = 16 + 5 + 10 = 31 G(4) = 4 + 3 + 1 = 8 G(7) = 31 + 6 + 20 = 58

퐷(1) = 1

퐷(푛) = 퐷(푛 − 1) + 푛 − 11 + 푛 − 1

3

Seri berfikir kombinatorik 2011

Sutopo, Fisika UM 4

Langkah 5: mencari formula langsung (tanpa rekursi) untuk 퐷(푛)

Berdasarkan rumus rekursi tersebut dapat diturunkan formula umum 퐷(푛) sebagai berikut.

퐷(푛) =

⎩⎪⎪⎨

⎪⎪⎧

⎩⎪⎪⎨

⎪⎪⎧

퐷(1) + 01 + 0

3( )

+ 11 + 1

3

( )

+ 21 + 2

3

⎭⎪⎪⎬

⎪⎪⎫

( )

+ ⋯

⎭⎪⎪⎬

⎪⎪⎫

( )

+ 푛 − 11 + 푛 − 1

3

Jika kurung-kurungnya dibuka, diperoleh deretan:

퐷(푛) = 퐷(1) + 01 + 0

3 + 11 + 1

3 + 21 + 2

3 + 21 + 2

3 + ⋯+ 푛 − 11 + 푛 − 1

3

Dengan mengamati suku-suku yang ada, rumusan tersebut dapat disederhanakan menjadi:

퐷(푛) = 퐷(1) + 푗1 + 푗

3 = 1 + 푛 − 1 + 11 + 1 + 푛 − 1 + 1

3 + 1 = 푛0 + 푛

2 + 푛4 .

Dalam menyelesaian penjumlahan tersebut telah digunakan formula: ∑ 푗푘 = 푛 + 1

푘 + 1 .

Jadi diperoleh formula akhir:

Banyaknya daerah yang dihasilkan oleh 푛 titik maksimum sebanyak:

퐷(푛) = 푛0 + 푛

2 + 푛4 .

Mengapa maksimum? Karena rumusan tersebut diperoleh dengan asumsi tidak ada 3 atau lebih garis yang berpotongan di satu titik di dalam lingkaran. Apa akibatnya jika ada 3 atau lebih garis yang seperti itu? Perhatikan gambar di samping. Pada gambar kiri, garis 푄3 memotong garis 14 dan 25 di titik yang berbeda dan secara keseluruhan memotong 4 garis yang sudah ada. Akibatnya, kehadiran garis tersebut menambah 5 daerah baru. Pada gambar kanan, di lain pihak, 푄3 memotong garis 14 dan 25 di titik yang sama sehingga secara keseluruhan hanya menghasilkan 3 titik potong, dan menyumbang 4 daerah baru. Jadi, jika ada 3 garis yang berpotongan di satu titik di dalam lingkaran, banyaknya daerah lebih sedikit daripada jika ketiga garis tersebut tidak berpotongan di satu titik.

Seri berfikir kombinatorik 2011

Sutopo, Fisika UM 5

Cara lain Persoalan tersebut juga bisa diselesaikan dengan membuat garis-garis secara berurutan dari titik 1 ke titik-titik : 2, 3, …, 푛; dilanjutkan dari titik 2 ke titik-titik: 3, 4, …, 푛; (garis 21 sudah terbentuk sebelumnya), dilanjutkan dari titik 3 ke titik-titik: 4, 5, …, 푛; (garis 31 dan 32 sudah terbentuk sebelumnya), dst. Maka, banyaknya garis yang dibuat dari masing-masing titik tersebut dapat dirangkum dalam table berikut.

Tabel 1. Banyaknya garis baru yang dibuat dari titik-titik 1, 2, dst

Titik asal 1 2 3 4 … 풏 − ퟑ 풏 − ퟐ 풏 − ퟏ 풏 # garis 푛 − 1 푛 − 2 푛 − 3 푛 − 4 … 3 2 1 0

Ketika garis-garis itu dibuat:

Garis-garis dari titik 1 tidak memotong garis manapun. Jadi banyaknya daerah yang dihasilkan ketika itu sebanyak:

1 + 1 + 1 + … + 1 (sebanyak 푛 kali) = 푛 daerah

Garis-garis dari titik 2, kecuali garis 23, memotong garis-garis 13, 14, 15, … , 1(푛 − 1). Lihat gambar. Banyaknya titik potong dan daerah baru yang dihasilkan masing-masing garis dapat didaftar sebagai berikut. o Garis 23 tidak memotong garis lain,→daerah baru yang dihasilkan: 1 daerah. o Garis 24 memotong garis 13,→daerah baru yang dihasilkan: 2 daerah. o Garis 25 memotong garis 13 dan 14 →daerah baru yang dihasilkan: 3 daerah. o dst o Garis 2푛 memotong garis-garis: 13, 14, … , 1(푛 − 1), →daerah baru yang dihasilkan: 푛 − 2

daerah.

Banyaknya daerah yang disumbangkan oleh titik 2 adalah: 1 + 2 + 3 + … + (푛 − 2)

Garis-garis dari titik 3, kecuali garis 34, memotong garis-garis 14, 15, … , 1(푛 − 1) serta garis-garis 24, 25, … , 2(푛 − 1). Banyaknya titik potong dan daerah baru yang dihasilkan masing-masing garis adalah sebagai berikut. o Garis 34 tidak memotong garis lain,→daerah baru yang dihasilkan: 1 daerah. o Garis 35 memotong garis 14 dan 24→daerah baru yang dihasilkan: 3 daerah. o Garis 36 memotong garis 14 , 15 dan 24 , 25→daerah baru yang dihasilkan: 5 daerah. o dst o Garis 3푛 memotong garis-garis: 14, 15, … , 1(푛 − 1) dan 24, 25, … , 2(푛 − 1); →daerah baru yang

dihasilkan: [2(푛 − 4)+1]daerah.

Banyaknya daerah yang disumbangkan oleh titik 3 adalah: 1 + 3 + 5 + … + [2(푛 − 4)+1]

5

1 2

3

4

n

n-1

Seri berfikir kombinatorik 2011

Sutopo, Fisika UM 6

Dengan cara yang sama dapat ditunjukkan bahwa:

Banyaknya daerah yang disumbangkan oleh titik 푗; 1 < 푗 ≤ (푛 − 1) adalah

1 + [1 + (푗 − 1)] + [1 + 2(푗 − 1)] + [1 + 3(푗 − 1)] + ⋯+ [1 + (푛 − 푗 − 1)(푗 − 1)], yaitu deret aritmatika dengan 푎 = 1, 푏 = (푗 − 1), sebanyak 푛 − 푗 suku.

Untuk 푗 = 1, banyaknya daerah = 1 + 1 + 1+ … + 1 (sebanyak 푛 suku)

Total banyaknya daerah yang dihasilkan oleh 푛 titik pada lingkaran sama dengan jumlahan dari seluruh daerah yang disumbangkan oleh titik ke 1 s.d ke 푛 − 1.

Contoh, untuk 푛 = 10, maka

Titik ke-푗= Deret 푆

Karakter 푆 a b # suku

1 1 1 1 1 1 1 1 1 1 1 = 10 1 0 10 2 1 2 3 4 5 6 7 8 = 36 1 1 8 3 1 3 5 7 9 11 13 = 49 1 2 7 4 1 4 7 10 13 16 = 51 1 3 6 5 1 5 9 13 17 = 45 1 4 5 6 1 6 11 16 = 34 1 5 4 7 1 7 13 = 21 1 6 3 8 1 8 = 9 1 7 2 9 1 = 1 1 1

10 0 = 0 Jum 9 36 49 51 45 34 21 9 1 1 = 256

Jika data tersebut ditata dalam bentuk segitiga (dengan memutar 450), diperoleh pola sebagai berikut.

1 1 1 1 2 1 1 = 퐶 + 퐶 2 3 1 1 2 = 퐶 + 퐶 4 4 1 2 1 4 = 퐶 + 퐶 8 5 1 3 3 1 8 = 퐶 + 퐶 16 6 1 4 5 4 1 15 = 퐶 + 퐶 31 7 1 5 7 7 5 1 26 = 퐶 + 퐶 57 8 1 6 9 10 9 6 1 42 = 퐶 + 퐶 99 9 1 7 11 13 13 11 7 1 64 = 퐶 + 퐶 163

10 1 8 13 16 17 16 13 8 1 93 = 퐶 + 퐶 256 11 1 9 15 19 21 21 19 15 9 1 130 = 퐶 + 퐶 386 ↑ 풏

↑ +0

↑ +1

↑ +2

↑ +3

↑ +4

↑ +5

↑ +6

↑ +7

↑ +8

↑ +9

↑ Jum per baris

↑ 퐷(푛)

퐷(푛) dihitung dengan menjumlahkan secara komulatif semua angka pada baris pertama sampai ke 푛.

Seri berfikir kombinatorik 2011

Sutopo, Fisika UM 7

Jika ditata lagi seperti pada segitiga Pascal, diperoleh pola sebagai berikut.

1 1 1

2 1 1

3 1 1 2

4 1 2 1 4

5 1 3 3 1 8

6 1 4 5 4 1 15

7 1 5 7 7 5 1 26

8 1 6 9 10 9 6 1 42

9 1 7 11 13 13 11 7 1 64

10 1 8 13 16 17 16 13 8 1 93

11 1 9 15 19 21 21 19 15 9 1 130

12 1 10 17 22 25 26 25 22 17 10 1 176 ↑ n 푪ퟏ풏 ퟏ + 푪ퟑ풏 ퟏ

퐶 + 퐶 = 푛 − 11 + 푛 − 1

3 adalah 푔(푛 − 1), yaitu 퐷(푛)−퐷(푛 − 1). Berdasarkan hal

itu, maka 퐷(푛) dapat dihitung dengan menjumlahkan secara komulatif nilai 푔(푛 − 1) dari 푛 = 1 s.d n. Tampak bahwa pola tersebut mirip dengan segitiga Pascal. Penyimpangan terhadap segitiga Pascal mulai nampak pada 푛 = 6, seperti yang ditunjukkan pada gambar. POLA BILANGAN APAKAH GERANGAN….? Selamat menikmati Catatan: Tulisan tersebut semata-mata ditulis berdasarkan pemikiran logis, tidak merujuk pada kaedah/teorema matematika tertentu, karena penulis memang tidak tahu teori-teori itu, jika memang ada.