Pembahasan Soal 3 Permutasi dan Kombinasi

File Tayangan

Soal: Tentukan banyaknya solusi bulat non negatif dari

    \[x + y + z = 12\]

dengan kendala 0\leq x \leq 4, 0\leq y \leq 5, 0\leq z \leq 6.

Pembahasan:

Untuk x,y,z \geq 0, menurut Stars and Bars theorem, diperoleh banyaknya solusi, yaitu

    \[|S| =\binom{3+12-1}{12} = \binom{14}{12} = 91 .\]

Didefinisikan

    \begin{align*} \begin{cases} A = \{x\in\mathbb{Z}|x+y+z=12,x\geq 5\} \\ B = \{ y\in\mathbb{Z}|x+y+z=12, y\geq 6\} \\ C = \{z\in\mathbb{Z}|x+y+z=12,z\geq 7\} \\ \end{cases} \end{align*}

Untuk memperoleh himpunan 0\leq x \leq 4, 0\leq y \leq 5, 0\leq z \leq 6, yaitu irisan dari negasi ketiga himpunan tersebut. Dinotasikan

    \[|A^{c}\cap B^{c} \cap C^{c}| .\]

Dengan Prinsip Inklusi-Eksklusi, akan ditentukan banyak solusinya dari |A^{c}\cap B^{c} \cap C^{c}|.
Diperoleh,

    \[|A^{c} \cap B^{c} \cap C^{c}| = |S| - |A| - |B| - |C| + |A \cap B| + |A \cap C| + |B \cap C | - | A \cap B \cap C|.\]

Selanjutnya, akan dicari:

  • Solusi x + y +z = 12, dengan kendala

        \[\begin{array}{cc} x \geq 5 \\ (x-5) \geq 0 \\ x_1 \geq 0, \text{untuk} \ x_1 = x-5 \end{array}\]

    Maka,

        \begin{align*} x + y + z &= 12 \\ (x - 5) + y + z &= 12 - 5 \\ x_1 + y + z &= 7 \\ \end{align*}

    Untuk x_1,y,z \geq 0, menurut Stars and Bars Theorem, diperoleh banyaknya solusi yaitu

        \[|A| = \binom{7+3-1}{7} = \binom{9}{7} = 36.\]

  • Solusi x + y +z = 12, dengan kendala

        \[\begin{array}{cc} y \geq 6 \\ (y-6) \geq 0 \\ y_1 \geq 0, \text{untuk} \ y_1 = y-6 \end{array}\]

    Maka,

        \begin{align*} x + y + z &= 12 \\ x + (y - 6) + z &= 12 - 6 \\ x + y_1 + z &= 6 \\ \end{align*}

    Untuk x,y_1,z \geq 0, menurut Stars and Bars Theorem, diperoleh banyaknya solusi yaitu

        \[|B| = \binom{6+3-1}{6} = \binom{8}{6} = 28.\]

  • Solusi x + y +z = 12, dengan kendala

        \[\begin{array}{cc} z \geq 7 \\ (z-7) \geq 0 \\ z_1 \geq 0, \text{untuk} \ z_1 = z-7 \end{array}\]

    Maka,

        \begin{align*} x + y + z &= 12 \\ x + y + (z - 7) &= 12 - 7 \\ x + y + z_1 &= 5 \\ \end{align*}

    Untuk x,y,z_1 \geq 0, menurut Stars and Bars Theorem, diperoleh banyaknya solusi yaitu

        \[|C| = \binom{5+3-1}{5} = \binom{7}{5} = 21.\]

  • Solusi x + y +z = 12, dengan kendala

        \[\begin{array}{cc} x \geq 5, y \geq 6 \\ (x-5) \geq 0, (y-6) \geq 0 \\ x_1 \geq 0,y_1 \geq 0, \text{untuk} \ x_1 = x-5 , y_1 = x-6 \end{array}\]

    Maka,

        \begin{align*} x + y + z &= 12 \\ (x - 5) + (y - 6) + z &= 12 - 5 -6\\ x_1 + y_1 + z &= 1 \\ \end{align*}

    Untuk x_1,y_1,z \geq 0, menurut Stars and Bars Theorem, diperoleh banyaknya solusi yaitu

        \[|A \cap B| = \binom{1+3-1}{1} = \binom{3}{1} = 3.\]

  • Solusi x + y +z = 12, dengan kendala

        \[\begin{array}{cc} x \geq 5, z \geq 7 \\ (x-5) \geq 0, (z-7) \geq 0 \\ x_1 \geq 0,z_1 \geq 0, \text{untuk} \ x_1 = x-5 , z_1 = z-7 \end{array}\]

    Maka,

        \begin{align*} x + y + z &= 12 \\ (x - 5) + y + (z - 7) &= 12 - 5 - 7 \\ x_1 + y + z_1 &= 0 \\ \end{align*}

    Untuk x_1,y,z_1 \geq 0, menurut Stars and Bars Theorem, diperoleh banyaknya solusi yaitu

        \[|A \cap C| = \binom{0+3-1}{0} = \binom{2}{0} = 1.\]

  • Solusi x + y +z = 12, dengan kendala

        \[\begin{array}{cc} y \geq 6, z \geq 7 \\ (y-6) \geq 0, (z-7) \geq 0 \\ y_1 \geq 0,z_1 \geq 0, \text{untuk} \ y_1 = y-6 , z_1 = z-7 \end{array}\]

    Maka,

        \begin{align*} x + y + z &= 12 \\ x + (y - 6) + (z - 7) &= 12 - 6 - 7 \\ x + y_1 + z_1 &= -1 \\ \end{align*}

    Diperhatikan bahwa, \forall x,y_1,z_1 \geq 0, berlaku x + y_1 + z_1 \geq 0. Sedangkan, pernyataan awal akan ditentukan banyaknya solusi x + y_1 + z_1 = -1, dengan x , y_1 , z_1 \geq 0. Akibatnya, diperoleh -1 \geq 0 , kontradiksi dengan pernyataan awal dimana \forall x,y_1,z_1 \geq 0, berlaku x + y_1 + z_1 \geq 0. Dengan demikian, banyaknya solusi
    x + y + z = 12 dengan kendala y \geq 6 , z \geq 7 yaitu

        \[|B \cap C |=0.\]

  • Solusi x + y +z = 12, dengan kendala

        \[\begin{array}{cc} x\geq 5, y \geq 6, z \geq 7 \\ (x-5)\geq 0, (y-6) \geq 0, (z-7) \geq 0 \\ x_1\geq 0, y_1 \geq 0,z_1 \geq 0, \text{ untuk } \ x_1 = x - 5, y_1 = y-6 , z_1 = z-7 \end{array}\]

    Maka,

        \begin{align*} x + y + z &= 12 \\ (x - 5) + (y - 6) + (z - 7) &= 12 - 5 - 6 - 7\\ x_1 + y_1 + z_1 &= -6 \\ \end{align*}

    Diperhatikan bahwa, \forall x,y_1,z_1 \geq 0 berlaku x_1 + y_1 + z_1 \geq 0. Sedangkan, pernyataan awal akan ditentukan banyaknya solusi x_1 + y_1 + z_1 = -6, dengan x_1 , y_1 , z_1 \geq 0 .
    Akibatnya, diperoleh -6 \geq 0 , kontradiksi dengan pernyataan awal dimana \forall x_1,y_1,z_1 \geq 0, berlaku x_1 + y_1 + z_1 \geq 0.
    Dengan demikian, banyaknya penyelesaian
    x + y + z = 12 dengan kendala x\geq 5, y \geq 6 , z \geq 7, yaitu

        \[|A \cap B \cap C|=0.\]

Dengan menggunakan Prinsip Inklusi-Eksklusi, diperoleh

    \begin{align*} |A^{c} \cap B^{c} \cap C^{c}| &= |S| - |A| - |B| - |C| + |A \cap B| + |A \cap C| + |B \cap C | - | A \cap B \cap C| \\ &= 91-36-28-21+1+3+0-0 \\ &= 10 \end{align*}

Maka, banyaknya solusi dari x + y + z = 12 dengan kendala 0\leq x \leq 4, 0\leq y \leq 5, 0\leq z \leq 6, yaitu sebanyak 10 solusi unik.

Jika menghimpun secara manual untuk penyelesaian persamaan

    \[x + y + z = 12\]

yang memenuhi kendala
0 \leq x \leq 4, 0\leq y \leq 5, dan 0\leq z \leq 6.
Diperoleh himpunan penyelesaian nya sebagai berikut :

    \[{(1,5,6),(2,4,6),(2,5,5),(3,3,6),(3,4,5),(3,5,4),(4,2,6),(4,3,5),(4,4,4),(4,5,3)}.\]

Jadi diperoleh ada 10 solusi unik.

 

Credit: Fadhlan Zhaahiran

Leave A Comment

Alamat email Anda tidak akan dipublikasikan.

*