Количество последовательностей.

[yestlmush]

Пришли на ум две похожие задачи:

1) посчитать количество двоичных последовательностей длины n, не содержащих k единиц подряд,
2) посчитать количество двоичных последовательностей длины n, не содержащих k одинаковых символов подряд.

Понятно, что какое-то динамическое программирование, но что-то не придумать никак.
Подскажите, пожалуйста.

[Euler7]

А комбинаторикой тут не обойтись?

[nikvic]

Для битовой последовательности можно составить цепь Маркова - там появится матрица и её степени.

[yestlmush]

Euler7 в сообщении #754514 писал(а):

А комбинаторикой тут не обойтись?

Ну хорошо, как тут комбинаторику пропихнуть?

[nikvic]

Рекурренцией для числа слов со всеми допустимыми видами хвоста.

[yestlmush]

nikvic в сообщении #754530 писал(а):

Рекурренцией для числа слов со всеми допустимыми видами хвоста.

Да, но конкретно для такой задачи проблема, ибо "хвост" нужен длины k.

[worm2]

У меня получилось так: $n$ целое, $k$ натуральное. $s(n,k)=2s(n-1,k)-s(n-k-1,k)$, $s(n,k)=1$, если $n\leqslant 0$, $s(n,k)=2^n$, если $n<k$.

[ewert]

Для количества наборов, в которых есть цепочки из $k$ единиц:

$S(n+1,k)=2\,S(n,k)+2^{n-k}-S(n-k,k),\qquad n\geqslant k;$

$S(k,k)=1;$

$S(n,k)\equiv0,\qquad n<k.$

И это правда.

[maxal]

yestlmush в сообщении #754444 писал(а):

Пришли на ум две похожие задачи:
1) посчитать количество двоичных последовательностей длины n, не содержащих k единиц подряд,
2) посчитать количество двоичных последовательностей длины n, не содержащих k одинаковых символов подряд.

Ответ к 1) - это коэффициент при $x^n$ в разложении

$$\frac{1-x^k}{1-2x+x^{k+1}}$$

Откуда нетрудно получить явную формулу:

$$q(n,k) - q(n-k,k)$$

где

$$q(n,k) = \sum_{j=0}^{\lfloor n/(k+1)\rfloor} \binom{n-jk}{j} (-1)^j 2^{n-j(k+1)}.$$

Например, для $k=3$, это ряд

$$\frac{1-x^3}{1-2x+x^4} = 1 + 2x + 4x^2 + 7x^3 + 13x^4 + 24x^5 + 44x^6 + 81x^7 + 149x^8 + 274x^9 + \dots$$

и коэффициет при $x^9$ здесь равен $q(9,3)-q(6,3)=326-52=274$.

Для 2) тоже можно получить ответ в явном виде.

[Neos]

yestlmush в сообщении #754444 писал(а):

Пришли на ум две похожие задачи:

1) посчитать количество двоичных последовательностей длины n, не содержащих k единиц подряд,
2) посчитать количество двоичных последовательностей длины n, не содержащих k одинаковых символов подряд.

1) $ s(n,k) = 2^{n}-(n-k+1) $

2) $ s(n,k) = 2^{n}- 2(n-k+1) $

почему-то получилось так

[ewert]

Neos в сообщении #768245 писал(а):

1) $ s(n,k) = 2^{n}-(n-k+1) $

$s(k+1,k)=?$
$s(n,2)=?$

[Neos]

$ s(k+1,k) = 2^{k+1} -2 $

$ s(n,2) = 2^n - (n-1) $

$ ( n \ge k ) $

Вижу ошибку. Выбросил только по одной "сплошной" последовательности. Ок! Нужно учесть
несколько поледовательностей. Но, формула будет работать, если
$ k $ больше $ n/2 $

[ewert]

Neos в сообщении #768261 писал(а):

Но, формула будет работать, если
$ k $ больше $ n/2 $

Так не бывает. Т.е. не бывает так вообще, чтобы на половине траектории формула была линейной, а на другой -- нет.

[Neos]

Для случая 1) общий вид

$ s(n,k) = 2^{n} - F(n,k)(n-k+1) $,

где $ F(n,k) = 1 $ при $ k > \frac{n}{2} $

с видом $ F(n,k) $ нужно разбираться.

Хорошая задача при внешней простоте формулировки.

ewert, благодарю за замечание.

Не нужно ли привлекать частное(целую часть) и остаток от деления $n$ на $k$ ?

[maxal]

Neos в сообщении #768296 писал(а):

Для случая 1) общий вид

$ s(n,k) = 2^{n} - F(n,k)(n-k+1) $,

где $ F(n,k) = 1 $ при $ k > \frac{n}{2} $

с видом $ F(n,k) $ нужно разбираться.

Ваше утверждение неверно. Например, для $n=4$ и $k=3$ ответом является $13$, что неравно $2^4 - (n-k+1)=14$.

А вообще я привел явную формулу для $s(n,k)$ выше. Вряд ли получится получить что-то более простое.