Изменения

Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">S=Seq(A)</tex> {{---}} множество всех последовательностей из элементов <tex dpi="130">A</tex>, <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{m}\}</tex> {{---}} количество объектов веса <tex dpi="130">\{1 \ldots m\}</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда '''количество последовательностей''' веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">S_{n}=\sum_{i=1}^{n} w_{i} S_{n-i}</tex>.

:<tex dpi="150">S_{n}=\sum_{i=1}^{n} T_{i} S_{n-i}=\sum_{i=1}^{n} S_{i-1} S_{n-i}=\sum_{i=0}^{n-1} S_{i} S_{n-i-1}=C_{n}</tex>, где <tex dpi="150">C_{n}</tex> {{---}} <tex dpi="150">n</tex>-ое [[Числа Каталана|число Каталана]].

Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">S=PSet(A)</tex> {{---}} множество всех множеств составленных из элементов <tex dpi="130">A</tex>, <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{k}\}</tex> {{---}} количество объектов веса <tex dpi="130">\{1 \ldots k\}</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда '''количество множеств''' суммарного веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">S_{n}=s_{n, n}</tex>, где <tex dpi="150">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}}{i} s_{n-ik, k-1}</tex> {{---}} количество таких множеств, что они содержат объекты суммарного веса , вес которых не больше чем <tex dpi="130">\leqslant k</tex>.

Пусть <tex dpi="130">A=\{0, 1\}</tex>, <tex>S=PSet(A)</tex> {{---}} множество всех множеств из <tex dpi="130">A</tex>, <tex dpi="130">W=\{2, 0 \ldots 0\}</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда <tex dpi="150">S_{n}=s_{n, n}</tex>, где <tex tex dpi="150">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_{n-ik, k-1}</tex>.:<tex dpi="150">S_{0}=s_{0, 0} = 1</tex>.:<tex dpi="150">S_{1}=s_{1, 1} = s_{1, 0} + 2s_{0, 0} = 2s_{0, 0} = 2</tex>.:<tex dpi="150">S_{2}=s_{2, 2} = s_{2, 1} + 0 \cdot s_{0, 1} = s_{2, 0} + 2s_{1, 0} + s_{0, 0}= s_{0, 0} = 1</tex>.:<tex dpi="150">{S_{3}=s_{3, 3} = s_{3, 2} + 0 \cdot s_{0, 2} = s_{3, 1} + 0 \cdot s_{0, 1} = s_{3, 0} + 2s_{2, 0} + 0 \cdot s_{1, 0} + 0 \cdot s_{0, 0}= 0}</tex>.:Для <tex dpi="150">n > 2</tex>, <tex dpi="150">S_{n} = 0</tex> .

Пусть <tex dpi="130">A=\mathbb{N}</tex>, <tex dpi="130">S=PSet(A)</tex> {{---}} множество всех[[Нахождение количества разбиений числа на слагаемые|разбиений на слагаемые]], <tex dpi="130">W=\{1 \ldots 1\}</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда,

Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">S=MSet(A)</tex> {{---}} множество всех мультимножеств из элементов <tex dpi="130">A</tex>, <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{k}\}</tex> {{---}} количество объектов веса <tex dpi="130">\{1 \ldots k\}</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда '''количество мультимножеств''' из объектов суммарного веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">S_{n}=s_{n, n}</tex>, где <tex dpi="150">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i} s_{n-ik, k-1}</tex> {{---}} количество таких мультимножеств, что они содержат объекты суммарного веса , вес которых не более больше чем <tex dpi="130">k</tex>.

Пусть <tex dpi="130">A=\{0, 1\}</tex>, <tex dpi="130">S=PSet(A)</tex> {{---}} множество всех множеств из <tex dpi="130">A</tex>, <tex dpi="130">W=\{2, 0 \ldots 0\}</tex>, <tex dpi="130">w_{0} = 1</tex>.

:<tex dpi="150">S_{0}=s_{0, 0} = 1</tex>.:<tex dpi="150">S_{1}=s_{1, 1} = s_{1, 0} + 2s_{0, 0} = 2s_{0, 0} = 2</tex>.:<tex dpi="150">S_{2}=s_{2, 2} = s_{2, 1} + 0 \cdot s_{0, 1} = s_{2, 0} + 2s_{1, 0} + 3s_{0, 0}= 3s_{0, 0} = 3</tex>.:<tex dpi="150">S_{3}=s_{3, 3} = s_{3, 2} + 0 \cdot s_{0, 2} = s_{3, 1} + 0 \cdot s_{0, 1} = s_{3, 0} + 2s_{2, 0} + 3s_{1, 0} + 4s_{0, 0}= 4s_{0, 0} = 4</tex>.

:<tex dpi="150">{S_{n}=s_{n, n} = s_{n, n-1} + 0 \cdot s_{0, n-1} = s_{n, n-2} + 0 \cdot s_{0, n-2} = \ldots = s_{n, 0} + 2s_{n - 1, 0} + \ldots + ns_{1, 0} + (n+1) s_{0,0} = (n + 1) s_{0,0} = n+1}</tex>.

:<tex dpi="150">f{n,k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{T_{k}+i-1}{i} s_{n-ik, k-1}</tex>.

По [[Лемма Бёрнсайда и Теорема Пойа#Лемма Бёрнсайда|лемме Бёрнсайда]] <tex dpi="150">c_{n,s} =\sum_{i=0}^{s-1}\dfrac{|St(\vec{i})|}{s}</tex>, где <tex dpi="150">|St(\vec{i})|=z_{n,s,i}</tex> {{---}} количество стабилизаторов для циклического сдвига на <tex dpi="150">i</tex> .}}

Найдем <tex dpi="130">|St(\vec{i})|=z_{n,s,i}</tex> в общем случае. Пусть <tex dpi="150130">g=\mathrm{gcd}(s,i)</tex> {{---}} [[Наибольший общий делитель|наибольший общий делитель <tex dpi="150130">(s, i)</tex>]]. Заметим, что в <tex dpi = "130">i</tex>-ой перестановке на <tex dpi = "130">j</tex> и -ой позиции стоит элемент <tex dpi="150130">(i+ j)\bmod s</tex>. Тогда Также, заметим, что элемент <tex dpi = "130">a</tex> переходит в элемент <tex dpi = "130">a + in</tex>, где <tex dpi = "130">i = 1, 2, \ldots k</tex>. Из этого следует, что длина циклов при сдвиге на цикла для <tex dpi="150130">i</tex> -ой перестановки равна <tex dpi="150130">\fracdfrac{\mathrm{lcm}(s, i)}{i} = \dfrac{s}{g}</tex> , где <tex dpi = "130">\mathrm{lcm}(s, i)</tex> {{---}} [[Наименьшее общее кратное|наименьшее общее кратное<tex dpi = "130">(s, i)</tex>]]. Также заметим, что если вес <tex dpi="130">n</tex> нельзя равномерно распределить по всей длине цикла, то стабилизатор равен <tex dpi="130">0</tex>.

\left \{\begin{array}{ll} 0, & n \mod bmod \frac{s}{g} \neq 0 \\b_{\frac{ng}{s}, g}, & n \mod bmod \frac{s}{g} = 0 \end{array} \right.

<tex dpi="150">b_{n,k}=\sum_{i=1}^{n}w_{i}b_{n-i, k-1}</tex>, при чем <tex dpi="150">b_{n,1}=w_{n}</tex>. ===Задача об ожерельях===Решим данным способом [[Задача об ожерельях|задачу об ожерельях]]. Пусть необходимый вес <tex dpi="130">n</tex> это количество бусинок, а <tex dpi="130">k</tex> {{---}} количество цветов. При чем каждая бусинка весит <tex dpi="130">1</tex>. То есть <tex dpi="130">W=\{k, 0 \ldots 0\}</tex>. <tex dpi="130">C_{n}=\sum_{s=1}^{n}c_{n,s}=c_{n,n}</tex> так как невозможно набрать вес <tex dpi="130">n</tex> менее чем <tex dpi="130">n</tex> бусинами при весе бусин <tex dpi="130">1</tex>. <tex dpi="130">c_{n,n}=\sum_{i=0}^{n-1}\dfrac{|St(\vec{i})|}{n}=\dfrac{1}{n}\sum_{i=0}^{s-1}|St(\vec{i})|=\dfrac{1}{n}\sum_{i=0}^{s-1}b_{\mathrm{gcd}(n,i),\mathrm{gcd}(n,i)}</tex>. Поскольку все бусины имеют одинаковый вес <tex dpi="130">1</tex>, то <tex dpi="130">b_{n,k} \neq 0</tex> В итоге, <tex dpi="130">C_{n}=\dfrac{1}{n}\sum_{i=0}^{s-1}k^{\mathrm{gcd}(n,i)}</tex>.