Kombinasi yang mungkin. Elemen kombinatorik
Kombinasi adalah pemilihan elemen-elemen suatu himpunan berhingga yang tidak berurutan dengan bilangan tetap dan tanpa pengulangan elemen. Kombinasi yang berbeda harus berbeda setidaknya dalam satu elemen, dan urutan elemen tidak menjadi masalah. Misalnya, dari himpunan semua vokal huruf latin (AEIOU), Anda dapat membuat 10 kombinasi berbeda dari 3 huruf, membentuk kembar tiga tak berurutan berikut:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Menarik untuk dicatat bahwa dari lima huruf yang sama Anda juga bisa mendapatkan 10 kombinasi berbeda jika Anda menggabungkan 2 huruf sekaligus, sehingga menghasilkan pasangan tak berurutan berikut:
AE, AI, AO, AU, EI, EO, UE, IO, IU, OU.
Namun jika Anda menggabungkan huruf vokal latin yang sama sebanyak 4, Anda hanya akan mendapatkan 5 kombinasi berbeda berikut ini:
AEIO, AEIU, AIOU, EIOU, AEOU.
Secara umum, untuk menyatakan banyaknya kombinasi n elemen berbeda dari m elemen, digunakan simbolisme fungsional, indeks, atau vektor (Appel):
Apapun bentuk notasinya, banyaknya kombinasi n elemen dengan m elemen dapat ditentukan dengan menggunakan rumus perkalian dan faktorial berikut:
Sangat mudah untuk memeriksa bahwa hasil perhitungan menggunakan rumus ini sesuai dengan hasil contoh yang dibahas di atas dengan kombinasi vokal dalam huruf latin. Khususnya, dengan n=5 dan m=3, perhitungan menggunakan rumus ini akan memberikan hasil sebagai berikut:
Secara umum, rumus banyaknya kombinasi mempunyai arti kombinatorial dan berlaku untuk semua nilai bilangan bulat n dan m, sehingga n > m > 0. Jika m > n dan m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
Selain itu, penting untuk mengingat bilangan pembatas kombinasi berikut, yang dapat dengan mudah diperiksa dengan substitusi langsung ke dalam rumus perkalian dan faktorial:
Perlu diperhatikan juga bahwa rumus perkalian tetap valid meskipun n adalah bilangan real, selama m masih merupakan nilai bilangan bulat. Namun demikian, hasil perhitungan yang menggunakannya, dengan tetap menjaga validitas formal, kehilangan makna kombinatorialnya.
IDENTITAS KOMBINASI
Penggunaan praktis rumus perkalian dan faktorial untuk menentukan jumlah kombinasi nilai sembarang n dan m ternyata memiliki produktivitas yang rendah karena pertumbuhan eksponensial produk faktorial pembilang dan penyebutnya. Bahkan untuk nilai n dan m yang relatif kecil, produk ini sering kali melebihi kemampuan merepresentasikan bilangan bulat dalam sistem komputasi dan perangkat lunak modern. Selain itu, nilainya ternyata jauh lebih besar daripada nilai yang dihasilkan dari jumlah kombinasi, yang mungkin relatif kecil. Misalnya, jumlah kombinasi elemen n=10 kali m=8 hanya 45. Namun, untuk mencari nilai ini menggunakan rumus faktorial, Anda harus menghitung terlebih dahulu nilai 10 yang jauh lebih besar! di pembilang dan 8! dalam penyebut:
Untuk menghilangkan operasi yang memakan waktu dalam memproses jumlah besar, untuk menentukan jumlah kombinasi, Anda dapat menggunakan berbagai hubungan perulangan, yang langsung mengikuti rumus perkalian dan faktorial. Secara khusus, relasi perulangan berikut mengikuti rumus perkalian, yang memungkinkan kita mengambil rasio indeksnya di luar tanda jumlah kombinasi:
Terakhir, menjaga konstanta subskrip menghasilkan hubungan perulangan berikut, yang mudah diperoleh dari rumus faktorial untuk jumlah kombinasi:
Setelah transformasi dasar, tiga relasi perulangan yang dihasilkan dapat direpresentasikan dalam bentuk berikut:
Jika sekarang kita menjumlahkan ruas kiri dan kanan dari 2 rumus pertama dan mengurangi hasilnya sebesar n, kita mendapatkan hubungan perulangan yang penting, yang disebut identitas penjumlahan bilangan kombinasi:
Identitas penjumlahan memberikan aturan perulangan dasar untuk menentukan jumlah kombinasi secara efisien untuk nilai n dan m yang besar, karena identitas penjumlahan memungkinkan operasi perkalian dalam perkalian faktorial diganti dengan operasi penjumlahan yang lebih sederhana, dan untuk jumlah kombinasi yang lebih kecil. Secara khusus, dengan menggunakan identitas penjumlahan, sekarang mudah untuk menentukan jumlah kombinasi elemen n=10 kali m=8, yang telah dibahas di atas, dengan melakukan urutan transformasi berulang berikut:
Selain itu, beberapa relasi yang berguna untuk menghitung jumlah hingga dapat diturunkan dari identitas penjumlahan, khususnya rumus penjumlahan dengan subskrip, yang berbentuk sebagai berikut:
Relasi ini diperoleh jika dalam identitas penjumlahan kita memperluas perulangan sepanjang suku dengan superskrip terbesar sedangkan subskripnya lebih besar dari 0. Contoh numerik berikut mengilustrasikan proses transformasi berulang ini:
Rumus penjumlahan subskrip sering digunakan untuk menghitung jumlah pangkat bilangan asli. Khususnya, dengan asumsi m=1, dengan menggunakan rumus ini, mudah untuk mencari jumlah n bilangan pertama deret natural:
Versi lain yang berguna dari rumus penjumlahan dapat diperoleh dengan memperluas pengulangan identitas penjumlahan sepanjang suku dengan superskrip terkecil. Contoh numerik berikut mengilustrasikan versi transformasi berulang ini:
Dalam kasus umum, sebagai hasil dari transformasi tersebut, diperoleh jumlah jumlah kombinasi, yang kedua indeksnya berbeda satu dari suku-suku tetangganya, dan selisih indeksnya tetap konstan (dalam contoh yang dipertimbangkan, adalah juga sama dengan satu). Dengan demikian, kita memperoleh rumus penjumlahan berikut untuk kedua indeks angka kombinasi:
Selain hubungan perulangan dan rumus penjumlahan yang dibahas di atas, banyak identitas berguna lainnya untuk bilangan kombinasi telah diperoleh dalam analisis kombinatorial. Yang paling penting di antara mereka adalah identitas simetri, yang terlihat seperti ini:
Keabsahan identitas simetri dapat dibuktikan pada contoh berikut dengan membandingkan banyaknya kombinasi 5 unsur dengan 2 dan dengan (5 2) = 3:
Identitas simetri mempunyai arti kombinatorial yang jelas, karena dengan menentukan jumlah pilihan untuk memilih m elemen dari n elemen, ia secara bersamaan menentukan jumlah kombinasi dari sisa (nm) elemen yang tidak dipilih. Simetri yang ditunjukkan segera diperoleh dengan mengganti m dengan (nm) dalam rumus faktorial banyaknya kombinasi:
Bilangan dan identitas kombinasi banyak digunakan dalam berbagai bidang matematika komputasi modern. Namun, penerapannya yang paling populer berkaitan dengan binomial Newton dan segitiga Pascal.
TEOREMA BINOMIAL
Untuk melakukan berbagai transformasi dan perhitungan matematis, penting untuk dapat merepresentasikan pangkat alami apa pun dari binomial aljabar (binomial) dalam bentuk polinomial. Untuk pangkat kecil, polinomial yang diinginkan dapat diperoleh dengan mudah dengan mengalikan binomial secara langsung. Secara khusus, rumus kuadrat dan pangkat tiga dari jumlah dua suku berikut ini telah diketahui dengan baik dari mata pelajaran matematika dasar:
Dalam kasus umum, untuk derajat sembarang n suatu binomial, representasi yang diperlukan dalam bentuk polinomial disediakan oleh teorema binomial Newton, yang menyatakan persamaan berikut ini benar:
Persamaan ini biasa disebut binomial Newton. Polinomial di ruas kanannya dibentuk oleh jumlah hasil kali n suku X dan Y dari binomial di ruas kiri, dan koefisien di depannya disebut binomial dan sama dengan banyaknya kombinasi dengan indeks, yaitu diperoleh dari kekuatan mereka. Mengingat popularitas rumus binomial Newton dalam analisis kombinatorial, istilah koefisien binomial dan jumlah kombinasi umumnya dianggap sama.
Tentu saja, rumus jumlah kuadrat dan pangkat tiga adalah kasus khusus dari teorema binomial untuk n=2 dan n=3. Untuk menangani derajat yang lebih tinggi (n>3), rumus binomial Newton harus digunakan. Penerapannya untuk binomial derajat keempat (n=4) ditunjukkan pada contoh berikut:
Perlu dicatat bahwa rumus binomial telah dikenal bahkan sebelum Newton oleh ahli matematika abad pertengahan di Arab Timur dan Eropa Barat. Oleh karena itu, nama yang diterima secara umum tidaklah benar secara historis. Kelebihan Newton adalah ia menggeneralisasi rumus ini ke dalam kasus eksponen real sembarang r, yang dapat mengambil nilai rasional dan irasional positif atau negatif. Secara umum, rumus binomial Newton memiliki jumlah tak hingga di ruas kanan dan biasanya ditulis sebagai berikut:
Misalnya, dengan nilai pecahan positif dari eksponen r=1/2, dengan memperhitungkan nilai koefisien binomial, diperoleh ekspansi berikut:
Secara umum, rumus binomial Newton untuk eksponen apa pun adalah versi khusus rumus Maclaurin, yang memberikan perluasan fungsi sembarang menjadi deret pangkat. Newton menunjukkan bahwa untuk |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . Jika sekarang kita menetapkan Z=X/Y dan mengalikan ruas kiri dan kanan dengan Yn, kita mendapatkan versi rumus binomial Newton yang dibahas di atas.
Meskipun bersifat universal, teorema binomial mempertahankan makna kombinatorialnya hanya untuk pangkat bilangan bulat non-negatif dari binomial. Dalam hal ini, dapat digunakan untuk membuktikan beberapa identitas yang berguna untuk koefisien binomial. Secara khusus, rumus untuk menjumlahkan jumlah kombinasi berdasarkan subskrip dan kedua indeks telah dibahas di atas. Identitas penjumlahan superskrip yang hilang dapat dengan mudah diperoleh dari rumus binomial Newton dengan memasukkan X = Y = 1 atau Z = 1 ke dalamnya:
Identitas lain yang berguna menetapkan persamaan jumlah koefisien binomial dengan bilangan genap dan ganjil. Langsung didapat dari rumus binomial Newton jika X = 1 dan Y = 1 atau Z = 1:
Akhirnya, dari kedua identitas yang dipertimbangkan kita memperoleh identitas jumlah koefisien binomial dengan bilangan genap atau ganjil saja:
Berdasarkan identitas yang dipertimbangkan dan aturan berulang untuk menghilangkan indeks dari bawah tanda jumlah kombinasi, sejumlah hubungan menarik dapat diperoleh. Misalnya, jika dalam rumus penjumlahan superskrip kita mengganti n di mana pun dengan (n1) dan menghapus indeks di setiap suku, kita mendapatkan relasi berikut:
Dengan menggunakan teknik serupa dalam rumus jumlah koefisien binomial dengan bilangan genap dan ganjil, validitas dapat dibuktikan, misalnya, hubungan berikut:
Identitas lain yang berguna memungkinkan Anda dengan mudah menghitung jumlah produk dari koefisien binomial yang terletak secara simetris dari dua binomial dengan derajat sembarang n dan k menggunakan rumus Cauchy berikut:
Validitas rumus ini mengikuti persamaan koefisien yang diperlukan untuk setiap derajat m dari variabel Z di sisi kiri dan kanan dari hubungan identik berikut:
Dalam kasus khusus ketika n=k=m, dengan mempertimbangkan identitas simetri, diperoleh rumus yang lebih populer untuk jumlah kuadrat koefisien binomial:
Banyak identitas lain yang berguna untuk koefisien binomial dapat ditemukan dalam literatur luas tentang analisis kombinatorial. Namun, penerapan praktisnya yang paling terkenal terkait dengan segitiga Pascal.
SEGITIGA PASCAL
Segitiga aritmatika Pascal membentuk tabel numerik tak hingga yang terdiri dari koefisien binomial. Garis-garisnya diurutkan berdasarkan pangkat binomial dari atas ke bawah. Pada setiap baris, koefisien binomial disusun dalam urutan menaik dari superskrip bilangan kombinasi yang bersangkutan dari kiri ke kanan. Segitiga Pascal biasanya ditulis dalam bentuk sama kaki atau persegi panjang.
Yang lebih visual dan umum adalah format sama kaki, di mana koefisien binomial, terhuyung-huyung, membentuk segitiga sama kaki tak terhingga. Fragmen awalnya untuk binomial sampai derajat 4 (n=4) berbentuk sebagai berikut:
Secara umum, segitiga sama kaki Pascal memberikan aturan geometri yang mudah digunakan untuk menentukan koefisien binomial, yang didasarkan pada identitas penjumlahan dan simetri kombinasi bilangan. Secara khusus, menurut identitas penjumlahan, setiap koefisien binomial adalah jumlah dari dua koefisien pada baris sebelumnya yang paling dekat dengannya. Menurut identitas simetrinya, segitiga sama kaki Pascal adalah simetris terhadap garis baginya. Jadi, setiap garisnya merupakan palindrom numerik dari koefisien binomial. Fitur aljabar dan geometris yang ditunjukkan memungkinkan untuk dengan mudah memperluas segitiga sama kaki Pascal dan secara konsisten menemukan nilai koefisien binomial pangkat sewenang-wenang.
Namun, untuk mempelajari berbagai sifat segitiga Pascal, akan lebih mudah jika menggunakan format persegi panjang yang secara formal lebih ketat. Dalam format ini, koefisien binomial ditentukan oleh matriks segitiga bawah, yang membentuk segitiga siku-siku tak terhingga. Fragmen awal segitiga siku-siku Pascal untuk binomial sampai derajat 9 (n=9) berbentuk sebagai berikut:
Secara geometris, tabel persegi panjang tersebut diperoleh dengan mendeformasi segitiga sama kaki Pascal secara horizontal. Hasilnya, deret bilangan yang sejajar sisi segitiga sama kaki Pascal berubah menjadi vertikal dan diagonal segitiga siku-siku Pascal, dan garis horizontal kedua segitiga tersebut berimpit. Pada saat yang sama, aturan penjumlahan dan simetri koefisien binomial tetap berlaku, meskipun segitiga siku-siku Pascal kehilangan karakteristik simetri visual dari segitiga sama kaki. Untuk mengimbangi hal ini, akan lebih mudah untuk menganalisis secara formal berbagai sifat numerik dari koefisien binomial untuk garis horizontal, vertikal, dan diagonal segitiga siku-siku Pascal.
Memulai analisis horizontal segitiga siku-siku Pascal, mudah untuk melihat bahwa jumlah elemen-elemen dari setiap baris dengan angka n sama dengan 2n sesuai dengan rumus menjumlahkan binomial dengan superskrip. Oleh karena itu, jumlah elemen di atas salah satu garis horizontal bernomor n sama dengan (2 n 1). Hasil ini menjadi cukup jelas jika nilai jumlah elemen setiap horizontal ditulis dalam sistem bilangan biner. Misalnya, untuk n=4 penjumlahan ini dapat ditulis sebagai berikut:
Berikut adalah beberapa sifat horizontal menarik yang juga terkait dengan pangkat dua. Ternyata jika suatu bilangan mendatar merupakan pangkat dua (n=2 k), maka semua unsur dalamnya (kecuali unsur luarnya) adalah bilangan genap. Sebaliknya, semua bilangan suatu garis mendatar akan ganjil jika bilangan tersebut kurang dari satu pangkat dua (n=2 k 1). Validitas sifat-sifat ini dapat diverifikasi dengan memeriksa paritas koefisien binomial internal, misalnya pada garis horizontal n=4 dan n=3 atau n=8 dan n=7.
Misalkan sekarang bilangan baris segitiga siku-siku Pascal adalah bilangan prima p. Maka semua koefisien binomial internalnya habis dibagi p. Properti ini mudah untuk memeriksa nilai kecil dari bilangan kontur prima. Misalnya, semua koefisien binomial internal dari horizontal kelima (5, 10 dan 5) jelas habis dibagi 5. Untuk membuktikan hasil ini untuk bilangan prima horizontal p, Anda perlu menulis rumus perkalian koefisien binomialnya sebagai berikut:
Karena p adalah bilangan prima sehingga tidak habis dibagi m!, hasil kali faktor-faktor sisa pembilang rumus ini harus habis dibagi m! untuk menjamin nilai koefisien binomial bilangan bulat. Oleh karena itu rasio dalam tanda kurung siku adalah bilangan asli N dan hasil yang diinginkan menjadi jelas:
Dengan menggunakan hasil ini, kita dapat menetapkan bahwa banyaknya semua garis horizontal segitiga Pascal, yang elemen-elemen dalamnya habis dibagi suatu bilangan prima p, adalah pangkat dari p, yaitu berbentuk n=p k. Khususnya, jika p=3, maka bilangan prima p tidak hanya membagi semua elemen internal baris 3, seperti yang ditetapkan di atas, tetapi, misalnya, horizontal ke-9 (9, 36, 84, dan 126). Sebaliknya, dalam segitiga Pascal tidak mungkin ditemukan garis mendatar yang seluruh elemen dalamnya habis dibagi suatu bilangan komposit. Jika tidak, jumlah garis horizontal tersebut harus sekaligus merupakan pangkat pembagi prima dari bilangan komposit yang membagi semua elemen internalnya, tetapi hal ini tidak mungkin dilakukan karena alasan yang jelas.
Pertimbangan yang dipertimbangkan memungkinkan kita untuk merumuskan kriteria umum berikut untuk pembagian elemen horizontal segitiga Pascal. Pembagi persekutuan terbesar (PBT) dari semua elemen internal setiap garis horizontal segitiga Pascal dengan bilangan n sama dengan bilangan prima p jika n=pk atau 1 dalam semua kasus lainnya:
GCD(Cmn) = ( ) untuk sembarang 0< m < n .
Sebagai kesimpulan dari analisis garis horizontal, ada baiknya mempertimbangkan satu lagi sifat menarik yang dimiliki oleh rangkaian koefisien binomial yang membentuknya. Jika koefisien binomial suatu garis horizontal berbilangan n dikalikan dengan pangkat berturut-turut dari bilangan 10, lalu semua hasil kali ini dijumlahkan, hasilnya adalah 11 n. Pembenaran formal untuk hasil ini adalah substitusi nilai X=10 dan Y=1 (atau Z=1) ke dalam rumus binomial Newton. Contoh numerik berikut mengilustrasikan pemenuhan properti ini untuk n=5:
Analisis sifat-sifat vertikal segitiga siku-siku Pascal dapat dimulai dengan mempelajari ciri-ciri individu unsur-unsur penyusunnya. Secara formal, setiap vertikal m dibentuk oleh barisan koefisien binomial tak hingga berikut dengan superskrip konstan (m) dan pertambahan subskrip:
Jelasnya, ketika m=0 diperoleh barisan bilangan satu, dan ketika m=1 barisan bilangan asli terbentuk. Ketika m=2 garis vertikal terdiri dari bilangan segitiga. Setiap bilangan segitiga dapat digambarkan pada suatu bidang berbentuk segitiga sama sisi, yang berisi benda-benda sembarang (inti) yang tersusun dalam pola kotak-kotak. Dalam hal ini, nilai setiap bilangan segitiga T k menentukan jumlah kernel yang mewakili, dan indeks menunjukkan berapa banyak baris kernel yang diperlukan untuk mewakilinya. Misalnya, 4 bilangan segitiga awal mewakili konfigurasi jumlah simbol inti "@" berikut:
Perlu dicatat bahwa dengan cara yang sama seseorang dapat memasukkan bilangan kuadrat S k , yang diperoleh dengan mengkuadratkan bilangan asli dan, secara umum, bilangan berpola poligonal yang dibentuk dengan mengisi poligon beraturan secara teratur. Secara khusus, 4 bilangan kuadrat awal dapat direpresentasikan sebagai berikut:
Kembali ke analisis vertikal segitiga Pascal, kita dapat melihat bahwa vertikal berikutnya di m=3 diisi dengan bilangan tetrahedral (piramidal). Setiap angka P k menentukan jumlah inti yang dapat disusun dalam bentuk tetrahedron, dan indeks menentukan berapa banyak lapisan segitiga horizontal dari deretan inti yang diperlukan untuk menggambarkannya dalam ruang tiga dimensi. Dalam hal ini, semua lapisan horizontal harus direpresentasikan sebagai bilangan segitiga yang berurutan. Unsur-unsur vertikal segitiga Pascal berikut untuk m>3 membentuk rangkaian bilangan hipertetraedal, yang tidak memiliki interpretasi geometris visual pada bidang atau ruang tiga dimensi, tetapi secara formal sesuai dengan analog multidimensi bilangan segitiga dan tetrahedal.
Meskipun deret bilangan vertikal segitiga Pascal memiliki ciri-ciri berbentuk individual, bagi deret bilangan vertikal tersebut dimungkinkan untuk menghitung jumlah parsial nilai elemen awal dengan cara yang sama, menggunakan rumus untuk menjumlahkan bilangan kombinasi dengan subskrip . Dalam segitiga Pascal, rumus ini memiliki interpretasi geometris sebagai berikut. Jumlah nilai n koefisien binomial atas suatu vertikal sama dengan nilai elemen vertikal berikutnya, yang terletak satu garis di bawahnya. Hasil ini juga sesuai dengan struktur geometri bilangan segitiga, tetrahedral, dan hipertetrahedal, karena representasi setiap bilangan tersebut terdiri dari lapisan inti yang mewakili bilangan orde bawah. Secara khusus, bilangan segitiga ke-n Tn dapat diperoleh dengan menjumlahkan semua bilangan asli yang mewakili lapisan liniernya:
Demikian pula, tidak sulit mencari bilangan tetrahedral Pn dengan menghitung jumlah n bilangan segitiga pertama yang menyusun lapisan inti horizontal berikut ini:
Selain garis horizontal dan vertikal dalam segitiga siku-siku Pascal, seseorang dapat menelusuri deretan elemen diagonal, studi tentang sifat-sifatnya juga menarik. Dalam hal ini, perbedaan biasanya dibuat antara diagonal menurun dan diagonal naik. Diagonal ke bawah sejajar dengan sisi miring segitiga siku-siku Pascal. Mereka dibentuk oleh serangkaian koefisien binomial dengan pertambahan kedua indeks. Karena identitas simetrinya, diagonal-diagonal menurun bertepatan dalam nilai elemen-elemennya dengan baris vertikal segitiga Pascal yang bersesuaian dan oleh karena itu mengulangi semua sifat-sifatnya yang dibahas di atas. Korespondensi yang ditunjukkan dapat ditelusuri dengan kebetulan nilai elemen diagonal menurun dan vertikal dengan bilangan n apa pun, jika nol vertikal tidak diperhitungkan:
Diagonal menaik membentuk deret bilangan yang tegak lurus secara geometris terhadap sisi miring segitiga siku-siku Pascal. Mereka diisi dengan koefisien binomial dengan penurunan yang lebih rendah dan kenaikan superskrip. Secara khusus, 7 diagonal menaik atas membentuk barisan numerik berikut tanpa memperhitungkan angka nol di belakangnya:
Secara umum, bilangan diagonal menaik n berisi koefisien binomial berikut, yang jumlah indeksnya masing-masing sama dengan (n1):
Berdasarkan identitas penjumlahan untuk bilangan kombinasi, setiap elemen diagonal sama dengan jumlah dua elemen yang bersesuaian dalam indeks dari dua diagonal menaik sebelumnya. Hal ini memungkinkan setiap diagonal menaik berikutnya dibuat dengan penjumlahan berpasangan elemen horizontal yang berdekatan dari dua diagonal sebelumnya, memperluas segitiga Pascal sepanjang diagonal tanpa batas. Penggalan segitiga Pascal berikut ini menggambarkan konstruksi diagonal menaik angka 8 sepanjang diagonal bernomor 6 dan 7:
Dengan metode konstruksi ini, jumlah elemen diagonal menaik, mulai dari diagonal ke-3, akan sama dengan jumlah elemen dari dua diagonal menaik sebelumnya, dan 2 diagonal pertama hanya terdiri dari satu elemen, nilainya yaitu 1. Hasil perhitungan yang sesuai membentuk deret numerik berikut, yang dengannya Anda dapat memeriksa validitas properti yang dipertimbangkan dari diagonal menaik segitiga siku-siku Pascal:
Menganalisis angka-angka ini, Anda dapat melihat bahwa menurut hukum serupa, barisan angka Fibonacci yang terkenal terbentuk, di mana setiap angka berikutnya sama dengan jumlah dua angka sebelumnya, dan dua angka pertama sama dengan 1:
Dengan demikian, kita dapat menarik kesimpulan penting berikut ini: jumlah diagonal elemen-elemen segitiga Pascal merupakan deret Fibonacci. Properti ini memungkinkan kita untuk menetapkan fitur menarik lainnya dari segitiga Pascal. Memperluas rumus Fibonacci secara rekursif, mudah untuk membuktikan bahwa jumlah n bilangan Fibonacci pertama sama dengan (F n+2 1).
Oleh karena itu, jumlah koefisien binomial yang mengisi n diagonal atas juga sama dengan (F n+2 1). Maka jumlah n diagonal pertama segitiga Pascal adalah 1 lebih kecil dari jumlah koefisien binomial pada diagonalnya yang berbilangan (n+2).
Sebagai kesimpulan, perlu dicatat bahwa sifat-sifat horizontal, vertikal dan diagonal segitiga Pascal yang dipertimbangkan tidak menghilangkan berbagai macam kemungkinan yang menghubungkan berbagai aspek matematika yang pada pandangan pertama tidak memiliki kesamaan. Sifat-sifat yang tidak biasa seperti itu memungkinkan kita untuk menganggap segitiga Pascal sebagai salah satu sistem numerik yang paling sempurna, yang semua kemampuannya tidak dapat dicantumkan dan sulit untuk ditaksir terlalu tinggi.
Algoritma penghitungan banyaknya kombinasi menggunakan segitiga Pascal disajikan di bawah ini:
Fungsi Privat SochTT (ByVal n Sebagai Integer, ByVal k Sebagai Integer) Sebagai Double Dim i Sebagai Integer Dim j Sebagai Integer Dim TT () Sebagai Double ReDim TT (n, k) For i = 0 Ke n TT (0, i) = 1 TT (i, i) = 1 Berikutnya Untuk i = 2 Ke n Untuk j = 1 Ke i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Berikutnya Berikutnya SochTT = TT (n, k) Fungsi Akhir
Jika Anda perlu menghitung jumlah kombinasi berkali-kali, mungkin akan lebih mudah untuk membuat segitiga Pascal satu kali, dan kemudian menerima data dari array.
Redupkan TT() Sebagai Sub Pribadi Ganda CreateTT() ReDim TT (0, 0) BuildTT 0, 0 Fungsi Sub Pribadi Akhir SochTT (ByVal n Sebagai Integer, ByVal k Sebagai Integer) Sebagai Ganda Jika n > Ubound (TT) Maka BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) Fungsi Akhir Sub Privat TerminateTT () ReDim TT (0, 0) End Sub Swasta Sub BuildTT (ByVal mulai Sebagai Integer, ByVal berakhir Sebagai Integer) Dim i Sebagai Integer Dim j Sebagai Integer ReDim Pertahankan TT (akhir, akhir) For i = mulai Ke akhir TT (0, i) = 1 TT (i, i) = 1 Berikutnya Jika berakhir< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
Pertama, Anda perlu memanggil prosedur CreateTT. Anda kemudian dapat memperoleh jumlah kombinasi menggunakan fungsi SochTT. Bila Anda tidak lagi membutuhkan segitiga tersebut, panggil prosedur TerminateTT. Pada kode di atas, saat memanggil fungsi SochTT, jika segitiga belum mencapai level yang disyaratkan, maka diselesaikan menggunakan prosedur BuildTT. Fungsi tersebut kemudian mendapatkan elemen array TT yang diinginkan dan mengembalikannya.
Dim X () Sebagai Integer Dim Counter () Sebagai Integer Dim K Sebagai Integer Dim N Sebagai Integer Public Sub Soch() Dim i Sebagai Integer N = CInt(InputBox("Enter N")) K = CInt(InputBox("Enter K ")) K = K + 1 ReDim X(N) Untuk i = 1 Ke N X(i) = i Berikutnya txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c Sebagai Integer) Dim i Sebagai Integer Dim j Sebagai Integer Dim n1 Sebagai Integer Dim Out() Sebagai Integer Dim X1() Sebagai Integer Jika c = K Maka ReDim Out(K) X1 = X Untuk i = 1 Ke K - 1 n1 = 0 Untuk j = 1 Ke N Jika X1(j)<>0 Maka n1 = n1 + 1 Jika n1 = Penghitung(i) Maka Keluar(i) = X1(j) X1(j) = 0 Keluar Untuk Akhir Jika Berikutnya txtOut.Text = txtOut.Text & CStr(Out(i)) Berikutnya txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) Ke N - c + 1 SochGenerate c + 1 Next End If End Sub
DAFTAR KOMBINASI ANGKA ALAM
Untuk menyelesaikan banyak masalah praktis, perlu membuat daftar semua kombinasi kardinalitas tetap yang dapat diperoleh dari elemen-elemen suatu himpunan berhingga, dan tidak hanya menentukan jumlahnya. Mempertimbangkan kemungkinan penomoran bilangan bulat dari elemen-elemen himpunan berhingga yang selalu ada, dalam banyak kasus diperbolehkan untuk membatasi diri pada penggunaan algoritma untuk menghitung kombinasi bilangan asli. Yang paling natural dan sederhana adalah algoritma untuk membuat daftar kombinasi bilangan asli urutan leksigrafik.
Untuk mendeskripsikan algoritme ini secara formal, akan lebih mudah untuk mengasumsikan bahwa himpunan utama, yang semua kombinasi m elemennya harus dicantumkan, membentuk bilangan asli berurutan dari 1 hingga n. Maka kombinasi m apa pun Akibat pengurutan, nilai pada setiap posisi vektor kombinasi tersebut secara alamiah ternyata dibatasi nilainya dari atas dan bawah sebagai berikut: Algoritme leksigrafik secara berurutan menghasilkan vektor kombinasi tersebut, dimulai dengan vektor terkecil secara leksigrafik, di mana semua posisi berisi nilai minimum yang mungkin dari elemen yang sama dengan indeksnya: Setiap vektor kombinasi yang berurutan dibentuk dari vektor saat ini setelah memindai elemen-elemennya dari kiri ke kanan untuk menemukan elemen paling kanan yang belum mencapai nilai batasnya: Nilai elemen tersebut harus ditingkatkan sebesar 1. Setiap elemen di sebelah kanannya harus diberi nilai sekecil mungkin, yaitu 1 lebih besar dari tetangganya di sebelah kiri. Setelah perubahan ini, vektor kombinasi berikutnya akan memiliki komposisi unsur berikut: Jadi, vektor kombinasi berikutnya secara leksigrafik akan lebih besar dari vektor sebelumnya, karena nilai elemen awalnya (j1) sama nilainya, dan nilai elemen pada posisi j adalah 1 lebih besar dari nilai elemen sebelumnya. . Hubungan tertentu dari peningkatan tatanan leksigrafik dijamin terpenuhi pada semua iterasi algoritma. Hasilnya adalah barisan leksigrafis yang meningkat, yang dilengkapi dengan vektor kombinasi terbesar secara leksigrafik, dimana elemen-elemen di semua posisi memiliki nilai maksimum sebagai berikut: Algoritme leksigrafik yang dipertimbangkan diilustrasikan oleh contoh berikut, di mana perlu untuk membuat daftar dalam urutan leksigrafik yang meningkat semua 15 kombinasi n=6 bilangan asli pertama dengan m=4 bilangan, yaitu semua kemungkinan himpunan bagian 4 elemen dari pembangkit utama himpunan (1, 2, 3, 4, 5, 6) dari 6 elemen. Hasil perhitungan disajikan pada tabel berikut: Dalam contoh ini, nilai bilangan terbesar yang diperbolehkan pada posisi vektor kombinasi masing-masing adalah 3, 4, 5 dan 6. Untuk memudahkan interpretasi hasil, pada setiap vektor kombinasi, elemen paling kanan yang memiliki belum mencapai nilai maksimumnya, digarisbawahi. Indeks numerik dari vektor kombinasi menentukan jumlahnya dalam urutan leksigrafik. Dalam kasus umum, bilangan leksigrafik N dari setiap kombinasi n elemen dengan m dapat dihitung menggunakan rumus berikut, di mana, untuk alasan kosmetik, simbolisme Appel digunakan untuk menunjukkan jumlah kombinasi: Secara khusus, perhitungan berikut menggunakan rumus untuk kombinasi bilangan (1, 3, 4, 6) dari n=6 elemen m=4 dalam urutan leksigrafik akan memberikan hasil N=8, yang sesuai dengan contoh yang dibahas di atas: Dalam kasus umum, dengan menggunakan identitas jumlah kombinasi kedua indeks, dapat ditunjukkan bahwa banyaknya kombinasi terkecil secara leksigrafis (1, ... i, ... m) bila dihitung menggunakan ini rumus akan selalu sama dengan 1: Jelas juga bahwa banyaknya kombinasi terbesar secara leksigrafis (m, … nm+i, … n) jika dihitung menggunakan rumus ini akan sama dengan banyaknya kombinasi n elemen dengan m: Rumus menghitung bilangan kombinasi leksigrafik dapat digunakan untuk menyelesaikan soal invers, dimana Anda perlu menentukan vektor kombinasi berdasarkan bilangannya dalam urutan leksigrafik. Untuk menyelesaikan soal invers tersebut harus ditulis dalam bentuk persamaan, dimana semua nilai yang tidak diketahui dari elemen vektor kombinasi yang diinginkan (C 1, ... C i, ... C m ) terkonsentrasi pada banyaknya kombinasi ruas kanannya, dan selisih yang diketahui L dari banyaknya kombinasi ditulis di ruas kiri n elemen masing-masing m dan banyaknya kombinasi yang diperlukan N: Solusi untuk persamaan ini disediakan oleh algoritma "serakah" berikut, selama iterasi di mana nilai-nilai elemen vektor dari kombinasi yang diinginkan dipilih secara berurutan. Pada iterasi awal, nilai minimum yang mungkin (dalam batasannya) dari C 1 dipilih, di mana suku pertama di sisi kanan akan memiliki nilai maksimum tidak melebihi L: Sekarang ruas kiri L harus dikurangi dengan bilangan kombinasi pertama di ruas kanan dengan nilai C 1 yang dipilih, dan dengan cara yang sama tentukan nilai C 2 pada iterasi kedua: Demikian pula, semua iterasi selanjutnya harus dilakukan untuk memilih nilai semua elemen C i lainnya dari kombinasi yang diinginkan, hingga elemen terakhir C m: Untuk alasan yang jelas, nilai elemen terakhir C m dapat ditentukan berdasarkan persamaan jumlah kombinasinya dengan nilai sisa ruas kiri L: Perlu dicatat bahwa nilai elemen terakhir dari kombinasi C m dapat ditemukan dengan lebih sederhana, tanpa menyebutkan nilai yang mungkin: Implementasi iterasi dari algoritma yang dipertimbangkan diilustrasikan oleh contoh berikut, di mana perlu untuk menentukan kombinasi dengan angka N=8 dalam urutan leksigrafik, jika n=6 dan m=4: Kemampuan algoritmik untuk menentukan kombinasi bilangan tertentu dalam urutan leksigrafik dapat digunakan dalam berbagai arah. Khususnya, ketika membuat daftar kombinasi dalam urutan leksigrafik, perlu untuk memastikan kembalinya kombinasi apa pun yang diperoleh sebelumnya, cukup mengetahui nomornya saja. Selain itu, dimungkinkan untuk menghasilkan kombinasi dalam urutan apa pun, yang diatur oleh urutan nomor leksigrafisnya yang diberikan secara sewenang-wenang. Sekarang kami menyajikan algoritma untuk menghasilkan kombinasi dalam urutan leksikografis: 2 untuk i:= 1 sampai k lakukan A[i] := i; 5 mulai menulis(A, …, A[k]); 6 jika A[k] = n maka p:= p 1 lain p:= k; 8 untuk i:= k ke p melakukan A[i] := A[p] + i p + 1 KOMBINASI DENGAN ELEMEN BERULANG Berbeda dengan kombinasi klasik, yang semua elemennya berbeda, kombinasi dengan pengulangan membentuk pilihan elemen himpunan berhingga yang tidak berurutan, di mana setiap elemen dapat muncul secara sering tanpa batas dan belum tentu ada dalam satu salinan. Dalam hal ini, jumlah pengulangan elemen biasanya hanya dibatasi oleh panjang kombinasi, dan kombinasi yang berbeda pada setidaknya satu elemen dianggap berbeda. Misalnya, dengan memilih 4 angka opsional yang berbeda dari himpunan 1, 2, dan 3, Anda dapat membuat 15 kombinasi berikut dengan pengulangan: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
Secara umum, kombinasi dengan pengulangan dapat dibentuk dengan memilih n elemen bertipe sembarang. Namun, bilangan tersebut selalu dapat dikaitkan dengan bilangan asli berurutan dari 1 hingga n. Kemudian kombinasi m angka-angka yang berbeda secara opsional dalam rentang ini dapat ditulis dalam bentuk vektor, menyusunnya dalam urutan tidak menurun dari kiri ke kanan: Secara alami, dengan bentuk notasi ini, setiap elemen yang berdekatan dapat disamakan karena kemungkinan pengulangan yang tidak terbatas. Namun, setiap vektor kombinasi dengan pengulangan n elemen sebesar m dapat diasosiasikan dengan vektor kombinasi elemen (n+m−1) sebesar m, yang dibuat sebagai berikut: Jelas bahwa untuk sembarang nilai elemen vektor f, elemen vektor C dijamin berbeda dan terurut secara ketat dalam urutan nilainya dari rentang 1 hingga (n+m1) : Adanya korespondensi satu-satu antara elemen-elemen vektor kombinasi f dan C memungkinkan kita mengusulkan metode sederhana berikut untuk membuat daftar kombinasi secara sistematis dengan pengulangan n elemen sebanyak m. Kita hanya perlu membuat daftar, misalnya, dalam urutan leksigrafik, semua kombinasi C dari (n+m1) elemen m, secara berurutan mengubah elemen masing-masing elemen tersebut menjadi elemen kombinasi yang sesuai dengan pengulangan f menggunakan rumus berikut: Hasilnya adalah barisan vektor kombinasi dengan pengulangan elemen, yang disusun dalam urutan yang dihasilkan dengan membuat daftar kombinasi yang sesuai tanpa pengulangan elemen. Secara khusus, untuk memperoleh urutan kombinasi 3 digit 1, 2 dan 3 di atas dengan pengulangan 4 digit, perlu dicantumkan dalam urutan leksigrafik semua kombinasi tanpa pengulangan 6 digit 1,2,3,4, 5 dan 6 masing-masing terdiri dari 4 digit, konversikan sesuai petunjuk. Contoh berikut menunjukkan konversi kombinasi (1,3,4,6) dengan nomor leksikografis 8: Korespondensi satu-satu yang dipertimbangkan antara kombinasi dengan dan tanpa pengulangan elemen berarti bahwa himpunan mereka sama kuatnya. Oleh karena itu, secara umum, banyaknya kombinasi dengan pengulangan n elemen sebanyak m sama dengan banyaknya kombinasi tanpa pengulangan (n+m1) elemen sebanyak m. Dengan menggunakan simbolisme yang sama untuk menyatakan banyaknya kombinasi dengan pengulangan f dan tanpa pengulangan C, persamaan ini dapat ditulis sebagai berikut: Sangat mudah untuk memeriksa bahwa untuk contoh di atas, di mana n=3 dan m=4, jumlah kombinasi pengulangan akan sama dengan 15, yang bertepatan dengan hasil pencacahan langsungnya: Perlu dicatat bahwa, tidak seperti versi klasik, nilai parameter kombinasi dengan pengulangan n dan m tidak berhubungan langsung satu sama lain, oleh karena itu f(n,m)>0 untuk setiap kombinasi nilai positifnya. Kondisi batas yang sesuai ditentukan dari persamaan antara nilai (n+m1) dan (n1) atau (n+m1) dan m: Jelas juga bahwa jika m sama dengan 1, maka tidak ada pengulangan elemen yang mungkin terjadi dan, oleh karena itu, untuk setiap nilai positif n>0 persamaan berikut akan benar: Selain itu, untuk bilangan kombinasi dengan pengulangan untuk sembarang nilai positif n dan m, berlaku relasi perulangan berikut, yang mirip dengan identitas penjumlahan untuk bilangan kombinasi tanpa pengulangan elemen: Sebenarnya, ia berubah menjadi identitas penjumlahan yang ditunjukkan setelah substitusi formal dari bilangan kombinasi yang bersesuaian tanpa pengulangan ke ruas kiri dan kanannya: Hubungan perulangan yang dipertimbangkan dapat digunakan untuk secara efektif menentukan jumlah kombinasi dengan pengulangan, ketika penting untuk menghilangkan operasi padat karya dalam menghitung produk faktorial dan menggantinya dengan operasi penjumlahan yang lebih sederhana. Dalam hal ini, untuk menghitung nilai f(n,m), Anda hanya perlu menerapkan relasi perulangan ini hingga Anda memperoleh jumlah suku-suku dalam bentuk f(1,m) dan f(i,1), di mana i mengambil nilai dalam rentang dari n hingga 1. Menurut definisi kuantitas, suku-suku tersebut masing-masing sama dengan 1 dan i. Contoh berikut mengilustrasikan penggunaan teknik transformasi ini untuk kasus n=3 dan m=4: DAFTAR KOMBINASI BINER Saat mengimplementasikan kombinasi dalam perangkat keras atau pemrograman dalam bahasa assembly, penting untuk dapat memproses rekaman kombinasi dalam format biner. Dalam hal ini, setiap kombinasi n elemen m harus ditentukan dalam bentuk bilangan biner n-bit (B n,...B j,...B 1), di mana m digit satuan menunjukkan elemen-elemen dari m kombinasi, dan digit sisanya (nm) memiliki nilai nol. Jelasnya, dengan bentuk notasi ini, kombinasi yang berbeda harus berbeda dalam susunan angka 1, dan hanya ada cara C(n,m) untuk menyusun m angka nol atau (nm) dalam himpunan biner n-bit. Misalnya, tabel berikut mencantumkan keenam kombinasi biner tersebut, yang menyediakan bilangan biner 4-bit untuk semua kombinasi 4 elemen himpunan arbitrer (E 1 , E 2 , E 3 , E 4 ) dengan 2: Dalam kasus umum, tugas menghitung kombinasi biner tersebut direduksi menjadi pencarian sistematis semua himpunan biner n-bit dengan susunan m satu dan (nm) bit nol yang berbeda. Dalam bentuk yang paling sederhana, pencarian tersebut diimplementasikan dengan berbagai metode transposisi bit yang berdekatan dengan pergeseran (algoritma pergeseran transpositif). Ini adalah algoritma berulang, dan namanya mencerminkan sifat operasi yang dilakukan pada setiap langkah. Prosedur berulang dari algoritma pergeseran transpositif membentuk rangkaian kombinasi biner yang dimulai dengan himpunan biner, dimana semua himpunan tersebut terkonsentrasi pada digit orde rendah (di sebelah kanan), dan berakhir ketika semua 1 berada pada digit orde tinggi ( di kiri): Saat mencocokkan kombinasi awal dan akhir, urutan ini berbeda dalam urutan daftar himpunan biner perantara. Namun, dalam semua kasus, setiap kombinasi biner berikutnya terbentuk dari kombinasi biner sebelumnya sebagai hasil dari melakukan operasi transposisi dan pergeseran yang sesuai. Pada saat yang sama, berbagai algoritma pergeseran transpositif berbeda dalam cara mereka memilih sepasang bit untuk transposisi dan sekelompok bit untuk pergeseran. Kekhususan ini dibahas di bawah untuk algoritma transposisi dengan pergeseran kiri dan kanan. Pada algoritma transposisi dengan pergeseran ke kiri, pada setiap langkah diperoleh kombinasi biner berikutnya dari yang sekarang dengan mengganti pasangan digit paling kiri 01 dengan 10 (transposisi) dan menggeser kelompok digit satuan terdepan, jika ada, mendekati pasangan 10 diperoleh setelah transposisi (pergeseran). Jika dalam hal ini tidak ada satuan pada digit terdepan dalam kombinasi biner saat ini, maka pergeseran tidak dilakukan, meskipun satuan terdepan diperoleh setelah transposisi pada langkah ini. Pergeseran juga tidak dilakukan bila tidak ada angka nol pada bit paling signifikan sebelum pasangan 10 yang diperoleh setelah transposisi. Tindakan yang dipertimbangkan diilustrasikan oleh contoh berikut melakukan dua iterasi berturut-turut dari algoritma ini, di mana pada satu iterasi (15) hanya transposisi (T") yang dilakukan, dan pada iterasi lainnya (16) transposisi dilengkapi dengan pergeseran ( T"+S"): Dalam algoritma transposisi pergeseran kanan, langkah-langkah yang secara konseptual serupa dilakukan pada setiap langkah. Hanya transposisi yang memastikan bahwa bit paling kanan dari 01 digantikan oleh 10 (bukan bit paling kiri), dan kemudian semua bit di sebelah kanannya digeser ke bit yang paling tidak signifikan. Seperti sebelumnya, perpindahan dilakukan hanya jika ada unit yang dapat digeser ke kanan. Tindakan yang dipertimbangkan diilustrasikan dengan contoh berikut melakukan dua iterasi berturut-turut dari algoritma ini, di mana pada satu iterasi (3) hanya transposisi (T") yang dilakukan, dan pada iterasi lainnya (4) transposisi dilengkapi dengan pergeseran ( T"+S"): Perlu diperhatikan bahwa iterasi kedua algoritma dapat ditulis dalam bentuk aditif jika kombinasi biner diinterpretasikan sebagai bilangan bulat pada sistem bilangan basis 2. Khusus untuk algoritma transposisi dengan pergeseran ke kanan, setiap kombinasi biner berikutnya (B" n ,…B" j , …B" 1), selalu dapat diperoleh dari kombinasi saat ini (B n,…B j,…B 1) dengan melakukan operasi penjumlahan bilangan bulat menggunakan rumus penjumlahan berikut: Dalam rumus penjumlahan ini, eksponen pangkat dua f dan t masing-masing menunjukkan jumlah digit nol orde rendah dari kombinasi biner saat ini dan jumlah digit yang berurutan di sebelah kirinya. Misalnya, untuk kombinasi biner ke-4 (001110) dari n=6 digit f =1 dan t =3. Oleh karena itu, menghitung kombinasi biner berikutnya menggunakan rumus aditif pada iterasi 5 akan memberikan hasil sebagai berikut, setara dengan melakukan operasi transposisi dan shift: Untuk analisis komparatif dari algoritma transposisi dengan pergeseran kiri dan kanan, disarankan untuk membandingkan urutan kombinasi biner yang dihasilkannya dalam iterasinya. Tabel berikut menunjukkan dua rangkaian kombinasi biner dari 4 elemen 2, yang diperoleh masing-masing dengan algoritma pergeseran kiri (TSL) dan kanan (TSR): Membandingkan 2 barisan ini, Anda dapat melihat bahwa keduanya adalah cermin terbalik. Ini berarti bahwa dua kombinasi biner apa pun yang terletak di dalamnya pada jarak yang sama dari ujung-ujung urutannya yang berlawanan adalah bayangan cermin satu sama lain, yaitu, mereka bertepatan ketika pengindeksan bit-bit di salah satu dari mereka dibalik. Misalnya, pola biner kedua dari awal rangkaian TSL (0101) merupakan bayangan cermin dari pola biner (1010) yang berada di urutan kedua dari akhir rangkaian TSR. Secara umum, setiap kombinasi biner dengan bilangan i pada suatu barisan merupakan cerminan dari kombinasi biner dengan bilangan (ni+1) pada barisan yang lain. Hubungan antara barisan ini merupakan konsekuensi dari sifat simetris dari operasi transposisi dan pergeseran dalam dua algoritma yang dipertimbangkan untuk menghitung kombinasi biner. Perlu dicatat bahwa format biner juga dapat digunakan untuk merekam kombinasi dengan pengulangan elemen. Untuk itu perlu dibuat korespondensi satu-satu antara kombinasi dengan pengulangan dan kombinasi biner, yang dikonstruksi sebagai berikut. Misalkan ada kombinasi sembarang dengan pengulangan, yang diperoleh dengan memilih m elemen yang berbeda secara opsional dari n elemen himpunan pembangkit. Untuk membuat kecocokan yang diinginkan, pertama-tama Anda harus menambahkan semua elemen himpunan pembentuk (cat) ke dalam kombinasi, lalu mengurutkan gabungan yang dihasilkan (sort) sehingga semua elemen yang identik berada berdampingan. Hasilnya adalah barisan unsur (n+m), dimana terdapat n kelompok unsur yang identik. Akan terdapat total (n+m1) kesenjangan antar elemen, di antaranya akan terdapat (n1) kesenjangan antar kelompok elemen identik dan m kesenjangan antar elemen dalam kelompok. Agar lebih jelas, Anda dapat menempatkan simbol “|” pada ruang yang ditunjukkan. dan dengan demikian. Jika sekarang kita mencocokkan 1 dengan spasi antar grup (|) dan 0 dengan semua spasi lainnya (), kita mendapatkan kombinasi biner. Ini dibentuk oleh kumpulan biner (n+m1) bit, di mana (n1) adalah satu dan m bit nol, yang lokasinya secara unik sesuai dengan kombinasi asli dengan pengulangan elemen n hingga m. Teknik transformasi yang dipertimbangkan diilustrasikan dengan contoh pembuatan kombinasi biner (1001101) berikut menggunakan kombinasi dengan pengulangan (BBD), yang elemennya dipilih dari himpunan pembangkit lima huruf Latin pertama: Secara umum, jumlah himpunan biner tersebut menentukan banyaknya cara untuk menyusun (n1) satuan (atau m nol) dalam (n+m1) digit biner. Nilai ini jelas sama dengan banyaknya kombinasi dari (n+m1) dengan (n1) atau dengan m, yaitu C(n+m1,n1) atau C(n+m1,m), yang sama dengan banyaknya kombinasi dengan pengulangan f( n,m) dari n elemen, masing-masing m. Dengan demikian, dengan memiliki korespondensi satu-satu antara kombinasi dengan pengulangan dan kombinasi biner, maka sah untuk mereduksi pencacahan kombinasi dengan pengulangan menjadi pencacahan kombinasi biner, misalnya menggunakan algoritma transposisi dengan pergeseran kiri atau kanan. Setelah ini, Anda hanya perlu mengembalikan kombinasi yang diperlukan dengan pengulangan menggunakan kombinasi biner yang dihasilkan. Hal ini selalu dapat dilakukan dengan menggunakan teknik pemulihan berikut. Misalkan himpunan utama, yang unsur-unsurnya membentuk kombinasi dengan pengulangan m yang belum tentu unsur-unsurnya berbeda, diurutkan secara sembarang sehingga setiap unsurnya mempunyai nomor urut tertentu dari 1 sampai n. Mari kita implementasikan juga pencacahan kombinasi biner (n+m1) digit biner, di mana (n1) satuan dan m digit nol. Setiap kombinasi biner yang dihasilkan dapat ditambah di sebelah kiri dengan digit satuan fiktif, dan semua digit satuan dapat diberi nomor dari kiri ke kanan dengan bilangan bulat dari 1 hingga n. Maka jumlah angka nol berturut-turut setelah setiap unit ke-i dari kombinasi biner akan sama dengan jumlah kemunculan elemen ke-i dari himpunan utama dalam kombinasi yang sesuai dengan pengulangan. Teknik yang dipertimbangkan diilustrasikan oleh contoh berikut, di mana, menggunakan kombinasi biner (1001101), kombinasi dengan pengulangan BBD dipulihkan, elemen-elemennya dipilih dari set pembangkit lima huruf Latin pertama, ditulis dalam urutan abjad , dan garis atas menunjukkan elemen yang tidak ada dalam kombinasi ini: Dengan melakukan tindakan serupa dalam kondisi contoh ini, Anda dapat membuat daftar semua 35 kombinasi biner yang membentuk himpunan biner 7-bit, di mana terdapat 4 satu dan 3 nol, dan memulihkan kombinasi terkait dengan pengulangan 5 elemen dari 3. Musim dingin semakin dekat, dan Khoma serta Suslik memutuskan untuk membeli kacang polong. Sepanjang hari mereka berlari ke gudang dan membawa beberapa buah polong: Khoma, empat, dan Suslik, dua. Menjelang malam, mereka menghitung semua buah polong yang telah mereka panen dan bertanya-tanya bagaimana cara membagi kacang polong tersebut sekarang. Khoma berpendapat bahwa jika dia menarik dua kali lebih banyak dari Suslik, maka dia harus mendapat kacang polong dua kali lebih banyak. Suslik cukup keberatan dengan hal ini, pertama, kecepatan Khoma jauh lebih rendah daripada kecepatan Suslik, dan kedua, siapa tahu, mungkin Khoma hanya kabur satu atau dua kali, dan sisanya dia menganggur... Bantulah teman Anda setidaknya sedikit memahami situasi sulit ini. Tentukan semua opsi yang memungkinkan untuk berapa banyak polong yang dibawa Suslik dan berapa banyak Khoma. Pada baris pertama terdapat bilangan genap alami M – jumlah pod yang dicuri, 2 ≤ M ≤ 1000. Semua kemungkinan kombinasi jumlah polong yang dibawa oleh Suslik dan Khoma, satu kombinasi per baris. Setiap kombinasi mewakili dua bilangan bulat non-negatif yang dipisahkan oleh spasi: angka pertama adalah jumlah pod yang dibawa oleh Suslik, angka kedua – dibawa oleh Khoma. Urutkan kombinasi dalam urutan menurun dari angka pertama. #termasuk menggunakan namespace std ; ke dalam utama()( ke dalam a, b = 0; cin >> sebuah ; sementara (a >= 0 ) ( cout<<
a
<<
" "
<<
b
<<
"\n"
;
sebuah -= 4 ; b += 4 ; kembali 0; Misalkan a adalah banyaknya buah yang dibawa oleh Homa dan b adalah banyaknya buah yang dibawa oleh Suslik. Karena berdasarkan kondisi soal, Khoma hanya membawa empat buah polong, kita akan mempertimbangkan a = a-4 dan b = b + 4 untuk menghitung semua kemungkinan kombinasi jumlah buah yang dibawa oleh Suslik dan Khoma. Mari kita juga menggunakan loop ketika, yang akan mengulangi tindakan yang dijelaskan di atas hingga \geq 0. Dalam jawabannya, kami mencetak semua kemungkinan kombinasi jumlah pod yang dibawa oleh teman, satu per baris, diurutkan dalam urutan menurun dari angka pertama. Contoh // Kombinasi 3 dari 52 untuk (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
Di sini kita akan melihat masalah yang lebih kompleks, solusi yang belum saya temukan di RuNet (namun, saya akan memberikan satu tautan, tetapi rumus itu jelas salah) - berdasarkan kombinasi itu sendiri (dalam hal ini, satu set tiga angka) temukan indeksnya. Mari kita asumsikan, untuk lebih pastinya, setelah mengurutkan i1 = 3, i2 = 7, i3 = 12. Algoritme pembangkitan tipikal adalah kita menghasilkan kombinasi 2 dari 52, dan untuk setiap kombinasi tersebut dalam loop bersarang kita menghasilkan kombinasi 3 dari 50, dan memeriksa apakah indeks (i3, i4, i5) dalam kombinasi bersarang berfungsi tidak sesuai dengan indeks (i1, i2) dalam kombinasi eksternal: kode C++ // KOMBINASI EKSTERNAL untuk (int i1 = 0; i1< 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРЕННЕЕ СОЧЕТАНИЕ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...
kode C++ jika (i3 >= i1) --i3; jika (i3 >= i2) --i2; // serupa untuk i4, i5 Contoh kode untuk membagi indeks dengan 2, 3, 47 int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) ( // Indeks kombinasi 2 dari 52, dikalikan C(3, 50) int offset = ((52*51 - (51-i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // “Indeks ulang” grup internal sehingga penomorannya menjadi 0...49 jika (i3 > = i1) --i3; jika (i3 >= i2) --i3; jika (i4 >= i1) --i4; jika (i4 >= i2) --i4; jika (i5 >= i1) --i5 ; if (i5 >= i2) --i5; // Sekarang tambahkan indeks kombinasi sebanyak 3 // 0: // SUM untuk n = 0 sebanyak i3-1 KOMBINASI (2, 49-n) // = SUM untuk m = 50-i3 kali 49 (m * (m-1) / 2) offset += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3 )) / 2) / 2); // 1: // SUM untuk n = i3+1 hingga i4-1 KOMBINASI (1, 49-n) offset += (( (48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); // 2: // SUM untuk n = i4+1 hingga i5-1 (1) offset + = (i5 - i4 - 1); pengembalian offset ; ) Secara umum, saya akan membagi algoritma kombinatorial ke dalam kelas-kelas berikut: Jumlah kombinasi Kombinasi dari N Oleh k disebut satu set k elemen yang dipilih dari data N elemen. Himpunan yang hanya berbeda dalam urutan elemennya (tetapi tidak dalam komposisinya) dianggap identik; itulah sebabnya kombinasi berbeda dengan penempatan. Jumlah kombinasi dari N Oleh k
sama dengan koefisien binomial Untuk nilai tetap N menghasilkan fungsi bilangan kombinasi dengan pengulangan dari N Oleh k adalah: Fungsi pembangkit dua dimensi bilangan kombinasi dengan pengulangan adalah: Yayasan Wikimedia. 2010. 70 tujuh puluh 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Faktorisasi: 2×5×7 Notasi Romawi: LXX Biner: 100 0110 ... Wikipedia Bilangan ringan, bilangan bersyarat yang secara unik mengekspresikan bagian luar kondisi selama fotografi (biasanya kecerahan subjek dan fotosensitifitas bahan fotografi yang digunakan). Nilai E.h apa pun dapat dipilih beberapa kali. kombinasi nomor bukaan...... Kamus Besar Ensiklopedis Politeknik Suatu bentuk bilangan yang membedakan dua benda baik terhadap satu benda maupun terhadap banyak benda. Bentuk ini tidak ada dalam bahasa Rusia modern, namun sisa-sisa pengaruhnya masih ada. Jadi, kombinasi dua tabel (lih. jamak... ... Kamus istilah linguistik Matematika kombinatorial , kombinatorik , suatu cabang matematika yang dikhususkan untuk memecahkan masalah pemilihan dan penyusunan unsur-unsur tertentu, biasanya berhingga, yang dihimpunan sesuai dengan aturan yang diberikan. Setiap aturan tersebut menentukan metode konstruksi... ... Ensiklopedia Matematika Dalam kombinatorik, kombinasi by adalah himpunan elemen yang dipilih dari himpunan tertentu yang mengandung elemen berbeda. Himpunan yang hanya berbeda dalam urutan unsurnya (tetapi tidak dalam komposisinya) dianggap identik, kombinasi ini ... ... Wikipedia Bergerak dalam kajian peristiwa-peristiwa yang kejadiannya tidak diketahui secara pasti. Hal ini memungkinkan kita untuk menilai kewajaran dalam mengharapkan terjadinya suatu peristiwa dibandingkan dengan peristiwa lainnya, meskipun memberikan nilai numerik pada probabilitas suatu peristiwa seringkali tidak diperlukan... ... Ensiklopedia Collier 1) sama dengan analisis kombinatorial matematis. 2) Bagian matematika dasar yang berkaitan dengan studi tentang jumlah kombinasi, tergantung pada kondisi tertentu, yang dapat disusun dari sekumpulan objek berhingga tertentu... ... Ensiklopedia Besar Soviet - (Yunani paradoxos tak terduga, aneh) dalam arti luas: pernyataan yang sangat menyimpang dari opini yang diterima secara umum dan mapan, penolakan terhadap apa yang tampaknya “benar tanpa syarat”; dalam arti yang lebih sempit, dua pernyataan yang berlawanan, untuk... ... Ensiklopedia Filsafat - (atau prinsip inklusi dan eksklusi) rumus kombinatorial yang memungkinkan Anda menentukan kardinalitas gabungan sejumlah himpunan berhingga, yang secara umum dapat berpotongan satu sama lain ... Wikipedia Sebuah teori matematika yang berkaitan dengan menentukan jumlah cara berbeda dalam mendistribusikan objek tertentu dalam urutan yang diketahui; sangat penting dalam teori persamaan dan teori probabilitas. Tugas paling sederhana dari jenis ini adalah... ... Kamus Ensiklopedis F.A. Brockhaus dan I.A. EfronMemasukan data
Keluaran
Tes
Memasukan data
Keluaran
6
\\ 6 \; 0 \\ 2 \; 4
11
\\ 11\;0 \\ 7\;4 \\ 3\;8
18
\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16
Kode program
Solusi dari masalah tersebut
Indeks kombinasi
Setiap kombinasi, permutasi, susunan, dan objek kombinatorial lainnya dapat dikaitkan dengan indeks - ini adalah angka yang muncul saat melakukan iterasi melalui algoritme ini.
Ada opsi untuk mencari “langsung”. Kami menyalakan penghitung kombinasi, mengambil algoritma di atas dan mencoba semuanya hingga kami mencapai opsi yang diinginkan. Opsi ini memiliki kompleksitas waktu yang sangat tinggi, jadi kami akan membuang opsi ini.
Misalkan inputnya berisi angka i1, i2, i3. Pertama-tama, kita perlu mengaturnya dalam urutan menaik (perhatikan bahwa algoritma pembangkitan itu sendiri, yang diberikan di atas, selalu menghasilkannya dalam bentuk yang dipesan, meskipun konsep "kombinasi" itu sendiri menyiratkan urutan yang sewenang-wenang).
Ini berarti kita “melewati” semua kombinasi dimana i1 sama dengan 0, 1 dan 2.
Untuk i1 = 0, kita telah melalui kombinasi C(2, 51), karena indeks i1, i2 melewati semua kombinasi 2 dari 51 angka.
Untuk i1 = 1 kita melalui kombinasi C(2, 50).
Untuk i1 = 2 kita melalui kombinasi C(2, 49).
Secara total, kita menyelesaikan SUM (dari n = 0 hingga n = i1-1) C(2, 51-n).
Untuk i1 = 3, mari kita pertimbangkan kombinasi yang kita lalui saat menjalankan indeks i2 (dan bagi kita ini dimulai dengan i2 = i1+1 = 4).
Saat i2 = 4, kombinasi C(1, 47) lolos, saat i2 = 5, kombinasi C(1, 46) lolos, saat i2 = 6, kombinasi C(1, 45) lolos.
Dengan analogi lengkap, untuk i2 = 7 kita mempertimbangkan kombinasi yang dijalankan oleh indeks i3.
Kami mendapatkan rumus umum:
Indeks kombinasi yang diperlukan = SUM (dari n = 0 hingga i1-1) C(2, 51-n) + SUM (dari n = i1+1 hingga i2-1) C(1, 51-n) + SUM (dari n = i2+1 sampai i3-1) C (0, 51-n).Indeks subset
Dalam kombinatorik ada objek yang lebih kompleks - mempartisi menjadi himpunan bagian. Misalnya, membagi himpunan 52 elemen menjadi tiga himpunan bagian yang masing-masing terdiri dari 2, 3, dan 47 elemen, yang urutan elemen dalam setiap himpunan bagian tidak penting. (Omong-omong, kombinasi 2 dari 52 hanyalah kasus khusus pemisahan menjadi dua himpunan bagian yang masing-masing terdiri dari 2 dan 50 elemen).
Sekali lagi, setiap partisi tersebut memiliki indeksnya sendiri.
Ternyata algoritma kita untuk mencari indeks kombinasi dapat dimodifikasi untuk mencari indeks partisi.
Perlu dicatat bahwa kita perlu menyusun indeks dalam “kombinasi eksternal” i1, i2 di antara mereka sendiri, dan indeks i3, i4, i5 di antara mereka sendiri, tetapi secara independen dari dua yang pertama.
Perlu juga diingat bahwa dalam “kombinasi bersarang” kita pada dasarnya bekerja dengan kumpulan 50 elemen, tetapi indeks i3, i4, i5 perlu “digeser” dengan cara tertentu agar tidak berubah dari 0 hingga 51, tetapi dari 0 hingga 49:
(bisa dikatakan, kami memotong indeks i1, i2 dari kumpulan 52 elemen kami dan kemudian menggeser kumpulan yang tersisa untuk menutup lubang, sementara indeks i3-i5 digeser).
Harus diingat bahwa di dalam setiap kombinasi “eksternal” kita memiliki kombinasi C(3, 50) yang “bersarang”.
Kemudian algoritmanya akan direduksi menjadi sebagai berikut:
COMBINATION_INDEX (i1, i2 dari 52) * COMBINATION_NUMBER BY_3_OF_50 + COMBINATION_INDEX (i3, i4, i5 dari 50 setelah pergeseran indeks). Membawa algoritma ke kompleksitas yang konstan
Saya harus segera mencatat bahwa “kesalahan” terjadi dalam rumus jika, misalnya, i1 = 0 (kita menghitung jumlah n = dari 0 hingga -1) atau i2 = 1 (kita menghitung jumlah dari 1 hingga 0). Faktanya, dalam kasus seperti itu, jumlah yang sesuai harus diambil sama dengan nol, dan hasilnya akan benar.
Saya juga harus memperhatikan kompleksitas waktu dari algoritme kami: algoritme tersebut memiliki kompleksitas linier, asalkan Anda menganggap C sebagai waktu konstan. Ini sudah jauh lebih baik daripada kekerasan.
Tapi sebenarnya (dalam kasus kami 52) tidak ada yang menghalangi kami untuk mereduksi algoritme menjadi kompleksitas yang konstan. Untuk melakukan ini, kita akan menerapkan pengetahuan matematika dan menghitung semua jumlahnya secara analitis.
Misalnya banyaknya kombinasi C(2, K), jika “diperluas” dalam bentuk rumus K! / ((K-2)! * 2!), direduksi menjadi polinomial derajat ke-2. Dan karena kita memilikinya di bawah tanda penjumlahan, kita dapat menerapkan rumus untuk jumlah pangkat ke-N dari bilangan-bilangan dalam deret natural (lihat Wikipedia) dan mendapatkan satu polinomial derajat ke-3. Yang jelas memiliki kompleksitas waktu yang konstan. (Apalagi “kesalahan” yang saya kutip di awal subjudul tidak muncul dengan sendirinya; rumusnya tetap benar).
Saya ulangi, ini untuk dimensi tetap dari himpunan dasar. Namun, saya yakin bahwa dengan bantuan metaprogramming Anda dapat "mengajarkan" kompiler agar ia dapat melakukan tugasnya untuk Anda. Kata penutup
Dalam simulator poker saya (Texas Hold'em), saya ingin menghitung dan menyimpan terlebih dahulu probabilitas kemenangan untuk semua kemungkinan kombinasi kartu tangan saya (2 buah) dan semua kartu gagal (3 kartu di atas meja). 52 himpunan dengan 2, 3, 47 himpunan bagian.
Dihitung dan disimpan.
Tetapi ketika tiba waktunya untuk membaca data dari suatu file untuk kombinasi tertentu, saya benar-benar tidak ingin menghitung sesuatu untuk waktu yang lama atau mencari dalam file gigabyte. Sekarang saya tinggal menentukan offset pada file dan membaca langsung apa yang saya butuhkan.
Menarik untuk memiliki buku referensi algoritma kombinatorial untuk semua objek kombinatorial, termasuk permutasi, kombinasi, penempatan, himpunan bagian, kombinasi dengan pengulangan, penempatan dengan pengulangan. Rumus eksplisit
Tautan
Lihat apa yang dimaksud dengan “Jumlah kombinasi” di kamus lain:
Buku