Найти количество 10-значных чисел состоящих только из цифр 1, 2 и 3, при этом с особыми условиями

Предмет: Математика

Раздел: Комбинаторика, рекуррентные соотношения

Разбор условия:

Нам нужно найти количество 10-значных чисел, состоящих только из цифр 1, 2 и 3, при этом с особыми условиями:

• После 1 обязательно должна идти 2.
• После 2 не может стоять 1.

То есть возможные пары цифр:

• 1 → 2 (обязательно)
• 2 → 2, 2 → 3 (возможно)
• 3 → 1, 3 → 2, 3 → 3 (возможно)

Введение обозначений:

Обозначим:

• a_n — количество таких чисел длины n, оканчивающихся на 1.
• b_n — количество таких чисел длины n, оканчивающихся на 2.
• c_n — количество таких чисел длины n, оканчивающихся на 3.
• Общее количество таких чисел длины n:
  F_n = a_n + b_n + c_n

Вывод рекуррентных соотношений:

1. Число длины n, оканчивающееся на 1, может получиться только из числа длины n-1, оканчивающегося на 3, так как 1 может идти только после 3: a_n = c_{n-1}

2. Число длины n, оканчивающееся на 2, может получиться из числа, заканчивающегося на 1 или 2: b_n = a_{n-1} + b_{n-1}

3. Число длины n, оканчивающееся на 3, может получиться из числа, заканчивающегося на 2 или 3: c_n = b_{n-1} + c_{n-1}

Таким образом, общее количество чисел длины n выражается через: F_n = a_n + b_n + c_n

Начальные условия:

Для n = 1 возможны только числа {1, 2, 3}, значит:

• a_1 = 1 (число "1")
• b_1 = 1 (число "2")
• c_1 = 1 (число "3")
• F_1 = 3

Вычисление значений:

Используем рекуррентные формулы для n = 10:

1. a_2 = c_1 = 1
2. b_2 = a_1 + b_1 = 1 + 1 = 2
3. c_2 = b_1 + c_1 = 1 + 1 = 2
4. F_2 = a_2 + b_2 + c_2 = 1 + 2 + 2 = 5

Продолжаем вычисления:

• a_3 = c_2 = 2

• b_3 = a_2 + b_2 = 1 + 2 = 3

• c_3 = b_2 + c_2 = 2 + 2 = 4

• F_3 = 2 + 3 + 4 = 9

• a_4 = c_3 = 4

• b_4 = a_3 + b_3 = 2 + 3 = 5

• c_4 = b_3 + c_3 = 3 + 4 = 7

• F_4 = 4 + 5 + 7 = 16

• a_5 = c_4 = 7

• b_5 = a_4 + b_4 = 4 + 5 = 9

• c_5 = b_4 + c_4 = 5 + 7 = 12

• F_5 = 7 + 9 + 12 = 28

• a_6 = c_5 = 12

• b_6 = a_5 + b_5 = 7 + 9 = 16

• c_6 = b_5 + c_5 = 9 + 12 = 21

• F_6 = 12 + 16 + 21 = 49

• a_7 = c_6 = 21

• b_7 = a_6 + b_6 = 12 + 16 = 28

• c_7 = b_6 + c_6 = 16 + 21 = 37

• F_7 = 21 + 28 + 37 = 86

• a_8 = c_7 = 37

• b_8 = a_7 + b_7 = 21 + 28 = 49

• c_8 = b_7 + c_7 = 28 + 37 = 65

• F_8 = 37 + 49 + 65 = 151

• a_9 = c_8 = 65

• b_9 = a_8 + b_8 = 37 + 49 = 86

• c_9 = b_8 + c_8 = 49 + 65 = 114

• F_9 = 65 + 86 + 114 = 265

• a_{10} = c_9 = 114

• b_{10} = a_9 + b_9 = 65 + 86 = 151

• c_{10} = b_9 + c_9 = 86 + 114 = 200

• F_{10} = 114 + 151 + 200 = 465

Ответ:

Количество таких 10-значных чисел равно
F_{10} = 465