Количество n-значных кодов, содержащих 666

[fatra]

Нужно найти количество n-значных
кодов, содержащих 666 (обозначение $a_n$ )
Коды состоят из цифр 0, 1, .. ,9.
Я нашел значения при n=3,4,5,6,7:
$ a_3=1, a_4=19, a_5=280, a_6=3700, a_7=45991$
Получил реккурентную формулу
$a_{n+1}=9\cdot a_n+9\cdot a_{n-1}+9\cdot a_{n-2}+10^{n-2}$

Но мне нужно получить общую формулу, чтобы подставить в ряд, использующийся при вычислении меры.

[ИСН]

Общая будет с корнями, а корни некрасивые.

[fatra]

А как её получить не подскажете?

-- Чт янв 12, 2012 12:52:36 --

Кстати начальная задача: найти меру множества тех точек из интервала (0;1) , у которых при разложении в десятичную дробь отсутствует последовательность из трех шестерок. Похоже её нужно решать как-то проще.

[Хорхе]

Конечно, проще -- мера ведь равна нулю. Тут не надо точно считать, достаточно оценить сверху.

[fatra]

Не получается у меня найти множество или последовательность множеств, содерщащих данное, мера которых стремится к нулю

[INGELRII]

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

Найти меру каждого из этих множеств и убедиться, что она стремится к нулю, сможете?

[fatra]

Пересечение этих множеств и есть данное множество, это хорошо.
Мера первого множества 0,999, второго 0,9981, третьего 0,9972, четвертого 0,9963. Похоже на арифметичскую прогрессию, но тогда мы выйдем на отрицательные числа. Поэтому должна быть более сложная реккурентная формула и опять получается комбинаторика. Действительно для пятого уже 0,9954009 . И у меня не получается получить реккурентную формулу порядка 1.
Может как-то проще. Было бы хорошо свести задачу к двум шестерках или еще лучше к одной, но не вижу как это сделать, наоборот можно.
Кстати нашел противоположную задачу в другой ветке, хотя и не понял, его идею.
http://dxdy.ru/post396732.html#p396732

[gris]

Ваше утверждение верно и для любой, сколь угодно длинной фиксированной последовательности цифр.
Интуитивно это легко понять через вероятность. Если генерировать бесконечную последовательность цифр (с ненулевыми вероятностями), то вероятность появления любой конечной комбинации равна 1.

[fatra]

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

[ИСН]

У, блин. С одной шестёркой знаете как доказать?

[fatra]

С одной знаю.

[INGELRII]

А зачем нам нужна точная формула членов этой последовательности? нам нужно лишь доказать стремление ее к нулю. Ну так возьмем некую мажорирующую стремящуюся к нулю последовательность, и возрадуемся, ибо сим докажем утверждение наше.

Одна геометрическая убывающая прогрессия так и просится, чтобы ею оценили сверху вашу последовательность.

[ИСН]

Ну так и считайте, что у Вас система счисления с основанием 1000, а 666 - это одна цифра в ней.
(Да, я вижу, что - - -, но это неважно.)

[fatra]

Можно и мажорировать, но пока не могу подобрать геометрическую прогрессию. Та и убывает она достаточно медленно.

-- Чт янв 12, 2012 16:23:00 --

ИСН в сообщении #526134 писал(а):

Ну так и считайте, что у Вас система счисления с основанием 1000, а 666 - это одна цифра в ней.
(Да, я вижу, что - - -, но это неважно.)

Но это наверное не равносильная задача: одна шестерка может быть из первой цифры, а две других - из второй цифры. В любом случае сложноватый способ.

[ИСН]

fatra в сообщении #526135 писал(а):

Но это наверное не равносильная задача: одна шестерка может быть из первой цифры, а две других - из второй цифры. В любом случае сложноватый способ.

Да, но это неважно. Ваши числа - это подмножество моих, так что если у моих мера 0, то у Ваших и подавно. Более простого способа я, право, не представляю. (Другие - есть, но они такие же или сложнее.)