2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Разбиение числа
Сообщение20.11.2013, 02:14 
Здравствуйте!

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

 
 
 
 Re: Разбиение числа
Сообщение20.11.2013, 02:24 
Аватара пользователя
Ну тривиально же. Вот, допустим, зафиксируем конкретное разбиение числа 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$
Легко увидеть, что подобное соответствие взаимнооднозначно.

 
 
 
 Re: Разбиение числа
Сообщение20.11.2013, 02:29 
Меня именно эта взаимнооднозначность и беспокоит. Как доказать что он взаимно-однозначно?

 
 
 
 Re: Разбиение числа
Сообщение20.11.2013, 02:39 
Аватара пользователя
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 быть не может.
Следовательно, разбиения равны как неупорядоченные наборы (по определению равенства неупорядоченных наборов). Но мы предполагали, что они различны — противоречие.

 
 
 
 Re: Разбиение числа
Сообщение20.11.2013, 10:01 
Ward в сообщении #790611 писал(а):
Меня именно эта взаимнооднозначность и беспокоит. Как доказать что он взаимно-однозначно?
Проще всего показать, что сопоставление обратимо.
Вам уже показали, как каждому разбиению поставить в соответствие одно решение. Аналогично показывается, что каждому решению соответствует одно разбиение.

 
 
 
 Re: Разбиение числа
Сообщение20.11.2013, 11:32 
Аватара пользователя
В уравнении $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$.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group