Число сочетаний из n по k с тождественными элементами

[sergey zhukov]

Хорошо известны две комбинаторные формулы: $C^k_n$ и $\bar{C}^k_n$.

Первая дает число разных сочетаний размера $k$ в случае, когда у нас $n$ типов объектов, и все в одном экземпляре.
Вторая дает число разных сочетаний размера $k$ в случае, когда у нас $n$ типов объектов, и все в неограниченном количестве.

На практике часто встречается промежуточный случай, когда есть $n$ типов объектов, причем объектов одного типа одно количество, другого типа - другое и т.д. Как получить число сочетаний из $n$ типов объектов по $k$, если известны количества $m_1...m_n$ объектов каждого типа?

Например, возьмем множество объектов $2, 2, 2, 3, 3, 5$. Здесь $n=3$, $m_1=3$, $m_2=2$, $m_3=1$. Допустим, мы хотим найти количество всех различных сочетаний по $3$ ($k=3$). Они будут такими:

$2, 2, 2$
$2, 2, 3$
$2, 2, 5$
$2, 3, 3$
$2, 3, 5$
$3, 3, 5$

Какая формула описывает их количество в общем случае?

Предположим, что $m_1...m_n$ отсортированы по возрастанию.
Очевидно, что если $m_1>k$, то задача сводится к неограниченному случаю $\bar{C}^k_n$.
Если $m_1<k$, но $m_1+m_2 \geqslant k$ то можно из неограниченного случая $\bar{C}^k_n$ вычесть число комбинаций, в которых объект с количеством $m_1$ используется более $m_1$ раз, т.е. $\bar{C}^k_n - \bar{C}^1_{n-1} - \bar{C}^2_{n-1}…- \bar{C}^{k-m_1}_{n-1}$. Такое же вычитание можно сделать и для $m_2$, если одновременно $m_1 <k$, $m_2<k$, но $m_1+m_2 \geqslant k$
Но если суммарное количество обьектов двух (а тем более нескольких) самых малочисленных типов слишком мало, т.е. $m_1 +m_2<k$, то просто так вычесть независимо все лишние комбинации отдельно для $m_1$ и отдельно для $m_2$ не получается. Некоторые комбинации удаляются дважды. Например, если применить этот принцип к задаче выбора четырех разных объектов из набора $2, 2, 2, 3, 4, 5, 5, 5$ то "запрещенная" комбинация $3, 3, 4, 4$ вычитается два раза отдельно по $3$ и отдельно по $4$.

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:


- отсутствуют собственные содержательные попытки решения задач(и).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[arseniiv]

Люди избегают рекуррентных соотношений, интересно почему.

Давайте обозначим интересующее количество $C(m_1,\ldots,m_s; k)$ и будем сокращать подпоследовательности $m_i,\ldots,m_j$ как $\overline m$. Тогда мы можем получить такую связь:

$$C(\overline m, m'; k) = C(\overline m; k) + C(\overline m; k-1) + \ldots + C(\overline m; k-\min(m', k)),$$

а именно: получить сочетание из набора $\overline m, m'$ элементов с $k$ элементами можно, взяв сочетание из набора $\overline m$ с $k$ элементами, или взяв сочетание из того набора с $k-1$ элементами и ещё один элемент из кучки $m'$ оставшихся неразличимых, и т. д. до сочетания из $k-\min(m', k)$ элементов из $\overline m$ и наибольшего возможного количества элементов из последней кучки, что и есть $\min(m', k)$.

В общем случае мы можем даже записать
\small$${C(\overline m, \overline m'; k) = \sum_{i\in\mathbb Z}C(\overline m; i)C(\overline m'; k-i),}$$
имея в виду, что сочетания с отрицательным числом элементов не существуют, а с нулевым их всегда ровно одна штука; \small${\overline m, \overline m'}$ — две кучки элементов, не содержащие одновременно элементы одинакового типа. Такая форма может тоже оказаться полезной, по крайней мере она симметричнее предыдущей, но для практических вычислений предыдущей достаточно.

Начальным условием будет $C(m; k) = (0\leqslant k\leqslant m)\mathbin? 1 : 0$ — мы можем выбрать единственным способом столько неразличимых элементов, сколько у нас в достатке, но не больше, и не отрицательное число.

Вот теперь можно попробовать раскрутить эти соотношения на что-то более простое. Можно например рассмотреть сначала ровно две группы, потом три группы, потом четыре и т. д.. Для двух групп мы получим из первого равенства, что

$$C(m_1, m_2; k) = C(m_1; k) + \ldots + C(m_1, k-\min(k, m_2)),$$

где ненулевые слагаемые начинаются с $C(m_1; m_1)$, каждое ненулевое слагаемое — единица, а всего их в формуле $\min(k, m_2) + 1$. Из всего этого, если это изложить более аккуратно, имеем в конечном итоге

$$C(m_1, m_2; k) = k + 1 - \max(k - m_1, 0) - \max(k - m_2, 0) - \max(-k - 1, 0) + \max(k - 1 - m_1 - m_2, 0),$$

где последние два слагаемых можно выкинуть, если $0\leqslant k\leqslant m_1+m_2$.

От максимумов или подобного им должно быть трудновато избавиться, потому что $C(\overline m; k)$ — это число решений системы линейных неравенств $0\leqslant k_i\leqslant m_i$ на гиперплоскости $\sum_i k_i = k$.

[mihiv]

Общую формулу получить вряд ли получится, но для любого набора элементов можно построить производящую функцию. Покажем это на примере набора элементов $2,2,2,3,3,5$. Производящая функция будет иметь вид:$P(x)=(1+x+x^2+x^3)(1+x+x^2)(1+x)$. Способ построения производящей функции очевиден. Число сочетаний по 3 равно коэффициенту при $x^3$ в полиноме $P(x)$.

[sergey zhukov]

arseniiv
Если я правильно понял, итерационная схема для примера $2, 2, 2, 3, 3, 5$ получается такая:

Каждое $C$ верхнего уровня $n$ представляется, как сумма $C$ на $n-1$ уровне, причем в этой сумме $k$ пробегает значения от $k$ до $\max (0, k-m_i)$ , где $k$ - это аргумент $C$ предыдущего уровня, $m_i$ - количество элементов типа $i$ в исходном множестве, которые мы отбрасываем на данном переходе. На нижнем уровне $n=1$ все $C$ просто равны $1$.
Поскольку результат не должен зависеть от порядка $m_i$, которые мы отбрасываем на каждом шаге, я попробовал сначала порядок $m_i=1, 2, 3$, а потом наоборот $m_i=3, 2, 1$. Получается одно и то же, но во втором случае правила для $k$ более сложные (я их не соблюдал, поэтому просто вычеркнул случаи, где $k>m$ уже в самом конце). Проще работать с $m_i$, сортированными в порядке возрастания.

mihiv
Отличное решение. Как я понимаю, число скобок - это число разных типов объектов, максимальная степень в каждой скобке - это количество объектов данного типа. Раскрытие скобок дает количества сразу всех сочетаний размером $k=0...\sum\limits_{i}^{n}m_i$, как коэффициент при $k$-ой степени.

[arseniiv]

sergey zhukov
Да, вы всё правильно понимаете в обоих случаях.


Да, почему-то забыл такую красивую производящую функцию для этого случая, хотя когда-то сталкивался. Зато ещё не поздно порадовать обобщением: если элементов какого-то сорта неограниченное количество, можно вместо соответствующей скобки взять ряд $1 + x + x^2 + \ldots$; результатом в целом будет тоже не полином, а формальный ряд, но с ними работать не сильно сложнее.

Вообще производящие функции часто облагораживают найденные рекуррентности (и потом уже из них можно найти что-то замкнутое, но здесь вот не судьба), и формула в фрагменте мелким шрифтом вообще говоря так и просится (она как раз дала бы (это видно сейчас, но не вспомнилось вчера), что п. ф. для $C(\overline m, \overline m')$ — произведение п. ф. для $C(\overline m)$ и $C(\overline m')$; а выражение для $C(m)$ уже дало бы многочлен $1 + x + \ldots + x^m$), но и поздно уже это делать, когда п. ф. найдена, и найти её с нуля по-моему даже проще, чем писать то, что я писал.

[wrest]

mihiv в сообщении #1422335 писал(а):

Покажем это на примере набора элементов $2,2,2,3,3,5$. Производящая функция будет иметь вид:$P(x)=(1+x+x^2+x^3)(1+x+x^2)(1+x)$. Способ построения производящей функции очевиден.

Гениально. Но раскрытие скобок все равно похоже на перебор. Или есть таки путь покороче?

[arseniiv]

Да, чтобы узнать коэффициент при одной степени, эффективно мы будем считать по тем рекуррентным формулам — как минимум делать свёртки маленьких последовательностей, задаваемых отдельными множителями, — но если мы уже записали функцию алгебраически, то часть вычислений мы уже сделали и при вычислении коэффициентов повторять каждый раз не будем, ну и вычислить сразу все их выйдет довольно удобно, а то и быстрее, если приделать векторизацию или что там.

[mihiv]

Можно еще немного сократить вычисления, если умножить и поделить каждую скобку на $(1-x)$ тогда каждая скобка сведется к двум слагаемым и все выражение умножится на производную порядка $(n-1)$ от геометрической прогрессии.

[sergey zhukov]

mihiv

Я так понял, что для нашего случая это:

$$(1+x+x^2+x^3)(1+x+x^2)(1+x)=(1-x^4)(1-x^3)(1+x) \frac{(1-x)}{(1-x)^3}= (1-x^4)(1-x^3)(1+x)\frac{1}{2}( \frac{(1-x^3)}{(1-x)})^{\prime \prime}=$$

$$=(1-x^4)(1-x^3)(1+x)\frac{1}{2}(1+x+x^2+x^3)^{\prime \prime}=(1-x^4)(1-x^3)(1+x)(1+3x)$$

[wrest]

sergey zhukov
Это зачем? Просто раскройте скобки. Коэффициенты при степенях будут искомыми количествами сочетаний для $k$ равных показателям степеней.

-- 27.10.2019, 00:26 --

$(1+x+x^2+x^3)(1+x+x^2)(1+x)=1 x^0+ 3 x ^1+ 5 x^2 + 6 x^3 + 5 x^4 + 3 x^5 + 1x^6$

[sergey zhukov]

wrest
В случае большого числа слагаемых в каждой скобке вместо прямого раскрытия проще превратить задачу в раскрытие скобок, в каждой из которых только два слагаемых, и эти скобки умножены на производную порядка $(n-1)$ от прогрессии $1+x^2+x^3...x^n$. Производную просто найти, и она добавляет еще одну скобку с двумя слагаемыми. Это хорошо работает в частных случаях.

[arseniiv]

Ненене, $(1-x)^{-3} = 1 + 3x + 6x^2 + 10x^3 + \ldots$ — п. ф. треугольных чисел, это бесконечный ряд. И зря вы не перемножили $(1 + x)(1 - x)$ как две первых скобки (наверно). Прийти к треугольным числам можно и через умножение (свёртка последовательности единиц дважды даёт $1,2,3,\ldots$, а трижды уже частичные суммы этой), и через дифференцирование, что в данном единственном случае даст (с точностью до факториала) то же. (Дифференцирование п. ф. умножает элементы последовательности $a_n, n\geqslant0$ на $n$, а потом выкидывая первый член последовательности.)

[sergey zhukov]

Да, я там неправильно производную вычислил. Даже не заметил, что степень многочлена выросла на 3.

Мне ясно только, что

$$(1+x+x^2+x^3)(1+x+x^2)(1+x)=(1-x^4)(1-x^3)(1-x^2)\frac{(1-x)^3}{(1-x)^3}$$

И что

$$\frac{(1-x)^3}{(1-x)^3}=\frac{1}{2}\Big (\frac{1-x^3}{1-x}\Big )^{\prime \prime}$$

Не могу понять, как это помогает сократить вычисления?