2014 dxdy logo

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

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




 
 Количество вариантов представления числа
Сообщение15.11.2009, 13:09 
Есть некоторое натуральное число X. Нужно определить количество представлений этого числа с помощью всех возможных натуральных чисел, меньших X и действий сложения и умножения. Заранее благодарю за помощь!

 
 
 
 Re: Количество вариантов представления числа
Сообщение15.11.2009, 13:43 
Аватара пользователя
У меня сразу возникла шуточная мысль, что количество представлений бесконечно, если разрешить использовать умножение на единицу.
Но если серьёзно, то должны ли все числа быть разными и учитывается ли их порядок?
Пример: $6=1+2+3=1\cdot2+4=1\cdot4+2=5+1=4+2=2\cdot3$. По моему, это все варианты. Или имеется в виду возможность $6=3+3=2+2+2=...$

Можно рассмотреть только варианты сумм, а потом определить, есть ли в них повторяющиеся слагаемые и заменять их на произведения.

 
 
 
 Re: Количество вариантов представления числа
Сообщение15.11.2009, 14:06 
5 4 3 2 1
х х х х х
1+0+0+0+1=
0+1+0+1+0=
0+1+0+0+2=
0+0+2+0+0=
0+0+1+1+1=
0+0+1+0+3=
0+0+0+2+2=
0+0+0+1+4=6

Вот такая табличка должна получиться для 6, если не пропустил какую-нибудь строчку. Около 9 вариантов :) Есть ли формула для получения количества вариантов?

 
 
 
 Re: Количество вариантов представления числа
Сообщение15.11.2009, 14:15 
Ноль ненатурален. И вообще непонятно, что это за табличка.

А количество способов разбить шестёрку на натуральные слагаемые (с учётом порядка) есть $N=2^{6-1}=32$.

 
 
 
 Re: Количество вариантов представления числа
Сообщение15.11.2009, 14:19 
Аватара пользователя
А почему Вы рассматриваете вариант 6=6? Ведь у Вас написано "меньших X"?
То есть многократные умножения не разрешены. Как и многократные сложения.
То есть $1+1+1+1+1+1=2\cdot1+4\cdot1=6\cdot1$ это всё один вариант.
Короче, надо найти число способов представления числа в виде

$N=k_1\cdot1+k_2\cdot2+k_3\cdot3+\cdots+k_N\cdot N$,

с неотрицательными целыми коэффициентами?

Умиляет правка. "Около десяти" вариантов на "около девяти". :)

 
 
 
 Re: Количество вариантов представления числа
Сообщение15.11.2009, 14:41 
Дополняю формулировку. Есть число Х. Есть Х-1 весовых коеффициентов Х-1, ...1. Сколько вариантов представления числа Х?

-- Вс ноя 15, 2009 14:45:17 --

ewert в сообщении #262240 писал(а):
Ноль ненатурален. И вообще непонятно, что это за табличка.

А количество способов разбить шестёрку на натуральные слагаемые (с учётом порядка) есть $N=2^{6-1}=32$.

Проиллюстрировать можете?

 
 
 
 Re: Количество вариантов представления числа
Сообщение15.11.2009, 14:45 
0101
Похоже на число разбиений.
P.S. У Вас в табличке, по-моему, пропущены варианты $0+0+0+3\cdot 2+0=6$ и $0+0+0+0+6\cdot 1=6$.

 
 
 
 Re: Количество вариантов представления числа
Сообщение15.11.2009, 14:51 
EtCetera в сообщении #262251 писал(а):
0101
Похоже на число разбиений.
P.S. У Вас в табличке, по-моему, пропущены варианты $0+0+0+3\cdot 2+0=6$ и $0+0+0+0+6\cdot 1=6$.

Это оно! Большое спасибо!

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


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