1.8 Angka Katalan: Eugene Charles Catalan (1814-1894) L [PDF]

Citation preview

1.8 Angka Katalan Nomor Catalan menarik dan ada di mana-mana. Mereka adalah tanggal candi yang sangat baik untuk eksplorasi, eksperimen, dan dugaan. Seperti Fibonacci dan Lucas angka (lihat Bagian 2.6), mereka memiliki, seperti yang ditulis Martin Gardner di Scientific Amer ican, “kecenderungan menyenangkan yang sama untuk muncul secara tak terduga, terutama di masalah kombinatorial” (1976). Tempat-tempat tak terduga itu termasuk aljabar abstrak, kombinatorika, ilmu komputer, teori graf, dan geometri. Bilangan Catalan merupakan bilangan bulat positif yang diperoleh dengan menghitung struktur kombinasi dari suatu barisan. Bilangan Catalan dapat dinyatakan dalam bentuk rekursif dan dapat diselesaikan dengan banyak cara, diantaranya dengan lattice path,



balanced paranthesis, persamaan karakteristik prinsip kombinatorial dan fungsi pembangkit momen. Bilangan Catalan dinamai menurut matematikawan Belgia Eugene C. Cata lan, yang menemukannya pada tahun 1838, ketika ia sedang mempelajari barisan yang terbentuk dengan baik dari tanda kurung. Sebelumnya, sekitar tahun 1751, matematikawan Swiss terkemuka Leon hard Euler (lihat Bagian 7.4) menemukannya saat mempelajari triangulasi cembung. poligon. Bahkan, mereka dibahas oleh ahli matematika Cina Antu Ming (1692?– 1763?) pada tahun 1730 melalui model geometrisnya. Karena karyanya tersedia hanya dalam bahasa Cina, penemuannya tidak dikenal di dunia barat.



Eugene Charles Catalan (1814–1894) lahir di Bruges, Belgia. Ia belajar di cole Polytechnique, Paris, dan menerima gelar Doctor of Science pada tahun 1841. Setelah mengundurkan diri dari posisinya di Departemen Jembatan dan Jalan Raya, ia menjadi profesor matematika di Collge de Chalons-sur Marne, dan kemudian di Collge Charlemagne. Catalan kemudian mengajar di Lycée Saint Louis dan pada tahun 1865 menjadi profesor analisis di Universitas Liège di Belgia. Selain menulis lements de Geometriè (1843) dan Notions d'astronomie (1860), ia menerbitkan banyak artikel tentang integral berganda, teori permukaan, analisis matematis, kalkulus probabilitas, dan geometri. Dia melakukan penelitian ekstensif pada harmonik bola, analisis persamaan diferensial, transformasi variabel dalam beberapa integral, pecahan lanjutan, seri, dan produk tak terbatas. Antu Ming (1692?–1763?), menurut Luo, adalah seorang anggota suku Zhengxianbai dari Mongolia Dalam dan seorang ilmuwan terkenal selama Dinasti Qing. Pendidikan matematika masa kecilnya, yang mengkhususkan diri dalam astronomi dan matematika, secara hati-hati diarahkan oleh Kaisar. Setelah menguasai pengetahuan ilmiah pada masa itu, Ming menjadi mandarin, pejabat tinggi pemerintah, di pusat astronomi nasional. Pada 1759, ia menjadi direktur pusat. Karyanya termasuk pemecahan masalah dalam astronomi, meteorologi, geografi, survei, dan matematika. Sekitar tahun 1730, ia mulai menulis Metode Efisien untuk Nilai Tepat Fungsi Melingkar, sebuah buku yang dengan jelas menunjukkan pemahamannya tentang bilangan Catalan. Buku itu diselesaikan oleh murid-murid Ming sebelum tahun 1774, tetapi tidak diterbitkan sampai tahun 1839.



Gambar 1.32 Triangulasi dari n-gon, dimana



3 ≤ n≤ 6.



Bilangan Catalan dapat diinterpretasikan sebagai banyak cara membagi poligon dengan 𝑛+2 sisi menjadi 𝑛 buah segitiga dengan sisi-sisi yang tidak berpotongan. Gambar di bawah menunjukkan ada 2 cara untuk segiempat, dan 5 cara untuk segilima.



Gambar 1.33 Banyak cara membagi segiempat dan segilima Interpretasi lain dari bilangan Catalan adalah banyak lintasan terpendek sepanjang 2𝑛 melalui grid berukuran 𝑛×𝑛 tanpa memotong diagonal utama. (Weisstein, 2020).



Gambar 1.34 Banyak lintasan terpendek sepanjang 2𝑛 tanpa memotong diagonal utama (untuk 𝑛=1,2,3,4)



Euler menggunakan argumen induktif, yang dia sebut "cukup melelahkan," untuk menetapkan rumusnya



An =



2 ∙ 6∙ 10 ⋯ ( 4 n−10 ) , n ≥3 ( n−1 ) !



Meskipun rumus Euler, yang diterbitkan pada tahun 1761, hanya masuk akal untuk



n ≥ 3, kita dapat



perluas untuk memasukkan kasus n = 0, 1, dan 2. Untuk tujuan ini, misalkan



k =n−3 . Kemudian Ak +3=



2∙ 6 ∙ 10 ⋯ ( 4 k +2 ) ,k ≥0 (k + 2)!



A3 =1, A 4=2 , A 5=5. Ini adalah bilangan Katalan C 1,C 2, dan C 3, masing-masing, digeser oleh



Maka



dua spasi ke kanan. Jadi kita definisikan



C n=



C n= Ak +2. Dengan demikian,



2∙ 6 ∙10 ⋯ ( 4 n−2 ) ,n≥1 ( n+1 ) !



Ini dapat ditulis ulang sebagai



C n=



4 n−2 2 ∙ 6 ∙10 ⋯ ( 4 n−6 ) ∙ n+1 n! ¿



Ketika



4 n−2 C n+1 n−1



n=1, ini menghasilkan C 1=C0 . Tetapi C 1=1. Jadi kita dapat mendefinisikan



C 0=1.Akibatnya, C ndapat didefinisikan secara rekursif.



Definisi Rekursif dari C n



C 0=1 C n=



4 n−2 C ,n≥1 n+1 n−1



C 4=



4 ∙ 4−2 C3 4+1



Misalnya,



¿



14 ∙ 5=14 5



(1.11)



Rumus Eksplisit untuk C n Rumus rekursif (1.11) dapat digunakan untuk menurunkan rumus eksplisit untuk



C n=



C n:



4 n−2 C n+1 n−1 ¿



( 4 n−2 ) ( 4 n−6 ) C n−2 ( n+ 1 ) n



¿



( 4 n−2 ) ( 4 n−6 ) ( 4 n−10 ) Cn−3 ( n+1 ) n ( n−1 )



⋮



Karena



¿



( 4 n−2 ) ( 4 n−6 ) ( 4 n−10 ) ∙ ∙∙ 6 ∙2 C0 ( n+1 ) n∙ ∙∙ 3 ∙ 2



¿



( 2n−1 ) (2 n−3 ) ( 2n−5 ) ∙∙ ∙ 3∙ 1 n ∙2 ( n+1 ) !



¿



( 2 n) ! 2n ( 2 n ) ! = n 2 ( n+1 ) ! n ! ( n+1 ) ! n !



¿



1 2n n+1 n



( )



( n+1 ) ∨ 2 n (lihat Latihan 20 di Bagian 1.5), maka setiap bilangan Katalan adalah bilangan bulat n



( )



positif. Berbagai nomor Katalan adalah 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,... Ini mengikuti dari rumus eksplisit bahwa setiap nomor Katalan



Bagilah setiap koefisien binomial pusat



(2nn )



oleh



C n dapat dibaca dari segitiga Pascal:



n+1 ; Lihat Gambar 1.33.



Gambar 1.33 Segitiga Paskal



Ada beberapa cara membaca



C n dari segitiga; lihat Latihan 1–9.



Rumus Rekursif Segner Pada tahun 1761, Johann Andreas von Segner (1704-1777), seorang matematikawan Hungaria, fisikawan, dan dokter, mengembangkan rumus rekursif untuk



C nmenggunakan masalah triangulasi:



C n=C 0 C n−1+ C1 Cn−2 +…+C n−2 C 1 +Cn−1 C0 Dimana



n ≥ 1.



Sebagai contoh,



C 5=C 0 C 4 +C 1 C 3+ C2 C2 +C 3 C 1+C 4 C 0 ¿ 1∙ 14+ 1∙ 5+2 ∙2+5 ∙ 1+14 ∙1=42 Secara sepintas, kami mencatat bahwa dengan menggunakan fungsi pembangkit, rumus Segner dapat digunakan untuk menurunkan rumus eksplisit untuk



C n ; lihat Latihan 10-13.