Soal Latihan dan Penyelesaian – Fungsi Pembangkit Untuk Permutasi

Anda sudah harus menguasai FUNGSI PEMBANGKIT (DASAR) untuk mempelajari materi ini.
Klik link berikut jika Anda ingin mempelajarinya lebih dalam. Selamat belajar! \bigstar\bigstar\bigstar\bigstar\bigstar
Soal Latihan – Fungsi Pembangkit (Dasar) Part 1
Soal Latihan – Fungsi Pembangkit (Dasar) Part 2

Soal Nomor 1
Tentukan banyaknya kata sandi yang dapat dibentuk dari kata CANTIK di mana setiap huruf vokalnya harus muncul.

Penyelesaian

Kasus ini cenderung mengarah pada kasus permutasi karena pada kata sandi, pembolak-balikan huruf akan dianggap berbeda.
Huruf vokal: A, I (ada 2)
Huruf konsonan: C, N, T, K (ada 4)
Misalkan P(x) adalah FPE dari kasus ini. Dengan memerhatikan syarat yang diperkenankan, yaitu huruf vokal harus muncul (huruf A dan I masing-masing setidaknya muncul 1 kali), diperoleh
P(x) = \left(1 + x + \dfrac{x^2}{2!} + ...\right)^4\left(x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + ...\right)^2
=(e^x)^4(e^x - 1)^2
=e^{4x}(e^{2x} - 2e^x + 1)
=e^{6x} - 2e^{5x} + e^{4x}
Ubahlah ke dalam operator sigma.
P(x) = \displaystyle \sum_{n=0}^{\infty} \dfrac{(6x)^n}{n!} - 2\sum_{n=0}^{\infty} \dfrac{(5x)^n}{n!} + \sum_{n=0}^{\infty} \dfrac{(4x)^n}{n!}
P(x) = \displaystyle \sum_{n=0}^{\infty} 6^n.\dfrac{x^n}{n!} - 2\sum_{n=0}^{\infty}5^n. \dfrac{x^n}{n!} + \sum_{n=0}^{\infty} 4^n.\dfrac{x^n}{n!}
Banyak kata sandi yang dapat terbentuk sama dengan koefisien \dfrac{x^n}{n!} dalam P(x), yaitu
a_n = 6^n - 2(5)^n + 4^n, n \geq 0
Catatan: Dalam kasus ini, n menyatakan banyak huruf dari kata sandi yang ingin dibentuk. Misalkan kata sandi yang diinginkan mengandung 9 huruf, maka n diganti menjadi 9.

[collapse]


Soal Nomor 2
Berapa banyak barisan kuarternair 3-angka yang memuat paling sedikit satu 1, satu 2, dan satu 3.

Penyelesaian

Barisan kuarternair didefinisikan sebagai barisan yang memuat 4 angka (4 digit) yang berbeda, yaitu 0, 1, 2, dan 3. Berdasarkan ketentuan di atas, dapat dituliskan
Angka 0 bebas syarat,
Angka 1, 2, dan 3 muncul paling sedikit 1 kali.
Karena urutan angka diperhatikan, maka kasus ini digolongkan sebagai kasus permutasi. Misalkan P(x) adalah FPE dari kasus ini, sehingga
P(x) = \left(1 + x + \dfrac{x^2}{2!} + ...\right)\left(x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + ....\right)^3
=e^x(e^x - 1)^3
=e^x(e^{3x} - 3e^{2x} + 3e^x - 1)
=e^{4x} - 3e^{3x} + 3e^{2x} - e^x
=\displaystyle \sum_{r=0}^{\infty} \dfrac{1}{r!}(4x)^r - 3\sum_{r=0}^{\infty} \dfrac{1}{r!}(3x)^r + 3 \sum_{r=0}^{\infty} \dfrac{1}{r!}(2x)^r - \sum_{r=0}^{\infty} \dfrac{1}{r!}x^r
Banyak barisan kuarternair r-angka dengan syarat tersebut adalah koefisien \dfrac{1}{r!}x^r dalam P(x), yaitu
\boxed{4^r - 3.3^r + 3.2^r - 1}
Untuk r = 3: Banyak barisan kuarternair 3-angka dengan syarat tersebut adalah
\boxed{4^3 - 3.3^3 + 3.2^3 - 1 = 64 - 81 + 24 - 1 = 6}

[collapse]


Soal Nomor 3
Berapa banyak barisan binair r-angka yang memuat 0 sebanyak bilangan genap dan 1 sebanyak bilangan genap pula?

Penyelesaian

Barisan binair didefinisikan sebagai barisan yang memuat 2 angka (2 digit) yang berbeda, yaitu 0 dan 1. Berdasarkan ketentuan di atas, angka 0 dan 1 masing-masing harus sebanyak bilangan genap (0, 2, 4, 6, 8, …)
Karena urutan angka diperhatikan, maka kasus ini digolongkan sebagai kasus permutasi. Misalkan P(x) adalah FPE dari kasus ini, sehingga
P(x) = \left(1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \dfrac{x^6}{6!} + ... \right)^2
Dengan menggunakan rumus Ekspansi Maclaurin, diperoleh bahwa
P(x) = \left(\dfrac{e^x + e^{-x}}{2}\right)^2
= \dfrac{e^{2x} + e^{-2x} + 2}{4}
= \dfrac{1}{2} \left(\dfrac{e^{2x} + e^{-2x}}{2}\right) + \dfrac{1}{2}
=\dfrac{1}{2} \left(1 + \dfrac{(2x)^2}{2!} + \dfrac{(2x)^4}{4!} + \dfrac{(2x)^6}{6!} ...\right) + \dfrac{1}{2}
= 1 + 2.\dfrac{x^2}{2!} + 2^3.\dfrac{x^4}{4!} + 2^5.\dfrac{x^6}{6!} + ...
Banyaknya barisan yang dimaksud sama dengan koefisien \dfrac{x^r}{r!} dalam P(x), yaitu
a_r = \begin{cases} 0, & \mbox{bila r ganjil} \\ 1, & \mbox{bila r = 0} \\ 2^{r-1}, & \mbox{bila r genap}, r > 0\end{cases}

[collapse]


Soal Nomor 4
Tentukan banyaknya barisan ternair r-angka yang memuat angka 0 sebanyak bilangan ganjil dan 1 sebanyak bilangan genap.

Penyelesaian

Barisan ternair didefinisikan sebagai barisan yang memuat 3 angka (3 digit) yang berbeda, yaitu 0, 1, dan 2. Berdasarkan ketentuan di atas, angka 0 harus sebanyak bilangan ganjil (1, 3, 5, 7, 9, …), angka 1 harus sebanyak bilangan genap (0, 2, 4, 6, 8, …), dan angka 2 bebas syarat.
Karena urutan angka diperhatikan, maka kasus ini digolongkan sebagai kasus permutasi. Misalkan P(x) adalah FPE dari kasus ini, sehingga
P(x) = \left(x + \dfrac{x^3}{3!} + \dfrac{x^5}{5!} + ...\right)\left(1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + ...\right)
\left(1 + x \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + ...\right)
Gunakan rumus Ekspansi Maclaurin berikut.
\boxed{\dfrac{e^x + e^{-x}}{2} = 1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + ....}
dan
\boxed{\dfrac{e^x - e^{-x}}{2} = x + \dfrac{x^3}{3!} + \dfrac{x^5}{5!} + ....}
Jadi, diperoleh,
P(x) = \left(\dfrac{e^x - e^{-x}}{2}\right)\left(\dfrac{e^x + e^{-x}}{2}\right)e^x
P(x) = \dfrac{e^{2x} + 1 - 1 - e^{-2x}}{4}e^x
P(x) = \dfrac{e^{2x} - e^{-2x}}{4}.e^x
P(x) = \dfrac{e^{3x} - e^{-x}}{4}
P(x) = \displaystyle \dfrac{1}{4} \sum_{r=0}^{\infty} \dfrac{(3x)^r}{r!} - \dfrac{1}{4} \sum_{r=0}^{\infty} \dfrac{(-x)^r}{r!}
Banyaknya barisan yang dimaksud sama dengan koefisien \dfrac{x^r}{r!} dalam P(x), yaitu
\boxed{\dfrac{3^r}{4} - \dfrac{(-1)^r}{4}}

[collapse]

Soal Nomor 5 (Soal UTS Matematika Diskrit Promat FKIP Untan, tahun 2017/2018)
Tentukan fungsi pembangkit eksponensial yang menyatakan banyaknya cara mendistribusikan r orang yang berbeda ke dalam n kamar berbeda sedemikian sehingga setiap kamar paling sedikit ada 2 orang dan paling banyak ada 5 orang.

Penyelesaian Belum Tersedia

Akan segera diupdate! \bigstar \bigstar

[collapse]

Soal Nomor 6 (Soal UTS Matematika Diskrit Promat FKIP Untan, tahun 2017/2018)
Dengan menggunakan fungsi pembangkit, tentukan banyaknya cara menyusun 10 huruf dari kata “MATEMATIKA”

Penyelesaian

Soal ini dapat diselesaikan dengan mudah menggunakan prinsip permutasi dengan objek yang sama (materi SMA), tetapi kita akan menggunakan prinsip fungsi pembangkit. Perhatikanlah bahwa kita harus menyusun kata yang terdiri dari 10 huruf dari huruf pembentuk MATEMATIKA (yang juga “kebetulan” terdiri dari 10 huruf). Berarti, kita sebenarnya hanya perlu membolak-balik susunan hurufnya sedemikian rupa agar berbeda dengan susunan huruf lainnya. Syarat yang diberikan:
Huruf M harus ada 2
Huruf T harus ada 2
Huruf A harus ada 3
Huruf I, K, E masing-masing harus ada 1
Misalkan P(x) adalah FPE dari kasus ini, sehingga dapat ditulis
P(x) = \left(\dfrac{x^2}{2!}\right)\left(\dfrac{x^2}{2!}\right)\left(\dfrac{x^2}{2!}\right)x^3
P(x) = \dfrac{x^{10}}{2!3!2!}
P(x) = \dfrac{10!}{2!3!2!} \times \dfrac{x^{10}}{10!}
Karena kata yang akan dibentuk terdiri dari 10 huruf, maka koefisien \dfrac{x^{10}}{10!} dalam P(x) menyatakan banyak cara penyusunannya, yaitu \boxed{\dfrac{10!}{2!3!2!}}

[collapse]

Soal Nomor 7
Misalkan Z menyatakan himpunan huruf pembentuk kata MATEMATIKA. Tentukan banyaknya cara menyusun barisan n huruf dari Z dengan syarat huruf T harus muncul (setidaknya 1 kali).

Penyelesaian

Diketahui Z = \{M, A, T, E, I, K\} dan n(Z) = 6. Ini merupakan kasus permutasi sehingga kita harus menggunakan prinsip fungsi pembangkit eksponensial.
Misalkan P(x) menyatakan fungsi pembangkit eksponensial dari kasus ini, sehingga dapat ditulis
P(x) = \left(x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots\right)\left(1 + x + \dfrac{x^2}{2!} + \cdots\right)^5
Ekspresi pada kurung pertamanya menyatakan fungsi pembangkit dari syarat huruf T harus muncul minimal 1 kali, sedangkan ekspresi pada kurung keduanya menyatakan fungsi pembangkit dari 5 huruf lainnya yang bebas syarat. Bila dilanjutkan,
P(x) = (e^x - 1)(e^x)^5 = (e^x - 1)e^{5x} = e^{6x} - e^{5x}
Ubah ke dalam notasi sigma,
\begin{aligned} P(x) & = \displaystyle \sum_{n = 0}^{\infty} \dfrac{(6x)^n}{n!} - \sum_{n = 0}^{\infty} \dfrac{(5x)^n}{n!} \\ & =  \sum_{n = 0}^{\infty} \dfrac{6^nx^n}{n!} - \sum_{n = 0}^{\infty} \dfrac{5^nx^n}{n!} \\ & = \sum_{n = 0}^{\infty} (6^n - 5^n)\dfrac{x^n}{n!} \end{aligned}
Banyak cara menyusun barisan n huruf dari Z dengan syarat huruf T harus muncul sama dengan koefisien \dfrac{x^n}{n!} dalam P(x), yaitu
\boxed{a_n = 6^n - 5^n, n \geq 0}

[collapse]

Soal Nomor 8
Misalkan B adalah himpunan angka-angka pembentuk nomor handphone 081703789269. Tentukan banyak cara menyusun barisan n angka dengan syarat:
a) Angka 0 harus muncul
b) Angka 0 dan 8 harus muncul
c) Angka 0 muncul sebanyak genap
d) Angka 0 muncul sebanyak ganjil

Penyelesaian

Diketahui B = \{0, 1, 2, 3, 6, 7, 8, 9\} dan n(B) = 8
(Jawaban a)
 Tabel berikut menyatakan syarat kemunculan angka pada B.


Fungsi pembangkit eksponensial dari kasus tersebut adalah
P(x) = \left(x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots\right)\left(1 + x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots\right)^7
Ekspresi kurung pertamanya menyatakan fungsi pembangkit dari syarat angka 0 harus muncul (minimal 1 kali), sedangkan ekspresi kurung keduanya menyatakan fungsi pembangkit dari 7 angka lainnya yang bebas syarat. Bila dilanjutkan,
P(x) = (e^x - 1)(e^x)^7 = e^{8x} - e^{7x}
Ubah ke dalam notasi sigma.
\begin{aligned} P(x) & = \displaystyle \sum_{n=0}^{\infty} \dfrac{(8x)^n}{n!} - \sum_{n=0}^{\infty} \dfrac{(7x)^n}{n!} \\ & = \displaystyle \sum_{n=0}^{\infty} \dfrac{8^nx^n}{n!} - \sum_{n=0}^{\infty} \dfrac{7^nx^n}{n!} \\ & = \displaystyle \sum_{n=0}^{\infty} (8^n - 7^n)\dfrac{x^n}{n!} \end{aligned}
Banyak cara menyusun barisan n angka dari B dengan syarat angka 0 harus muncul sama dengan koefisien \dfrac{x^n}{n!} dalam P(x), yaitu
a_n = 8^n - 7^n, n \geq 0

(Jawaban b) Tabel berikut menyatakan syarat kemunculan angka pada B.

Fungsi pembangkit eksponensial dari kasus tersebut adalah
P(x) = \left(x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots\right)^2\left(1 + x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots\right)^6
Ekspresi kurung pertamanya menyatakan fungsi pembangkit dari syarat angka 0 dan 8 harus muncul (minimal 1 kali), sedangkan ekspresi kurung keduanya menyatakan fungsi pembangkit dari 6 angka lainnya yang bebas syarat. Bila dilanjutkan,
\begin{aligned} P(x) & = (e^x - 1)^2(e^x)^6 \\ & = (e^{2x} - 2e^x + 1)(e^{6x}) \\ & = e^{8x} - 2e^{7x} + e^{6x} \end{aligned}
Ubah ke dalam notasi sigma.
\begin{aligned} P(x) & = \displaystyle \sum_{n=0}^{\infty} \dfrac{(8x)^n}{n!} -2 \sum_{n=0}^{\infty} \dfrac{(7x)^n}{n!}+ \sum_{n=0}^{\infty} \dfrac{(6x)^n}{n!} \\ & = \displaystyle \sum_{n=0}^{\infty} \dfrac{8^nx^n}{n!} - 2 \sum_{n=0}^{\infty} \dfrac{7^nx^n}{n!} + \sum_{n=0}^{\infty} \dfrac{6^nx^n}{n!} \\ & = \displaystyle \sum_{n=0}^{\infty} (8^n - 2.7^n + 6^n)\dfrac{x^n}{n!} \end{aligned}
Banyak cara menyusun barisan n angka dari B dengan syarat angka 0 dan 8 harus muncul sama dengan koefisien \dfrac{x^n}{n!} dalam P(x), yaitu
a_n = 8^n - 2.7^n + 6^n, n \geq 0

(Jawaban c) Tabel berikut menyatakan syarat kemunculan angka pada B.

Fungsi pembangkit eksponensial dari kasus tersebut adalah
P(x) = \left(1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \cdots\right)\left(1 + x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots\right)^7
Ekspresi kurung pertamanya menyatakan fungsi pembangkit dari syarat angka 0 muncul sebanyak genap (boleh tidak muncul alias 0 kali, atau 2 kali, 4 kali, atau seterusnya), sedangkan ekspresi kurung keduanya menyatakan fungsi pembangkit dari 7 angka lainnya yang bebas syarat. Bila dilanjutkan,
P(x) = \left(\dfrac{e^x + e^{-x}}{2}\right)(e^x)^7 = \dfrac{e^{8x} + e^{6x}}{2}
Ubah ke dalam notasi sigma.
\begin{aligned} P(x) & = \displaystyle \dfrac{1}{2} \left(\sum_{n=0}^{\infty} \dfrac{(8x)^n}{n!} + \sum_{n=0}^{\infty} \dfrac{(6x)^n}{n!}\right) \\ & = \dfrac{1}{2} \left(\displaystyle \sum_{n=0}^{\infty} \dfrac{8^nx^n}{n!} + \sum_{n=0}^{\infty} \dfrac{6^nx^n}{n!}\right) \\ & = \displaystyle \sum_{n=0}^{\infty} \dfrac{1}{2}(8^n + 6^n)\dfrac{x^n}{n!} \end{aligned}
Banyak cara menyusun barisan n angka dari B dengan syarat angka 0 muncul sebanyak genap sama dengan koefisien \dfrac{x^n}{n!} dalam P(x), yaitu
a_n = \dfrac{1}{2}(8^n + 6^n), n \geq 0

(Jawaban d) Tabel berikut menyatakan syarat kemunculan angka pada B.

Fungsi pembangkit eksponensial dari kasus tersebut adalah
P(x) = \left(x + \dfrac{x^3}{3!} + \dfrac{x^5}{5!} + \cdots\right)\left(1 + x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots\right)^7
Ekspresi kurung pertamanya menyatakan fungsi pembangkit dari syarat angka 0 muncul sebanyak ganjil (1 kali, 3 kali, 5 kali, atau seterusnya), sedangkan ekspresi kurung keduanya menyatakan fungsi pembangkit dari 7 angka lainnya yang bebas syarat. Bila dilanjutkan,
P(x) = \left(\dfrac{e^x - e^{-x}}{2}\right)(e^x)^7 = \dfrac{e^{8x} - e^{6x}}{2}
Ubah ke dalam notasi sigma.
\begin{aligned} P(x) & = \displaystyle \dfrac{1}{2} \left(\sum_{n=0}^{\infty} \dfrac{(8x)^n}{n!} - \sum_{n=0}^{\infty} \dfrac{(6x)^n}{n!}\right) \\ & = \dfrac{1}{2} \left(\displaystyle \sum_{n=0}^{\infty} \dfrac{8^nx^n}{n!} - \sum_{n=0}^{\infty} \dfrac{6^nx^n}{n!}\right) \\ & = \displaystyle \sum_{n=0}^{\infty} \dfrac{1}{2}(8^n - 6^n)\dfrac{x^n}{n!} \end{aligned}
Banyak cara menyusun barisan n angka dari B dengan syarat angka 0 muncul sebanyak genap sama dengan koefisien \dfrac{x^n}{n!} dalam P(x), yaitu
a_n = \dfrac{1}{2}(8^n - 6^n), n \geq 0

[collapse]

Ayo Beri Rating Postingan Ini

5 Balasan untuk “Soal Latihan dan Penyelesaian – Fungsi Pembangkit Untuk Permutasi”

Tinggalkan Balasan

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