Сколько чисел с суммой цифр 8 можно составить из цифр 1 и 2?

[Ktina]

Сколько всего натуральных чисел с суммой цифр 8 можно составить из цифр 1 и 2?
У меня получилось 25, но был тупой перебор. Можно ли как-нибудь без перебора решить?

-- 30.10.2013, 00:30 --

Пардон, уже не 25, а 34. Кто больше?

[Urnwestek]

$p(n,s)$ — кол-во чисел длины n, с суммой цифр s.
$p(n,s) = p(n-1,s-1)+p(n-1,s-2)$
Отсюда
$p(n,s+n) = C_n^s$
А вам посчитать надо
$p(1,8)+p(2,8)+...+p(8,8)= p(4,8)+p(5,8)+...+p(8,8) = $
$C_4^4 + C_5^3 + C_6^2 + C_7^1 + C_8^0$

Вольфрам говорит, что 34.

Вы такой же перебор делали?

[Ktina]

Urnwestek в сообщении #781999 писал(а):

Вы такой же перебор делали?

Нет, более тупой

[Urnwestek]

Кстати интересен вопрос о том, можно ли свернуть сумму:
$\sum\limits_{k=0}^q C_{q+k}^{q-k}$
Тогда ответ бы вообще замечательным был...

[Ktina]

Urnwestek
Что означает "свернуть"?

[Urnwestek]

Представить ту сумму в виде конечного числа композиций алгебраических функций, степеней и факториалов.

[Ktina]

Urnwestek в сообщении #782006 писал(а):

Представить ту сумму в виде конечного числа композиций алгебраических функций, степеней и факториалов.

Это Ваше определение? А почему оно именно такое? Почему, например, факториалов - да, а функций Аккермана или Конвея - нет?

[Urnwestek]

Ktina в сообщении #782007 писал(а):

Это Ваше определение?

Да.

Ktina в сообщении #782007 писал(а):

Почему, например, факториалов - да, а функций Аккермана или Конвея - нет?

Они мне привычнее, а определение-то моё... Ну, так уж и быть, ради вас я официально пополняю своё определение функциями Конвея и Аккермана. (:

[nnosipov]

Urnwestek в сообщении #782004 писал(а):

Кстати интересен вопрос о том, можно ли свернуть сумму:
$\sum\limits_{k=0}^q C_{q+k}^{q-k}$
Тогда ответ бы вообще замечательным был...

Ну, так вбейте эту сумму в Maple (например) и посмотрите. Одно из чисел Фибоначчи в ответе совсем не случайно появилось.