Soal dan Pembahasan – Fungsi Pembangkit Untuk Permutasi

Fungsi pembangkit

       Berikut ini merupakan soal dan pembahasan terkait kasus permutasi 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 Kombinasi

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

Pembahasan

Kasus ini cenderung mengarah pada kasus permutasi karena pada kata sandi, bolak-baliknya 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 memperhatikan syarat yang diperkenankan, yaitu huruf vokal harus muncul (huruf A dan I masing-masing setidaknya muncul $1$ kali), diperoleh
$$\begin{aligned} P(x) & = \left(1 + x + \dfrac{x^2}{2!} + \cdots \right)^4\left(x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots \right)^2 \\ & =(e^x)^4(e^x-1)^2 \\ & =e^{4x}(e^{2x}- 2e^x + 1) \\ &=e^{6x}- 2e^{5x} + e^{4x} \end{aligned}$$Ubahlah ke dalam notasi sigma.
$$\begin{aligned} 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!} \\ & = \displaystyle \sum_{n=0}^{\infty} 6^n \cdot \dfrac{x^n}{n!}- 2\sum_{n=0}^{\infty}5^n \cdot \dfrac{x^n}{n!} + \sum_{n=0}^{\infty} 4^n \cdot \dfrac{x^n}{n!} \end{aligned}$$Banyak kata sandi yang dapat terbentuk sama dengan koefisien $\dfrac{x^n}{n!}$ dalam $P(x)$, yaitu $\boxed{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$?

Pembahasan

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:

  1. Angka $0$ bebas syarat.
  2. 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
$$\begin{aligned} P(x) & = \left(1 + x + \dfrac{x^2}{2!} + \cdots \right)\left(x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots \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 \end{aligned}$$Banyak barisan kuarternair $r$-angka dengan syarat tersebut adalah koefisien $\dfrac{1}{r!}x^r$ dalam $P(x)$, yaitu
$\boxed{4^r- 3 \cdot 3^r + 3 \cdot 2^r-1}$
Untuk $r = 3$: Banyak barisan kuarternair $3$-angka dengan syarat tersebut adalah
$\boxed{\begin{aligned} & 4^3- 3 \cdot 3^3 + 3 \cdot 2^3-1 \\ & = 64- 81 + 24-1 = 6 \end{aligned}}$

[collapse]

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

Pembahasan

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, \cdots).$
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!} + \cdots \right)^2.$$Dengan menggunakan rumus Ekspansi Maclaurin, diperoleh bahwa
$$\begin{aligned} 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!} + \cdots \right) + \dfrac{1}{2} \\ & = 1 + 2 \cdot \dfrac{x^2}{2!} + 2^3 \cdot \dfrac{x^4}{4!} + 2^5 \cdot \dfrac{x^6}{6!} + \cdots \end{aligned}$$Banyaknya barisan yang dimaksud sama dengan koefisien $\dfrac{x^r}{r!}$ dalam $P(x)$, yaitu
$\boxed{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.

Pembahasan

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, \cdots)$, angka $1$ harus sebanyak bilangan genap $(0, 2, 4, 6, 8, \cdots)$, 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!} + \cdots \right)\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)$$Gunakan rumus Ekspansi Maclaurin berikut.
$\boxed{\dfrac{e^x + e^{-x}}{2} = 1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \cdots}$
dan
$\boxed{\dfrac{e^x-e^{-x}}{2} = x + \dfrac{x^3}{3!} + \dfrac{x^5}{5!} + \cdots}$
Jadi, diperoleh,
$$\begin{aligned} P(x) & = \left(\dfrac{e^x- e^{-x}}{2}\right)\left(\dfrac{e^x + e^{-x}}{2}\right)e^x \\ & = \dfrac{e^{2x} + 1-1- e^{-2x}}{4} \cdot e^x \\ & = \dfrac{e^{2x}-e^{-2x}}{4} \cdot e^x \\ &= \dfrac{e^{3x}-e^{-x}}{4} \\ & = \displaystyle \dfrac{1}{4} \sum_{r=0}^{\infty} \dfrac{(3x)^r}{r!}-\dfrac{1}{4} \sum_{r=0}^{\infty} \dfrac{(-x)^r}{r!}. \end{aligned}$$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
Dengan menggunakan fungsi pembangkit, tentukan banyaknya cara menyusun $10$ huruf dari kata “MATEMATIKA”.

Pembahasan

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 adalah sebagai berikut.

  1. Huruf M harus ada $2.$
  2. Huruf T harus ada $2.$
  3. Huruf A harus ada $3.$
  4. Huruf I, K, E masing-masing harus ada $1.$

Misalkan $P(x)$ adalah FPE dari kasus ini sehingga dapat ditulis
$\begin{aligned} P(x) & = \left(\dfrac{x^2}{2!}\right)\left(\dfrac{x^2}{2!}\right)\left(\dfrac{x^3}{3!}\right)x^3 \\ & = \dfrac{x^{10}}{2!3!2!} \\ &  = \dfrac{10!}{2!3!2!} \times \dfrac{x^{10}}{10!}. \end{aligned}$
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 6
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).

Pembahasan

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,
$\begin{aligned} P(x) & = (e^x- 1)(e^x)^5 \\ & = (e^x-1)e^{5x} \\ & = e^{6x}-e^{5x}. \end{aligned}$
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]

Baca: Soal dan Pembahasan- Notasi Sigma

Soal Nomor 7
Misalkan $B$ adalah himpunan angka-angka pembentuk nomor handphone $081703789269$. Tentukan banyak cara menyusun barisan $n$ angka dengan syarat:

  1. Angka $0$ harus muncul
  2. Angka $0$ dan $8$ harus muncul
  3. Angka $0$ muncul sebanyak genap
  4. Angka $0$ muncul sebanyak ganjil

Pembahasan

Diketahui $B = \{0, 1, 2, 3, 6, 7, 8, 9\}$ dan $n(B) = 8.$
Jawaban a)

Tabel berikut menyatakan syarat kemunculan angka pada $B$.
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline \text{Anggota B} & 0 & 1 & 2 & 3 & 6 & 7 & 8 & 9 \\ \hline \text{Syarat kemunculan} & \geq 1 & \geq 0 & \geq 0 & \geq 0 & \geq 0 & \geq 0 & \geq 0 & \geq 0 \\ \hline \end{array}$$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$.
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline \text{Anggota B} & 0 & 1 & 2 & 3 & 6 & 7 & 8 & 9 \\ \hline \text{Syarat kemunculan} & \geq 1 & \geq 0 & \geq 0 & \geq 0 & \geq 0 & \geq 0 & \geq 1 & \geq 0 \\ \hline \end{array}$$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 \cdot 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 \cdot 7^n + 6^n, n \geq 0.$
Jawaban c)
Tabel berikut menyatakan syarat kemunculan angka pada $B$.
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline \text{Anggota B} & 0 & 1 & 2 & 3 & 6 & 7 & 8 & 9 \\ \hline \text{Syarat kemunculan} & \text{genap} & \geq 0 & \geq 0 & \geq 0 & \geq 0 & \geq 0 & \geq 0 & \geq 0 \\ \hline \end{array}$$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$.
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline \text{Anggota B} & 0 & 1 & 2 & 3 & 6 & 7 & 8 & 9 \\ \hline \text{Syarat kemunculan} & \text{ganjil} & \geq 0 & \geq 0 & \geq 0 & \geq 0 & \geq 0 & \geq 0 & \geq 0 \\ \hline \end{array}$$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]