Subbab 8.6 Fungsi pembangkit eksponensial
Seandainya kita ingin benar-benar cermat pada bagian awal bab ini, kita akan menyebut fungsi pembangkit yang telah dipelajari sebagai
fungsi pembangkit biasa atau bahkan
fungsi pembangkit deret pangkat biasa. Alasannya, terdapat jenis-jenis fungsi pembangkit lain yang didasarkan pada jenis deret pangkat yang berbeda. Dalam bagian ini, kita memperkenalkan secara singkat jenis fungsi pembangkit lain, yaitu
fungsi pembangkit eksponensial. Jika fungsi pembangkit biasa berbentuk
\(\sum_{n}
a_n x^n\text{,}\) fungsi pembangkit eksponensial didasarkan pada deret pangkat bagi fungsi eksponensial
\(e^x\text{.}\) Jadi, fungsi pembangkit eksponensial bagi barisan
\(\{a_n\colon
n\geq 0\}\) adalah
\(\sum_n a_n x^n/n!\text{.}\) Dalam bagian ini, kita akan melihat beberapa cara menggunakan fungsi pembangkit eksponensial untuk menyelesaikan persoalan yang tidak dapat ditangani dengan fungsi pembangkit biasa. Namun, kita baru akan menyinggung sebagian kecil potensi jenis fungsi pembangkit ini. Kita mulai dengan fungsi pembangkit eksponensial yang paling mendasar, sebagai analogi fungsi pembangkit biasa
\(1/(1-x)\) dalam
Contoh 8.1.
Contoh 8.17.
Perhatikan barisan konstan \(1, 1, 1, 1, \dots\text{.}\) Fungsi pembangkit eksponensial bagi barisan ini adalah
\begin{equation*}
E(x) = \sum_{n=0}^\infty \frac{x^n}{n!}.
\end{equation*}
Dari kalkulus, Anda mungkin ingat bahwa ini merupakan deret pangkat bagi fungsi eksponensial \(e^x\text{.}\) Itulah sebabnya jenis fungsi pembangkit ini disebut fungsi pembangkit eksponensial. Dari contoh ini, kita dapat segera mengenali bahwa fungsi pembangkit eksponensial untuk banyaknya untai biner dengan panjang \(n\) adalah \(e^{2x}\) karena
\begin{equation*}
e^{2x} = \sum_{n=0}^\infty \frac{(2x)^n}{n!} = \sum_{n=0}^\infty
2^n\frac{x^n}{n!}.
\end{equation*}
Dalam pembahasan fungsi pembangkit biasa sebelumnya pada bab ini, kita meninjau contoh-contoh yang mementingkan jumlah (banyaknya apel, etc.), tetapi tidak mementingkan urutan. Salah satu bidang yang membuat fungsi pembangkit eksponensial lebih sesuai daripada fungsi pembangkit biasa adalah penerapan yang mementingkan urutan, seperti pencacahan untai. Sebagai contoh, meskipun untai bit
\(10001\) dan
\(01100\) sama-sama memuat tiga nol dan dua satu, keduanya bukan untai yang sama. Sebaliknya, dua keranjang buah yang masing-masing memuat dua apel dan tiga jeruk akan dianggap setara, bagaimanapun buah-buah itu ditata. Sekarang kita tinjau beberapa contoh untuk menggambarkan teknik ini.
Contoh 8.18.
Misalkan kita ingin menentukan banyaknya untai terner dengan jumlah digit \(0\) yang genap. (Banyaknya digit \(1\) dan \(2\) tidak dibatasi.) Seperti pada fungsi pembangkit biasa, kita menentukan fungsi pembangkit bagi setiap digit, lalu mengalikan semuanya. Untuk digit \(1\) dan \(2\text{,}\) karena masing-masing boleh muncul berapa kali pun, kita memasukkan satu faktor \(e^x\) untuk setiap digit tersebut. Untuk banyaknya digit \(0\) yang genap, kita memerlukan
\begin{equation*}
1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \frac{x^6}{6!} + \cdots =
\sum_{n=0}^\infty \frac{x^{2n}}{(2n)!}.
\end{equation*}
Berbeda dengan fungsi pembangkit biasa, kita tidak dapat menyatakan deret ini dalam bentuk yang lebih ringkas hanya dengan menyubstitusikan suatu fungsi dari \(x\) ke dalam deret bagi \(e^y\text{.}\) Namun, dengan sedikit kecerdikan, kita dapat memperoleh hasil yang diinginkan. Untuk itu, mula-mula perhatikan bahwa
\begin{equation*}
e^{-x} = 1 - x + \frac{x^2}{2!} - \frac{x^3}{3!} + \cdots =
\sum_{n=0}^\infty \frac{(-1)^nx^n}{n!}.
\end{equation*}
Jadi, ketika kita menjumlahkan deret bagi \(e^{-x}\) dengan deret bagi \(e^x\text{,}\) semua suku dengan pangkat \(x\) yang ganjil akan saling meniadakan! Dengan demikian, kita memperoleh
\begin{equation*}
e^x+e^{-x} = 2+2\frac{x^2}{2!} + 2\frac{x^4}{4!} + \cdots,
\end{equation*}
yang nilainya tepat dua kali lipat dari yang kita perlukan. Oleh karena itu, faktor yang kita masukkan untuk digit \(0\) adalah \((e^x+e^{-x})/2\text{.}\)
Sekarang kita memperoleh fungsi pembangkit eksponensial
\begin{equation*}
\frac{e^x+e^{-x}}{2}e^x e^x = \frac{e^{3x} + e^x}{2} =
\frac{1}{2}\left(\sum_{n=0}^\infty \frac{3^nx^n}{n!} +
\sum_{n=0}^\infty \frac{x^n}{n!}\right).
\end{equation*}
Untuk menentukan banyaknya untai terner dengan jumlah digit \(0\) yang genap, kita perlu melihat koefisien \(x^n/n!\) dalam penjabaran deret tersebut. Dengan cara ini, kita mendapati bahwa banyaknya untai terner dengan jumlah digit \(0\) genap adalah \((3^n+1)/2\text{.}\)
Kita juga dapat menggunakan fungsi pembangkit eksponensial ketika terdapat batas pada banyaknya kemunculan suatu simbol, seperti dalam contoh berikut.
Contoh 8.19.
Ada berapa untai terner dengan panjang
\(n\) yang memuat sedikitnya satu digit
\(0\) dan sedikitnya satu digit
\(1\text{?}\)
Penyelesaian.
Untuk memastikan bahwa suatu simbol muncul sedikitnya sekali, kita memerlukan fungsi pembangkit eksponensial berikut
\begin{equation*}
x+\frac{x^2}{2!} + \frac{x^3}{3!} + \cdots = \sum_{n=1}^\infty
\frac{x^n}{n!}.
\end{equation*}
Perhatikan bahwa deret ini hampir sama dengan deret bagi \(e^x\text{,}\) kecuali suku pertamanya tidak ada. Jadi, \(\sum_{n=1}^\infty x^n/n! = e^x-1\text{.}\) Dengan menggunakan fakta ini, kita memperoleh
\begin{equation*}
(e^x-1)(e^x-1)e^x=e^{3x}-2e^{2x}+e^x
\end{equation*}
sebagai fungsi pembangkit eksponensial untuk persoalan ini. Dengan mencari penjabaran deretnya, kita memperoleh
\begin{equation*}
\sum_{n=0}^\infty \frac{3^nx^n}{n!} - 2\sum_{n=0}^\infty
\frac{2^nx^n}{n!} + \sum_{n=0}^\infty \frac{x^n}{n!}.
\end{equation*}
Sekarang kita dapat menjawab pertanyaan tersebut dengan langsung membaca koefisien \(x^n/n!\text{,}\) yaitu \(3^n
- 2\cdot 2^n + 1\text{.}\)
Sebelum beralih ke contoh tambahan, mari kita luangkan waktu sejenak untuk melihat cara lain menjawab pertanyaan pada contoh sebelumnya. Untuk menghitung banyaknya untai terner dengan panjang
\(n\) yang memuat sedikitnya satu digit
\(0\) dan sedikitnya satu digit
\(1\text{,}\) kita dapat menghitung semua untai terner dengan panjang
\(n\text{,}\) lalu menggunakan prinsip inklusi–eksklusi untuk menyingkirkan untai yang tidak diinginkan, yaitu yang tidak memiliki digit
\(0\) dan/atau digit
\(1\text{.}\) Jika suatu untai terner tidak memiliki digit
\(0\text{,}\) kita menghitung semua untai yang tersusun atas digit
\(1\) dan
\(2\text{,}\) sehingga terdapat
\(2^n\) untai. Hal yang sama berlaku jika digit
\(1\) tidak ada. Namun, jika kita mengurangkan
\(2\cdot 2^n\text{,}\) kita telah mengurangkan dua kali untai yang sekaligus tidak memiliki digit
\(0\) dan digit
\(1\text{.}\) Untai terner tanpa digit
\(0\) dan tanpa digit
\(1\) hanya terdiri atas digit
\(2\text{.}\) Tepat ada satu untai terner dengan panjang
\(n\) yang memenuhi kriteria ini. Jadi, melalui cara lain ini kita juga memperoleh
\(3^n-2\cdot 2^n+1\text{.}\)
Contoh 8.20.
Alice perlu menetapkan kode sandi delapan digit untuk telepon selulernya. Pembatasan pada kode sandi itu agak tidak biasa. Secara khusus, kode tersebut harus memuat digit \(0\) dalam jumlah genap, sedikitnya satu digit \(1\text{,}\) dan paling banyak tiga digit \(2\text{.}\) Bob berpendapat bahwa meskipun pembatasan ini tidak biasa, banyaknya kemungkinan kode sandi tidak jauh berkurang dari keseluruhan \(10^8\) untai delapan digit. Carlos tidak yakin akan hal itu, jadi ia menyusun fungsi pembangkit eksponensial sebagai berikut. Untuk tujuh digit yang tidak dikenai pembatasan, dimasukkan faktor \(e^{7x}\text{.}\) Untuk memperhitungkan jumlah digit \(0\) yang genap, ia menggunakan \((e^x+e^{-x})/2\text{.}\) Untuk sedikitnya satu digit \(1\text{,}\) diperlukan faktor \(e^x-1\text{.}\) Terakhir, \(1+x+x^2/2!+x^3/3!\) memperhitungkan pembatasan paling banyak tiga digit \(2\text{.}\) Jadi, fungsi pembangkit eksponensial untuk banyaknya kode sandi \(n\) digit adalah
\begin{equation*}
e^{7x}\frac{e^x+e^{-x}}{2}(e^x-1)\left(1+x+\frac{x^2}{2!} +
\frac{x^3}{3!}\right).
\end{equation*}
Dave melihat rumus rumit di papan tulis itu dan mengeluh. Menurutnya, mereka akan menghabiskan waktu seharian mengalikan dan membuat kesalahan aljabar saat berusaha mencari koefisien yang diinginkan. Alice menunjukkan bahwa mereka sebenarnya tidak perlu mencari koefisien
\(x^n/n!\) untuk semua
\(n\text{.}\) Sebagai gantinya, ia menyarankan penggunaan SageMath untuk mencari koefisien
\(x^8/8!\) saja.
Karena
\(8! = 40320\text{,}\) hasil ini menunjukkan bahwa terdapat
\(33847837\) kode sandi yang sah untuk telepon seluler tersebut. Perhitungan singkat menunjukkan bahwa Bob keliru besar ketika menyatakan bahwa banyaknya untai yang dapat digunakan sebagai kode sandi tidak berkurang secara berarti. Jumlah kode sandi yang sah hanya
\(33.85\%\) dari jumlah seluruh untai delapan digit!
Fungsi pembangkit eksponensial berguna dalam banyak situasi lain di luar pencacahan untai. Sebagai contoh, fungsi ini dapat digunakan untuk menghitung banyaknya graf terhubung berlabel dengan
\(n\) simpul. Namun, pembahasan tersebut berada di luar cakupan buku ini. Jika Anda berminat mempelajari fungsi pembangkit secara jauh lebih mendalam, buku
generatingfunctionology karya Herbert S. Wilf tersedia daring di
http://www.math.upenn.edu/~wilf/DownldGF.html.
