Pembahasan Tugas Matematika Diskrit Terkait Aturan Perkalian dan Aturan Penjumlahan

 Oke pada kesempatan kali ini kita akan membahas tentang tugas matematika diskrit. Bab yang kita bahas pada kesempatan hari ini adalah terkait aturan perkalian dan aturan penjumlahan. Dimana, aturan perkalian dan aturan penjumlahan merupakan prinsip dasar dalam kaidah pencacahan. Sebelum ke pembahasannya kita akan mereview dulu nih tentang aturan perkalian dan aturan penjumlahan.

Aturan perkalian yaitu jika kejadian pertama dapat dikerjakan dalam $m$ cara dan diikuti oleh kejadian kedua dapat dikerjakan dalam $n$ cara, maka kejadian pertama dan kejadian kedua tersebut secara bersama sama dapat terjadi dalam $m\times n$ cara.

Aturan penjumlahan yaitu jika kejadian pertama dapat dikerjakan dalam $m$ cara dan kejadian kedua secara terpisah dapat dikerjakan dalam $n$ cara, maka kejadian pertama atau kejadian kedua tersebut dapat terjadi dalam $m+n$ cara.

Oke kita langsung saja ke soal dan pembahasannya. Berikut adalah soal Tugas Matematika Diskrit terkait Aturan Perkalian dan Aturan Penjumlahan.

1. a. Jika $m$ koin dan $n$ dadu dilempar bersama, berapakah banyaknya hasil yang mungkin muncul.

    b. Sebuah tim yang terdiri dari ketua, wakil ketua, sekretaris, dan bendahara dipilih dari $25$ mahasiswa. Berapakah banyak tim yang mungkin terbentuk?

    c. Sebuah plat nomor mobil terdiri dari sebuah huruf, diikuti lima angka, dan diakhiri tiga huruf. Ada berapakah plat nomor mobil yang dapat dibentuk? Jika disyaratkan tidak boleh ada huruf yang sama dan tidak ada angka yang sama, ada berapakah plat nomor yang bisa dibentuk?

    d. Barisan binair adalah barisan yang terdiri dari angka "0" dan angka "1"; Barisan ternair adalah barisan yang terdiri dari angka "0","1","2". Panjang barisan adalah banyaknya angka dalam barisan tersebut. Jika panjang barisan tersebut $n$, maka barisan tersebut barisan $n$-angka. Ada berapakah barisan binair $n$-angka? Ada berapakah barisan ternair $n$-angka?

2. a. Tentukan banyak polindrom panjang $k$, yang dibentuk dari $n$ objek berbeda

    b. Tentukan banyak polindrom panjang $k$ yang dibentuk dari $n$ objek berbeda sedemikian hingga setiap objek muncul maksimum dua kali dalam polindrom.

3. Misalkan $A=\{x_1,x_2,x_3,\cdots,x_k\}$ dan $B=\{y_1,y_2,y_3,\cdots,y_n\}$. Gunakan aturan perkalian untuk membuktikan bahwa

    a. Banyak fungsi yang mungkin dari $A$ ke $B$ adalah $n^k$

    b. Banyak fungsi 1-1 yang mungkin dari $A$ ke $B$ adalah

        $f(n,k)=\begin{cases}0 ,& \text{Jika } k>n\\ n(n-1)\cdots (n-k+1) ,& \text{Jika } k\leq n\end{cases}$

Pembahasan

1. a. Sebagaimana kita tahu bahwa banyaknya mata koin yaitu $2$ (angka dan gambar) sedangkan banyaknya sisi dadu itu ada $6$ (1,2,3,4,5,6). Maka dari $m$ koin masing masing kejadian yang mungkin ada sebanyak $2$ dari setiap pelemparan satu koin, sehingga dapat disimpulkan karena ada $m$ koin dengan aturan perkalian maka didapat kemungkinan sebanyak $2\times 2\times 2\times 2\cdots$ sebanyak $m$ kali yaitu $2^m$. Sedangkan untuk dadu yaitu dari $n$ dadu masing masing kejadian yang mungkin ada sebanyak $6$ dari setiap pelemparan satu dadu, sehingga dengan cara yang sama didapat banyak kemungkinan kejadiannya adalah $6^n$. Dengan demikian dapat disimpulkan banyaknya hasil yang mungkin dari pelemparan $m$ koin dan $n$ dadu adalah sebanyak $2^m6^n$

    b. Diketahui banyaknya mahasiswa $25$. Maka banyak mahasiswa yang mungkin untuk dijadikan sebagai ketua ada $25$ kemungkinan, kemudian dilanjut karena satu orang sudah terpilih maka banyak mahasiswa yang mungkin untuk dijadikan sebagai wakil ketua ada $25-1$ kemungkinan, kemudian dilanjut dengan pemilihan sekretaris yaitu $25-1-1$ kemungkinan (1 sudah dipilih sebagai ketua, 1 sudah dipilih sebagai wakil ketua), kemudian dilanjut pemilihan bendahara yaitu $25-1-1-1$ kemungkinan (1 sudah dipilih sebagai ketua, 1 sudah dipilih sebagai wakil ketua, 1 sudah dipilih sebagai sekretaris). Jadi, menurut aturan perkalian maka banyak tim yang akan terbentuk adalah $25\times 24\times 23\times 22=303600$

    c. Sebagaimana kita ketahui bahwa banyaknya huruf ada sebanyak $26$ dan banyaknya angka ada sebanyak $10$. Maka banyak kemugkinan pemilihan satu huruf adalah $26$. Lalu dilanjutkan banyak pemilihan empat lima yaitu masing masing terdapat $10$ kejadian yang mungkin. Lalu dilanjutkan lagi dengan pemilihan tiga huruf yang masing masing terdapat $26$ kejadian yang mungkin. Jadi kita peroleh banyak plat mobil yang dapat dibentuk adalah $26\times 10^5\times 26^3$. Kemudian untuk kasus jika disyaratkan tidak boleh ada huruf yang sama dan tidak ada angka yang sama, karena hurufnya tidak boleh ada yang sama dan kelima angka tsb harus berbeda maka banyak plat nomor yang dapat dibentuk adalah $26\times 10\times 9\times 8\times 7\times 6\times 25\times 24\times 23$

    d. Banyaknya angka binair adalah 2 yaitu "0" dan "1". Jadi banyaknya barisan binair $n$-angka adalah $2\times 2\times 2\times 2\cdots \times 2$ sebanyak n atau $2^n$. Dengan cara serupa didapat banyaknya barisan ternair $n$-angka adalah $3^n$

2. a.  Akan dibagi menjadi dua kasus yaitu :

-) Jika $k$ genap

Objek pada urutan pertama haruslah sama dengan objek pada urutan ke $k$

Objek pada urutan kedua haruslah sama dengan objek pada urutan ke $k-1$

dst.

Objek pada urutan ke-$\frac{k}{2}$ haaruslah sama dengan objek pada urutan ke $\frac{k}{2}+1$

Jadi dengan menggunakan aturan perkalian didapat bahwa banyak polindrom panjang $k$ yang dibentuk dari $n$ objek berbeda dimana $k$ genap adalah $n\times n\times n\cdots \times n$ sebanyak $\frac{k}{2}$ atau sama dengan $n^{\frac{k}{2}}$

-) Jika $k$ ganjil

Objek pada urutan pertama haruslah sama dengan objek pada urutan ke $k$

Objek pada urutan kedua haruslah sama dengan objek pada urutan ke $k-1$

dst.

Objek pada urutan ke-$\frac{k-1}{2}$ haaruslah sama dengan objek pada urutan ke $\frac{k+1}{2}+1$

Objek pada urutan ke $\frac{k+1}{2}$ berada tepat di tengah

Jadi dengan menggunakan aturan perkalian didapat bahwa banyak polindrom panjang $k$ yang dibentuk dari $n$ objek berbeda dimana $k$ ganjil adalah $n\times n\times n\cdots \times n$ sebanyak $\frac{k+1}{2}$ atau sama dengan $n^{\frac{k+1}{2}}$

    b. Akan dibagi menjadi dua kasus yaitu :

-) Jika $k$ genap

Objek pada urutan pertama haruslah sama dengan objek pada urutan ke $k$

Objek pada urutan kedua haruslah sama dengan objek pada urutan ke $k-1$

dst.

Objek pada urutan ke-$\frac{k}{2}$ haaruslah sama dengan objek pada urutan ke $\frac{k}{2}+1$

Karena setiap objek maksimum muncul dua kali dalam polindrom, hal ini terjadi jika objek pertama hingga objek ke-$\frac{k}{2}$ semuanya berbeda. Jadi untuk kasus ini didapat banyak polindrom yang bisa dibentuk dari $n$ objek berbeda untuk kasus ini adalah

$f(n,k)=\begin{cases}0 ,& \text{jika } n<\frac{k}{2}\\ n(n-1)\cdots (n-\frac{k+2}{2}) ,& \text{jika } n\geq\frac{k}{2}\end{cases}$

-) Jika $k$ ganjil

Objek pada urutan pertama haruslah sama dengan objek pada urutan ke $k$

Objek pada urutan kedua haruslah sama dengan objek pada urutan ke $k-1$

dst.

Objek pada urutan ke-$\frac{k-1}{2}$ haaruslah sama dengan objek pada urutan ke $\frac{k+1}{2}+1$

Objek pada urutan ke $\frac{k+1}{2}$ berada tepat di tengah

Karena setiap objek maksimum muncul dua kali dalam polindrom, hal ini terjadi jika objek pertama hingga objek ke-$\frac{k+1}{2}$ semuanya berbeda. Jadi untuk kasus ini didapat banyak polindrom yang bisa dibentuk dari $n$ objek berbeda untuk kasus ini adalah

$f(n,k)=\begin{cases}0 ,& \text{jika } n<\frac{k+1}{2}\\ n(n-1)\cdots (n-\frac{k-1}{2}) ,& \text{jika } n\geq\frac{k+1}{2}\end{cases}$

3. a. Karena $\mid A\mid=k$ maka bisa kita pecah menjadi $k$ kasus yang saling bebas namakan $T_1,T_2,T_3,\cdots T_k$

$T_1$ memasangkan $x_1\in A$ ke tepat satu anggota $B$, $T_1$ dapat dilakukan dengan $n$ cara, karena $\mid B\mid=n$

$T_2$ memasangkan $x_2\in A$ ke tepat satu anggota $B$, $T_2$ dapat dilakukan dengan $n$ cara juga, karena $\mid B\mid=n$. Begitu seterusnya hingga $T_k$ juga dapat dilakukan dengan $n$ cara.

Berdasarkan aturan perkalian $T_1\wedge T_2\wedge T_3\wedge\cdots \wedge T_k$ dapat dikerjakan dalah $n\times n\times n\cdots \times n=n^k$

    b. Jelas jika $k>n$ maka akan ada $x_i\in A$ sehingga tidak dapat dipasangkan dengan $y_i\in B$ maka banyak untuk kasus ini adalah 0. Jika $k\leq n$, karena $\mid A\mid=k$ maka bisa kita pecah menjadi $k$ kasus yang saling bebas namakan $T_1,T_2,T_3,\cdots T_k$

$T_1$ memasangkan $x_1\in A$ ke tepat satu anggota $B$, $T_1$ dapat dilakukan dengan $n$ cara, karena $\mid B\mid=n$

$T_2$ memasangkan $x_2\in A$ ke tepat satu anggota $B$ sedemikian sehingga $f(x_2)\neq f(x_1)$, $T_2$ dapat dilakukan dengan $n-1$ cara.

$T_3$ memasangkan $x_3\in A$ ke tepat satu anggota $B$ sedemikian sehingga $f(x_3)\neq f(x_2)\neq f(x_1)$, $T_3$ dapat dilakukan dengan $n-2$ cara.

Begitu seterusnya hingga

$T_k$ memasangkan $x_k\in A$ ke tepat satu anggota $B$ sedemikian sehingga $f(x_k)\neq f(x_{k-1})\neq\cdots\neq f(x_2)\neq f(x_1)$, $T_3$ dapat dilakukan dengan $n-(k-1)$ cara.

Berdasarkan aturan perkalian $T_1\wedge T_2\wedge T_3\wedge\cdots \wedge T_k$ dapat dikerjakan dalah $n\times (n-1)\cdots \times (n-k+1)$

Jadi terbukti bahwa banyak fungsi 1-1 yang mungkin dari $A$ ke $B$ adalah

$f(n,k)=\begin{cases}0 ,& \text{jika } k>n\\ n(n-1)\cdots (n-k+1) ,& \text{jika } k\leq n\end{cases}$

Untuk tugas matematika diskrit selanjutnya kalian bisa baca disini.