Подсчитать количество бинарных строк

[semigradsky]

Имеются бинарные строки (т.е. состоящие из цифр 0 и 1 ) длины $n$, содержащие $k$ единиц, в которых никакие две единицы не стоят рядом.
Подсчитать сколько таких строк существует.

Мои размышления:

1. Справа от первых $(k-1)$ единиц выкидываем по нулю.
Этим мы избавляемся от условия "никакие две единицы не стоят рядом".
Теперь это самые обычные бинарные строки.

2. Каждую бинарную строку можно взаимно однозначно сопоставить со строкой количества нулей между единицами.
Например строке $100101100001...$ соответствует строка $02104...$.
В получившейся строке $k+1$ цифр, а сумма цифр равна $n-k-(k-1)=n-2k+1$ (длина первоначальной строки - кол-во единиц - кол-во ранее выкинутых нулей).

Видно что кол-во получившихся строк - это то же, что и кол-во вариантов разложения $n-2k+1$ шара по $k+1$ корзине.
Т.е. сочетания с повторениями:

$\left({n-2k+1 \choose k+1}\right) = {n-k+1 \choose k+1}$

Ответ получился неверный. Знаю другой способ решения (шаг 1 такой же, шаг 2 другой, проще), там получается верный ответ:

${n-k+1 \choose k}$

Но что в этом решении не так?

[slavav]

Ошибка здесь:

semigradsky в сообщении #1188264 писал(а):

Видно что кол-во получившихся строк - это то же, что и кол-во вариантов разложения $n-2k+1$ шара по $k+1$ корзине.
Т.е. сочетания с повторениями:
$\left({n-2k+1 \choose k+1}\right) = {n-k+1 \choose k+1}$

Чтобы проверить себя решите задачу: сколькими способами целое число $S$ можно представить в виде суммы $k$ неотрицательных целых чисел?

[semigradsky]

slavav в сообщении #1188317 писал(а):

сколькими способами целое число $S$ можно представить в виде суммы $k$ неотрицательных целых чисел?

Понял. Разложить $S$ шаров в $k$ корзин это то же самое, что и составить ряд из $S$ шаров и $k-1$ перегородки. Число различных рядов:

${S+k-1 \choose k-1}$

Возвращаясь к первоначальной задаче, получаем:

${n-k+1 \choose k}$

Спасибо!

[tolstopuz]

Кстати, есть способ решить эту задачу в одно действие: написать в ряд $n-k$ нулей, а потом решить, в какие из $n-k+1$ промежутков попадут единицы.