Количество вариантов представления числа

[0101]

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

[gris]

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

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

[0101]

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 вариантов Есть ли формула для получения количества вариантов?

[ewert]

Ноль ненатурален. И вообще непонятно, что это за табличка.

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

[gris]

А почему Вы рассматриваете вариант 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$,

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

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

[0101]

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

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

ewert в сообщении #262240 писал(а):

Ноль ненатурален. И вообще непонятно, что это за табличка.

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

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

[EtCetera]

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

[0101]

EtCetera в сообщении #262251 писал(а):

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

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