Subbab 8.2 Meninjau kembali pembagian apel atau map

Salah satu persoalan yang berulang kali muncul sejauh ini dalam buku ini adalah pembagian objek-objek yang tak terbedakan (misalnya apel) kepada entitas-entitas yang berbeda (misalnya anak-anak). Kita memulainya dalam Bab 2 dengan menanyakan banyaknya cara membagikan \(40\) apel kepada \(5\) anak sedemikian sehingga setiap anak dijamin memperoleh sedikitnya satu apel, dan kita melihat bahwa jawabannya adalah \(C(39,4)\text{.}\) Kita bahkan telah melihat cara membatasi situasinya agar salah seorang anak hanya dapat menerima paling banyak \(10\) apel. Dalam Bab 7, kita belajar memperluas pembatasan tersebut sehingga banyak anak dapat memiliki batas masing-masing atas banyaknya apel yang boleh diterima dengan memanfaatkan Prinsip Inklusi–Eksklusi. Sebelum melanjutkan untuk melihat bagaimana fungsi pembangkit memungkinkan kita menerapkan pembatasan yang lebih beragam, mari kita luangkan waktu sejenak untuk melihat bagaimana fungsi pembangkit menyelesaikan persoalan paling dasar yang sedang kita hadapi.

Contoh 8.4.

Kita telah mengetahui bahwa banyaknya cara membagikan \(n\) apel kepada \(5\) anak sedemikian sehingga setiap anak memperoleh sedikitnya satu apel adalah \(C(n-1,4)\text{.}\) Namun, akan bermanfaat untuk melihat bagaimana hasil ini dapat diturunkan dengan fungsi pembangkit. Mari kita mulai dengan persoalan yang lebih sederhana: ada berapa cara untuk membagikan \(n\) apel kepada satu anak sedemikian sehingga anak tersebut menerima sedikitnya satu apel? Persoalan ini tidak sulit karena hanya ada satu cara untuk melakukannya—berikan semua apel kepada anak yang beruntung itu! Jadi, barisan yang menghitung banyaknya cara tersebut adalah \(\{a_n\colon n\geq 1\}\) dengan \(a_n=1\) untuk setiap \(n\geq 1\text{.}\) Fungsi pembangkit bagi barisan ini kemudian adalah

\begin{equation*} x+x^2+x^3+\cdots = x(1+x+x^2+x^3+\cdots) = \frac{x}{1-x}. \end{equation*}

Bagaimana fakta ini dapat membawa kita kepada persoalan dengan lima anak? Perhatikan apa yang terjadi ketika kita mengalikan

\begin{equation*} (x+x^2+\cdots)(x+x^2+\cdots)(x+x^2+\cdots)(x+x^2+\cdots) (x+x^2+\cdots). \end{equation*}

Untuk memahami makna hasil kali ini, mula-mula tinjau ada berapa cara untuk memperoleh \(x^6\text{.}\) Kita dapat mengambil \(x^2\) dari faktor pertama dan \(x\) dari masing-masing empat faktor lainnya, atau \(x^2\) dari faktor kedua dan \(x\) dari masing-masing empat faktor lainnya, etc.. Dengan demikian, koefisien \(x^6\) adalah \(5 = C(5,4)\text{.}\) Secara lebih umum, berapakah koefisien \(x^n\) dalam hasil kali tersebut? Dalam penjabarannya, kita memperoleh sebuah \(x^n\) untuk setiap hasil kali berbentuk \(x^{k_1}x^{k_2}x^{k_3}x^{k_4}x^{k_5}\) dengan \(k_1+k_2+k_3+k_4+k_5 = n\text{.}\) Kembali ke persoalan umum kita, sebenarnya kita sedang membagikan \(n\) apel kepada \(5\) anak. Karena \(k_i> 0\) untuk \(i=1,2,\dots,5\text{,}\) kita juga memperoleh jaminan bahwa setiap anak menerima sedikitnya satu apel. Jadi, hasil kali fungsi pembangkit untuk satu anak menghasilkan fungsi pembangkit untuk lima anak.

Anggaplah sejenak bahwa kita belum mengetahui bahwa koefisien-koefisiennya haruslah \(C(n-1,4)\text{.}\) Bagaimana kita dapat menentukan koefisien tersebut hanya dari fungsi pembangkitnya? Fungsi pembangkit yang kita perlukan adalah \(x^5/(1-x)^5\text{,}\) yang dapat Anda lihat dengan cukup cepat memenuhi

\begin{align*} \frac{x^5}{(1-x)^5} \amp = \frac{x^5}{4!}\frac{d^4}{dx^4}\left(\frac{1}{1-x}\right) = \frac{x^5}{4!}\sum_{n=0}^\infty n(n-1)(n-2)(n-3)x^{n-4}\\ \amp =\sum_{n=0}^\infty \frac{n(n-1)(n-2)(n-3)}{4!}x^{n+1} = \sum_{n=0}^\infty \binom{n}{4}x^{n+1}. \end{align*}

Koefisien \(x^n\) dalam deret ini adalah \(C(n-1,4)\text{,}\) tepat seperti yang kita harapkan.

Kita dapat meninjau kembali sebuah contoh dari Bab 7 untuk melihat bahwa jika kita ingin membatasi seorang anak agar menerima paling banyak \(4\) apel, kita akan menggunakan \((x+x^2+x^3+x^4)\) sebagai fungsi pembangkitnya, bukan \(x/(1-x)\text{.}\) Namun, daripada membahasnya panjang lebar di sini, mari kita coba sesuatu yang sedikit lebih tidak biasa.

Contoh 8.5.

Sebuah toko bahan pangan sedang menyiapkan keranjang buah untuk hari raya yang akan dijual. Setiap keranjang berisi \(20\) buah yang dipilih dari apel, pir, jeruk, dan grapefruit. Ada berapa cara berbeda untuk menyiapkan keranjang seperti itu jika setiap keranjang harus memuat sedikitnya satu apel, tidak boleh memuat lebih dari tiga pir, dan banyaknya jeruk harus merupakan kelipatan empat?

Penyelesaian.

Untuk menentukan banyaknya keranjang yang terdiri atas \(20\) buah, mari kita selesaikan persoalan yang lebih umum, yaitu setiap keranjang berisi \(n\) buah. Metode kita sederhana: tentukan fungsi pembangkit untuk setiap jenis buah secara terpisah, lalu kalikan semuanya. Seperti pada contoh sebelumnya, hasil kali tersebut akan memuat suku \(x^n\) untuk setiap cara menyusun sebuah keranjang berisi \(n\) buah yang memenuhi pembatasan kita. Fungsi pembangkit untuk apel adalah \(x/(1-x)\) karena kita hanya menginginkan pangkat positif dari \(x\) (yang memastikan adanya sedikitnya satu apel). Fungsi pembangkit untuk pir adalah \((1+x+x^2+x^3)\) karena sebuah keranjang hanya boleh memuat nol, satu, dua, atau tiga pir. Untuk jeruk, kita mempunyai \(1/(1-x^4) = 1+x^4+x^8+\cdots\text{,}\) sedangkan banyaknya grapefruit tidak dibatasi sehingga memberikan faktor \(1/(1-x)\text{.}\) Dengan mengalikannya, kita memperoleh

\begin{equation*} \frac{x}{1-x} (1+x+x^2+x^3) \frac{1}{1-x^4} \frac{1}{1-x} = \frac{x}{(1-x)^2(1-x^4)} (1+x+x^2+x^3). \end{equation*}

Sekarang kita gunakan fakta bahwa \((1+x+x^2+x^3) =(1-x^4)/(1-x)\) (berdasarkan (8.1.1)) untuk melihat bahwa fungsi pembangkit kita adalah

\begin{align*} \frac{x}{(1-x)^3} \amp= \frac{x}{2}\sum_{n=0}^\infty n(n-1)x^{n-2} = \sum_{n=0}^\infty\frac{n(n-1)}{2} x^{n-1} \\ \amp=\sum_{n=0}^\infty\binom{n}{2} x^{n-1} = \sum_{n=0}^\infty\binom{n+1}{2} x^n. \end{align*}

Jadi, terdapat \(C(n+1,2)\) kemungkinan keranjang buah yang berisi \(n\) buah. Dengan demikian, jawaban atas pertanyaan awal kita adalah \(C(21,2) = 210\text{.}\)

Bentuk ringkas penyelesaian Contoh 8.5 mengisyaratkan bahwa mungkin ada cara memperoleh jawaban ini tanpa menggunakan fungsi pembangkit. Memikirkan pendekatan seperti itu merupakan cara yang baik untuk memperkuat pemahaman Anda tentang berbagai topik pencacahan yang telah kita bahas.

Contoh 8.6.

Tentukan banyaknya solusi bilangan bulat untuk persamaan

\begin{equation*} x_1 + x_2 + x_3 = n \end{equation*}

dengan \(n\geq 0\) suatu bilangan bulat, \(x_1 \geq 0\) suatu bilangan genap, \(x_2\geq 0\text{,}\) dan \(0\leq x_3\leq 2\text{.}\)

Penyelesaian.

Sekali lagi, kita meninjau fungsi pembangkit yang diperoleh jika setiap variabel diperlakukan secara terpisah, lalu mengambil hasil kalinya. Untuk \(x_1\text{,}\) kita memperoleh faktor \(1/(1-x^2)\text{;}\) untuk \(x_2\text{,}\) kita mempunyai \(1/(1-x)\text{;}\) dan untuk \(x_3\text{,}\) faktornya adalah \((1+x+x^2)\text{.}\) Oleh karena itu, fungsi pembangkit untuk banyaknya solusi persamaan di atas adalah

\begin{equation*} \frac{1+x+x^2}{(1-x)(1-x^2)} = \frac{1+x+x^2}{(1+x)(1-x)^2}. \end{equation*}

Dalam kalkulus, ketika hendak mengintegralkan fungsi rasional berbentuk seperti ini, kita menggunakan metode pecahan parsial untuk menuliskannya sebagai jumlah fungsi-fungsi rasional yang “lebih sederhana” dan antiturunannya telah kita kenali. Teknik kita di sini sama karena kita dapat dengan mudah mengenali deret pangkat formal bagi banyak fungsi rasional. Tujuan kita adalah menulis

\begin{equation*} \frac{1+x+x^2}{(1+x)(1-x)^2} = \frac{A}{1+x} + \frac{B}{1-x} + \frac{C}{(1-x)^2} \end{equation*}

untuk konstanta-konstanta \(A\text{,}\) \(B\text{,}\) dan \(C\) yang sesuai. Untuk menentukan konstanta tersebut, kita mengalikan kedua ruas guna menghilangkan penyebut sehingga diperoleh

\begin{equation*} 1+x+x^2 = A(1-x)^2 + B(1-x^2) + C(1+x). \end{equation*}

Dengan menyamakan koefisien suku-suku yang berderajat sama, kita memperoleh

\begin{align*} 1 \amp = A+B+C\\ 1 \amp = -2A + C\\ 1 \amp = A - B \end{align*}

Dengan menyelesaikan sistem ini, kita mendapatkan \(A=1/4\text{,}\) \(B=-3/4\text{,}\) dan \(C=3/2\text{.}\) Oleh karena itu, fungsi pembangkit kita adalah

\begin{align*} \amp\frac{1}{4}\frac{1}{1+x} -\frac{3}{4} \frac{1}{1-x} +\frac{3}{2} \frac{1}{(1-x)^2}\\ =\amp \frac{1}{4}\sum_{n=0}^\infty (-1)^n x^n - \frac{3}{4} \sum_{n=0}^\infty x^n + \frac{3}{2}\sum_{n=0}^\infty n x^{n-1}\text{.} \end{align*}

Jadi, solusi bagi persoalan kita adalah koefisien \(x^n\) dalam fungsi pembangkit di atas, yaitu

\begin{equation*} \frac{(-1)^n}{4} - \frac{3}{4} + \frac{3(n+1)}{2}, \end{equation*}

yang merupakan jawaban mengejutkan dan tidak mudah diperoleh dengan metode lain!

Penggunaan pecahan parsial dalam Contoh 8.6 sangat ampuh. Namun, menyelesaikan sistem persamaan yang diperlukan lalu berharap deret pangkat formal yang dihasilkan mempunyai penjabaran yang langsung kita kenali dapat menjadi tantangan. Seandainya Contoh 8.6 tidak menanyakan kasus umum dengan \(n\) di ruas kanan persamaan, tetapi secara khusus menanyakan \(n=30\text{,}\) Anda mungkin bertanya-tanya apakah lebih cepat menulis kode Python untuk menghasilkan semua solusi atau lebih menarik untuk berkumpul dan merancang strategi pencacahan yang cerdik. Untungnya, teknologi dapat membantu kita ketika bekerja dengan fungsi pembangkit. Dalam SageMath, kita dapat menggunakan metode series() untuk memperoleh penjabaran deret pangkat dari suatu fungsi. Dua argumen bagi series adalah variabel dan derajat suku tempat pemotongan dilakukan. Dalam sel di bawah ini, kita meminta SageMath menjabarkan fungsi pembangkit dari Contoh 8.6 dengan memberikan semua suku yang berderajat paling tinggi 30, lalu merangkum sisa deret dalam notasi O-besar. Bagian ini kita buang dengan menyimpan keluaran series() dalam polinom f(x).

Jika yang benar-benar kita inginkan hanyalah koefisien suatu suku tertentu, kita dapat menggunakan metode list() untuk mengubah polinom menjadi daftar koefisien, lalu mengakses daftar tersebut menurut indeks dengan sintaks standar SageMath atau Python:

Mari kita pastikan bahwa jawaban ini sama dengan nilai yang diberikan rumus dalam penyelesaian Contoh 8.6 untuk \(n=30\text{:}\)

Hasil yang sama ini melegakan, dan selama kita hanya memerlukan satu koefisien, persoalannya telah tertangani. Namun, bagaimana jika kita benar-benar memerlukan rumus umum untuk koefisien \(x^n\text{?}\) Mari kita lihat bagaimana SageMath dapat membantu kita pada beberapa langkah lain dalam Contoh 8.6. Hal pertama yang kita perlukan adalah metode partial_fraction():

Jika tampilan tersebut kurang Anda sukai, fungsi pretty_print() dapat membuatnya lebih mudah dibaca:

Terlepas dari posisi sebuah tanda minus, hasil ini sama dengan yang kita peroleh secara manual, tetapi didapat jauh lebih cepat! Dari tahap ini, kita sering dapat menggunakan pengetahuan tentang deret pangkat dasar tertentu yang muncul ketika melakukan penjabaran pecahan parsial untuk memperoleh bentuk umum koefisien suatu suku sembarang dalam deret pangkat. Untuk mendukung hal tersebut, kita menutup bagian ini dengan contoh yang memperlihatkan cara menggunakan solusi persoalan pencacahan yang telah kita pelajari untuk menentukan koefisien fungsi pembangkit.

Contoh 8.7.

Misalkan \(n\) adalah bilangan bulat positif. Berapakah koefisien \(x^k\) dalam fungsi pembangkit

\begin{equation*} \frac{1}{(1-x)^n}\text{?} \end{equation*}

Penyelesaian.

Kita telah menjumpai kasus \(n=5\) ketika mengerjakan Contoh 8.4, tetapi saat itu kita menggunakan kalkulus. Mari kita meninjaunya hanya dari sudut pandang pencacahan. Fungsi pembangkit \(1/(1-x) = 1+x+x^2+\cdots\) menyandikan barisan banyaknya cara membagikan \(n\) apel kepada satu anak. Hanya ada satu cara melakukannya: berikan semua apel kepada anak yang beruntung itu. Mengalikan sejumlah salinan \(1/(1-x)\) kemudian berfungsi menambah banyaknya anak yang menerima pembagian apel. Karena setiap deret pangkat yang dikalikan dimulai dengan \(1\text{,}\) banyaknya apel yang diterima setiap anak haruslah tak negatif. Oleh karena itu, persoalan ini berasal dari Subbab 2.5. Kita mempunyai \(n\) anak, dan koefisien \(x^k\) adalah banyaknya cara membagikan \(k\) apel kepada mereka. Untuk itu diperlukan \(n\) apel fiktif, sehingga kita membagikan \(k+n\) apel yang menentukan \(k+n-1\) celah, dan kita harus memilih \(n-1\) di antaranya sebagai letak pemisah. Oleh karena itu, kita dapat menyimpulkan bahwa

\begin{equation*} \frac{1}{(1-x)^n} = \sum_{k=0}^\infty \binom{k+n-1}{n-1}x^k = \sum_{k=0}^\infty \binom{k+n-1}{k}x^k\text{.} \end{equation*}

Kesimpulan ini juga dapat diperoleh dengan teknik kalkulus, tetapi ada banyak faktorial dan \(-1\) yang perlu dipantau, sehingga pendekatan kombinatorial ini mungkin lebih kecil kemungkinannya menimbulkan kesalahan!

Sblm Ke Atas Lnjt