4.3 Разбиение числа на слагаемые. Диаграммная техника

4.3 Разбиение числа на слагаемые. Диаграммная техника

модуль 4.3 шаг 4

Докажите полученное рекуррентное соотношение

с помощью формулы включения-исключения.

Решение и ответ

модуль 4.3 шаг 5

Сколькими способами можно разменять монету в 10 копеек на монеты в 1, 2, 3 и 5 копеек?

Решение

Sergey

По аналогии с примером

рекуррентная формула \(s_n=s_{n-1}+s_{n-2}-s_{n-4}-s_{n-7}+s_{n-9}+s_{n-10}-s_{n-11}\)

при \(s_0=1, \quad s_k=0, \quad k<0.\)

Вычисляя 10 раз, получается \(s_{10}=20\).

Ответ

20

модуль 4.3 шаг 8

Чему равна производящая функция \(f(z)\) для количества способов разбиения числа на слагаемые 1, 2 и 5?

Решение

Пишите в комментариях

Ответ

1/(1-z-z^2+z^3-z^5+z^6+z^7-z^8)

модуль 4.3 шаг 10

Найдите аналитическое выражение для \(p_3(n)\).

Вход программы состоит из единственной строки — списка из не более чем ста тысяч чисел \(n_i \leq2000000000\), разделённых пробелом.

Выведите единственную строку — список значений \(p_3(n_i)\), разделенных пробелом, для чисел из входа.

Sample Input:

1
 
1 3 5
 

Sample Output:

1
 
0 1 2
 

Решение и ответ

Вариант 1

1
2
3
4
5
6
7
 
def main():
"""My function."""
nums, divider = list(map(int, input().split())), 12
print(*((num**2 + 3) // divider for num in nums))

if __name__ == "__main__":
main()
 

Вариант 2

1
2
3
4
5
6
7
8
9
10
11
12
 
inputs = list(map(int,input().split()))
res = []
for i in inputs:
    if i%6==0:
        res.append(((i*i)//12))
    elif i%6==1 or i%6==5:
        res.append(((i*i-1)//12))
    elif i%6==2 or i%6==4:
        res.append(((i*i-4)//12))
    else:
        res.append(((i*i+3)//12))
print(*res)
 

модуль 4.3 шаг 13

Выразите количество \(q(n)\) разбиений, в которых равны три наибольшие части, через \(p(n), p(n−1), p(n−2) \quad и \quad p(n−3)\).

На первой строке входа находится натуральное число \(t \leq 100000\). На каждой из \(t\) следующих строк содержится 4 натуральных числа \(p(n),p(n-1),p(n-2)\) и \(p(n-3)\) для некоторого неизвестного \(n>3\). Каждое из этих чисел не превосходит миллиарда.

Выведите \(t\) строк, в каждой из которых находится \(q(n)\) для соответствующего набора чисел \(p(i)\) во входе.

Sample Input:

1
2
 
1
5 3 2 1
 

Sample Output:

1
 
1
 

модуль 4.3 шаг 15

Чему равна производящая функция для количества способов разбить число \(n\) на 3 слагаемых, каждое из которых не меньше 3?

Решение

Николай Доронин

Представим разбиение числа как \(n=1y_1+2y_2+3y_3\), где используя диаграмму Ферре получаем, что \(y_1 \geqslant 0, y_2 \geqslant 0, y_3 \geqslant 3\). Отсюда получаем, что \(\varphi_1(z)=1+z+z^2+...=\frac{1}{1-z}\), \(\varphi_2(z)=1+z+z^2+z^4+...=\frac{1}{1-z^2}\), \(\varphi_3(z)=z^9+z^{12}+z^{15}+...=\frac{z^9}{1-z^3}\), слагаемые \(1,z^3,z^6\) быть не могут, так как \(y_3 \geqslant 3\). Тогда производящая функция \(\varphi(z)=\frac{1}{(1-z)(1-z^2)(1-z^3)}.\)

Ответ

z^9/((1-z)*(1-z^2)*(1-z^3))

```