|
Istilah '''kombinasi''' dalam [[matematika kombinatorik]] berarti [[himpunan]] objek yang tidak mementingkan urutan. Kombinasi berbeda dengan [[permutasi]] yang mementingkan urutan objek. Perkataan '''kombinasi''' memiliki sebutan lainnya yaitu '''gabungan''', '''padu-padan''' atau '''kepadupadanan'''
== Definisi ==
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
== Membangkitkan Kombinasi ==
<!--===Fungsi Pembangkit Kombinasi===
Jika diberikan fungsi:
:<math>f(S) = \prod_{s \in S}^{ } (x + s)</math>
dapat digunakan untuk membangkitkan kombinasi dari himpunan ''S''.
Sebagai contoh, jika <math>S = \{a, b, c\}</math>:
:<math>f(\{a, b, c\}) = \prod_{s \in \{a, b, c\}}^{ } (x + s)</math>
::<math>= (x + a)(x + b)(x + c)</math>
::<math>= x^3 + (a + b + c)x^2 + (ab + ac + bc)x + abc</math>
Menggunakan fungsi pembangkit ini, setiap koefisien <math>x^k</math> akan menunjukkan kombinasi ''k'' dari himpunan S (berupa perkalian).
Jika yang diinginkan bukan daftar kombinasinya melainkan banyaknya kombinasi, maka dapat digunakan <math>a = b = c = 1</math>. Sehingga:
:<math>f(S) = (x + 1)(x + 1)(x + 1)</math>
::<math>= (x + 1)^3</math>
::<math>= x^3 + 3x^2 + 3x + 1</math>
Fungsi pembangkit untuk banyaknya kombinasi juga dapat dinyatakan sebagai:
:<math>f(n) = (x + 1)^n</math>
Yang merupakan bentuk '''binomial''', dengan koefisien <math>x^k</math> akan menunjukkan <math>C_k^n</math>.
===Menambah Himpunan Kuasa secara rekursif===
Karena himpunan seluruh kombinasi dari ''S'' adalah sama dengan himpunan kuasa dari ''S'', yaitu <math>\mathcal{P}(S)</math>, maka kita dapat membentuk seluruh kombinasi dari {''a, b, c, d''} dengan cara yang ditunjukkan dalam langkah-langkah berikut ini. Untuk membedakan, daftar himpunan bagian yang baru terbentuk dalam setiap langkah dicetak tebal, dan setiap elemen diberi indeks ''n'', ''k'' sesuai kombinasi ke ''k'' dari ''n'' unsur.
* Mulai dari sebuah himpunan kosong { }, maka <math>\mathcal{P}(\{ \})</math> berisi:
C(0, 0) = { }
* Dengan menambah setiap elemen <math>\mathcal(P)(\{ \})</math>, dan menggabungkan dengan himpunan kuasa semula, maka terbentuklah <math>\mathcal(P)(\{ a \})</math>:
C(0, 0) = { }
C(1, 0) = '''{ a }''' <- didapat dari 0 + { a }
* Kemudian tambah setiap elemen <math>\mathcal(P)(\{ a \})</math>, dan menggabungkan dengan himpunan kuasa sebelumnya, terbentuklah <math>\mathcal(P)(\{ a, b\})</math>:
C(0, 0) = { }
C(1, 0) = { a }
C(1, 1) = '''{ b }''' <- dari C(0, 0) + { b }
C(2, 0) = '''{ a, b }''' <- dari C(1, 0) + { b }
* Langkah berikutnya menghasilkan:
C(0, 0) = { }
C(1, 0) = { a }
C(1, 1) = { b }
C(2, 0) = { a, b }
C(1, 2) = '''{ c }''' <- dari 0 + { c }
C(2, 1) = '''{ a, c }''' <- dari 1 + { c }
C(2, 2) = '''{ b, c }''' <- dari 2 + { c }
C(0, 0) = '''{ a, b, c }''' <- dari 3 + { c }
* Kemudian:
0: { }
1: { a }
2: { b }
3: { a, b }
4: { c }
5: { a, c }
6: { b, c }
7: { a, b, c }
8: '''{ d }'''
9: '''{ a, d }'''
10: '''{ b, d }'''
11: '''{ a, b, d }'''
12: '''{ c, d }'''
13: '''{ a, c, d }'''
14: '''{ b, c, d }'''
15: '''{ a, b, c, d }'''-->
== Lihat pula ==
|
