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

Доказательство: функция f(t,х₁,…,х_n)= ∏(1+x_kt/1! + [x_kt]²/2! + … + (x_kt)^C_k/C_k!) =
=((x₁t)⁰/0!+(x₁t)¹/1!+..+(x₁t)^0C₁ /C₁! )*..*((x_nt)⁰/0! + (x_nt)¹/1! +..+ (x_nt)^C_n/C_n! )=
= ∑[ ((x₁t)^a1/a₁!+(x₂t)^a2/a₂!+..+(x_nt)^an /a_n! )]=// cгруппируем относительно t^r //=
= ∑ ( ∑x₁^a1x₂^a2..x_n^an/a₁!a₂!…a_n! t^r
внутренняя сумма (обозначим ее h_r(x₁,…,x_n) является коэффициентом при t^r, перечисляет все сочетания из n по r. При этом в каждом сочетании элемент X_r встречается a_k≤ С_К раз, к= 1,2,..,n . Сочетания (Х₁^а1, .., Х_n^an) из r элементов, среди которых имеется а_к элементов Х_к, породят S размещений (перестановок) спецификации A_n^r(a₁,a₂,..,a_n) , причём S= r!/(a₁!*a₂!*..*a_n!). Тогда
функция g (t)= f (t, 1,…1)= ∏(1 + t/1! + t²/2! + … + t^Ck/C_k!) = ∑(∑1/a₁!a₂!..a_n!)t^r = //умножим и разделим на r!// = ∑ (A_n^r(a₁,a₂,..,a_n) t^r/r! ⇒ f (t, х₁,…,х_n ) есть искомая производящая функция для размещений с повторами из n элементов множества М (с учётом сделанного выше замечания относительно S). Причём в каждом размещении элемент Х_К встречается ≤ С_К раз к= 1,2,..,n .
В функции f (t, х₁,…х_n ) положим х₁=…=х_n=1 , тогда функция g (t)= f (t, 1,…1) является энумератором для числа размещений с повторами из n элементов, причём каждое размещение содержит элемент Х_k не более чем С_k раз к= 1,2,..,n.

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

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

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