Pembahasan Matematika Diskrit Tentang Permutasi Linear, Permutasi Siklik, Kombinasi Tanpa Atau Dengan Pengulangan

Matematika Diskrit adalah salah satu cabang ilmu matematika yang mempelajari objek-objek diskrit. Salah satu materi yang diajarkan di dalamnya yakni tentang Permutasi linear, Permutasi siklik, Kombinasi tanpa atau dengan pengulangan. Pada postingan ini akan dibahas tugas matematika diskrit tentang Permutasi linear, Permutasi siklik, Kombinasi tanpa atau dengan pengulangan. Berikut pembahasannya.

Permutasi linear adalah susunan ulang dari elemen-elemen dalam himpunan sedemikian rupa sehingga tidak ada elemen yang berulang, dan setiap elemen hanya muncul satu kali dalam susunan baru. Jadi, dalam permutasi linear, setiap elemen memiliki posisi yang unik dalam susunan tersebut. Contoh: Untuk himpunan $\{A, B, C\}$, beberapa permutasi linearnya adalah $ABC$, $BCA$, dan $CAB$.

Permutasi siklik melibatkan rotasi elemen dalam himpunan. Ini berarti elemen-elemen dipindahkan ke posisi berikutnya dalam susunan, dan setelah perpindahan tertentu, elemen-elemen akan kembali ke posisi awal. Permutasi siklik dapat digambarkan dalam bentuk siklus, di mana elemen-elemen yang berpindah saling berhubungan dalam suatu siklus. Contoh: Untuk himpunan $\{A, B, C\}$, beberapa permutasi sikliknya direpresentasikan sebagai $(ABC)$ dan $(ACB)$. Perhatikan bahwa $(BCA)$ dan $(CAB)$ dianggap sama dengan $(ABC)$ sedangkan $(BAC)$ dan $(CBA)$ dianggap sama dengan $(ACB)$.

Kombinasi tanpa pengulangan terjadi ketika kita memilih sejumlah elemen dari suatu himpunan tanpa memperhatikan urutan elemen yang dipilih. Dalam kombinasi ini, setiap elemen hanya dapat dipilih sekali. Contoh: Dalam himpunan $\{A, B, C\}$, beberapa kombinasi tanpa pengulangan dari 2 elemen adalah $AB$, $AC$, dan $BC$. Perhatikan bahwa $BA$, $CA$, dan $CB$ dianggap sama dengan $AB$, $AC$, dan $BC$ karena dalam kombinasi ini urutan tidak diperhatikan.

Kombinasi dengan pengulangan memungkinkan kita memilih sejumlah elemen dari suatu himpunan tanpa memperhatikan urutan dan dengan memperbolehkan pengambilan elemen yang sama lebih dari sekali. Contoh: Dalam himpunan $\{A, B, C\}$, beberapa kombinasi dengan pengulangan dari 2 elemen adalah $AA$, $AB$, $AC$, $BB$, $BC$, dan $CC$. Di sini, kita dapat memilih elemen yang sama lebih dari sekali, seperti dalam kasus $AA$.

Oke langsung saja ke pembahasan soalnya.

1. a. Dalam sebuah keranjang terdapat 20 apel merah dan 10 apel hijau. Berapakah peluang dari 15 apel yang diambil secara acak (tanpa pengembalian) terdapat paling sedikit 7 apel hijau?

b. Ada berapakah matriks $m \times n$ yang entri-entrinya 0 atau 1?

c. Ada berapa barisan binair 10-angka yang memuat tepat lima angka “1”?

2. a. Misalkan $S$ adalah sebuah barisan n elemen sedemikian hingga dari $n$ elemen tersebut terdapat: $n_1$ elemen tipe-1 identik, $n_2$ elemen tipe-2 identik, … , $n_k$ elemen tipe-k identik. Tunjukkan bahwa banyak barisan $S$ yang demikian adalah $\frac{n!}{n_1!n_2!\cdots n_k!}$

b. Jika huruf-huruf dalam kata “MATEMATIKA” dipermutasikan, ada berapa permutasi yang mungkin?

3. a. Misalkan terdapat tiga kotak berbeda ( merah, biru, hijau) dan setiap kotak berisi minimal 10 bola.(i) Ada berapa cara berbeda memilih 10 bola? (ii) Ada berapa cara memilih 10 bola, sedemikian hingga dari setiap kotak terpilih minimal satu bola?

b. Ada berapa cara membagikan 10 buku matematika yang identik kepada tiga orang mahasiswa Andre, Rino, dan Johan?

4. Jika $n$ bilangan bulat non negatif, dengan teorema binomial tunjukan bahwa :

a. $\binom{n}{0} +\binom{n}{1}+\cdots +\binom{n}{n}=2^n$

b. $\binom{n}{0} -\binom{n}{1}+\cdots +(-1)^n\binom{n}{n}=0$

5. Diberikan himpunan $A=\{x_1,x_2,\cdots ,x_n\}$. Buktikan banyak himpunan bagian dari $A$ adalah $2^n$

6. Diberikan kisi-kisi persegi $OPQR$ pada bidang koordinat cartesius dengan $O(0,0)$, $P(10,0)$, $Q(10,10)$, dan $R(0,10)$. Titik $S(4,4)$, $T(7,7)$, dan $U(6,8)$. Diperkenankan bergerak "ke kanan" dan ke atas" saja pada kisi-kisi. Tentukanlah:

a. Banyak lintasan terpendek dari titik $O$ ke titik $Q$ melalui titik $S$ tetapi tidak melalui titik $U$

b. Banyak lintasan tak cantik dari $O$ ke $Q$

c. Banyak lintasan cantik dari $O$ ke $Q$ melalui titik $S$ dan titik $T$

d. Banyak lintasan cantik dari $O$ ke $Q$ melalui titik $S$ atau titik $T$

e. Banyak lintasan cantik dari $O$ ke $Q$ tidak melalui titik $S$ dan tidak melalui titik $T$

Jawaban untuk soal di atas dapat di download disini.