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


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

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

Доказательство: функция f(t,х1,…,хn)= ((x1t )0+(x1t)1+(x1t)2+…)(x2t)0+(x2t)1+(x2t)2+…)*…..*((xnt)0+(xnt)1+(xnt)2+ …)=
= \\ группируем относительно tr \\=
= ∑{∑[x1a1x2a2…xnan]}tr; \\ в [ ] –одно сочетание из n по r с повторами элементов.
\\ в { }- все сочетания с повторами из n по r является порождающей функцией для сочетаний с повторами из n элементов множества М.

В функции f (t, х1,…,хn ) положим х1=…=хn=1 ,
тогда g (t)= f (t, 1,…1)= ∏(1 + t + t2 + …) = ∑{∑[x1a1x2a2…xnan]}tr\\ в [ ] –одно сочетание с повтором
\\ в { }- число всех сочетаний из n по r с повторами элементов без ограничения на число повторов.

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

Замечание: g (t)= f (t, 1,…1)= ∏(1 + t + t2 + …) =(1 + t + t2 + …)n = \\ в скобках сумма членов геом. прогрессии\\ =(1/1-t)n=(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 = ∑Arn+r-1/r!)tr = ∑(n+r-1)!/((n+r-1-r)!r!)tr = Crn+r-1 tr) .


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




Статистика