Производящие функции для размещений с повторениями с ограничениями и без ограничений на число повторов

Теорема: Пусть множество М={х1,…,хn}.
Функции f (t, х1,…,хm)= ∏(1+xkt/1! + [xkt]2/2! + … + (xkt)Ck/Ck!) и
g (t)= f (t, 1,…1)= ∏(1+t/1! + t2/2! + … + tCk/Ck!)
являются производящими функциями для размещений и для числа размещений из n элементов, причём в каждом размещении элемент ХК встречается ≤ СК раз к= 1,2,..,n .

Доказательство: функция f(t,х1,…,хn)= ∏(1+xkt/1! + [xkt]2/2! + … + (xkt)Ck/Ck!) =
=((x1t)0/0!+(x1t)1/1!+..+(x1t)0C1 /C1! )*..*((xnt)0/0! + (xnt)1/1! +..+ (xnt)Cn/Cn! )=
= ∑[ ((x1t)a1/a1!+(x2t)a2/a2!+..+(xnt)an /an! )]=// cгруппируем относительно tr //=
= ∑ ( ∑x1a1x2a2..xnan/a1!a2!…an! tr
внутренняя сумма (обозначим ее hr(x1,…,xn) является коэффициентом при tr, перечисляет все сочетания из n по r. При этом в каждом сочетании элемент Xr встречается ak≤ СК раз, к= 1,2,..,n . Сочетания (Х1а1, .., Хnan) из r элементов, среди которых имеется ак элементов Хк, породят S размещений (перестановок) спецификации Anr(a1,a2,..,an) , причём S= r!/(a1!*a2!*..*an!). Тогда
функция g (t)= f (t, 1,…1)= ∏(1 + t/1! + t2/2! + … + tCk/Ck!) = ∑(∑1/a1!a2!..an!)tr = //умножим и разделим на r!// = ∑ (Anr(a1,a2,..,an) tr/r! ⇒ f (t, х1,…,хn ) есть искомая производящая функция для размещений с повторами из n элементов множества М (с учётом сделанного выше замечания относительно S). Причём в каждом размещении элемент ХК встречается ≤ СК раз к= 1,2,..,n .
В функции f (t, х1,…хn ) положим х1=…=хn=1 , тогда функция g (t)= f (t, 1,…1) является энумератором для числа размещений с повторами из n элементов, причём каждое размещение содержит элемент Хk не более чем Сk раз к= 1,2,..,n.

Коэффициент при tr/r! есть число размещений из n элементов по r, причём в каждом размещении элемент ХК встречается не более СК раз к= 1,2,..,n.

Замечание: для числа размещений с повторами без ограничений на число повторов производящая функция g(t)= (1+t/1!+t2/2!+t3/3!+…)n=ent= ∑nr/tr/r!. Коэффициент nr при tr/r! равен числу всех размещений без ограничений на число повторов из n элементов по r, т.е. числу всех наборов длины r из n элементов.


Комментарии запрещены.





Статистика

Рейтинг@Mail.ru