286
правок
Изменения
fix
{{Утверждение
|statement=
Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">M=MSet(A)</tex> {{---}} множество всех мультимножеств <ref>[[wikipedia:Multiset|Wikipedia {{---}} Мультимножества]]</ref> из элементов <tex dpi="130">A</tex>, <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{l}\}</tex> {{---}} количество объектов веса от <tex dpi="130">1</tex> до <tex dpi="130">l</tex>. Тогда '''количество мультимножеств''' из объектов суммарного веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">M_{n}=m_{n, n}</tex>, где <tex dpi="150">m_{n, k}=\sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i} m_{n-ik, k-1}</tex> {{---}} количество таких мультимножеств, которые содержат объекты, вес которых не больше чем <tex dpi="130">k</tex>. Причем <tex dpi="150">m_{0, i} = 1</tex>, так как не набирать никакой вес есть один способ, а <tex dpi="150">m_{i, 0} = 0</tex>, <tex dpi="150"">i \ne 0</tex>, так как нельзя набрать положительный вес из ничего.
|proof=Рассуждения аналогичны рассуждениям <tex dpi="130">PSet</tex>, однако теперь мы можем брать один и тот же элемент несколько раз. То есть для подсчета вместо обычных сочетаний нужно использовать сочетания с повторениями.
}}
==Метод производящих функций==
Такие большие группы часто анализируют с помощью [[Производящая функция|производящих функций]]. Один из популярных методов {{---}} метод символов <ref>[[wikipedia:Symbolic method (англ. ''combinatorics) | Wikipedia {{---}} Symbolic method'')]]</ref>. Он использует внутреннюю структуру объектов для получения производящих функций. В случае непомеченных объектов, как и в анализе в нашей статье, считается, что нет объектов нулевого веса. Иногда для удобства их добавляют, чтобы показать наличие одного пустого множества.
При непомеченных объектах рассмотренные классы имеют следующие производящие функции:
Аналогичные рассуждения можно провести и для больших <tex dpi="130">k</tex>, однако расчеты быстро становятся сложными. Классический способ исправления таких вопросов {{---}} [[Лемма Бёрнсайда и Теорема Пойа#Теорема Пойа | теорема Пойа]].
Однако в методе символов предлагается более глобальный подход, основанный на многомерных производящих функциях и использующий ряд Бюрмана—Лагранжа Бюрмана-Лагранжа <ref>[[wikipedia:Lagrange inversion theorem | Wikipedia {{---}} Lagrange inversion theorem]]</ref>. В общем случае, используя метод символов, производящие функции ограниченных конструкций можно подсчитать следующим способом:
{| class="wikitable"
