Разбиение числа

[Ward]

Здравствуйте!

Число разбиений натурального числа $n$ на невозрастающие слагаемые равно $p(n)$. Почему число решений уравнения $n=k_1+2k_2+\dots+nk_n$ в неотрицательных числах также равно $p(n)$. Помогите понять это пожалуйста.

[Urnwestek]

Ну тривиально же. Вот, допустим, зафиксируем конкретное разбиение числа 29:
$29 = 1 + 1 + 1 + 3 + 3 + 5 + 7 + 8$
ему соответствует решение
$29 = 1 \cdot 3 + 2 \cdot 0 + 3 \cdot 2 + 4 \cdot 0 + 5 \cdot 0 + 6 \cdot 0 + 7 \cdot 1 + 8 \cdot 1 + 9 \cdot 0 + 10 \cdot 0 + ... + 29 \cdot 0$
Легко увидеть, что подобное соответствие взаимнооднозначно.

[Ward]

Меня именно эта взаимнооднозначность и беспокоит. Как доказать что он взаимно-однозначно?

[Urnwestek]

Ward в сообщении #790611 писал(а):

Меня именно эта взаимнооднозначность и беспокоит. Как доказать что он взаимно-однозначно?

Пусть решению уравнения $n=k_1+2k_2+\dots+nk_n$ соответствуют два различных разбиения n на натуральные слагаемые, разбиения A и B. Следует заметить, что разбиения считаются различными, если они неравны как неупорядоченные наборы.
В разбиении А и разбиении B, не может быть элементов больше, нежели n.
В разбиении A и разбиении B, количество элементов «1» равно $k_1$.
В разбиении A и разбиении B, количество элементов «2» равно $k_2$.
....
В разбиении A и разбиении B, количество элементов «n» равно $k_n$.
Других элементов в разбиении A и разбиении B быть не может.
Следовательно, разбиения равны как неупорядоченные наборы (по определению равенства неупорядоченных наборов). Но мы предполагали, что они различны — противоречие.

[VAL]

Ward в сообщении #790611 писал(а):

Меня именно эта взаимнооднозначность и беспокоит. Как доказать что он взаимно-однозначно?

Проще всего показать, что сопоставление обратимо.
Вам уже показали, как каждому разбиению поставить в соответствие одно решение. Аналогично показывается, что каждому решению соответствует одно разбиение.

[ex-math]

В уравнении $n=x_1+\ldots+x_n$, $x_1\geqslant\ldots\geqslant x_n$, сделайте замену переменных $y_i=x_i-x_{i-1}$ при $i=1,\ldots,n-1$, $y_n=x_n$. Получится уравнение $n=y_1+2y_2+\ldots+ny_n$, $y_i\geqslant0$. Такая замена взаимно-однозначна: $x_i=y_i+\ldots+y_n$.