www.wikidata.id-id.nina.az

Fungsi pembangkit Halaman ini berisi artikel tentang fungsi pembangkit dalam matematika Untuk generator dalam pemrograma

Fungsi pembangkit

Halaman ini berisi artikel tentang fungsi pembangkit dalam matematika. Untuk generator dalam pemrograman, lihat Generator (pemrogramam). Untuk fungsi pembangkit momen dalam statistika, lihat Fungsi pembangkit momen.

Dalam matematika, fungsi pembangkit adalah sebuah cara menyatakan suku-suku dari barisan takhingga sebagai koefisien-koefisien suatu deret pangkat formal. Deret yang dihasilkan proses ini disebut dengan fungsi pembangkit dari barisan tersebut. Berbeda dengan deret pada umumnya, deret pangkat formal tidak perlu konvergen: malahan, fungsi pembangkit sebenarnya tidak dianggap sebagai sebuah fungsi, dan "variabel" pada fungsi adalah besaran yang tidak terdefinisi. Fungsi pembangkit pertama kali diperkenalkan oleh Abraham de Moivre di tahun 1730, dalam upaya menyelesaikan permasalahan rekursi perulangan linear secara umum. Deret pangkat formal dapat diperumum ke bentuk multi-"variabel", untuk mencatat informasi multidimensi dari barisan bilangan.

Terdapat berbagai tipe fungsi pembangkit, beberapa diantaranya fungsi pembangkit biasa, fungsi pembangkit eksponensial, deret Lambert, deret Bell, dan deret Dirichlet; definisi dan contoh mengenai tipe-tipe fungsi tersebut akan dijelaskan dibawah. Setiap barisan pada prinsipnya memiliki sebuah fungsi pembangkit untuk setiap tipe fungsi pembangkit (kecuali deret Lambert dan Dirichlet, yang memerlukan indeks barisan dimulai dari 1 ketimbang 0), namun tingkat kesulitan untuk menggunakan setiap tipe dapat berbeda secara signifikan. Tipe fungsi pembangkit yang paling sesuai untuk suatu konteks, jika ada, akan bergantung pada sifat dari barisan dan detail dari masalah yang dikerjakan.

Fungsi pembangkit umumnya dinyatakan dalam bentuk tertutup (ketimbang sebagai sebuah deret), lewat beberapa ekspresi yang terdefinisi bagi deret formal. Ekspresi-ekspresi ini diterapkan pada variabel—yang tak terdefinisi -- , dan dapat melibatkan operasi aritmetika, diferensiasi, komposisi fungsi dengan fungsi-fungsi pembangkit lainnya. Karena operasi-operasi ini juga terdefinisi pada fungsi, hasil yang didapatkan terlihat sebagai fungsi terhadap . Lagipula, ekspresi bentuk tertutup dapat diinterpretasi sebagai sebuah fungsi yang dapat dievaluasi pada suatu nilai , sehingga pengembangan deret fungsi tersebut menghasilkan deret formal; hal ini menjelaskan asal usul "fungsi pembangkit". Tapi interpretasi itu tidak diharuskan perlu dilakukan, karena deret formal tidak harus menghasilkan deret konvergen ketika nilai taknol disubtitusi ke . Selain itu, tidak semua ekspresi yang berlaku pada fungsi terhadap dapat digunakan (secara berarti) untuk deret formal; sebagai contoh, pangkat negatif dan pecahan dari pada fungsi tidak memiliki padanan deret formal.

Fungsi pembangkit bukan merupakan fungsi dalam artian formal, yakni sebagai sebuah pemetaan dari sebuah domain ke suatu kodomain. Fungsi pembangkit terkadang disebut sebagai deret pembangkit. Fungsi pembangkit berguna untuk membantu menyelesaikan berbagai masalah pencacahan, rekursi, dan relasi pengulangan.

Definisi Sunting

Beberapa penulis memberikan definisi informal dari fungsi pembangkit:

(terj.) Fungsi pembangkit adalah alat yang agak mirip dengan sebuah tas. Ketimbang membawa banyak benda kecil secara terpisah, yang dapat membuat malu, kita menempatkan semuanya dalam sebuah tas, sehingga kita cukup membawa satu benda: tas.

— George Pólya, Mathematics and plausible reasoning (1954)

(terj.) Fungsi pembangkit adalah sebuah tali jemuran tempat kita menggantungkan barisan bilangan-bilangan untuk ditampilkan.

— Herbert Wilf, Generatingfunctionology (1994)

Fungsi pembangkit biasa Sunting

Fungsi pembangkit biasa dari sebuah barisan adalah

Ketika istilah fungsi pembangkit digunakan tanpa keterangan, umumnya hal itu merujuk pada sebuah fungsi pembangkit biasa. Jika menyatakan fungsi massa peluang dari sebuah variabel acak diskret, maka fungsi pembangkit biasa yang dihasilkan disebut dengan fungsi pembangkit peluang.

Fungsi pembangkit biasa dapat diperumum untuk barisan dengan banyak indeks. Sebagai contoh, fungsi pembangkit biasa dari barisan dua dimensi , dengan dan berupa bilangan asli, adalah

Fungsi pembangkit eksponensial Sunting

Fungsi pembangkit eksponensial dari sebuah barisan adalah

Fungsi pembangkit eksponensial umumnya lebih mudah digunakan ketimbang fungsi pembangkit biasa untuk permasalahan pencacahan kombinatorial yang melibatkan objek berlabel. Keuntungan lain dari fungsi pembangkit eksponensial adalah kemudahannya membawa relasi pengulangan ke ranah persamaan diferensial. Sebagai contoh, barisan Fibonacci yang memenuhi relasi pengulangan memiliki fungsi pembangkit eksponensial dengan bentuk
dan turunan-turunan dari fungsi tersebut memenuhi persamaan diferensial yang analog dengan relasi pengulangan di atas. Pada fungsi pembangkit tipe ini, suku faktorial digunakan semata-mata untuk menormalisasi efek melakukan turunan pada .

Fungsi pembangkit Poisson Sunting

Fungsi pembangkit Poisson dari sebuah barisan adalah

Contoh Sunting

Contoh sederhananya, fungsi pembangkit untuk barisan adalah

untuk .

Catatan kaki Sunting

  1. Knuth, Donald E. (1997). "§1.2.9 Generating Functions". Fundamental Algorithms. The Art of Computer Programming. 1 (edisi ke-3rd). Addison-Wesley. ISBN 0-201-89683-4. 
  2. Istilah alternatif ini dapat ditemukan di E.N. Gilbert (1956), "Enumeration of Labeled graphs", Canadian Journal of Mathematics 3, p. 405–411. Istilah ini jarang digunakan sebelum tahun 2000, namun terlihat meningkat sejak tahun itu.
  3. Flajolet & Sedgewick 2009, hlm. 95

Referensi Sunting

  • Aigner, Martin (2007). A Course in Enumeration. Graduate Texts in Mathematics. 238. Springer. ISBN 978-3-540-39035-0. dari versi asli tanggal 2023-07-26. Diakses tanggal 2022-06-10. 
  • Doubilet, Peter; Rota, Gian-Carlo; Stanley, Richard (1972). "On the foundations of combinatorial theory. VI. The idea of generating function". Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability. 2: 267–318. Zbl 0267.05002. dari versi asli tanggal 2020-08-07. Diakses tanggal 2022-06-10.  Reprinted in Rota, Gian-Carlo (1975). "3. The idea of generating function". Finite Operator Calculus. With the collaboration of P. Doubilet, C. Greene, D. Kahaner, A. Odlyzko and R. Stanley. Academic Press. hlm. 83–134. ISBN 0-12-596650-4. Zbl 0328.05007. 
  • Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics. Cambridge University Press. ISBN 978-0-521-89806-5. Zbl 1165.05001. 
  • Goulden, Ian P.; Jackson, David M. (2004). Combinatorial Enumeration. Dover Publications. ISBN 978-0486435978. 
  • Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). "Chapter 7: Generating Functions". Concrete Mathematics. A foundation for computer science (edisi ke-2nd). Addison-Wesley. hlm. 320–380. ISBN 0-201-55802-5. Zbl 0836.00001. 
  • Lando, Sergei K. (2003). Lectures on Generating Functions. American Mathematical Society. ISBN 978-0-8218-3481-7. dari versi asli tanggal 2023-07-26. Diakses tanggal 2022-06-10. 
  • Wilf, Herbert S. (1994). Generatingfunctionology (edisi ke-2nd). Academic Press. ISBN 0-12-751956-4. Zbl 0831.05001. dari versi asli tanggal 2013-02-11. Diakses tanggal 2022-06-10. 

Pranala luar Sunting

wikipedia, wiki, buku, buku, perpustakaan, artikel, baca, unduh, gratis, unduh gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, gambar, musik, lagu, film, buku, permainan, permainan.
Tanggal penerbitan:
Halaman ini berisi artikel tentang fungsi pembangkit dalam matematika Untuk generator dalam pemrograman lihat Generator pemrogramam Untuk fungsi pembangkit momen dalam statistika lihat Fungsi pembangkit momen Dalam matematika fungsi pembangkit adalah sebuah cara menyatakan suku suku dari barisan takhingga a n displaystyle a n sebagai koefisien koefisien suatu deret pangkat formal Deret yang dihasilkan proses ini disebut dengan fungsi pembangkit dari barisan tersebut Berbeda dengan deret pada umumnya deret pangkat formal tidak perlu konvergen malahan fungsi pembangkit sebenarnya tidak dianggap sebagai sebuah fungsi dan variabel pada fungsi adalah besaran yang tidak terdefinisi Fungsi pembangkit pertama kali diperkenalkan oleh Abraham de Moivre di tahun 1730 dalam upaya menyelesaikan permasalahan rekursi perulangan linear secara umum 1 Deret pangkat formal dapat diperumum ke bentuk multi variabel untuk mencatat informasi multidimensi dari barisan bilangan Terdapat berbagai tipe fungsi pembangkit beberapa diantaranya fungsi pembangkit biasa fungsi pembangkit eksponensial deret Lambert deret Bell dan deret Dirichlet definisi dan contoh mengenai tipe tipe fungsi tersebut akan dijelaskan dibawah Setiap barisan pada prinsipnya memiliki sebuah fungsi pembangkit untuk setiap tipe fungsi pembangkit kecuali deret Lambert dan Dirichlet yang memerlukan indeks barisan dimulai dari 1 ketimbang 0 namun tingkat kesulitan untuk menggunakan setiap tipe dapat berbeda secara signifikan Tipe fungsi pembangkit yang paling sesuai untuk suatu konteks jika ada akan bergantung pada sifat dari barisan dan detail dari masalah yang dikerjakan Fungsi pembangkit umumnya dinyatakan dalam bentuk tertutup ketimbang sebagai sebuah deret lewat beberapa ekspresi yang terdefinisi bagi deret formal Ekspresi ekspresi ini diterapkan pada variabel yang tak terdefinisi x displaystyle x dan dapat melibatkan operasi aritmetika diferensiasi komposisi fungsi dengan fungsi fungsi pembangkit lainnya Karena operasi operasi ini juga terdefinisi pada fungsi hasil yang didapatkan terlihat sebagai fungsi terhadap x displaystyle x Lagipula ekspresi bentuk tertutup dapat diinterpretasi sebagai sebuah fungsi yang dapat dievaluasi pada suatu nilai sehingga pengembangan deret fungsi tersebut menghasilkan deret formal hal ini menjelaskan asal usul fungsi pembangkit Tapi interpretasi itu tidak diharuskan perlu dilakukan karena deret formal tidak harus menghasilkan deret konvergen ketika nilai taknol disubtitusi ke x displaystyle x Selain itu tidak semua ekspresi yang berlaku pada fungsi terhadap x displaystyle x dapat digunakan secara berarti untuk deret formal sebagai contoh pangkat negatif dan pecahan dari x displaystyle x pada fungsi tidak memiliki padanan deret formal Fungsi pembangkit bukan merupakan fungsi dalam artian formal yakni sebagai sebuah pemetaan dari sebuah domain ke suatu kodomain Fungsi pembangkit terkadang disebut sebagai deret pembangkit 2 Fungsi pembangkit berguna untuk membantu menyelesaikan berbagai masalah pencacahan rekursi dan relasi pengulangan Daftar isi 1 Definisi 1 1 Fungsi pembangkit biasa 1 2 Fungsi pembangkit eksponensial 1 3 Fungsi pembangkit Poisson 2 Contoh 3 Catatan kaki 4 Referensi 5 Pranala luarDefinisi SuntingBeberapa penulis memberikan definisi informal dari fungsi pembangkit terj Fungsi pembangkit adalah alat yang agak mirip dengan sebuah tas Ketimbang membawa banyak benda kecil secara terpisah yang dapat membuat malu kita menempatkan semuanya dalam sebuah tas sehingga kita cukup membawa satu benda tas George Polya Mathematics and plausible reasoning 1954 terj Fungsi pembangkit adalah sebuah tali jemuran tempat kita menggantungkan barisan bilangan bilangan untuk ditampilkan Herbert Wilf Generatingfunctionology 1994 Fungsi pembangkit biasa Sunting Fungsi pembangkit biasa dari sebuah barisan a n displaystyle a n nbsp adalahG a n x a 0 a 1 x a 2 x 2 a k x k n 0 a n x n displaystyle G a n x a 0 a 1 x a 2 x 2 a k x k sum n 0 infty a n x n nbsp Ketika istilah fungsi pembangkit digunakan tanpa keterangan umumnya hal itu merujuk pada sebuah fungsi pembangkit biasa Jika a n displaystyle a n nbsp menyatakan fungsi massa peluang dari sebuah variabel acak diskret maka fungsi pembangkit biasa yang dihasilkan disebut dengan fungsi pembangkit peluang Fungsi pembangkit biasa dapat diperumum untuk barisan dengan banyak indeks Sebagai contoh fungsi pembangkit biasa dari barisan dua dimensi a m n displaystyle a m n nbsp dengan m displaystyle m nbsp dan n displaystyle n nbsp berupa bilangan asli adalahG a m n x y m n 0 a m n x m y n displaystyle G a m n x y sum m n 0 infty a m n x m y n nbsp Fungsi pembangkit eksponensial Sunting Fungsi pembangkit eksponensial dari sebuah barisan a n displaystyle a n nbsp adalahEG a n x n 0 a n x n n displaystyle operatorname EG a n x sum n 0 infty a n frac x n n nbsp Fungsi pembangkit eksponensial umumnya lebih mudah digunakan ketimbang fungsi pembangkit biasa untuk permasalahan pencacahan kombinatorial yang melibatkan objek berlabel 3 Keuntungan lain dari fungsi pembangkit eksponensial adalah kemudahannya membawa relasi pengulangan ke ranah persamaan diferensial Sebagai contoh barisan Fibonacci f n displaystyle f n nbsp yang memenuhi relasi pengulangan f n 2 f n 1 f n displaystyle f n 2 f n 1 f n nbsp memiliki fungsi pembangkit eksponensial dengan bentukEF x n 0 f n n x n displaystyle operatorname EF x sum n 0 infty frac f n n x n nbsp dan turunan turunan dari fungsi tersebut memenuhi persamaan diferensial EF x EF x EF x displaystyle operatorname EF x operatorname EF x operatorname EF x nbsp yang analog dengan relasi pengulangan di atas Pada fungsi pembangkit tipe ini suku faktorial n displaystyle n nbsp digunakan semata mata untuk menormalisasi efek melakukan turunan pada x n displaystyle x n nbsp Fungsi pembangkit Poisson Sunting Fungsi pembangkit Poisson dari sebuah barisan a n displaystyle a n nbsp adalahPG a n x n 0 a n e x x n n e x EG a n x displaystyle operatorname PG a n x sum n 0 infty a n e x frac x n n e x operatorname EG a n x nbsp Contoh SuntingContoh sederhananya fungsi pembangkit untuk barisan 1 1 1 displaystyle 1 1 1 ldots nbsp adalah n 0 x n 1 1 x displaystyle sum n 0 infty x n frac 1 1 x nbsp untuk x 1 displaystyle x leq 1 nbsp Catatan kaki Sunting Knuth Donald E 1997 1 2 9 Generating Functions Fundamental Algorithms The Art of Computer Programming 1 edisi ke 3rd Addison Wesley ISBN 0 201 89683 4 Istilah alternatif ini dapat ditemukan di E N Gilbert 1956 Enumeration of Labeled graphs Canadian Journal of Mathematics 3 p 405 411 Istilah ini jarang digunakan sebelum tahun 2000 namun terlihat meningkat sejak tahun itu Flajolet amp Sedgewick 2009 hlm 95Referensi SuntingAigner Martin 2007 A Course in Enumeration Graduate Texts in Mathematics 238 Springer ISBN 978 3 540 39035 0 Diarsipkan dari versi asli tanggal 2023 07 26 Diakses tanggal 2022 06 10 Doubilet Peter Rota Gian Carlo Stanley Richard 1972 On the foundations of combinatorial theory VI The idea of generating function Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability 2 267 318 Zbl 0267 05002 Diarsipkan dari versi asli tanggal 2020 08 07 Diakses tanggal 2022 06 10 Reprinted in Rota Gian Carlo 1975 3 The idea of generating function Finite Operator Calculus With the collaboration of P Doubilet C Greene D Kahaner A Odlyzko and R Stanley Academic Press hlm 83 134 ISBN 0 12 596650 4 Zbl 0328 05007 Flajolet Philippe Sedgewick Robert 2009 Analytic Combinatorics Cambridge University Press ISBN 978 0 521 89806 5 Zbl 1165 05001 Goulden Ian P Jackson David M 2004 Combinatorial Enumeration Dover Publications ISBN 978 0486435978 Graham Ronald L Knuth Donald E Patashnik Oren 1994 Chapter 7 Generating Functions Concrete Mathematics A foundation for computer science edisi ke 2nd Addison Wesley hlm 320 380 ISBN 0 201 55802 5 Zbl 0836 00001 Lando Sergei K 2003 Lectures on Generating Functions American Mathematical Society ISBN 978 0 8218 3481 7 Diarsipkan dari versi asli tanggal 2023 07 26 Diakses tanggal 2022 06 10 Wilf Herbert S 1994 Generatingfunctionology edisi ke 2nd Academic Press ISBN 0 12 751956 4 Zbl 0831 05001 Diarsipkan dari versi asli tanggal 2013 02 11 Diakses tanggal 2022 06 10 Pranala luar Sunting Introduction To Ordinary Generating Functions Diarsipkan 2023 06 08 di Wayback Machine by Mike Zabrocki York University Mathematics and Statistics Hazewinkel Michiel ed 2001 1994 Generating function Encyclopedia of Mathematics Springer Science Business Media B V Kluwer Academic Publishers ISBN 978 1 55608 010 4 Generating Functions Power Indices and Coin Change Diarsipkan 2013 04 29 di Wayback Machine at cut the knot Generating Functions Diarsipkan 2013 06 01 di Wayback Machine by Ed Pegg Jr Wolfram Demonstrations Project 2007 Diperoleh dari https id wikipedia org w index php title Fungsi pembangkit amp oldid 24102232