Теорема: Пусть М={x₁,x₂,…,x_n}. Функции f(t,x₁, ₂, …, _n) = ∏(1+x_kt) и g(t) = f(t, 1, 1, …, 1) = (1 + t)ⁿ есть порождающие функции для сочетаний и для числа сочетаний из n элементов.

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

f(t,x₁, ₂, …, _n) = ∏(1+x_kt) = (1 + x_kt)…(1 + x_kt) = ∑(x₁t)^a…(x_nt)^an = {сгруппируем относительно t^r }= ∑ (∑x₁^a1x₂^a2…x_n^an))t^r

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

g(t) = f(t, 1, 1, …, 1) = ∏(1+t) = (1+t)ⁿ = ∑x₁^a1x₂^a2…x_n^an = ∑ ( ∑1^a1…1^an)t^r

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

Замечание:
1) бином Ньютона (1 + t)ⁿ = ∑C_n^rt^r.
2) Положим в предыдущем равенстве t=a/b и умножим результат на bⁿ, тогда получим (a+b)ⁿ = ∑C_n^ra^rb^n-r.
3) Сумма биномиальных коэффициентов 2ⁿ = ∑C_n^r
4) (1 — t)ⁿ = ∑(-1)^rC_n^rt^r.
5) 0 = ∑(-1)^rC_n^r.
6) (∑a_r)ⁿ = ∑n!/(n₁!…n_k!)a₁ⁿ¹..a_k^nk.

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

Теорема: Пусть М={x₁,x₂,…,x_n}.
Функции f(t, x₁,x₂,…,x_n) = ∏(1+x_kt + (x_kt)² + … + (x_kt)^Ck)

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

Доказательство:
f(t, x₁, …, x_k) = ∏(1 + x_kt + (x_kt)^Ck = ∑ (∑x₁^a1..x_n^an)t^r

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

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

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

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