Сложная числовая задача (6 класс)

[Yadryara]

Я имел в виду метод номер 3:

gris в сообщении #1492941 писал(а):

$95$
$941$
$932$
$9311$
...
$221111111111$
$2111111111111$
$11111111111111$
Ну а потом для каждой строки применить перемешивание с учётом повторений.

[wrest]

Yadryara в сообщении #1493035 писал(а):

Я имел в виду метод номер 3:

А, ну да, количество строк -- это количество разбиений числа 14 на слагаемые, не бОльшие 9 (равно количеству разбиений числа 14 на не больше чем 9 слагаемых, но это к делу не относится).
Таких 123. Могу вам их подкинуть все, если хотите :)
И каждую потом перемешать ещё :)

[Sender]

Yadryara в сообщении #1493030 писал(а):

У нас тут целая иерархия методов образовалась.

Рискну предложить ещё один.

Используется синтаксис Haskell

dsum :: Int -> Int
dsum 0 = 1
dsum n = sum (map dsum[max 0 n-9..n-1])
main = print(dsum 14)

[Verkhovtsev]

Yadryara в сообщении #1493030 писал(а):

У нас тут целая иерархия методов образовалась. По трудозатратности:

1. Andrey A
2. TOTAL
3. gris
4. Eiktyrnir
Haskell. Sender

[Andrey A]

Yadryara в сообщении #1493030 писал(а):

По трудозатратности:

Явная формула для десятичной системы вроде бы такая: $2^{s-1}-(s-8) \cdot 2^{s-11}$, где $s>9$ – сумма цифр.

[Yadryara]

Andrey A, по-моему это перебор для ПР/Р. Здесь же нельзя давать готовые ответы. Может сотрёте формулу, пока ТС не видел.

[wrest]

Yadryara в сообщении #1493077 писал(а):

Может сотрёте формулу, пока ТС не видел.

ТС, кажется, полностью потрял интерес получив ответ самостоятельно (неправильный, но как уж есть).

[Sender]

Yadryara в сообщении #1493077 писал(а):

Здесь же нельзя давать готовые ответы.

Мне кажется, формула без доказательства её корректности вряд ли может считаться таковым.

[Andrey A]

)))
1) Думаю, в $6$-м классе нынче формулой никого не удивишь, даже учителя. Да еще без надобности выставленной — типа самый умный? Штоли.
2) По поводу корректности предъява справедливая. Просто нашел последовательность в OEIS, потом сумму и подставил формулу, особо не вникая в то что там написано. Не привык я с английским бодаться. Старомодный.
3) Возможно, формула верна только для для $s<20$ и нуждается в обобщении. Далее приходится учитывать варианты с двумя "чуждыми" цифрами и более, поэтому верный результат может оказаться меньше. Хорошо бы это проверить, так что пусть пока лежит.

Исправлено 21:25

[TOTAL]

Вот ещё формула.
Обозначим $C_k$ - количество чисел с суммой цифр $k$.
Положим
$C_k=0$ при $k<0$
$C_0=C_1=1$
Тогда $C_k=2C_{k-1}-C_{k-10}$ при $k>1$

Коэффициент перед $x^k$ в $1/(1-x-x^2-\dots -x^9)$

Если разрешены только цифры $1,3,7$, то $C_k=C_{k-1}+C_{k-3}+C_{k-7}$ и т.д.

[Andrey A]

Andrey A в сообщении #1493085 писал(а):

Возможно, формула верна только для для $s<20$

Так и есть, с $20$-го номера начинается разночтение. Можно добавлять еще слагаемые, но смысла нет: алгоритм TOTAL хорошо работает.

[Yadryara]

Yadryara в сообщении #1493030 писал(а):

Третий метод бросил на полдороге. Количество подходящих разбиений числа $14$ — около сотни.

Досчитал, сошлось. Да, $123$ варианта разбиения. Самый популярный $111112223$ встречается $\binom94\binom41 = 504$ раза.