Сколько есть натуральных чисел длины N где каждая цифра X встречается не больше чем X раз подряд?

Сколько есть натуральных чисел длины N где каждая цифра X встречается не больше чем X раз подряд?

0

Ну и как же решать такую задачу? Мне в голову пока ничего не пришло... Можно, наверное, придумать что-нибудь сложное с применением формул включений — исключений; можно выделить «строительные блоки» (последовательности вида XXXX, длина которых не превышает X) и набирать ими запись числа, следя при этом, чтобы блоки типа 77777 и 777 не следовали друг за другом...

0

Andoroid, А может эта цифра встречаться в нескольких "блоках"?
То есть вот такое допустимо
22121
?

Добавлено через 4 минуты
Если да, то можно попыитатся пойти таким путем. Составляем алфавит
1 2 22 3 33 333 ...
Считаем сколько слов можно составить в этом алфавите с некоторыми ограничениями следования "букв"

Добавлено через 11 минут

Сообщение от Байт А может эта цифра встречаться в нескольких "блоках"? То есть вот такое допустимо 22121

Перечел и понял, что чушь написал. Если такое допустить, то чисел будет бесконечно много, и задача теряет всякий смысл.
Тогда, наверное так
9!*10! и из этого надо исключить случаи, когда каких-то цифр вообще нет и эти "пустоты" стоят рядом.
Ход своих мыслей излагать не буду, ибо они смутны и не решают полностью задачу.
Вот если бы каждая цифра должна непременно встретится, тогда 9!*9! и это я бы уже взялся объяснтить

Добавлено через 7 минут
DrType, мое первоначальное понимание совпало с вашим, и даже соображения на этот счет. Но это понимание приводит к бесконечности и лишает задачу смысла.
В общем, попросим ТС более четко сформулировать задачу. Или сами разобьем на несколько разных.
Простейший вариант - цифры расположены блоками от 1 до Х штук в блоке, как будто не составил большого труда...

0

Байт, не понимаю, почему при первом допущении чисел окажется бесконечно много. У нас задана "длина числа" (очевидно, число цифр в записи) N, и чисел "длины N" в принципе конечное множество.

Согласен с тем, что для начала лучше рассмотреть другую задачу, с дополнительными условиями.

Добавлено через 19 минут
В любом случае, если всё же решать задачу путем составления «алфавита», то необходимо следить ещё и за тем, чтобы длина последовательности цифр равнялась N.

1

Сообщение от DrType У нас задана "длина числа"

Да, вы совершенно правы. Увлекшись другими рассуждениями я об этой длине просто забыл. Это, конечно, меняет все дело.

0

Я бы действовал примерно так.

Сначала считаем количество чисел длины , в которых любые две соседние цифры различны. Это нетрудно, и это будет у нас слагаемое.

Затем из чисел длины , в которых любые две соседние цифры различны, можно получить числа длины , удовлетворяющие условиям задачи. Это делается заменой любой цифры, не равной 1, блоком, в котором эта цифра идёт дважды подряд. Например, если задано , то число 4317 даёт нам 44317, 43317 и 43177.

Потом переходим к числам длины (здесь, конечно, всё усложняется) и так далее.

Что-то рекуррентное родится в итоге, может быть.

0

Сообщение от eropegov Сначала считаем количество чисел длины N, в которых любые две соседние цифры различны. Это нетрудно,

9*8^N-1 (нулей нет по условию)

0