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

Теорема: Пусть М={x1,x2,…,xn}. Функции f(t,x1, 2, …, n) = ∏(1+xkt) и g(t) = f(t, 1, 1, …, 1) = (1 + t)n есть порождающие функции для сочетаний и для числа сочетаний из n элементов.

Доказательство: Разложим функцию f в степенной ряд по степеням t.

f(t,x1, 2, …, n) = ∏(1+xkt) = (1 + xkt)…(1 + xkt) = ∑(x1t)a…(xnt)an = {сгруппируем относительно tr }= ∑ (∑x1a1x2a2…xnan))tr

Слагаемые x1t,…,xnt называются кодирующими множителями. Функция f(t,x1,…,xn) есть порождающая функция для сочетаний из n по r (из M по r) без повторов элементов в каждом сочетании. Положим x1=…=xn=1. Тогда функция

g(t) = f(t, 1, 1, …, 1) = ∏(1+t) = (1+t)n = ∑x1a1x2a2…xnan = ∑ ( ∑1a1…1an)tr

g(t) есть порождающая функция (энумератор) для числа сочетаний из n элементов без повторений.

Замечание:
1) бином Ньютона (1 + t)n = ∑Cnrtr.
2) Положим в предыдущем равенстве t=a/b и умножим результат на bn, тогда получим (a+b)n = ∑Cnrarbn-r.
3) Сумма биномиальных коэффициентов 2n = ∑Cnr
4) (1 — t)n = ∑(-1)rCnrtr.
5) 0 = ∑(-1)rCnr.
6) (∑ar)n = ∑n!/(n1!…nk!)a1n1..aknk.

Сочетания с повторами с ограничениями на число повторов.

Теорема: Пусть М={x1,x2,…,xn}.
Функции f(t, x1,x2,…,xn) = ∏(1+xkt + (xkt)2 + … + (xkt)Ck)

g(t) = f(t, 1, 1, …,1) = ∏(1 + t + t2 + … + tCk) есть порождающие функции для сочетаний и для числа сочетаний из n элементов соответственно. Каждое сочетание имеет ≤Ck элементов xk, k = 1, 2, …, n

Доказательство:
f(t, x1, …, xk) = ∏(1 + xkt + (xkt)Ck = ∑ (∑x1a1..xnan)tr

Все сочетания из n по r в повторами, в которых элемент xk встречается ≤Сk раз, k=1,2,…,n.

Это порождающая функция для числа сочетаний из n – элементного множества М. Каждое сочетание имеет не более, чем Ck элементов xk, k=1,2,…,n. Тогда при x1=…=xn=1 функция
g(t) = f(t, 1,1,..,1) = ∑( ∑1a1..1an)tr
Число всех сочетаний из n по r с повторами элементов, причем элемент xk встречается ≤Сk раз (в каждом сочетании), k=1,2,…,n.

Эта функция энумератор для числа сочетаний из n по r с повторами, причем в каждом сочетании элемент xk встречается ≤Сk раз, k=1,2,…,n.


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





Статистика

Рейтинг@Mail.ru