Об одной комбинаторной задачке...

Вот здесь я писал:

Кстати, если порядок рюмок неразличим, у нас всего 2 варианта:

(Б,Б,Б)
(Б,Б,С)

Подумайте - какие здесь работают комбинаторные законы?

На самом деле, думать можно очень долго - под известные комбинаторные формулы такая задача просто не подходит.

В общем виде условие можно сформулировать так:

Имеется N объектов, относящихся к L сортам.

Количество объектов каждого сорта известно и равно k1, k2, ..., kL, сумма ki=N.

Определить число различных сочетаний по M объектов из N, если объекты, относящиеся к одному сорту, считаются неразличимыми между собой.

Доступный пример: N=4, L=2, k1=3, k2=1, M=3, например, имеем 3 белых рюмки и 1 синюю.

Число сочетаний по 3 из 4 равно в данном случае 2 - (Б, Б, Б) и (Б, Б, C).

Формула числа сочетаний С₄³ даст 4, так как в ней все объекты считаются различимыми.

Под сочетания с повторениями, число которых здесь = 20, наш случай тем более не подходит - неразличимы-то только объекты одного вида.

Известная формула для числа различных перестановок на множестве из n элементов, среди которых имеется ki элементов i-го вида - нам тоже не подойдёт, у нас не перестановки.

Видимо, решать нужно так:

найти число решений уравнения
x1 + ... + xL = M
при ограничениях
0 <= x₁ <= k₁, ..., 0 <= x_L <= k_L
Формула для числа решений выводится при этом индуктивно.

Фактически, всё свелось к решению диофантова уравнения "в общем виде", а это невозможно (десятая проблема Гильберта, алгоритмическая неразрешимость которой считается доказанной). Похоже, что простой замкнутой формулы нет в принципе. Сложный расчёт с вложенными суммами можно сделать, но вычисление по такой формуле-монстру мало чем будет отличаться просто от перебора. Ещё существуют производящие функции - но практический счёт они никак не упростят. Лучше всего - рекуррентный подсчёт с конкретными числами.

Ну а само по себе приведённое уравнение вполне исследовано - например, известно, что диофантово уравнение x1 + ... + xL = M имеет СM-1L-1 различных решений в натуральных числах. Увы, нам это не поможет - скажем, имеем 3 белых рюмки, 2 синих, выбираем всего 2 (L=2, M=2, формула даёт C11, на самом деле ответ = 3 (ББ, БС, СС).

Если учесть "вырожденные" решения уравнения, то есть, случаи, когда какого-то вида объектов нет в наборе, и соответствующий xi=0, для него формула будет CM+L-1L-1

Пример того, что и эта формула не подходит - 3 белых, 1 синяя, выбираем всего 3 (L=2, M=3): C41=4

Это потому, что посчитались и те комбинации, для которых не хватит рюмок (2 последних):

ББС
БББ
БCC
ССС

Можно попытаться вычитать из СM+L-1L-1 (число сочетаний с перестановками для нашей задачи) все лишние "цэшки", которые получаются при ki<M (если не хватает рюмок какого-то вида, их число меньше числа выбираемых M), я попытался... Убив кучу времени, получил дикую и неуниверсальную при этом формулу, убедился в правильности выделенного красным :)

30.09.2011, 23:34 [11441 просмотр]