Теорема: пусть множество М={х₁,…,х_n}

Функции f (t, х₁,…,х_n)= ∏ (1+x_kt + [x_kt]² + …) и g (t)= f (t, 1,…1) = ∏ (1+t+t² + …)
являются порождающими функциями для сочетаний и для числа сочетаний из n элементов с повторами без ограничений на число повторов.

Доказательство: функция f(t,х₁,…,х_n)= ((x₁t )⁰+(x₁t)¹+(x₁t)²+…)(x₂t)⁰+(x₂t)¹+(x₂t)²+…)*…..*((x_nt)⁰+(x_nt)¹+(x_nt)²+ …)=
= \\ группируем относительно t^r \\=
= ∑{∑[x₁^a1x₂^a2…x_n^an]}t^r; \\ в [ ] –одно сочетание из n по r с повторами элементов.
\\ в { }- все сочетания с повторами из n по r является порождающей функцией для сочетаний с повторами из n элементов множества М.

В функции f (t, х₁,…,х_n ) положим х₁=…=х_n=1 ,
тогда g (t)= f (t, 1,…1)= ∏(1 + t + t² + …) = ∑{∑[x₁^a1x₂^a2…x_n^an]}t^r\\ в [ ] –одно сочетание с повтором
\\ в { }- число всех сочетаний из n по r с повторами элементов без ограничения на число повторов.

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

Замечание: g (t)= f (t, 1,…1)= ∏(1 + t + t² + …) =(1 + t + t² + …)ⁿ = \\ в скобках сумма членов геом. прогрессии\\ =(1/1-t)ⁿ=(1-t)^-n = ∑(-n)(-n-1)(-n-2)…(-n-r+1)/r! (-t)^r = ∑(n)(n+1)(n+2)…(n+r-1)/r! (t)^r = ∑A^r_n+r-1/r!)t^r = ∑(n+r-1)!/((n+r-1-r)!r!)t^r = C^r_n+r-1 t^r) .

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