Десять чисел в ряд

[Ktina]

Сколькими способами можно расставить натуральные числа от 1 до 10 в ряд так, чтобы каждое (кроме первого) число было делителем суммы всех предыдущих?

[gris]

Сумма всех чисел 55. Отсюда следует, что на последнем месте может стоять 1 или 5. Что если организовать процесс задом наперёд? то есть начинаем с десятой позиции и ставим числа так, чтобы разница между 55 и суммой написанных чисел делилась на это число?
Мне кажется, что задачу надо попробовать решить для меньших чисел.
$2: (2,1)$
$3: (2,1,3),(3,1,2)$
$4: (3,1,4,2),(4,2,3,1)$
Для пяти у меня чего-то заскок произошёл

[slavav]

22 способа. Вычислено полным перебором.

[Ktina]

slavav
Вручную?

[slavav]

Нет, не вручную. Перебором всех перестановок и проверкой их свойств на компьютере. $10!$ - не большое число.

[Geen]

slavav в сообщении #1071062 писал(а):

22 способа. Вычислено полным перебором.

Странно, что для 9 решений больше - 24.

slavav в сообщении #1071085 писал(а):

$10!$ - не большое число.

А это уже перебор - gris подсказал алгоритм.

-- 07.11.2015, 19:39 --

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

надо попробовать решить для меньших чисел

У Вас ошибка для 5 только...

[slavav]

Geen в сообщении #1071101 писал(а):

[quote="slavav в А это уже перебор - gris подсказал алгоритм.

Подсказанный алгоритм можно использовать для ограничения перебора. Зато для полного перебора можно использовать готовые инструменты, то есть написать программу за несколько минут.

c( 1 ) = 1
c( 2 ) = 1
c( 3 ) = 2
c( 4 ) = 2
c( 5 ) = 4
c( 6 ) = 5
c( 7 ) = 7
c( 8 ) = 7
c( 9 ) = 24
c( 10 ) = 22
c( 11 ) = 29
c( 12 ) = 39

[Geen]

slavav в сообщении #1071106 писал(а):

Зато для полного перебора можно использовать готовые инструменты, то есть написать программу за несколько минут.

Так она и так за несколько минут пишется...
Сейчас, для $n=20$ подсчитает, выложу результат

[gris]

Я вначале подумал, что из каких-нибудь соображений делимости, простоты и т.п. требуемая комбинация невозможна. Потом попробовал на маленьких числах. Потом подумал, что если уж есть перестановки, то искать теоретически их число дело муторное и написал прямейший, тупейший, неэффективнейший скрипт, который и выдал <вовсе не случайное> число нужных перестановок .

[slavav]

Перебор с ограничением:
c( 1 ) = 1
c( 2 ) = 1
c( 3 ) = 2
c( 4 ) = 2
c( 5 ) = 4
c( 6 ) = 5
c( 7 ) = 7
c( 8 ) = 7
c( 9 ) = 24
c( 10 ) = 22
c( 11 ) = 29
c( 12 ) = 39
c( 13 ) = 67
c( 14 ) = 55
c( 15 ) = 386
c( 16 ) = 235
c( 17 ) = 312
c( 18 ) = 347
c( 19 ) = 451
c( 20 ) = 1319
c( 21 ) = 5320
c( 22 ) = 3220
c( 23 ) = 4489
c( 24 ) = 20237

[Geen]

до 25:
1 1 2 2 4 5 7 7 24 22 29 39 67 55 386 235 312 347 451 1319 5320 3220 4489 20237 36580

[gris]

Посмотрел в OEIS и увидел там эту последовательность

[slavav]

c( 26 ) = 52875

[Geen]

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

Посмотрел в OEIS и увидел там эту последовательность

Блин, всё украдено до нас

[slavav]

slavav в сообщении #1071142 писал(а):

c( 26 ) = 52875

(Оффтоп)

Клянусь обновлять форум перед отправкой сообщения!