2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Количество 6значных чисел где 7ки группами
Сообщение26.06.2015, 20:32 
1. Посчитать все шестизначные числа такие, в которых семерки идут группами (либо их вообще нет).
(Например: $772771$, $777177$, $345890$ допустимые, а $711111$, $777173$ недопустимые)
2. Посчитать все шестизначные числа такие, в которых семерки есть и идут группами.

Пусть $a_n$ количество n-буквенных слов, в которых если есть семерки, то идут группами и они начинаюся не с $0$. Пусть $b_n$ количество n-буквенных слов, в которых если есть семерки, то они идут группами и они начинаются с $0$. Ответ на вопрос 1 задачи есть $a_6$, на вопрос 2 $a_6-8\cdot9^5$.

Рассмотрим $a_n$. Если начинается с $7$, то и вторая цифра должна быть семерка. Третья может быть $0$ и может быть любая другая. Получаем, $a_{n-2}+b_{n-2}$. Если начинается не $7$, т.е. c $\{1,2,3,4,5,6,8,9\}$ -- $0$ не может быть по определению $a_{n}$, имеем $8$ вариантов. Вторая цифра может быть любая, тогда получаем $8(a_{n-1}+b_{n-1})$.
Итого:
$$a_n=a_{n-2}+b_{n-2}+8(a_{n-1}+b_{n-1})$$

Рассмотрим $b_n$.
Вторая цифра может быть любой, так что тут
$$b_n=b_{n-1}+a_{n-1}$$
Заметим, что $a_{n-1}=b_{n}-b_{n-1}$. Т.е. если мы научимся вычислять (или найдем в замкнутой форме) последовательность $b_n$, то по ней последовательность $a_n$ восстанавливается тут же.

Первое уравнение с учетом $b_n=b_{n-1}+a_{n-1}$ переформулирется как:
$$a_n=b_{n-1}+8b_{n}$$
Или, что тоже самое:
$$a_{n-1}=b_{n-2}+8b_{n-1}$$
И исключая $a_{n-1}$ получаем:
$$b_{n}-b_{n-1}=b_{n-2}+8b_{n-1}$$
В итоге:
$$b_{n}=b_{n-2}+9b_{n-1}$$

Это линейное реккурентное уравнение. Легко получить замкнутое выражение, но корни иррациональные, поэтому просто вычислим до $b_7$ и получим $a_6=b_7-b_6$.
$b_1=1$ (единственное однозначное с первым $0$ это $0$)
$b_2=9$ (единcтвенное двузначное с первым $0$ и с $7$ это $07$, не подходит, остальные подходят, $00,01,02,03,04,05,06,08,09$)
$b_3=1+9\cdot9=1+9^2=82$
$b_4=b_2+9b_3=9+9(1+9^2)=2\cdot9+9^3=747$
$b_5=b_3+9b_4=1+9^2+9(2\cdot9+9^3)=1+3\cdot9^2+9^4=6805$
$b_6=b_4+9b_5=61992$
$b_7=b_5+9b_6=564733$

И наконец:
$$a_6=b_7-b_6=502741$$
Всего шестизначных чисел, где 7ки либо отсутствуют, либо идут блоками $a_6=502741$, шестизначных чисел, где обязательно 7ки есть и идут блоками $a_6-8\cdot9^5=30349$

Где-то я ошибаюсь. Правильный $a_6=505449$. Помогите разобраться, пожалуйста.

 
 
 
 Re: Количество 6значных чисел где 7ки группами
Сообщение26.06.2015, 22:04 
Аватара пользователя
Возможна только одна либо две группы семёрок. В первом случае группа может иметь размер: $2, 3, 4, 5, 6.$ Во втором либо $(2,2),$ либо $(2,3).$ Рассмотрите каждый случай по отдельности. Сколько, например, положений может иметь единственная группа длины два? Для каждого такого положения возможно либо $8\cdot9^3,$ либо $9^4$ чисел (первый случай когда 7-ка не в самой левой позиции, так как первая цифра не может быть нулём).

 
 
 
 Re: Количество 6значных чисел где 7ки группами
Сообщение27.06.2015, 07:41 
whitefox
Спасибо, так я умею, хотелось мое решение довести до конца

 
 
 
 Re: Количество 6значных чисел где 7ки группами
Сообщение27.06.2015, 14:48 
whitefox в сообщении #1031402 писал(а):
Для каждого такого положения возможно либо $8\cdot9^3,$ либо $9^4$ чисел (первый случай когда 7-ка не в самой левой позиции, так как первая цифра не может быть нулём).

Проще допустить начальный ноль и вычесть из количества шестизначных комбинаций количество пятизначных. Там много чего сократится, и останется лишь $5\cdot9^4+9^6-9^5+2\cdot9+3\cdot9^2-9$.

 
 
 
 Re: Количество 6значных чисел где 7ки группами
Сообщение27.06.2015, 15:05 
Аватара пользователя
ewert в сообщении #1031570 писал(а):
Там много чего сократится, и останется лишь $5\cdot9^4+9^6-9^5+2\cdot9+3\cdot9^2-9$

Можно и ещё подсократить — $85031_9$ :D

 
 
 
 Re: Количество 6значных чисел где 7ки группами
Сообщение27.06.2015, 15:11 
whitefox в сообщении #1031574 писал(а):
Можно и ещё подсократить — $85031_9$ :D

Ну я-то выписал слагаемые, остающиеся после только буквального сокращения (потому даже не стал объединять $2\cdot9-9$).

И, кстати, Ваше замечательное сокращение чуток сбито.

 
 
 
 Re: Количество 6значных чисел где 7ки группами
Сообщение27.06.2015, 15:18 
Аватара пользователя
ewert в сообщении #1031576 писал(а):
И, кстати, Ваше замечательное сокращение чуток сбито.

Что Вы имеете ввиду?

 
 
 
 Re: Количество 6значных чисел где 7ки группами
Сообщение27.06.2015, 15:21 
whitefox в сообщении #1031579 писал(а):
Что Вы имеете ввиду?

А чему равен его остаток от деления на девять?...

 
 
 
 Re: Количество 6значных чисел где 7ки группами
Сообщение27.06.2015, 15:26 
Аватара пользователя
А, ну да :?
$850310_9$

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group