Количество слов с условием в указанном алфавите

@oobarbazanoo · Регистрация: 13.05.2015

Студворк — интернет-сервис помощи студентам

Имеем алфавит {a, b, c}. Необходимо посчитать количество слов заданной длины n > 2 в данном алфавите таких, что в слове хотя бы один раз встречаются две буквы a подряд.

Вот как я решаю задачу. Пускай у нас уже встретились две буквы а подряд, теперь просто переставляя их и выбирая один из трёх вариантов для оставшихся мест получим все варианты где буква а встречается два раза подряд хотя бы раз. Итак, выбираем место для двух a, это можно сделать n-1 способами, далее заполняем оставшиеся n-2 места выбирая символы из алфавита - это можно сделать $https://www.cyberforum.ru/cgi-bin/latex.cgi?{3}^{(n-2)}$ способами. Но мы посчитали случаи, где имеются два случая того что идут две а подряд дважды, поэтому вычтим их и тут прихожу к формуле включений-исключений, но чувствую что кучу всего теряю и что задачу можно решить хитрее. Помогите, пожалуйста.

Байт · 05.12.2017, 21:50

oobarbazanoo, как будто специально для вас

Вычислить количество слов длины n для алфавита

@oobarbazanoo · 06.12.2017, 02:11 **[ТС]**

Байт, на самом деле не понятно откуда у вас рекуррентные соотношения появились и как Вы потом из них числа получили. Хотя цепями маркова задача вроде легко решается...

Байт · 06.12.2017, 10:37

Сообщение от oobarbazanoo

не понятно откуда у вас рекуррентные соотношения появились

Ну, там довольно подробно все расписано. Что именно непонятно?
Да, и я сначала допустил ошибочку. Но исправился. Насоящие уравнения такие
A_n+ = 2A_n+2B_n
B_n+1 = A_n

Сообщение от oobarbazanoo

цепями маркова задача вроде легко решается...

Интересно...

@oobarbazanoo · 06.12.2017, 13:08 **[ТС]**

Имеем три состояния a, b, c.
ij - переход из состояния i в состояние j, 1 - если можно, 0 - иначе.
a - первое состояние, b - второе состояние, c - третье состояние.
Начать можем следующими векторами (1, 0, 0), (0, 1, 0), (0, 0, 1).
Матрица переходов вот такая
0 1 1
1 1 1
1 1 1
Теперь нам нужно возвести данную матрицу в n-1-ю степень, умножить полученную матрицу на каждый из трёх векторов и сложить все девять координат.
Таким образом получим количество слов из n букв, где a ни разу не повторяется дважды. Теперь просто вычитаем полученное число из 3ⁿ - это и будет ответ.
Верно?

Байт · 06.12.2017, 13:29

oobarbazanoo, Наверное, вы правы. Только как эту матрицу в степень возводить?

@oobarbazanoo · 06.12.2017, 15:14 **[ТС]**

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

@jogano · 06.12.2017, 15:38

oobarbazanoo, почти. Количество вариантов, которые нужно вычитать из 3ⁿ, равно
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(1;4;4 \right)\left(\begin{matrix}0 & 2 & 0\\ 0 & 0 & 2\\ 0 & 1 & 2\end{matrix} \right)^{n-1}\left(\begin{matrix}0\\ 1\\ 1\end{matrix} \right)$
Та матрица, что в степени, получается из рекурентного соотношения для элементов цепи Маркова
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases}a'_{11}=2a_{12}\\ a'_{12}=2a_{22}\\ a'_{22}=a_{12}+2a_{22} \end{cases}$

@oobarbazanoo · 06.12.2017, 16:14 **[ТС]**

jogano, как-то почти вовсе непонятно почему Вы такое написали... )з Объясните поподробнее, пожалуйста, откуда такое соотношение?

@jogano · 06.12.2017, 17:56

Матрица перехода (какая буква должна быть следующей) та же, что и у вас:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(\begin{matrix}0 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\end{matrix} \right)$ - запрещён только переход от а к а, поэтому элемент матрицы (1;1) равен 0.
Дальше, если начать возводить эту матрицу в степень, можно увидеть закономерности в коэффициентах:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(\begin{matrix}0 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\end{matrix} \right)^2=\left(\begin{matrix}2 & 2 & 2\\ 2 & 3 & 3\\ 2 & 3 & 3\end{matrix} \right)\\\left(\begin{matrix}0 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\end{matrix} \right)^3=\left(\begin{matrix}4 & 6 & 6\\ 6 & 8 & 8\\ 6 & 8 & 8\end{matrix} \right)$
Т.е. матрица степени состоит из трёх разных чисел- элемента (1;1), элемента (1;2), который равен элементам (1;3), (2;1) и (3;1), и элемента (2;2), который равен ещё трём элементам. Приведённые в посте #8 рекурентные соотношения отражают формулы, по которым получаются элементы этой матрицы степени из предыдущей при умножении предыдущей на исходную справа (исходная - правый множитель). Если эти три различных коэффициента записать в виде вектора, то выходит
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(\begin{matrix}a'_{11}\\ a'_{12}\\ a'_{22}\end{matrix} \right)=\left(\begin{matrix}0 & 2 & 0\\ 0 & 0 & 2\\ 0 & 1 & 2\end{matrix} \right)\left(\begin{matrix}a_{11}\\ a_{12}\\ a_{22}\end{matrix} \right)$
А начальные значения этих коэффициентов (0;1;1).
А найти в итоге нужно сумму всех элементов матрицы. С учётом повторяемости этих трёх коэффициентов получаем, что нужно найти сумму $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_{11}+4a_{12}+4a_{22}$
Именно поэтому в посте #8 есть слева множитель (1;4;4) (вектор-строка).

@oobarbazanoo · 06.12.2017, 19:29 **[ТС]**

jogano,
1. Почему Вы можете использовать закономерности?
2. Почему начальные значения (0; 1; 1),
3. Что неправильно в моих рассуждениях или Вы просто привели оптимизацию?

@jogano · 06.12.2017, 19:47

1), 2) А какой ответ вы ожидаете на такой вопрос? Допускается делать всё, что не противоречит логике и правилам выполнения математических операций.
3) Не вижу неправильностей. Просто другой способ.

@oobarbazanoo · 06.12.2017, 21:56 **[ТС]**

jogano, то есть, могу считать своим способом и ничего страшного. Верно?

Байт · 06.12.2017, 22:44

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

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@oobarbazanoo 7 / 30 / 9 Регистрация: 13.05.2015 Сообщений: 1,835

	Количество слов с условием в указанном алфавите 05.12.2017, 19:04. Показов 2261. Ответов 13 Метки нет (Все метки) Имеем алфавит {a, b, c}. Необходимо посчитать количество слов заданной длины n > 2 в данном алфавите таких, что в слове хотя бы один раз встречаются две буквы a подряд. Вот как я решаю задачу. Пускай у нас уже встретились две буквы а подряд, теперь просто переставляя их и выбирая один из трёх вариантов для оставшихся мест получим все варианты где буква а встречается два раза подряд хотя бы раз. Итак, выбираем место для двух a, это можно сделать n-1 способами, далее заполняем оставшиеся n-2 места выбирая символы из алфавита - это можно сделать $https://www.cyberforum.ru/cgi-bin/latex.cgi?{3}^{(n-2)}$ способами. Но мы посчитали случаи, где имеются два случая того что идут две а подряд дважды, поэтому вычтим их и тут прихожу к формуле включений-исключений, но чувствую что кучу всего теряю и что задачу можно решить хитрее. Помогите, пожалуйста. 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	05.12.2017, 21:50
	oobarbazanoo, как будто специально для вас Вычислить количество слов длины n для алфавита 1

@oobarbazanoo 7 / 30 / 9 Регистрация: 13.05.2015 Сообщений: 1,835
	06.12.2017, 02:11 [ТС]
	Байт, на самом деле не понятно откуда у вас рекуррентные соотношения появились и как Вы потом из них числа получили. Хотя цепями маркова задача вроде легко решается... 0

@oobarbazanoo 7 / 30 / 9 Регистрация: 13.05.2015 Сообщений: 1,835
	06.12.2017, 13:08 [ТС]
	Имеем три состояния a, b, c. ij - переход из состояния i в состояние j, 1 - если можно, 0 - иначе. a - первое состояние, b - второе состояние, c - третье состояние. Начать можем следующими векторами (1, 0, 0), (0, 1, 0), (0, 0, 1). Матрица переходов вот такая 0 1 1 1 1 1 1 1 1 Теперь нам нужно возвести данную матрицу в n-1-ю степень, умножить полученную матрицу на каждый из трёх векторов и сложить все девять координат. Таким образом получим количество слов из n букв, где a ни разу не повторяется дважды. Теперь просто вычитаем полученное число из 3ⁿ - это и будет ответ. Верно? 1

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	06.12.2017, 13:29
	oobarbazanoo, Наверное, вы правы. Только как эту матрицу в степень возводить? 1

@oobarbazanoo 7 / 30 / 9 Регистрация: 13.05.2015 Сообщений: 1,835
	06.12.2017, 15:14 [ТС]
	Байт, беру функцию шаблон для возведения в степень за логарифмическое время, беру структуру Матрицу и определяю операцию умножения для матрицы. Вроде бы всё супер тут выходит. Единственный вопрос - правильно ли я разобрался с цепью Маркова в данном случае... 0

@jogano $Эксперт по математике/физике$ 6360 / 4067 / 1512 Регистрация: 09.10.2009 Сообщений: 7,550 Записей в блоге: 4
	06.12.2017, 15:38
	oobarbazanoo, почти. Количество вариантов, которые нужно вычитать из 3ⁿ, равно $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(1;4;4 \right)\left(\begin{matrix}0 & 2 & 0\\ 0 & 0 & 2\\ 0 & 1 & 2\end{matrix} \right)^{n-1}\left(\begin{matrix}0\\ 1\\ 1\end{matrix} \right)$ Та матрица, что в степени, получается из рекурентного соотношения для элементов цепи Маркова $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases}a'_{11}=2a_{12}\\ a'_{12}=2a_{22}\\ a'_{22}=a_{12}+2a_{22} \end{cases}$ 1

@oobarbazanoo 7 / 30 / 9 Регистрация: 13.05.2015 Сообщений: 1,835
	06.12.2017, 16:14 [ТС]
	jogano, как-то почти вовсе непонятно почему Вы такое написали... )з Объясните поподробнее, пожалуйста, откуда такое соотношение? 0

@jogano $Эксперт по математике/физике$ 6360 / 4067 / 1512 Регистрация: 09.10.2009 Сообщений: 7,550 Записей в блоге: 4
	06.12.2017, 17:56
	Сообщение было отмечено oobarbazanoo как решение Решение Матрица перехода (какая буква должна быть следующей) та же, что и у вас: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(\begin{matrix}0 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\end{matrix} \right)$ - запрещён только переход от а к а, поэтому элемент матрицы (1;1) равен 0. Дальше, если начать возводить эту матрицу в степень, можно увидеть закономерности в коэффициентах: $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(\begin{matrix}0 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\end{matrix} \right)^2=\left(\begin{matrix}2 & 2 & 2\\ 2 & 3 & 3\\ 2 & 3 & 3\end{matrix} \right)\\\left(\begin{matrix}0 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\end{matrix} \right)^3=\left(\begin{matrix}4 & 6 & 6\\ 6 & 8 & 8\\ 6 & 8 & 8\end{matrix} \right)$ Т.е. матрица степени состоит из трёх разных чисел- элемента (1;1), элемента (1;2), который равен элементам (1;3), (2;1) и (3;1), и элемента (2;2), который равен ещё трём элементам. Приведённые в посте #8 рекурентные соотношения отражают формулы, по которым получаются элементы этой матрицы степени из предыдущей при умножении предыдущей на исходную справа (исходная - правый множитель). Если эти три различных коэффициента записать в виде вектора, то выходит $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left(\begin{matrix}a'_{11}\\ a'_{12}\\ a'_{22}\end{matrix} \right)=\left(\begin{matrix}0 & 2 & 0\\ 0 & 0 & 2\\ 0 & 1 & 2\end{matrix} \right)\left(\begin{matrix}a_{11}\\ a_{12}\\ a_{22}\end{matrix} \right)$ А начальные значения этих коэффициентов (0;1;1). А найти в итоге нужно сумму всех элементов матрицы. С учётом повторяемости этих трёх коэффициентов получаем, что нужно найти сумму $https://www.cyberforum.ru/cgi-bin/latex.cgi?a_{11}+4a_{12}+4a_{22}$ Именно поэтому в посте #8 есть слева множитель (1;4;4) (вектор-строка). 1

@oobarbazanoo 7 / 30 / 9 Регистрация: 13.05.2015 Сообщений: 1,835
	06.12.2017, 19:29 [ТС]
	jogano, 1. Почему Вы можете использовать закономерности? 2. Почему начальные значения (0; 1; 1), 3. Что неправильно в моих рассуждениях или Вы просто привели оптимизацию? 0

@jogano $Эксперт по математике/физике$ 6360 / 4067 / 1512 Регистрация: 09.10.2009 Сообщений: 7,550 Записей в блоге: 4
	06.12.2017, 19:47
	1), 2) А какой ответ вы ожидаете на такой вопрос? Допускается делать всё, что не противоречит логике и правилам выполнения математических операций. 3) Не вижу неправильностей. Просто другой способ. 1

@oobarbazanoo 7 / 30 / 9 Регистрация: 13.05.2015 Сообщений: 1,835
	06.12.2017, 21:56 [ТС]
	jogano, то есть, могу считать своим способом и ничего страшного. Верно? 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	06.12.2017, 22:44
	Господа! Вы привели алгоритмы вычисления, и это здорово. Но дело в том, что я пытался вам предложить конечную формулу. И способ ее получения. Не исключаю своих возможных ошибок. 1

Количество слов с условием в указанном алфавите

Решение