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

[Alexander__]

Требуется найти кол-во $n$-значных чисел, которые не начинаются с нуля и которые не содержат фрагмента 43 (подряд идущие цифры 4 и 3).

---

Посчитать кол-во чисел, не содержащих, например, $4$ просто: $8 \cdot 9^{n-1}$. Не понимаю как посчитать при условии, что за $4$ следует $3$. Подскажите?

[mihaild]

Посчитайте число $k$-значных чисел, не начинающихся с нуля, не содержащих $43$, и 1) заканчивающихся четверкой; 2) не заканчивающихся четверкой.

[Alexander__]

mihaild в сообщении #1610265 писал(а):

Посчитайте число $k$-значных чисел, не начинающихся с нуля, не содержащих $43$, и 1) заканчивающихся четверкой; 2) не заканчивающихся четверкой.

Давайте обозначим это число $N_{\{1,2\}}(k)$.

$N_1(1)=1$ -- только четвёрка
$N_2(1)=8$ -- все, кроме нуля и четвёрки
$N_1(2)=(N_1(1) + N_2(1)) \cdot 1$ -- четвёрку можем присоединить к любому ранее правильному числу
$N_2(2)=N_2(1) \cdot 1 + (N_1(1) + N_2(1)) \cdot 8$ -- тройку можем присоединить только к числу, не заканчивающемуся на $4$; любое оставшееся число (т.е. не $3$ и не $4$) можем присоединить к правильному числу

Это верно?

[mihaild]

Да, правильно. Можно это записать вот в таком виде:

$$\begin{pmatrix} N_1(k + 1) \\ N_2(k + 1)\end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 8 & 9 \end{pmatrix} \begin{pmatrix} N_1(k) \\ N_2(k)\end{pmatrix}$$

Из этого выразить $N_1$ и $N_2$ - стандартная задача на рекурренты. Если не знаете, как её решать - запишите матрицу в жордановой форме (это штуки, которые должны изучаться, самостоятельно додуматься ИМХО довольно сложно).

[Alexander__]

mihaild в сообщении #1610273 писал(а):

Да, правильно. Можно это записать вот в таком виде:

$$\begin{pmatrix} N_1(k + 1) \\ N_2(k + 1)\end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 8 & 9 \end{pmatrix} \begin{pmatrix} N_1(k) \\ N_2(k)\end{pmatrix}$$

Из этого выразить $N_1$ и $N_2$ - стандартная задача на рекурренты. Если не знаете, как её решать - запишите матрицу в жордановой форме (это штуки, которые должны изучаться, самостоятельно додуматься ИМХО довольно сложно).

И ответом будет $N_1(n) + N_2(n)$?

[TOTAL]

Alexander__ в сообщении #1610274 писал(а):

И ответом будет $N_1(n) + N_2(n)$?

Сразу запишите трёхточечное скалярное уравнение для искомой $N(n) = N_1(n) + N_2(n)$

[gris]

Вдруг пригодится
Перебрал немного чисел разной значности и вот:
for 2-digits k= 90 - 1 =89
for 3-digits k= 900 - 19 =881
for 4-digits k= 9000 - 279 =8721
for 5-digits k= 90000 - 3671 =86329
for 6-digits k= 900000 - 45431 =854569
for 7-digits k= 9000000 - 540639 =8459361
for 8-digits k= 90000000 - 6260959 =83739041
Разность общего количества n-значных чисел и количества чисел, содержащих фрагмент (хотя бы раз). Интересна вероятность случайного n-значного числа не содержать фрагмент "43".

[мат-ламер]

Alexander__ в сообщении #1610263 писал(а):

Посчитать кол-во чисел, не содержащих, например, $4$ просто: $8 \cdot 9^{n-1}$. Не понимаю как посчитать при условии, что за $4$ следует $3$. Подскажите?

Можно перейти от 10-тичной системе исчисления с 100-ичной. Посчитать два раза. При втором подсчёте последнюю цифру оставить десятичной. Подробности не расписываю. Пока сам до конца не продумал.

Чтобы исключения пересечения, придётся многократно использовать формулу включений-исключений. Проще наверное это сделать через рекуррентные соотношения.

P.S. На этот пост внимание не обращайте. Появилась новая идея. Попроще.

[TOTAL]

Можно как-нибудь напрямую заключить, что $10x(n) = x(n-1) + x(n+1)$?

[mihaild]

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

Интересна вероятность случайного n-значного числа не содержать фрагмент "43".

Примерно $1 - c \cdot \left(\frac {|\lambda|} {10}\right)^n$, где $\lambda$ - максимальное по модулю собственное значение матрицы выше.

TOTAL в сообщении #1610314 писал(а):

Можно как-нибудь напрямую заключить, что $10x(n) = x(n-1) + x(n+1)$?

Это Ваш вопрос или подсказка ТС? (да, можно, и наверное даже вычислений в результате чуть меньше будет, но ИМХО подход с учетом суффикса нагляднее)

[TOTAL]

mihaild в сообщении #1610318 писал(а):

TOTAL в сообщении #1610314 писал(а):

Можно как-нибудь напрямую заключить, что $10x(n) = x(n-1) + x(n+1)$?

Это Ваш вопрос или подсказка ТС? (да, можно, и наверное даже вычислений в результате чуть меньше будет, но ИМХО подход с учетом суффикса нагляднее)

Это я спрашивал. А теперь у меня есть версия.
$10x(n)$ - дописали в конце произвольную цифру, получив $x(n+1)$ и ещё что-то лишнее. Лишнее может быть исключительно потому, что в самом конце стоит $43$, а перед $43$ всевозможные варианты из $x(n-1)$.