Soal dan Pembahasan – Fungsi Pembangkit Untuk Kombinasi

        Berikut ini merupakan soal dan pembahasan terkait kasus kombinasi yang terselesaikan dengan menggunakan prinsip fungsi pembangkit.

Baca Juga: Soal dan Pembahasan- Fungsi Pembangkit: Dasar Bagian 1

Baca Juga: Soal dan Pembahasan- Fungsi Pembangkit: Dasar Bagian 2

Baca Juga: Soal dan Pembahasan- Fungsi Pembangkit untuk Permutasi

Soal Nomor 1
Dengan berapa cara $60$ objek yang identik dapat ditempatkan dalam $4$ sel (kotak) yang berbeda sedemikian sehingga setiap sel (kotak) mendapat paling sedikit $1$ objek?

Pembahasan

Ini merupakan kasus kombinasi, karena objek yang ditinjau adalah identik.
Misalkan $G(x)$ adalah FPB dari kasus tersebut. Sesuai syarat yang diperkenankan, yaitu MINIMAL $1$ objek ditempatkan pada masing-masing kotak (semua kotaknya ada $4$), diperoleh:
$\begin{aligned} G(x) & = (x + x^2 + x^3 + \cdots)^4 \\ &= x^4(1+x+x^2+\cdots)^4 \\ & =x^4\left(\dfrac{1}{1-x}\right)^4 \\ & =x^4 \displaystyle \sum_{k=0}^{\infty} \binom{4+k-1}{k}x^k \\ & =x^4 \displaystyle \sum_{k=0}^{\infty} \binom{3+k}{k}x^k \end{aligned}$
Banyak cara menempatkan $60$ objek yang identik dalam $4$ sel (kotak) yang berbeda sama dengan koefisien $x^{60}$ dalam $G(x)$. Dari bentuk di atas, kita hanya perlu mencari koefisien $x^{56}$ pada bentuk sumasi. Ini artinya, $k$ yang diambil adalah $56$ dan kita tahu bahwa koefisien $x^{56}$ adalah
$$\boxed{\displaystyle \binom{3+56}{56} =\displaystyle \binom{59}{56} = \dfrac{59!}{56! \times 3!} = 32.509}$$Jadi, banyak cara $60$ objek yang identik dapat ditempatkan dalam $4$ sel (kotak) yang berbeda sedemikian sehingga setiap sel (kotak) mendapat paling sedikit $1$ objek adalah $32.509$ cara.

[collapse]

Soal Nomor 2
Ada berapa cara $60$ objek yang identik dapat ditempatkan dalam $4$ sel (kotak) yang berbeda, sedemikian sehingga setiap sel (kotak) mendapat paling sedikit $10$ objek dan paling banyak $20$ objek?

Pembahasan

Ini merupakan kasus kombinasi, karena objek yang ditinjau adalah identik.
Misalkan $P(x)$ adalah FPB dari kasus tersebut, sehingga berdasarkan syarat yang diperkenankan, diperoleh
$$\begin{aligned} P(x) & = (x^{10} + x^{11} + \cdots + x^{20})^4 \\ &= (x^{10}(1+x+x^2+\cdots+x^{10}))^4 \\ & =x^{40}(1+x+x^2+\cdots+x^{10})^4 \\ & =x^{40}(1-x^{11})^4(1+x+x^2+\cdots)^4 \\ & =(x^{40}-4x^{51}+6x^{62}-4x^{73}+x^{84})\left(\dfrac{1}{1-x}\right)^4 \\ & =(x^{40}-4x^{51}+6x^{62}-4x^{73}+x^{84})\displaystyle \sum_{k=0}^{\infty} \binom{4+k-1}{k}x^k \end{aligned}$$Banyak cara penempatannya sama dengan koefisien $x^{60}$.
Hanya dua suku berpangkat $x^{40}$ dan $x^{51}$ dalam ekspresi pertama yang akan ditinjau, karena pangkatnya tidak melebihi $60$. Berturut-turut $k$ yang diambil adalah $k = 20$ dan $k = 9$, sehingga banyak cara menempatkan objek-objek yang identik tersebut ke dalam $4$ sel (kotak) yang berbeda adalah
$$\displaystyle \binom{4+20-1}{20}-4\binom{4+9-1}{9}= \boxed{\displaystyle \left[\binom{23}{20}-4\binom{12}{9}\right]~\text{cara}}$$Catatan: Jika hasil yang diperoleh terlihat rumit untuk dihitung, maka kita cukupkan penyelesaiannya sampai pada bentuk binomial saja.

[collapse]

Soal Nomor 3
Ada berapa cara menyeleksi $20$ huruf dari kata JUNGKAT dengan syarat paling sedikit satu G dan paling banyak tiga A?

Pembahasan

Ini merupakan kasus kombinasi, karena huruf yang identik dan diposisikan berlainan tetap akan dianggap sama.
Misalkan $P(x)$ adalah FPB kasus tersebut, sehingga
$P(x) = (x + x^2 + x^3 + \cdots)$ $(1+x+x^2+x^3)(1+x+x^2+\cdots)^5$
Ekspresi kurung pertama mewakili syarat minimal satu G. Ekspresi kurung kedua mewakili syarat maksimal tiga A. Ekspresi kurung terakhir mewakili $5$ huruf lainnya yang bebas syarat.
Jika dilanjutkan proses pengerjaannya, didapat
$$\begin{aligned} P(x) & = x(1+x+x^2+\cdots)(1+x+x^2+x^3)(1+x+x^2+…)^5 \\ & =x(1+x+x^2+x^3)(1+x+x^2+\cdots)^6 \\ & =(x+x^2+x^3+x^4)\left(\dfrac{1}{1-x}\right)^6 \\ & =(x+x^2+x^3+x^4) \displaystyle \sum_{k=0}^{\infty} \binom{6+k-1}{k}x^k \end{aligned}$$Banyak cara penyusunan huruf-huruf tersebut sama dengan koefisien $x^{20}$ dalam $P(x)$. Berturut-turut (dengan meninjau bentuk pangkat di luar notasi sigma) ambil $k = 19, 18, 17, 16$, diperoleh bahwa banyak cara menyeleksi (memilih) $20$ huruf dari kata JUNGKAT dengan syarat yang telah disebutkan sebelumnya adalah
$$\begin{aligned} & \displaystyle \binom{6+19-1}{19}+\binom{6+18-1}{18}+\binom{6+17-1}{17}+\binom{6+16-1}{16} \\ & = \displaystyle \left[ \binom{24}{19}+\binom{23}{18}+\binom{22}{17}+\binom{21}{16}\right]~\text{cara} \end{aligned}$$

[collapse]

Soal Nomor 4
Ada berapa cara untuk memilih $10$ huruf dari kata PINTAR dengan syarat paling sedikit satu T dan paling banyak $3$ N?

Pembahasan

Ini merupakan kasus kombinasi, karena huruf yang identik dan diposisikan berlainan tetap akan dianggap sama.
Misalkan $P(x)$ adalah FPB kasus tersebut, sehingga
$P(x) = (x + x^2 + x^3 + \cdots)$ $(1+x+x^2+x^3)(1+x+x^2+\cdots)^4$
Ekspresi kurung pertama mewakili syarat minimal satu T. Ekspresi kurung kedua mewakili syarat maksimal tiga N. Ekspresi kurung terakhir mewakili $4$ huruf lainnya yang bebas syarat.
Jika dilanjutkan proses pengerjaannya, didapat
$$\begin{aligned} P(x)  &= x(1+x+x^2+\cdots)(1+x+x^2+x^3)(1+x+x^2+\cdots)^4 \\ & =x(1+x+x^2+x^3)(1+x+x^2+\cdots)^5 \\ & =(x+x^2+x^3+x^4)\left(\dfrac{1}{1-x}\right)^5 \\ & =(x+x^2+x^3+x^4) \displaystyle \sum_{k=0}^{\infty} \binom{5+k-1}{k}x^k \end{aligned}$$Banyak cara penyusunan huruf-huruf tersebut sama dengan koefisien $x^{10}$ dalam $P(x)$. Berturut-turut (dengan meninjau bentuk pangkat di luar notasi sigma) ambil $k = 9, 8, 7, 6$, diperoleh bahwa banyak cara memilih $10$ huruf dari kata PINTAR dengan syarat yang telah disebutkan sebelumnya adalah
$$\begin{aligned} & \displaystyle \binom{5+9-1}{9}+\binom{5+8-1}{8}+\binom{5+7-1}{7}+\binom{5+6-1}{6} \\ & = \displaystyle \left[ \binom{13}{9}+\binom{12}{8}+\binom{11}{7}+\binom{10}{6}\right]~\text{cara} \end{aligned}$$

[collapse]

Soal Nomor 5
Tentukan banyaknya solusi integer (bulat) dari persamaan
$x_1 + x_2 + x_3 + x_4 + x_5 = 50, x_i \geq 0$, $i \in \{1, 2, 3, 4, 5\}$

Pembahasan

Beberapa solusi bulat yang memenuhi persamaan itu adalah $(0, 0, 0, 0, 50)$, $(0, 0, 5, 10, 35)$, atau $(1, 2, 3, 14, 30)$, dan ini merupakan kasus yang cenderung mengarah pada kombinasi.
Karena dalam persamaan tersebut memuat $5$ variabel, maka fungsi pembangkit dari permasalahan itu memuat $5$ faktor. Selanjutnya, karena setiap variabel $x_i \geq 0$, maka setiap faktor dalam fungsi pembangkit tersebut adalah $(1 + x + x^2 + x^3 + \cdots)$. Misalkan $P(x)$ adalah FPB dari permasalahan ini, maka
$\begin{aligned} P(x) & = (1 + x + x^2 + x^3 + \cdots)^5 \\ & = \left(\dfrac{1}{1-x}\right)^5 \\ &= \displaystyle \sum_{k=0}^{\infty} \binom{5+k-1}{k}x^k \end{aligned}$
Banyak solusi bulat yang dimaksud sama dengan koefisien $x^{50}$ ($k$ yang diambil adalah $50$) dalam $P(x)$, yaitu
$$\boxed{\displaystyle \binom{5 + 50- 1}{50} = \binom{54}{50} = \dfrac{54!}{50!\times4!} = 316.251~\text{cara}}$$Jadi, banyaknya solusi integer (bulat) dari persamaan
$$x_1 + x_2 + x_3 + x_4 + x_5 = 50, x_i \geq 0, i \in \{1, 2, 3, 4, 5\}$$ adalah $316.251$ cara.

[collapse]

Soal Nomor 6
Tentukan banyaknya solusi integer (bulat) dari persamaan
$x_1 + x_2 + x_3= 50, x_i \geq 3, i \in \{1, 2, 3\}$

Pembahasan

Beberapa solusi bulat yang memenuhi persamaan itu adalah $(10, 20, 20)$, $(5, 15, 30)$, atau $(3, 4, 43)$, dan ini merupakan kasus yang cenderung mengarah pada kombinasi.
Karena dalam persamaan tersebut memuat $3$ variabel, maka fungsi pembangkit dari permasalahan itu memuat $3$ faktor. Selanjutnya, karena setiap variabel $x_i \geq 3$, maka setiap faktor dalam fungsi pembangkit tersebut adalah $(x^3 + x^4 + x^5 + \cdots)$. Misalkan $P(x)$ adalah FPB dari permasalahan ini, maka
$\begin{aligned} P(x) & = (x^3 + x^4 + x^5 + \cdots)^3 \\ & = (x^3(1 + x + x^2 + \cdots))^3 \\ & = x^9\left(\dfrac{1}{1-x}\right)^3 \\ & = x^9 \displaystyle \sum_{k=0}^{\infty} \binom{3+k-1}{k}x^k \end{aligned}$
Banyak solusi bulat yang dimaksud sama dengan koefisien $x^{50}$ ($k$ yang diambil adalah $50-9 = 41$) dalam $P(x)$, yaitu
$$\boxed{\displaystyle \binom{3 + 41-1}{41} = \binom{43}{41} = \dfrac{43!}{41!\times2!} = 903~\text{cara}}$$Jadi, banyaknya solusi integer (bulat) dari persamaan
$x_1 + x_2 + x_3= 50, x_i \geq 3, i \in \{1, 2, 3\}$ adalah $903$ cara.

[collapse]

Soal Nomor 7
Tentukan banyaknya solusi bulat dari persamaan
$x_1 + x_2 + x_3 + x_4 = 80, 1 \leq x_i \leq 30$, $i \in \{1, 2, 3, 4\}$

Pembahasan

Misalkan $P(x)$ adalah fungsi pembangkit biasa dari kasus ini, maka
$\begin{aligned}P(x) & = (x + x^2 + x^3 + \cdots + x^{30})^4 \\ & =(x(1 + x + x^2 + \cdots + x^{29})^4 \\ & =x^4(1+x+x^2+\cdots+x^{29})^4 \end{aligned}$
Gunakan preposisi berikut.
$$\boxed{1+x+x^2+\cdots+x^{m-1})^n = (1-x^m)^n(1+x+x^2+\cdots)^n}$$Jadi, diperoleh
$P(x) = x^4(1-x^{30})^4(1+x+x^2+\cdots)^4$
Uraikan ekspresi $(1-x^{30})^4$ dengan Segitiga Pascal atau Teorema Binomial untuk memperoleh
$$\begin{aligned} P(x) & = x^4(1-4x^{30} + 6x^{60}-4x^{90} + x^{120})(1+x+x^2+\cdots)^4 \\ & =(x^4-4x^{34} + 6x^{64}-4x^{94} + x^{124})\left(\dfrac{1}{1-x}\right)^4 \\ & =(x^4- 4x^{34} + 6x^{64}- 4x^{94} + x^{124})\displaystyle \sum_{k=0}^{\infty} \binom{4+k-1}{k}x^k \end{aligned}$$Banyaknya solusi bulat yang dimaksud adalah koefisien $x^{80}$ dalam $P(x)$. Hanya tiga suku dalam ekspresi di luar notasi sigma yang akan ditinjau, yaitu $x^4,-4x^{34}, \text{dan}, 6x^{64}$, karena pangkatnya tidak melebihi $80$. Tinjau satu per satu:
(i) $x^{80} = x^4.x^{76}$ berarti notasi sigmanya menjadi,
$\displaystyle \sum_{n=0}^{\infty}\binom{4+76-1}{76}x^{76}$
Koefisien $x^{76} = \displaystyle \binom{79}{76}$
(ii) $x^{80} = x^{34}.x^{46}$ berarti notasi sigmanya menjadi,
$\displaystyle \sum_{n=0}^{\infty}\binom{4+46-1}{46}x^{46}$
Koefisien $x^{46} = \displaystyle \binom{49}{46}$
(iii) $x^{80} = x^{64}.x^{16}$ berarti notasi sigmanya menjadi,
$\displaystyle \sum_{n=0}^{\infty}\binom{4+16-1}{16}x^{16}$
Koefisien $x^{16} = \displaystyle \binom{19}{16}$
Akhirnya, kita dapatkan koefisien $x^{80}$ dalam $P(x)$ adalah
$\displaystyle \binom{79}{76}- 4\binom{49}{46} + 6\binom{19}{16}$.
Jadi, banyaknya solusi bulat dari persamaan
$x_1 + x_2 + x_3 + x_4 = 80, 1 \leq x_i \leq 30$, $i \in \{1, 2, 3, 4\}$
adalah
$\displaystyle \binom{79}{76}-4\binom{49}{46} + 6\binom{19}{16}$

[collapse]

Soal Nomor 8 
Diketahui bahwa akan ada $3$ kendaraan baru yaitu sedan, bus dan truk yang akan dibeli pihak pabrik. Pihak pabrik membeli $n$ buah kendaraan baru dengan syarat paling sedikit $1$ sedan, paling banyak $10$ bus, dan sekurang-kurangnya $2$ tapi tak lebih dari $15$ truk. Ada berapa cara yang dapat dilakukan jika $2$ kendaraan sejenis tidak dibedakan?

Pembahasan

Misalkan $s, b, t$ berturut-turut menyatakan banyaknya sedan, bus, dan truk, sehingga berdasarkan informasi yang diberikan,
$s \geq 1, b \leq 10, 2 \leq t \leq 15$
Karena $2$ kendaraan sejenis dianggap sama, maka kasus ini tergolong kasus kombinasi.
Fungsi pembangkit yang bersesuaian dengan syarat yang diberikan tersebut adalah
$$\begin{aligned} P(x) & = (x + x^2 + \cdots) + (1 + x + \cdots + x^{10})(x^2 + x^3 + \cdots + x^{15}) \\ & = x^3(1-x^{11})(1-x^{14})(1+x+x^2 + \cdots)^3 \\ &= (x^3- x^{14}-x^{17} + x^{28}) \displaystyle \sum_{k=0}^{\infty} \binom{3 + k-1}{k}x^k \\ & = \displaystyle \sum_{k=0}^{\infty} \binom{2 + k}{k}x^{k+3}- \sum_{k=0}^{\infty} \binom{2 + k}{k}x^{k+14}-\sum_{k=0}^{\infty} \binom{2 + k}{k}x^{k+17} + \sum_{k=0}^{\infty} \binom{2 + k}{k}x^{k+28} \\ & = \displaystyle \sum_{k=3}^{\infty} \binom{k-1}{k-3}x^{k}-\sum_{k=14}^{\infty} \binom{k-12}{k-14}x^k-\displaystyle \sum_{k=17}^{\infty} \binom{k-15}{k-17}x^k + \sum_{k=0}^{\infty} \binom{k-26}{k-28}x^k \end{aligned}$$Banyak cara yang dimaksud sama dengan koefisien $x^k$ (untuk $n = k$) dari $P(x)$, yaitu
$$\begin{cases} \displaystyle 0 & \text{jika}~k < 3 \\ \displaystyle  \binom{k-1}{k-3} & \text{jika}~3 \leq k \leq 13 \\ \displaystyle \binom{k-1}{k-3}-\binom{k-12}{k-14} & \text{jika}~14 \leq k \leq 16 \\ \displaystyle \binom{k-1}{k-3}-\binom{k-12}{k-14}-\binom{k-15}{k-17} & \text{jika}~17 \leq k \leq 27 \\ \displaystyle \binom{k-1}{k-3}-\binom{k-12}{k-14}- \binom{k-15}{k-17}+ \binom{k-26}{k-28} & \text{jika}~k \geq 28 \end{cases}$$

[collapse]

Baca: Soal dan Pembahasan – Notasi Sigma

Soal Nomor 9
Tentukan banyaknya cara mendistribusikan $15$ objek identik ke dalam $10$ kotak berbeda sedemikian sehingga setiap kotak berjumlah sebanyak genap objek identik.

Pembahasan

Kasus ini tergolong kasus kombinasi, karena objek yang ditinjau identik.
Misalkan $P(x)$ adalah FPB kasus tersebut, sehingga berdasarkan syarat yang diberikan, didapat
$P(x) = (1 + x^2 + x^4 + \cdots)^{10}$
Berdasarkan Soal Latihan- Fungsi Pembangkit (Dasar) Bagian 2 Soal Nomor 19 , diperoleh
$P(x) = \left(\dfrac{1}{1-x^2}\right)^{10}$
$P(x) = \displaystyle \sum_{n=0}^{\infty} \binom{10+k-1}{k}x^{2k}$
Kita akan mencari koefisien $x^{15}$ dalam $P(x)$ yang selanjutnya menyatakan banyak cara pendistribusian yang dimaksud. Tetapi, perhatikan bahwa $2k$ merupakan bilangan genap, sehingga tidaklah mungkin $x^{15}$ ada, sebab $15$ adalah bilangan ganjil. Jadi, ada $0$ cara (tidak ada cara) mendistribusikan $15$ objek identik ke $10$ kotak yang berbeda sedemikian sehingga setiap kotak berjumlah sebanyak genap objek yang identik.

[collapse]

Soal Nomor 10
Tentukan fungsi pembangkit untuk menemukan banyaknya solusi bilangan bulat dari persamaan linear 
$x_1 + 2x_2 + 3x_3 + 4x_4 = r$ dengan $x_i \geq 0$.

Pembahasan

Misalkan
$x_1 = y_1$, dengan barisan $(0, 1, 2, 3, \cdots)$
$2x_2 = y_2$, dengan barisan $(0, 2, 4, 6, \cdots)$
$3x_3 = y_3$, dengan barisan $(0, 3, 6, 9, \cdots)$
$4x_4 = y_4$, dengan barisan $(0, 4, 8, 12, \cdots)$
Catatan: barisan bilangan yang mewakili $y_i$ tersebut didapat dengan cara mensubstitusikan $x_i \geq 0$ ke masing-masing pemisalan.
Dengan demikian, diperoleh persamaan linear baru
$y_1 + y_2 + y_3 + y_4 = r$
Misalkan $P(x)$ merupakan fungsi pembangkit biasa dari kasus ini, sehingga
$$\begin{aligned} P(x) & = (1 + x + x^2 + \cdots)(1 + x^2 + x^4 + \cdots )(1 + x^3 + x^6 + \cdots)(1 + x^4 + x^8 + \cdots) \\ & = \displaystyle (\dfrac{1}{1-x}) (\dfrac{1}{1-x^2}) (\dfrac{1}{1-x^3}) (\dfrac{1}{1-x^4}) \\ & = \displaystyle \sum_{n=0}^{\infty} x^n + \sum_{n=0}^{\infty} x^{2n} + \sum_{n=0}^{\infty} x^{3n} + \sum_{n=0}^{\infty} x^{4n} \end{aligned}$$Jadi, fungsi pembangkit yang digunakan untuk menemukan banyaknya solusi bulat dari persamaan linear tersebut adalah $\boxed{ \displaystyle \sum_{n=0}^{\infty} x^n + \sum_{n=0}^{\infty} x^{2n} + \sum_{n=0}^{\infty} x^{3n} + \sum_{n=0}^{\infty} x^{4n}}$

[collapse]

Soal Nomor 11 
Ada berapa cara membagi $p$ buah apel identik kepada $q$ anak, sedemikian sehingga tiap anak mendapat tidak lebih dari $100$ buah apel tetapi juga tidak kurang dari $10$ buah apel?

Pembahasan

Misalkan $a$ menyatakan banyak apel yang dapat diterima setiap anak, sehingga berdasarkan informasi yang diberikan,diperoleh  $10 \leq a \leq 100$.
Karena apel-apelnya dianggap sama/identik, maka kasus ini tergolong kasus kombinasi.
Fungsi pembangkit yang bersesuaian dengan syarat yang diberikan tersebut adalah
$\begin{aligned} P(x) & = (x^{10} + x^{11} + x^{12} + \cdots + x^{100})^q \\ & = x^{10q}(1 + x + x^2 + x^3 + \cdots + x^{90})^q \\ & = x^{10q}(1-x^{91})^q\left(\dfrac{1}{1-x}\right)^q \\ & = (x^{10}-x^{101})^q\left(\dfrac{1}{1-x}\right)^q \\ & =  (x^{10}-x^{101})^q \displaystyle \sum_{k = 0}^{\infty} \binom{q-k + 1}{k}x^k \end{aligned}$
Banyak cara yang dimaksud sama dengan koefisien $x^p$ dalam $P(x)$. Perhatikan bahwa bentuk $(x^{10}-x^{101})^q$ masih berbentuk umum (karena eksistensi $q$), sehingga tidak dapat kita uraikan secara manual. Oleh karenanya, kita gunakan perluasan Teorema Binomial Newton, yaitu
$$\begin{aligned} P(x) & = \displaystyle (x^{10}-x^{101})^q \\ & = \left[\displaystyle \binom{q}{0}x^{10q}-\binom{q}{1}x^{10(q-1)}x^{101} + \binom{q}{2}x^{10(q-2)}x^{202}-\cdots \binom{q}{q}x^{101q}\right] \sum_{k=0}^{\infty} \binom{n-k + 1}{k}x^k \\ = & \binom{q}{0} \displaystyle \sum_{k=0}^{\infty} \binom{n- k + 1}{k}x^{k+10q}-\binom{q}{1} \displaystyle \sum_{k=0}^{\infty} \binom{n-k + 1}{k}x^{k+10q+91} + \binom{q}{2} \displaystyle \sum_{k=0}^{\infty} \binom{n-k + 1}{k}x^{k+10q+182}- \cdots + \cdots \\ & =  \binom{q}{0} \displaystyle \sum_{k=10q}^{\infty} \binom{n-k + 10q + 1}{k- 10q}x^k- \binom{q}{1} \displaystyle \sum_{k=10q+91}^{\infty} \binom{n-k + 10q + 92}{k-10q- 91}x^k + \binom{q}{2} \displaystyle \sum_{k=10q+182}^{\infty} \binom{n-k + 10q + 183}{k}x^k-\cdots + \cdots \end{aligned}$$Koefisien $x^p$ menentukan banyak cara pembagian apelnya, yaitu dengan nilai dan syarat berikut (ubah $k$ sebagai $p$)
$$\boxed{\begin{cases} 0 & \text{jika}~p < 10q \\ \displaystyle \binom{q}{0}\binom{n-p + 10q + 1}{p-10q} & \text{jika}~10q \leq p < 10q + 91 \\ \displaystyle \binom{q}{1}\binom{n-p + 10q + 92}{p-10q-91} & \text{jika}~10q+91 \leq p < 10q + 182 \\ \vdots~~\vdots~~\vdots \end{cases}}$$

[collapse]

Soal Nomor 12
Ada berapa cara mendistribusikan (membagikan) $r$ bola yang identik ke dalam $n$ wadah berbeda dengan syarat paling banyak $3$ bola dalam setiap wadah?

Pembahasan

Karena bolanya dianggap identik, maka kasus ini tergolong kasus kombinasi. Misalkan $P(x)$ adalah FPB dari kasus ini, sehingga didapat
$\begin{aligned} P(x) & = (1 + x + x^2 + x^3)^n \\ & = (1-x^4)^n(1 + x + x^2 + \cdots)^n \\ & = (1-x^4)^n\left(\dfrac{1}{1-x}\right)^n \\ & = (1-x^4)^n\displaystyle \sum_{k=0}^{\infty} \binom{n+k-1}{k}x^k \end{aligned}$
Penguraian bentuk $(1-x^4)^n$ dapat dilakukan dengan menggunakan Teorema Binomial Newton sebagai berikut.
$$(1-x^4)^n = \displaystyle\binom{n}{0}-\binom{n}{1}x^4 + \binom{n}{2}x^8-\cdots \pm \binom{n}{n}x^{4n}$$Jika masing-masing suku ini dikalikan ke dalam bentuk sumasinya, diperoleh
$$\begin{aligned} P(x) & = \displaystyle \binom{n}{0} \sum_{k=0}^{\infty} \binom{n +k-1}{k}x^k-\binom{n}{1} \sum_{k=0}^{\infty} \binom{n+k-1}{k}x^{k+4} + \binom{n}{2} \sum_{k=0}^{\infty} \binom{n+k-1}{k}x^{k+8}\cdots \pm \binom{n}{n} \sum_{k=0}^{\infty} \binom{n+k-1}{k}x^{k + 4n} \\ & = \displaystyle \binom{n}{0} \sum_{r=0}^{\infty} \binom{n+r-1}{r}x^r-\binom{n}{1} \sum_{r=4}^{\infty} \binom{n+r-5}{r-4}x^r + \binom{n}{2} \sum_{r=8}^{\infty} \binom{n+r-9}{r-8}x^r \cdots \pm \binom{n}{n} \sum_{r=4n}^{\infty} \binom{-3n+r-1}{r-4n}x^{r} \end{aligned}$$Kita akan menentukan koefisien $x^r$ dalam $P(x)$ karena koefisiennya mewakili banyaknya cara pendistribusiannya.
$$\boxed{\begin{cases} \displaystyle\binom{n+r-1}{r} & \text{jika}~r < 4 \\ \displaystyle \binom{n+r-1}{r}-\binom{n}{1}\binom{n+r-5}{r-4} & \text{jika}~4 \leq r < 7 \\ \displaystyle \binom{n}{r}-\binom{n}{1}\binom{n+r-5}{r-4} + \binom{n}{2}\binom{n+r-9}{r-8} & \text{jika}~8 \leq r < 12 \\ \vdots~~\vdots~~\vdots \end{cases}}$$ 

[collapse]

Soal Nomor 13
Tiga buah dadu digulirkan secara bersamaan. Tentukan banyaknya kombinasi yang mungkin untuk mendapatkan jumlah mata dadu $n$.

Pembahasan

Total kombinasi yang dapat terjadi pada $3$ buah dadu adalah $6^3 = 216$ kombinasi. Misalkan $P(x)$ menyatakan fungsi pembangkit biasa dari kasus ini, sehingga
$P(x) = (x + x^2 + x^3 + x^4 + x^5 + x^6)^3$
Penjelasan: Masing-masing dadu (ada $3$) memiliki jumlah sisi $6$, dengan jumlah mata dadunya dari $1$ sampai $6$, sehingga perpangkatan $x$ juga dimulai dari $1$, yaitu $x$ sampai $x^6$.
Bila dilanjutkan,
$$\begin{aligned}P(x) & = x^3(1 + x + x^2 + x^3 + x^4 1 x^5)^3 \\ & = x^3(1- x^6)^3(1 + x + x^2 + \cdots)^3 \\ & = x^3(1- 3x^6 + 3x^{12}-x^{18})\left(\dfrac{1}{1-x}\right)^3 \\ & = (x^3-3x^9 + 3x^{15}-x^{21}) \displaystyle \sum_{n=0}^{\infty} \binom{3 + k-1}{k} x^k \end{aligned}$$Kalikan masing-masing suku dalam kurung ke dalam ekspresi notasi sigma.
$$\begin{aligned} P(x) = & \displaystyle \sum_{k=0}^{\infty} \binom{2 + k}{k} x^{k+3}- 3 \sum_{k=0}^{\infty} \binom{2 + k}{k} x^{k+9} \\ \displaystyle & + 3 \sum_{k=0}^{\infty} \binom{2 + k}{k} x^{k+15}- \sum_{k=0}^{\infty} \binom{2 + k}{k} x^{k+21} \end{aligned}$$Ubah perpangkatan $x$ dengan memanipulasi batas bawah sumasi.
$$\begin{aligned} P(x) & = \displaystyle \sum_{n=3}^{\infty} \binom{2 + (n- 3)}{n-3} x^n-3 \sum_{n=9}^{\infty} \binom{2 + (n-9)}{n- 9} x^n + 3 \sum_{n=15}^{\infty} \binom{2 + (n- 15)}{n-15} x^n-\sum_{n=21}^{\infty} \binom{2 + (n-21)}{n-21} x^n \\ & = \displaystyle \sum_{n=3}^{\infty} \binom{n-1}{n-3} x^n-3 \sum_{n=9}^{\infty} \binom{n- 7}{n- 9} x^n + 3 \sum_{n=15}^{\infty} \binom{n-13}{n-15} x^n-\sum_{n=21}^{\infty} \binom{n-19}{n-21} x^n \end{aligned}$$Dari sini, kita dapat nyatakan banyaknya kombinasi untuk jumlah mata dadu $n$ yaitu sebanyak koefisien $x^n$ dari $P(x)$,
$$\boxed{a_n = \begin{cases} 0 & \text{jika}~n < 3 \\ \displaystyle \binom{n-1}{n-3} & \text{jika}~ 3 \leq n < 9 \\ \displaystyle \binom{n-1}{n-3}-3\binom{n-7}{n-9} & \text{jika}~ 9 \leq n < 15 \\ \displaystyle \binom{n- 1}{n-3}-3\binom{n-7}{n-9} + 3\binom{n-13}{n-15} & \text{jika}~ 15 \leq n < 21 \\ \displaystyle \binom{n-1}{n-3}-3\binom{n-7}{n-9} + 3\binom{n-13}{n-15}-\binom{n-19}{n-21} & \text{jika}~ n \geq 21 \end{cases}}$$Ilustrasi:Jika dimisalkan $n = 4$ (berarti yang ditanya adalah banyak kombinasi munculnya jumlah mata dadu $4$ dari pelemparan $3$ buah dadu), maka
$a_4 = \displaystyle \binom{4-1}{4-3} = \binom{3}{1} = 3$
Kombinasi yang dimaksud adalah
$(1, 1, 2), (2, 1, 1), (1, 2, 1)$

[collapse]

Soal Nomor 14
Berapa banyak cara memilih $k$ huruf dari kata PESAWAT jika memuat paling banyak $3$ huruf A dan tepat $1$ T?

Pembahasan

Ini merupakan kasus kombinasi karena yang ditanyakan adalah PEMILIHAN, bukan PENYUSUNAN hurufnya, sehingga penyelesaiannya menggunakan konsep fungsi pembangkit biasa.
Misalkan $P(x)$ adalah FPB dari kasus ini sehingga dapat dinyatakan bahwa
$$\begin{aligned} P(x) & = x(1 + x + x^2 + x^3)(1 + x + x^2 + \cdots)^4 \\ & = x(1-x^4)(1 + x + x^2 + \cdots)^5 \\ & = (x-x^5)\left(\dfrac{1}{1-x}\right)^5 \\ & = (x-x^5) \displaystyle \sum_{n=0}^{\infty} \binom{5 + k-1}{k}x^k \\ & = \displaystyle \sum_{k=0}^{\infty} \binom{k + 4}{k}x^{k+1}-\sum_{k=0}^{\infty} \binom{k + 4}{k}x^{k+5} \\ & = \displaystyle \sum_{n=1}^{\infty} \binom{(n-1) + 4}{n-1}x^n- \sum_{n=5}^{\infty} \binom{(n-5) + 4}{n-5}x^n \\ & = \displaystyle \sum_{n=1}^{\infty} \binom{n + 3}{n- 1}x^n-\sum_{n=5}^{\infty} \binom{n-1}{n-5}x^n \end{aligned}$$Banyak cara memilih $k$ huruf sama dengan koefisien $x^n$ dalam $P(x)$ yang dinyatakan sebagai
$$\boxed{a_n = \begin{cases} 0 & \text{jika}~n = 0 \\ \displaystyle \binom{n + 3}{n-1} & \text{jika}~1 \leq n \leq 4 \\ \displaystyle \binom{n + 3}{n-1}-\binom{n-1}{n-5} & \text{jika}~n \geq 5 \end{cases}}$$

[collapse]