Задача по комбинаторике(тер.вер.)

[apatic]

Граждане, помогите. Ну никак не понимаю, с какой стороны тут подойти.
Задача: Найти количество цепочек длины 7, составленных из букв a,b,c при условии, что нет двух рядом стоящих букв b .

Что это за тема? Это ведь не простые анаграммы.
Даже не понимаю, как это ограничение из двух рядом стоящих букв записать. Спасибо.

[Neanod007]

http://www.pm298.ru/nut.shtml смотриш сочетания находиш число общих сочетаний потом
от этого нада отнять варианты где буквы b повторяются

[apatic]

Neanod007, да не, это понятно, что из общего кол-ва возможных перестановок (5040) надо вычислить все возможные перестановки, где b повторяются. Но как составить эти варианты? их очень много, а логики в них я не вижу.

[Really]

apatic в сообщении #166252 писал(а):

да не, это понятно, что из общего кол-ва возможных перестановок (5040)

Перестановки здесь вообще ни при чем. $5040=7!$ это неправильно
посчитанное число всех цепочек из трех символов.

[apatic]

3 в 7 степени = 2187 - размещение с повторениями. Так?

[Really]

apatic в сообщении #166255 писал(а):

343

Нет. Не то в степень возводите. Да и то при условии, что допускаются
варианты, где присутствуют не все буквы. Из текста задачи это
однозначно не ясно...

Добавлено спустя 1 минуту 17 секунд:

apatic в сообщении #166255 писал(а):

3 в 7 степени = 2187 - размещение с повторениями. Так?

Эту формулу обычно называют число всех отображений. Опять же,
если допускается, что не все буквы должны присутствовать...

[apatic]

Really, да с 343 я погорячился, исправил даже. Размещение с повторениями 7 ячеек, 3 различных числа. В первую ячейку может быть вставлено одно из трёх, во вторую одно из трех и тд... Всего 3 в 7 степени. Что делать с ограничением неясно. Видимо *bb*****, *bbb****, *bbbbb*, а так же *bb*bbb и похожее - тоже недопустимо.

[Really]

apatic в сообщении #166259 писал(а):

Что делать с ограничением неясно. Видимо *bb*****, *bbb****, *bbbbb*, а так же *bb*bbb и похожее - тоже недопустимо.

Верно. Ничего умнее придумать не могу, чем просто перебирать варианты. Разобейте множество всех вариантов $S$ на непересекающиеся
подмножества $S_i, i=1\ldots 7$, по количеству символов $b$ в
каждой цепочке. И считайте отдельно...

Кстати, число всех вариантов так и считать не надо...

[--mS--]

По формуле включения-исключения можно посчитать число цепочек, в которых хотя бы где-то есть две рядом стоящие семёрки. Для этого завести множества $A_i$ - множество всех цепочек, в которых места $i$ и $i+1$ заняты буквами $b$. Множество всех возможных цепочек с двумя буквами $b$ рядом есть объединение $A_1\cup\ldots\cup A_6$. Дальше - формула включения-исключения.

[Really]

--mS-- в сообщении #166282 писал(а):

По формуле включения-исключения можно посчитать число цепочек, в которых хотя бы где-то есть две рядом стоящие семёрки. Для этого завести множества $A_i$ - множество всех цепочек, в которых места $i$ и $i+1$ заняты буквами $b$. Множество всех возможных цепочек с двумя буквами $b$ рядом есть объединение $A_1\cup\ldots\cup A_6$. Дальше - формула включения-исключения.

Все равно придется повозиться. Например, множества $A_1\cap A_2$ и $A_1\cap A_3$
не равномощны.

[--mS--]

Безусловно. А может, одинаковые буквы $bb$ на 1-ом и последнем местах тоже можно считать "стоящими рядом"? Как бы это упростило жизнь!

Туплю. Замкнуть в кольцо - жизнь не упростит, всё равно плохо.

[xaxa3217]

apatic писал(а):

Даже не понимаю, как это ограничение из двух рядом стоящих букв записать. Спасибо.

Назовем хорошей цепочкой длины $n$ последовательность $n$ букв набора ('a', 'b', 'c') без подряд идущих букв 'bb'. Обозначим за $f_n$ кол-во различных хороших цепочек длины $n$ оканчивающихся на 'b', а за $g_n$ кол-во различных хороших цепочек длины $n$ оканчивающихся НЕ на 'b'. Искомое число равно $f_7+g_7$. Выведем рекурентную для $f$ и $g$:
$f_n = g_{n-1}*1 = g_{n-1}$ - без последнего символа должна быть хорошей (не оканчиваться на 'b'), а сама может оканчиваться только на один символ - 'b'.
$g_n = f_{n-1}*2+g_{n-1}*2 = 2(g_{n-2}+g_{n-1})$ - если цепочка без последнего символа оканчивается на 'b', то в конец можно записать либо 'a', либо 'c'; если же она оканчивается на 'a' или 'c', то в конец можно записать опять же - либо 'a', либо 'c'.

Теперь складываем до седьмого члена (почти как по Фибоначчи), восстанавливаем по первому уравнению $f_7$, и получаем искомое число хороших цепочек длины 7. Вроде бы похоже на правду.

[TOTAL]

$$2^7C_8^0+2^6C_7^1+2^5C_6^2+2^4C_5^3+2^3C_4^4$$

[xaxa3217]

Да уж, еще проще получается, благо что хоть ответы совпадают

[apatic]

xaxa3217 писал(а):

Выведем рекурентную для $f$ и $g$:
$f_n = g_{n-1}*1 = g_{n-1}$ - без последнего символа должна быть хорошей (не оканчиваться на 'b'), а сама может оканчиваться только на один символ - 'b'.
$g_n = f_{n-1}*2+g_{n-1}*2 = 2(g_{n-2}+g_{n-1})$ - если цепочка без последнего символа оканчивается на 'b', то в конец можно записать либо 'a', либо 'c'; если же она оканчивается на 'a' или 'c', то в конец можно записать опять же - либо 'a', либо 'c'.

Теперь складываем до седьмого члена (почти как по Фибоначчи), восстанавливаем по первому уравнению $f_7$, и получаем искомое число хороших цепочек длины 7. Вроде бы похоже на правду.

Меня это решение очень заинтересовало. Но я не знаю, что такое рекуррентные соотношения, только сегодня начал читать про них. Можешь объяснить как их считать? Какие начальные значения?

Total писал(а):

писал

$$2^7C_8^0+2^6C_7^1+2^5C_6^2+2^4C_5^3+2^3C_4^4$$

А как это так получилось? Здесь используется правило суммы и произведения? Как составлена эта формула? Или это общее решение рекуррентного соотношения?

Добавлено спустя 13 минут 48 секунд:

Кажется, начинает доходить...