Сколько существует двоичных чисел с определенными условиями?

[b099ard]

Сколько существует двоичных чисел, которые содержат в своей записи ровно 7 нулей и 3 единицы и в их записи никакие две единицы не идут подряд.

Решение:
Всего десяти разрядное двоичное число
Перебераем варианты:
0001010001
0001010010
0001010101

0001001001
0001001010

0000101001
0000101010

....
Есть какая нибудь формула для этого?

-- Чт май 05, 2011 19:25:34 --

Вообще мне кажется что цыклически сдвигая влево на бит мы получим еще один вариант т.е. всего 4*7 = 28 вариантов

[Sonic86]

Можно попробовать составить рекуррентную формулу:
Пусть $M(n,k)$ - число двоичных чисел длины $n$ с $k$ единицами ($k \leq n$). Рассмотрим левый край числа. Он может начинаться либо с нуля единиц, либо с одной единицы, либо с 2-х единиц, либо с 3-х, ..., причем после каждой группы единиц необходимо идет нуль. Тогда
$M(n;n)=1$
$k<n \Rightarrow M(n,k)=\sum\limits_{j=0}^{n-1}M(n-j-1,k-j)$.
Для начала

[venco]

b099ard в сообщении #442329 писал(а):

Сколько существует двоичных чисел, которые содержат в своей записи ровно 7 нулей и 3 единицы и в их записи никакие две единицы не идут подряд.

Решение:
Всего десяти разрядное двоичное число
Перебераем варианты:
...

Мне кажется от вас требуется решить задачу без перебора.
Если между каждой парой единиц есть ноль, то что получится, если этот ноль убрать?

[nnosipov]

Воткнём три единицы в восемь промежутков между семью нулями $C_8^3$ способами. Разве нет?

[venco]

nnosipov в сообщении #442341 писал(а):

Воткнём три единицы в восемь промежутков между семью нулями $C_8^3$ способами. Разве нет?

Пропустили условие "никакие две единицы не идут подряд".

[nnosipov]

venco в сообщении #442343 писал(а):

nnosipov в сообщении #442341 писал(а):

Воткнём три единицы в восемь промежутков между семью нулями $C_8^3$ способами. Разве нет?

Пропустили условие "никакие две единицы не идут подряд".

Между любыми двумя единицами есть хотя бы один ноль.

[venco]

nnosipov в сообщении #442344 писал(а):

venco в сообщении #442343 писал(а):

nnosipov в сообщении #442341 писал(а):

Воткнём три единицы в восемь промежутков между семью нулями $C_8^3$ способами. Разве нет?

Пропустили условие "никакие две единицы не идут подряд".

Между любыми двумя единицами есть хотя бы один ноль.

Да, получается то же самое. Я на другой подход намекал. А вы всё испортили прямым решением учебной задачи.

[b099ard]

Sonic86 в сообщении #442339 писал(а):

Можно попробовать составить рекуррентную формулу:
Пусть $M(n,k)$ - число двоичных чисел длины $n$ с $k$ единицами ($k \leq n$). Рассмотрим левый край числа. Он может начинаться либо с нуля единиц, либо с одной единицы, либо с 2-х единиц,

либо с 3-х, ..., причем после каждой группы единиц необходимо идет нуль. Тогда
$M(n;n)=1$
$k<n \Rightarrow M(n,k)=\sum\limits_{j=0}^{n-1}M(n-j-1,k-j)$.
Для начала

Не с двух и трех не может они идут подряд, я написал варианты для правого края.
если переносить числа с левого края на правый то это даст еще 7*9 варантов + первоначальные 7 всего 7*10=70 вариантов.

-- Чт май 05, 2011 19:49:23 --

nnosipov в сообщении #442341 писал(а):

Воткнём три единицы в восемь промежутков между семью нулями $C_8^3$ способами. Разве нет?

А что вы подразумеваете под промежутками? Нули? Тогда 4 промежутка.

[nnosipov]

venco в сообщении #442347 писал(а):

Да, получается то же самое. Я на другой подход намекал. А вы всё испортили прямым решением учебной задачи.

Не беда. Пусть найдут и Ваше решение, это в любом случае полезно. (Сегодня проводил уроки по элементам комбинаторики в 9-м классе и решал как раз подобные задачки. Приятно порадовался, когда школьники несколькими способами решили одну и ту же комбинаторную задачу, вот такую: в кондитерской продают пирожные трёх сортов, а надо купить семь пирожных; найти число способов это сделать. Её и в этой теме можно порешать.)

-- Чт май 05, 2011 22:56:01 --

b099ard в сообщении #442350 писал(а):

nnosipov в сообщении #442341 писал(а):

Воткнём три единицы в восемь промежутков между семью нулями $C_8^3$ способами. Разве нет?

А что вы подразумеваете под промежутками? Нули? Тогда 4 промежутка.

Выпишите семь нулей в ряд и приглядитесь.

[zhekas]

3 еденички - это стенки ящиков придвинутых друг к другу.

Получаются 4 ящика. Чтобы уденицы не стояли рядом. Положим в центральные ящики по шарику (по нолику).

Оставшиеся шарики разложим произвольно.

Итого, получилась задача: разложить 7-2=5 шариков по 4-м ящикам

$$C_{4+5-1}^5=C_8^5=C_8^3$$

[Евгений Машеров]

Допишем к 10-значному двоичному числу 0, получая 11-значное, оканчивающееся нулём. Очевидно, количество удовлетворяющих условию чисел от этого не изменится. Но мы сможем рассматривать "единицу, за которой не следует другая единица", как новый символ Х. Это, в свою очередь, позволяет свести задачу к определению числа различных последовательностей из 3-х элементов Х и 5 нулей. Число это равно $ C_8^5=56$

[ewert]

Выложу-ка вариант решения venco, раз он сам стесняется.

Задача А: сколько существует двоичных комбинаций с семью нулями и тремя единицами, у которых единицы не стоят рядом?

Задача В: сколько существует вообще двоичных комбинаций с пятью нулями и тремя единицами? Тут ответ тривиален: $C_8^3=C_8^5$.

Между тем задачи эквивалентны: любая комбинация из задачи А после удаления одного нолика между первой и второй единичкой и одного между второй и третьей превращается в некую комбинацию задачи В и наоборот, и это соответствие взаимно однозначно.

[nnosipov]

Как-то стало интересно: сколькими способами можно подсчитать число сочетаний с повторениями? Нашёл четыре разных доказательства. Может, есть ещё?

[b099ard]

Евгений Машеров в сообщении #442624 писал(а):

Допишем к 10-значному двоичному числу 0, получая 11-значное, оканчивающееся нулём. Очевидно, количество удовлетворяющих условию чисел от этого не изменится.

Совсем не очевидно
допустим не три еденицы, а две и не семь нулей а два
тогда число вариантов до приписки:
0101
1001
1010
после приписки:
01010
10010
10100
01001

Евгений Машеров в сообщении #442624 писал(а):

Но мы сможем рассматривать "единицу, за которой не следует другая единица", как новый символ Х. Это, в свою очередь, позволяет свести задачу к определению числа различных последовательностей из 3-х элементов Х и 5 нулей. Число это равно $C_8^5=56$

А полную формулу можно увидеть?
Мы можем считать комбинации строки 01 как x в строке длиной 10 и строку 10 как y в этой же строке, причем y не может идти за x, а наоборот можно.

Поэтому y считаем первым это$C_5^4$
на x остается $C_4^3$ дважды
= 13

[Евгений Машеров]

Нет, можно идти и сложным путём.

(Оффтоп)

- Доченька, что привезти тебе из чужих краёв?
- Привези, батюшка, чудище страшное для утех сексуальных!
- Да что ты такое говоришь, доченька?! Проси чего другого!
- Ну хорошо, пойдёт сложным путём. Привези, батюшка, цветочек аленький!

Но как-то естественно исходить из того, что если нет двух единиц подряд, то, значит, за каждой единицей следует 0, и пару 10 можно рассматривать как новый неделимый символ (последняя единица нарушает это, но если приписать в конце 0, то и она исключения не порождает). Число пар символов 10 (обозначаемых через Х), очевидно, равно числу исходных единиц, а число оставшихся к размещению среди них нулей равно разности числа 10-1=9 и числа единиц.
То есть задача естественно свелась к "сколькими способами можно расставить три Х-а и 5 0". Общая формула "Цэ из эн по ка".
Но, можно, безусловно, и все варианты явно выписывать. Конституция позволяет (С). Не позволяет лишь получить, как у Вас выше, 01001 приписыванием нуля справа к заданному набору единиц и нулей.