Combinatorial Problem

Combinatorial Problem

kombinasi analisis kadang-kadang mudah dengan formula standar yang tersedia. Misalnya, jumlah permutasi dari N item hanya N! (N faktorial). Jika salah satu item (S) adalah sama, Anda hanya membagi dengan S! untuk mendapatkan jawaban tanpa kesedihan. Demikian pula, jumlah kombinasi (pilihan tanpa memperhatikan urutan) dari N item diambil R pada suatu waktu mudah ditemukan dengan N! / R! (N-R) !.

Sayangnya, hal itu tidak lagi menjadi mudah ketika Anda mempertimbangkan kombinasi mana beberapa item yang sama, atau item partisi ke dalam kelompok. Rumus memang ada untuk banyak situasi, tapi kadang-kadang mereka terlalu rumit untuk menjadi berguna. Dengan kata lain, sering akan lebih cepat untuk memecahkan masalah secara langsung oleh komputer daripada mencoba untuk mengatur dan memecahkan rumus. Setidaknya itulah saya mengambil itu, memiliki pengetahuan yang baik dari matematika praktis tetapi umumnya kehilangan di daerah seperti kalkulus.

Semua Spots Dibuat Sama

Perhatikan masalah berikut:

Jika kartu spot (9-2) di masing-masing sesuai dianggap sama, berapa banyak penawaran yang berbeda ada?

Dengan kata lain, di masing-masing sesuai hanya kehormatan (A-10) yang unik, dan delapan peringkat yang lebih rendah seperti 'x' kartu. Jawaban yang jelas adalah, "Siapa yang peduli?" Tapi masalahnya adalah menarik. Sangat mudah untuk menentukan jumlah penawaran ketika semua kartu yang unik:! (! 13) 52/4, tapi sekarang itu menjadi tugas yang menakutkan dengan ada rumus yang tersedia, atau setidaknya tidak ada yang saya bisa merancang. Untuk menemukan jawabannya, saya mengambil keuntungan dari salah satu usaha konyol saya sebelumnya - menghitung dealprints - dan kekerasan sedikit oleh komputer.

Pertama, mempertimbangkan masalah partisi lima penghargaan dari satu setelan menjadi empat tangan. Tabel berikut menunjukkan cara ini dapat dilakukan. (Jumlah dapat diverifikasi dengan rumus sebagai sejumlah cara untuk mendistribusikan lima item dalam empat kelompok = 4 ^ 5 = 1024.)

Untuk menjelaskan perhitungan, pertimbangkan kasus ketika kehormatan didistribusikan 3-1-1-0. Tiga penghargaan dapat dipilih di 10 cara (5C3), kehormatan selanjutnya dapat dipilih dengan 2 cara (2C1), maka penghormatan terakhir dipaksa. Ini berarti ada 10 × 2 = 20 kombinasi untuk setiap distribusi tertentu. Karena pola 3-1-1-0 memiliki 12 permutasi, ada 20 × 12 = 240 Total kombinasi. Kasus-kasus lainnya ditentukan sama.

Langkah selanjutnya adalah menentukan berapa banyak di atas 1.024 kombinasi akan masuk ke masing-masing dari 39 distribusi jas generik. Misalnya, jika gugatan dibagi 4-4-3-2, jelas bahwa tidak ada 5-0-0-0 kombinasi yang mungkin karena Anda tidak dapat menempatkan lima kartu di satu tangan. Selanjutnya, perlu untuk memeriksa setiap permutasi secara terpisah sejak gugatan dibagi, katakanlah, 5-4-3-1 akan menerima hanya setengah dari 4-1-0-0 kombinasi. Ini menghasilkan tabel berikut.

Apa tabel di atas menunjukkan adalah sejumlah cara lima kehormatan dapat didistribusikan untuk setiap distribusi jas. Misalnya, untuk setiap pola 4-4-3-2 jas, ada 900 cara untuk mendistribusikan kartu kehormatan. Delapan kartu tempat hanya akan mengisi ruang yang tersisa, tetapi ini tidak bisa dibedakan per kondisi masalah.

Semua yang tersisa adalah, untuk setiap dealprint tertentu, untuk mencari empat pola gugatan di tabel di atas dan memperbanyak faktor yang sesuai untuk menentukan jumlah penawaran yang mungkin untuk dealprint itu; kemudian menambahkan total untuk semua dealprints. Mengingat ada 37.478.624 dealprints tertentu, ini masih merupakan tugas berat. Untungnya, itu sepotong kue untuk komputer. Butuh beberapa jam untuk menulis dan debug program, tetapi sekali menjalankannya kembali jawabannya dalam waktu sekitar 15 detik: 

800,827,437,699,287,808

Jadi, ada lebih dari 800 kuadriliun penawaran yang berbeda jika kartu spot (2-9) di masing-masing sesuai dianggap sama. Hal ini mungkin tampak seperti banyak, dan itu pasti, tapi itu sangat kecil dibandingkan dengan 53+ octillion mungkin penawaran jembatan.

 

Kasus Generalized

Masalah ini dapat digeneralisasi untuk jumlah kartu yang unik di masing-masing sesuai, seperti dirangkum oleh tabel berikut. The "Gugatan Makeup" menunjukkan penampilan masing-masing sesuai, dengan asumsi kartu unik yang ditunjuk dari atas.

Mengamati bahwa dengan tidak ada kartu yang unik (baris atas), jumlah penawaran sama dengan jumlah dealprints tertentu. Juga mencatat bahwa tidak ada perbedaan antara 12 dan 13 kartu yang unik; dalam kedua kasus itu menghasilkan jumlah penuh penawaran. Hal ini jelas jika Anda berpikir tentang hal itu, karena dengan kartu hanya satu 'x', semua kartu yang efektif yang unik.

Sekarang, jika seseorang dapat menunjukkan formula mana saya bisa pasang di, mengatakan, 7 sebagai jumlah kartu yang unik (dan nilai-nilai lain yang sesuai seperti 52, 13, dan 4) untuk menghasilkan jawaban 5197480921767366548160, saya akan benar-benar terkesan.

Referensi :http://www.rpbridge.net/7z74.htm