2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Подсчитать количество бинарных строк
Сообщение29.01.2017, 15:01 


15/10/13
14
Беларусь
Имеются бинарные строки (т.е. состоящие из цифр 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 
Заслуженный участник


26/05/14
981
Ошибка здесь:
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 


15/10/13
14
Беларусь
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 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: lantza


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group