2014 dxdy logo

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

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




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

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

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

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

 
 
 
 
Сообщение09.12.2008, 22:41 
apatic в сообщении #166252 писал(а):
да не, это понятно, что из общего кол-ва возможных перестановок (5040)


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

 
 
 
 
Сообщение09.12.2008, 22:46 
3 в 7 степени = 2187 - размещение с повторениями. Так?

 
 
 
 
Сообщение09.12.2008, 22:55 
apatic в сообщении #166255 писал(а):
343


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

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

apatic в сообщении #166255 писал(а):
3 в 7 степени = 2187 - размещение с повторениями. Так?


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

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

 
 
 
 
Сообщение09.12.2008, 23:17 
apatic в сообщении #166259 писал(а):
Что делать с ограничением неясно. Видимо *bb*****, *bbb****, *bbbbb*, а так же *bb*bbb и похожее - тоже недопустимо.


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

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

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

 
 
 
 
Сообщение10.12.2008, 00:51 
--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$
не равномощны.

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

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

 
 
 
 
Сообщение10.12.2008, 11:25 
Аватара пользователя
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. Вроде бы похоже на правду.

 
 
 
 
Сообщение10.12.2008, 13:51 
Аватара пользователя
$$2^7C_8^0+2^6C_7^1+2^5C_6^2+2^4C_5^3+2^3C_4^4$$

 
 
 
 
Сообщение10.12.2008, 17:35 
Аватара пользователя
Да уж, еще проще получается, благо что хоть ответы совпадают :)

 
 
 
 
Сообщение11.12.2008, 00:18 
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 секунд:

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

 
 
 [ Сообщений: 22 ]  На страницу 1, 2  След.


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