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

[xaxa3217]

Цитата:

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

Это простой индукционный шаг, в котором, при уверенности в правильности всех предыдущих, делается обоснованно-корректное продвижение "вперед". Все начинается с базы - первого шага, в данном случае $g_2 = 6, g_1 = 2$ в чем легко убедится мелким перебором.

Цитата:

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

Всего навсего используется тот факт, что буква 'b' может стоять только между двумя "небэ" (ну или в конце, начале цепочки).

[apatic]

xaxa3217, точно индукционный шаг, не подумал про него. Уже разобрался, кажется, перебором. т.е. для n=1 возможны вариант "а" "b" "c" g1=2;
для n=2 "аа" "bb" "ac" "ba" "bb" "bc" "ca" "cb" "cc" g2=6 и тд. формула подходит.

Пока не могу осознать, почему искомое число равно $f_7+g_7$.

Добавлено спустя 15 минут 44 секунды:

в итоге получилось 1224. т.е. больше половины от числа возможных цепочек без ограничения (2187).

[xaxa3217]

Не спешите доходить до $f_7 + g_7$ Обратите внимание еще раз на то, как были определены эти две последовательности. Перечитайте первое мое сообщение в этой теме, там вроде бы все понятно изложено. Отмечу только, что мы разбиваем искомое число вариантов на два НЕ пересекающихся класса цепочек - тех что оканчиваются на 'b' и не содержат в себе подстроки 'bb', и те что оканчиваются на что-то другое 'a' или 'c'. Любая строка не принадлежащая ни первому, ни второму классу нас вообще не устраивает (в ней есть подстрока 'bb'), именно поэтому $f_7+g_7$ в результате дает нужное кол-во.

[apatic]

Вроде бы даже разобрался, однако расписал все возможные цепочки длины 3, а таких 27. в них присутствуют abb; bba;bbb;bbc;cbb - т.е. 5 плохих цепочки. В итоге 22 интересующие нас комбинации.
Смотрим формулы :
$g_3 = 2(g_1+g_2) = 2(2+6)=16, f_3=g_2=6; f_3 + g_3 = 24$ что-то не сходится.

[TOTAL]

apatic писал(а):

Total писал(а):

писал

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

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

Поймайте $K$ двуглавых и $N-2K+1$ одноглавых драконов и прислоните их к стенке разными способами:
,:mrgreen: , , , ,:mrgreen: (всего $C_{N-K+1}^K$ способов)
Левую голову каждого двуглавого дракона замените буквой $B$, а самую правую голову в шеренге отрубите:
,$B$ , , , ,$B -$
Оставшиесы головы замените буквами $A$ и $C$ разными способами:
$A,$ $BA,$ $C,$ $C,$ $A,$ $B -$ (всего $2^{N-K}$ способов)

Таким образом, существует $2^{N-K}C_{N-K+1}^K$ подходящих слов из $N$ букв с $K$ буквами $B$

[xaxa3217]

apatic, ну вы даете, я даже специально программку написал, чтобы не обсчитаться:

#include <math.h>
#include <stdio.h>

int main()
{
   int g[11];
   g[2] = 6;
   g[1] = 2;
   //

   for(int i = 3; i <=7; i++)
   {
      g[i] = 2*(g[i-1]+g[i-2]);
   }
   
   printf("%u\n", g[3]+g[3-1]);
   printf("%u\n", g[7]+g[7-1]);

   return 0;
}

У меня, признаюсь, часто ошибки такого рода возникают, так что видеть в '16' число равное 18 не Вы один умеете

[apatic]

Граждане, большое спасибо за помощь и конечно же за терпение(особое спасибо xaxa3217 и TOTAL). В 3 ночи уже мозг опух от комбинаторики и теории графов, а эта задача прямо-таки заклинила. Но утром разобрался, расписал и защитился. Ещё раз спасибо. Мне бы ваше терпение.