[Комбинаторика] Число сочетаний игральных кубиков

asgrig

Есть x=5 пронумерованных кубиков с y=6 гранями
Откуда получается формула (x-1+y)!/x-1)!*y!) для числа уникальных сочетаний?
Комбинаторику просто последний раз видел лет 10-12 назад. На пальцах можно объяснить?

lordkay

сочетания=размешения/число перестановок
размещения k из n элементов - первый можно разместить (n -1) способом, второй (n -2) и k-ый (n-(k -1 способами
в итоге получаем, что размещений n!/(n-k)!
а для сочетаний надо еще поделить на k!

lordkay

>>сочетания=размешения/число перестановок
потому что из каждого сочетания можно сделать k! перестановок

asgrig

как выражаются k и n через x и y?

gr_nik

Тебе надо узнать, сколько единиц, двоек, троек и так далее может быть, общее их число должно быть 5.
Обозначим a_i - количество выпавших на кубиках значений i.
Тогда надо найти количество таких комбинаций a_i, что их сумма равна x, и каждый a_i не меньше нуля.
Пусть b_i=a_i+1. Тогда это условие преобразуется в условие: найти количество таких комбинаций b_i, что их сумма равна x+y, и каждый b_i не меньше 1.
Это всё равно, что между x+y шариками расставить y перегородок. Число шариков между n и (n+1) перегородками равно b_i.
Тогда возможных мест для перегородок x+y-1, а значит количество способов их расставить равно количеству сочетаний из (x+y-1) по y элементов, то есть написанным (x-1+y)!/x-1)!*y!)
Кривовато написал, но суть такая.

lordkay

в случае кубиков это сочетания с повторениями
можно построить соответствие между сочетаниями с повторениями и последовательностями из 0 и 1
пишем столько единиц, сколько элементов такого вида входит в сочетание, группы единиц отделяем нулями (в конце ноль не ставим получаем для каждого сочетания с повторениями последовательность из n единиц и m - 1 нулей.
получаем что число сочетаний с повторениями равно числу сочетаний n элементов из n+m-1
Оставить комментарий
Имя или ник:
Комментарий: