Soal Latihan – Fungsi Pembangkit Untuk Kombinasi

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?

Penyelesaian

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:
G(x) = (x + x^2 + x^3 + ...)^4
= x^4(1+x+x^2+...)^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
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~\text{cara}}
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?

Penyelesaian

Ini merupakan kasus kombinasi, karena objek yang ditinjau adalah identik.
Misalkan P(x) adalah FPB dari kasus tersebut, sehingga berdasarkan syarat yang diperkenankan, diperoleh
P(x) = (x^{10} + x^{11} + ... + x^{20})^4
= (x^{10}(1+x+x^2+...+x^{10}))^4
=x^{40}(1+x+x^2+...+x^{10})^4
=x^{40}(1-x^{11})^4(1+x+x^2+...)^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
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?

Penyelesaian

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 + ...)(1+x+x^2+x^3)(1+x+x^2+...)^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
P(x) = x(1+x+x^2+...)(1+x+x^2+x^3)(1+x+x^2+...)^5
=x(1+x+x^2+x^3)(1+x+x^2+...)^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
Banyak cara penyusunan huruf-huruf tersebut sama dengan koefisien x^{20} dalam P(x). Berturut-turut (dengan meninjau bentuk pangkat di luar operator 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
\displaystyle \binom{6+19-1}{19}+\binom{6+18-1}{18}+\binom{6+17-1}{17}+\binom{6+16-1}{16}
= \boxed{\displaystyle \left[ \binom{24}{19}+\binom{23}{18}+\binom{22}{17}+\binom{21}{16}\right]~\text{cara}}

[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?

Penyelesaian

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 + ...)(1+x+x^2+x^3)(1+x+x^2+...)^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
P(x) = x(1+x+x^2+...)(1+x+x^2+x^3)(1+x+x^2+...)^4
=x(1+x+x^2+x^3)(1+x+x^2+...)^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
Banyak cara penyusunan huruf-huruf tersebut sama dengan koefisien x^{10} dalam P(x). Berturut-turut (dengan meninjau bentuk pangkat di luar operator sigma) ambil k = 9, 8, 7, 6, diperoleh bahwa banyak cara memilih 10 huruf dari kata PINTAR dengan syarat yang telah disebutkan sebelumnya adalah
\displaystyle \binom{5+9-1}{9}+\binom{5+8-1}{8}+\binom{5+7-1}{7}+\binom{5+6-1}{6}
= \boxed{\displaystyle \left[ \binom{13}{9}+\binom{12}{8}+\binom{11}{7}+\binom{10}{6}\right]~\text{cara}}

[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\}

Penyelesaian

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 + ...). Misalkan P(x) adalah FPB dari permasalahan ini, maka
P(x) = (1 + x + x^2 + x^3 + ...)^5
= \left(\dfrac{1}{1-x}\right)^5
= \displaystyle \sum_{k=0}^{\infty} \binom{5+k-1}{k}x^k
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\}

Penyelesaian

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 + ...). Misalkan P(x) adalah FPB dari permasalahan ini, maka
P(x) = (x^3 + x^4 + x^5 + ...)^3
= (x^3(1 + x + x^2 + ...))^3
= x^9\left(\dfrac{1}{1-x}\right)^3
= x^9 \displaystyle \sum_{k=0}^{\infty} \binom{3+k-1}{k}x^k
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\}

Penyelesaian

Misalkan P(x) adalah fungsi pembangkit biasa dari kasus ini, maka
P(x) = (x + x^2 + x^3 + ... + x^{30})^4
=(x(1 + x + x^2 + ... + x^{29})^4
=x^4(1+x+x^2+...+x^{29})^4
Gunakan preposisi berikut.
\boxed{1+x+x^2+...+x^{m-1})^n = (1-x^m)^n(1+x+x^2+...)^n}
Jadi, diperoleh
P(x) = x^4(1-x^{30})^4(1+x+x^2+...)^4
Uraikan ekspresi (1-x^{30})^4 dengan Segitiga Pascal atau Teorema Binomial untuk memperoleh
P(x) = x^4(1-4x^{30} + 6x^{60} - 4x^{90} + x^{120})(1+x+x^2+...)^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
Banyaknya solusi bulat yang dimaksud adalah koefisien x^{80} dalam P(x). Hanya tiga suku dalam ekspresi di luar operator 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 operator 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 operator 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 operator 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?

Penyelesaian

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
P(x) = (x + x^2 + \cdots) + (1 + x + \cdots + x^{10})(x^2 + x^3 + \cdots + x^{15})
P(x) = x^3(1-x^{11})(1-x^{14})(1+x+x^2 + \cdots)^3
P(x) = (x^3 - x^{14} - x^{17} + x^{28}) \displaystyle \sum_{k=0}^{\infty} \binom{3 + k - 1}{k}x^k
\begin{aligned} P(x) = & \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} \end{aligned}
\begin{aligned} P(x) = & \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]

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

Penyelesaian

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 + ...)^{10}
Berdasarkan Soal Latihan – Fungsi Pembangkit (Dasar) Part 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

Penyelesaian

Misalkan
x_1 = y_1, dengan barisan (0, 1, 2, 3, …)
2x_2 = y_2, dengan barisan (0, 2, 4, 6, …)
3x_3 = y_3, dengan barisan (0, 3, 6, 9, …)
4x_4 = y_4, dengan barisan (0, 4, 8, 12, …)
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
P(x) = (1 + x + x^2 + ...)(1 + x^2 + x^4 + ...)(1 + x^3 + x^6 + ...)(1 + x^4 + x^8 + ...)
P(x) = \displaystyle (\dfrac{1}{1-x}) (\dfrac{1}{1-x^2}) (\dfrac{1}{1-x^3}) (\dfrac{1}{1-x^4})
\boxed{P(x) = \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}}
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 (Requested by Tamvan on December, 27th 2017) 
Ada berapa cara membagi p buah apel identik kepada anak, sedemikian sehingga tiap anak mendapat tidak lebih dari 100 buah apel tetapi juga tidak kurang dari 10 buah apel?

Penyelesaian

Misalkan a menyatakan banyak apel yang dapat diterima setiap anak, sehingga berdasarkan informasi yang diberikan,
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
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
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
\displaystyle (x^{10} - x^{101})^q
\begin{aligned} P(x) = & \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 \end{aligned}
\begin{aligned} P(x) = & \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 \end{aligned}
\begin{aligned} P(x) = & \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?

Penyelesaian

Karena bolanya dianggap identik, maka kasus ini tergolong kasus kombinasi. Misalkan P(x) adalah FPB dari kasus ini, sehingga didapat
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
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 \binom{n}{n}x^{8n}
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 \binom{n}{n} \sum_{k=0}^{\infty} \binom{n - k + 1}{k}x^{k + 4n} \end{aligned}
\begin{aligned} P(x) = & \displaystyle \binom{n}{0} \sum_{r=0}^{\infty} \binom{n - r + 1}{k}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 \binom{n}{n} \sum_{r=4n}^{\infty} \binom{5n - 4r + 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-k+5}{k-4} & \text{jika}~4 \leq r < 7 \\ \displaystyle \binom{n - r + 1}{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

Penyelesaian

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 \end{aligned}
\begin{aligned} P(x) = & \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 </span>\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.

Penyelesaian

Ini merupakan kasus kombinasi karena yang ditanyakan adalah PEMILIHAN, bukan PENYUSUNAN hurufnya (jadi, gunakan fungsi pembangkit biasa). Diketahui huruf vokal: A, E dan huruf konsonan: P, S, W, T.
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]
Ayo Beri Rating Postingan Ini

6 Balasan untuk “Soal Latihan – Fungsi Pembangkit Untuk Kombinasi”

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *