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]
CategoriesMatematika DiskritTags, , , , ,

Leave a Reply

Silakan beri tanggapan dan saran, tidak perlu sungkan. Mohon juga diinformasikan melalui kolom komentar ini bila ada kesalahan pengetikan sekecil apapun (typo atau bahasa latex yang error) atau kesalahan konsep dan pembahasan soal. Terima kasih. Ganbatte!

Your email address will not be published. Required fields are marked *