286
правок
Изменения
м
Нет описания правки
<tex dpi="150">S_{n}=\sum\limits_{i=1}^{n} w_{i} S_{n-i}</tex>. Причем <tex dpi="150"">S_{0} = 1</tex>.
|proof=
<tex dpi="150130"">S_{0} = 1</tex>, так как есть единственный способ составить пустую последовательность.
Докажем по индукции.
<tex dpi="150">P_{n}=p_{n, n}</tex>, где <tex dpi="150">p_{n, k}=\sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}}{i} p_{n-ik, k-1}</tex> {{---}} количество таких множеств, которые содержат объекты, вес которых не больше чем <tex dpi="150">k</tex>. Причем <tex dpi="150">p_{0, i} = 1</tex>, а <tex dpi="150">p_{i, 0} = 0</tex>, <tex dpi="150"">i \ne 0</tex>.
|proof=
<tex dpi="150130">p_{0, i} = 1</tex>, так как не набирать никакой вес есть один способ, а <tex dpi="150130">p_{i, 0} = 0</tex>, <tex dpi="150130"">i \ne 0</tex>, так как нельзя набрать положительный вес из ничего.
Изначально у нас есть только пустое множество веса <tex dpi="130">0</tex>. Рассмотрим очередной этап вычисления <tex dpi="130">p_{n,k}</tex>. Для данных <tex dpi="130">n</tex> и <tex dpi="130">k</tex> у нас уже имеется множество, которое необходимо дополнить. Мы можем сделать это добавляя от <tex dpi="130">0</tex> до <tex dpi="130">\lfloor \frac{n}{k} \rfloor</tex> элементов веса <tex dpi="130">k</tex> (при условии, что столько различных элементов имеется) в данное множество. Выбрать нужное количество элементов можно с помощью сочетаний. Следовательно, у нас образуется новые множества, которые будет необходимо дополнить элементами веса меньше <tex dpi="130">k</tex> (чтобы избежать повторений) суммарного веса <tex dpi="130">n-ik</tex>, где <tex dpi="130">i</tex> {{---}} количество элементов веса <tex dpi="130">k</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="150130">m_{0, i} = 1</tex>, так как не набирать никакой вес есть один способ, а <tex dpi="150130">m_{i, 0} = 0</tex>, <tex dpi="150130"">i \ne 0</tex>, так как нельзя набрать положительный вес из ничего.
Рассуждения аналогичны рассуждениям <tex dpi="130">PSet</tex>, однако теперь мы можем брать один и тот же элемент несколько раз. То есть для подсчета вместо обычных сочетаний нужно использовать сочетания с повторениями.
