Lema 9.27.
Untuk setiap \(k\ge 1\text{,}\)
\begin{equation*}
\binom{1/2}{k}=\frac{(-1)^{k-1}}{k}\frac{\binom{2k-2}{k-1}}{2^{2k-1}}.
\end{equation*}
Subbab 9.7 Menyelesaikan rekurensi nonlinear
Dalam bagian ini, kita akan menggunakan fungsi pembangkit untuk mencacah suatu jenis pohon tertentu. Melalui pencacahan tersebut, kita akan melihat bagaimana fungsi pembangkit dapat digunakan untuk menyelesaikan persamaan rekurensi nonlinear. Kita juga akan menghubungkannya dengan suatu barisan pencacahan yang pernah kita jumpai dalam Bab 2. Untuk melakukan semua ini, kita perlu memperkenalkan beberapa istilah. Sebuah pohon disebut berakar jika kita menetapkan sebuah simpul khusus yang disebut akar pohon tersebut. Kita akan selalu menggambar pohon dengan akarnya di atas dan semua simpul lainnya di bawahnya. Pohon tak berlabel adalah pohon yang tidak kita bedakan berdasarkan nama yang diberikan kepada simpul-simpulnya. Untuk keperluan kita, pohon biner adalah pohon yang setiap simpulnya memiliki \(0\) atau \(2\) anak, sedangkan pohon terurut adalah pohon yang anak-anak setiap simpulnya memiliki suatu urutan (pertama, kedua, ketiga, etc.). Karena kita akan berfokus pada pohon berakar, tak berlabel, biner, dan terurut (disingkat RUBOT, mengikuti istilah Inggrisnya), dua anak dari setiap simpul yang memiliki anak akan kita sebut anak kiri dan anak kanan.
Dalam Gambar 9.26, kita menampilkan pohon berakar, tak berlabel, biner, dan terurut yang memiliki \(n\) daun untuk \(n\leq 4\text{.}\)
RUBOT dengan \(n\) daun untuk \(n\leq 4\)
Misalkan \(C(x) = \sum_{n=0}^\infty c_n x^n\) merupakan fungsi pembangkit bagi barisan \(\{c_n\colon n\geq 0\}\text{,}\) dengan \(c_n\) menyatakan banyaknya RUBOT yang memiliki \(n\) daun. (Demi kemudahan, kita mengambil \(c_0=0\text{.}\)) Dari Gambar 9.26, kita dapat melihat bahwa \(C(x) = x + x^2 + 2x^3 + 5x^4 + \cdots\text{.}\) Namun, berapakah koefisien-koefisien selanjutnya? Mari kita uraikan sebuah RUBOT dengan \(n\) daun menjadi gabungan dua RUBOT yang lebih kecil untuk melihat apakah \(c_n\) dapat dinyatakan menggunakan beberapa \(c_k\) dengan \(k\lt n\text{.}\) Ketika kita memperhatikan sebuah RUBOT dengan \(n\geq 2\) daun, simpul akarnya pasti memiliki dua anak. Kedua anak itu dapat dipandang sebagai simpul akar RUBOT yang lebih kecil. Misalkan anak kiri menjadi akar RUBOT dengan \(k\) daun; berarti anak kanan menjadi akar RUBOT dengan \(n-k\) daun. Karena ada \(c_k\) kemungkinan sub-RUBOT bagi anak kiri dan \(c_{n-k}\) sub-RUBOT bagi anak kanan, seluruhnya terdapat \(c_kc_{n-k}\) RUBOT yang sub-RUBOT pada anak kiri dari akarnya memiliki \(k\) daun. Kita dapat melakukan ini untuk setiap \(k=1,2,\dots,n-1\text{,}\) sehingga diperoleh
\begin{equation*}
c_n = \sum_{k=1}^{n-1} c_kc_{n-k}.
\end{equation*}
(Rumus ini berlaku karena \(n\geq 2\text{.}\)) Karena \(c_0=0\text{,}\) kita sebenarnya dapat menuliskannya sebagai
\begin{equation*}
c_n = \sum_{k=0}^{n} c_kc_{n-k}.
\end{equation*}
Mari kita perhatikan kuadrat fungsi pembangkit \(C(x)\text{.}\) Berdasarkan Proposisi 8.3, kita mempunyai
\begin{align*}
C^2(x) \amp = c_0^2 + (c_0c_1 + c_1c_0)x + (c_0c_2 +c_1c_1 + c_2c_0)x^2 +
\cdots\\
\amp = 0 + 0 + (c_0c_2 +c_1c_1 + c_2c_0)x^2 + (c_0c_3 +
c_1c_2+c_2c_1+c_3c_0)x^3 + \cdots.
\end{align*}
Namun, dari relasi rekurensi di atas, sekarang kita melihat bahwa koefisien \(x^n\) dalam \(C^2(x)\) tidak lain adalah \(c_n\) untuk \(n\geq 2\text{.}\) Satu-satunya yang belum ada ialah suku \(x\text{;}\) dengan menambahkannya, kita memperoleh
\begin{equation*}
C(x) = x + C^2(x).
\end{equation*}
Persamaan ini merupakan persamaan kuadrat dalam \(C(x)\text{,}\) sehingga kita dapat menyelesaikannya untuk \(C(x)\) dan memperoleh
\begin{equation*}
C(x) = \frac{1\pm \sqrt{1-4x}}{2} = \frac{1\pm (1-4x)^{1/2}}{2} .
\end{equation*}
Dengan demikian, kita dapat menggunakan Teorema Binomial Newton untuk menguraikan \(C(x)\text{.}\) Untuk melakukannya, kita menggunakan lemma berikut. Buktinya hampir sama dengan bukti Lema 8.12, sehingga tidak disertakan.
Sekarang kita melihat bahwa
\begin{align*}
C(x) \amp = \frac{1}{2} \pm \frac{1}{2} \sum_{n=0}^\infty\binom{1/2}{n}
(-4)^n x^n
= \frac{1}{2} \pm \frac{1}{2}\left(1+ \sum_{n=1}^\infty
\frac{(-1)^{n-1}}{n}\frac{\binom{2n-2}{n-1}}{2^{2n-1}}(-4)^n
x^n\right)\\
\amp =
\frac{1}{2} \pm\frac{1}{2} \mp\sum_{n=1}^\infty \frac{\binom{2n-2}{n-1}}{n} x^n.
\end{align*}
Karena kita memerlukan \(c_n\geq 0\text{,}\) kita memilih tanda “minus” dari pilihan “plus-atau-minus” dalam rumus kuadrat dan dengan demikian memperoleh teorema berikut.
Teorema 9.28.
Fungsi pembangkit bagi bilangan \(c_n\) yang menyatakan banyaknya pohon berakar, tak berlabel, biner, dan terurut dengan \(n\) daun adalah
\begin{equation*}
C(x) = \frac{1-\sqrt{1-4x}}{2} = \sum_{n=1}^\infty \frac{1}{n}\binom{2n-2}{n-1}x^n.
\end{equation*}
