Комбинаторная задача.

bvlady552

Здравствуйте помогите с решением такой задачи.
Сколько есть чисел от 0 до 999999, в котором нет двух рядом стоящих одинаковых цифр?
Я вот так пытаюсь решить.
Очевидно, что количество двузначных чисел, в котором есть две стоящие рядом одинаковые цифры ровно 9. Это 11, 22, 33, 44, 55, 66, 77, 88, 99.
Я доказал, что количество трехзначных чисел, в котором есть две стоящие рядом одинаковые цифры равно 81=9^2.
Но не могу доказать этот факт для n-значных чисел. То есть, что количество n-значных чисел, в котором есть две стоящие рядом одинаковые цифры равно 9^(n-1). Подскажите пожалуйста как это сделать.
P.S. По индукции как то не получается.
Буду очень рад если кто-нибудь что-нибудь подскажет.

shpanenoc

Я доказал, что количество трехзначных чисел, в котором есть две стоящие рядом одинаковые цифры равно 81=9^2.
Интересно, как? Это ведь неверно.

shpanenoc

Назовем число "красивым", если в нем есть 2 подряд одинаковые цифры, и некрасивым иначе.
Пусть N-значных красивых чисел f(N). Соответственно, некрасивых [math]$9*10^{N-1} - f(N)$[/math]
Каждое N-значное красивое число путем дописывания справа одной любой цифры становится (N+1)-значным красивым.
Каждое N-значное некрасивое число путем дописывания одной (и только одной) цифры справа превращается в (N+1)-значное красивое. Если же справа дописать другую цифру, то получится (N+1)-значное некрасивое.
Получается:
[math]$$  f(N+1) = f(N)*10 + (9*10^{N-1} - f(N = 9f(N) + 9*10^{N-1}  $$[/math]

bvlady552

Извиняюсь таких всего по-моему 19*9.

SHYRIK

Проще рассуждать, подсчитывая сразу нужные тебе числа, т.е. те, у которых нет двух рядом стоящих одинаковых цифр. Все однозначные подходят - 10 штук. Далее, если число n-значное (n>=2 то первую цифру можно выбрать 9 способами (так как 0 запрещен вторую - тоже девятью (т.к. 0 уже разрешен, но запрещена выбранная до этого цифра) и т.д., то есть количество таких чисел 9^n. В итоге получим 10+9^2+...+9^6=(9^7-1)/8.

bvlady552

Отлично! Спасибо большое
Оставить комментарий
Имя или ник:
Комментарий: