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

[Neos]

maxal, для $ s(4,3)$ я выбрасываю комбинации с 3 подряд единичками $ 1110 $ и $ 0111 $. Ок ! пропустил комбинацию $1111$ . Вычислял путем сдвига $k$ бит.
Благодарю за замечание.

Вопрос. Откуда в комбинаторной задаче появилось выражение:

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

?

[Null]

Это производящая функция. При ее разложении в ряд Тейлора в 0 его коэффициенты совпадут с искомой последовательностью.

[Neos]

Ок, Null , спасибо.

[Euler7]

maxal в сообщении #768082 писал(а):

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

Объясните пожалуйста, как вы пришли к этой функции?

[maxal]

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

maxal в сообщении #768082 писал(а):

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

Объясните пожалуйста, как вы пришли к этой функции?

Пусть в последовательности $t$ нулей. Обозначим через $y_i$ ($i=0,1,\dots,t$) количество единиц между $i$-м и $(i+1)$-м нулём. Нас интересует количество решение уравнения $y_0 + \dots + y_t = n - t$ в целых числах $0 \leq y_i < k$. Нетрудно понять, что это количество равно коэффициенту при $x^{n-t}$ в разложении $(1+x+\dots+x^{k-1})^{t+1}$, что то же самое, что коэффициент при $x^{n+1}$ в

$$(x+x^2+\dots+x^k)^{t+1} = \left(\frac{x-x^{k+1}}{1-x}\right)^{t+1}.$$

Суммируя по различным $t$, окончательно имеем:

$$\sum_{t=0}^{\infty} \left(\frac{x-x^{k+1}}{1-x}\right)^{t+1} = x\frac{1-x^k}{1-2x+x^{k+1}}.$$

Таким образом, нас интересует коэффициент при $x^n$ в $\frac{1-x^k}{1-2x+x^{k+1}}$.

[frodohrucik]

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

Подскажите пожалуйста при первом j = 0 1/( n! * (-n)! ) чему будет равно такое выражение

Deggial: предупреждение за неправильное оформление формул.