2014 dxdy logo

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

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




 
 Подсчитать количество бинарных строк
Сообщение29.01.2017, 15:01 
Имеются бинарные строки (т.е. состоящие из цифр 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}$

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

 
 
 
 Re: Подсчитать количество бинарных строк
Сообщение29.01.2017, 18:04 
Ошибка здесь:
semigradsky в сообщении #1188264 писал(а):
Видно что кол-во получившихся строк - это то же, что и кол-во вариантов разложения $n-2k+1$ шара по $k+1$ корзине.
Т.е. сочетания с повторениями:
$\left({n-2k+1 \choose k+1}\right) = {n-k+1 \choose k+1}$


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

 
 
 
 Re: Подсчитать количество бинарных строк
Сообщение29.01.2017, 20:12 
slavav в сообщении #1188317 писал(а):
сколькими способами целое число $S$ можно представить в виде суммы $k$ неотрицательных целых чисел?

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

Возвращаясь к первоначальной задаче, получаем:
${n-k+1 \choose k}$


Спасибо!

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

 
 
 [ Сообщений: 4 ] 


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