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

[mihiv]

sergey zhukov в сообщении #1422571 писал(а):

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

$$(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+x^2+x^3)(1+x+x^2)(1+x)=\dfrac {(1-x^4)(1-x^3)(1+x)}{(1-x)^2}$Поскольку нам нужен коэффициент при $x^3$, то можно опустить более высокие степени $x$, и тогда это эквивалентно:

$$\dfrac {(1-x^3)(1+x)}{(1-x)^2}=\dfrac {1+x-x^3+x^4}{(1-x)^2}\sim (1+x-x^3)\dfrac d{dx}(1+x+x^2+\dots )\sim (1+x-x^2)(1+2x+3x^2+4x^3)$$

где знак $\sim $ показывает, что две соединенные этим знаком п.ф. имеют одинаковый коэффициент при $x^3$. Что в общем не сильно проще.

[wrest]

Функция на PARI/GP

zhukov_cnk(v,n)={
my(f=x^0);
for(i=1,#v,f=f*Polrev(vector(min(v[i],n)+1,i,1)));
return(polcoef(f,n));
}

где
v - вектор с количествами элементов разных типов
n - из скольких элементов делать сочетания
функция возвращает искомое количество сочетаний

Пример ТС-а
? zhukov_cnk([3,2,1],3)
%1 = 6

[arseniiv]

(wrest)

А там нельзя возвращать замыкание (которое будет хранить уже вычисленный многочлен), которое будет выдавать коэффициент по запросу, так что можно будет не повторять вычисления в сценарии, когда нужно больше одного числа для того же кортежа кратностей? И было бы как-то так:

? c = zhukov_cnk′(v);
? c(3)
%1 = 6
? c(100500)
%2 = 0

(Лень ставить, так что мог неправильно угадать как будет выглядеть протокол.)

[wrest]

arseniiv
Можно:

zhukov_cnk_2(v)={
my(f=x^0);
for(i=1,#v,f=f*Polrev(vector(v[i]+1,i,1)));
return(Vecrev(f));
}

v -- вектор количеств элементов
Функция возвращает вектор с количествами перестановок (но смещенный по индексам на единицу, у pari индексы массивов с единицы нумеруются).
? zhukov_cnk_2([3,2,1])
%1 = [1, 3, 5, 6, 5, 3, 1]
? c=zhukov_cnk_2([3,2,1]);
? c[3+1]
%2 = 6

Я так понимаю, что коэффициенты симметричные выходят, так что можно и не переворачивать т.е. вместо Vecrev() использовать Vec().

Конечно если всего элементов меньше чем надо для сочетания, то количество сочетаний будет ноль, это в программе не проверяется.

А, или вы хотели сам многочлен а не его коэффицтенты? Тогда в функции писать return(f) а коэффициенты получать как polcoef(f,n) - тут без смещения уже, для коэффициента третьей степени пишем polcoef(f,3)

[wrest]

Чего-то меня вчера переклинило. Функции работают верно, но я зачем-то, не знаю зачем, использовал преобразование вектора в полином с переворотом коэффициентов, т.е. использовал функцию Polrev(). А надо было просто Pol(). Разницы нет потому, что все коэффициенты - единицы. Но если вдруг кто-то обратил внимание на это, то вот.

[sergey zhukov]

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

Ну да, я имел в виду небольшие упрощения в частных случаях

Понял. Упрощение для конкретного $k$. Можно его еще так понимать, что в процессе перемножения скобок степени больше $k$ можно просто отбрасывать на каждом шаге. Оно, кстати, и проще делается. Если количество элементов какого-нибудь типа больше $k$, то есть смысл считать его просто равным $k$. Тогда степеней больше $k$ в скобках просто не будет. Если таких случаев много, то получится много одинаковых скобок с многочленом степени $k$. Их можно перемножить отдельно, используя просто $C^k_n$. Так же, кстати, можно и с остальными скобками поступить. В итоге если у нас есть, например, $10$ типов элементов с количествами $1,1,1,2,2,2,3,3,3,4$ и мы хотим подсчитать число комбинаций по $k=3$, то получается

$$(1+x)^3(1+x+x^2)^3(1+x+x^2+x^3)^4$$

Одного типа элементов у нас $4$, но мы считаем, что $3$. Все три скобки раскрываются с использованием $C^k_n$, причем только до степени $k$, все остальные степени в скобках отбрасываем. В конце остается перемножить три подобных скобки без степеней.

wrest
Я не знаком с программированием. Что делает эта функция? Использует какие-то стандартные математические функции для перемножения скобок?

[wrest]

sergey zhukov в сообщении #1422799 писал(а):

Я не знаком с программированием. Что делает эта функция? Использует какие-то стандартные математические функции для перемножения скобок?

Первая создаёт полиномы, степени не больше чем количество элементов в сочетаниях, с единичными коэффициентами, перемножает эти полиномы и выводит коэффициент перед нужной степенью. То есть действует тупо по указанному ув. mihiv пути.
А вторая перемножает полиномы и выводит сразу все коэффициенты полинома-произведения.

[sergey zhukov]

wrest
Интересно, что та функция, с которой мы начали это обсуждение (которая давала все возможные разбиения множества простых чисел на две разные группы) - она же просто дает сумму всех этих коэффициентов итогового многочлена. Точнее, половину этой суммы.

[wrest]

sergey zhukov в сообщении #1422808 писал(а):

wrest
Интересно, что та функция, с которой мы начали это обсуждение (которая давала все возможные разбиения множества простых чисел на две разные группы) - она же просто дает сумму всех этих коэффициентов итогового многочлена. Точнее, половину этой суммы.

Меткое наблюдение! Но только эта сумма всех коэффициентов равна, в обозначениях первого поста темы, вот такому произведению: $\prod \limits _{i=1}^n (m_i+1)$
Это и понятно: каждая скобка-полином производящей функции им. mihiv состоит из $m_i+1$ членов, при умножении скобок члены плодятся каждый из одной скобки с каждым из другой (давая в коэффициенте единицу) так что всего получается произведение увеличенных на единицу количеств элементов.