Простые задачи по комбинаторике

Irbis-S

Подскажите плз общее направление решения, что-то никак не могу сообразить сходу, как они решаются
1) Сколько есть 20-разрядных двоичных чисел, чтобы никакие 2 нуля не стояли рядом.
и похожая задача
2) На окружности 10 точек, сколько есть несамопересекающихся ломаных, проходящих через все эти точки.

luherstag

Каждое такое двадцатиразрядное число либо начинается с единицы, и таких их столько же, сколько девятнадцатиразрядных чисел с этим свойством, либо с нуля, тогда на втором месте единица, и таких столько же, сколько восемнадцатиразрядных.

Irbis-S

Отлично, спасибо
Более-менее понятно.
А со второй задачей ?

Damrad

выбираешь точку. строишь из нее ломанную. Чтобы при этом "не отсечь" никакие точки и не оставить их вне пределов последующей достижимости ты должен очередное звено вести либо к самой первой по окружности точке справа, либо к самой первой по окружности точки справа.
в итоге получаем 20 * 2^18. ну и еще пополам поделить, так как не у ломанной что конец, что начало - один хрен. и мы их дважды нашим методом посчитали

griz_a

Здесь была лажа

Damrad

бля. я подумал, что там 20 точек
в итоге у меня получается 10 * 2^8 / 2

Irbis-S

Все, теперь разобрался.
Спасибо всем за советы

Irbis-S

Еще 2 задачи
Подскажите плз идею или подход к решению, без деталей.
1. Какое количество неразличимых слонов можно расставить на шахматной доске, что бы они не били друг друга.
2. Найти число способов такой расстановки

griz_a

Чернопольные и белопольные слоны расставляются независимо и одинаково.
Черных диагоналей всего 15, из них две одноклеточных. Каждый слон вычеркивает 2, кроме слонов стоящих на главной диагонали, те 3 или 4.
Отсюда строится очевидная верхняя оценка для числа слонов, строится примитивный пример как сделать за столько, да и какие примеры бывают тоже довольно понятно

Irbis-S

С количеством слонов понятно, спасибо.
Как быть с количеством способов расстановки ?

griz_a

Если мы ставим 7 чернопольных слонов, то надо одного обязательно в угол главной диагонали совать, а 6 остальных так чтобы они друг друга не били на 6 пар оставшихся линий.
Довольно понятно как на 6 пар попарно пересекающихся линий можно расставлять 6 слонов, чтобы каждый бил свои 2 :)

Irbis-S

Спасибо, и в самом деле несложно.
Последняя порция задач, намекните как подступиться к решению
Есть ассортимент из n блюд, из их всевозможных комбинаций получаются обеды.
1) Сколько съешь в сумме блюд (кол-во штук если есть по одному новому обеду каждый день ?
2) Сколько есть вариантов обедов с нечетным кол-вом блюд
3) Сколько съешь в сумме блюд (кол-во штук если есть по одному новому обеду с нечетным кол-вом блюд каждый день
Получаются какие-то гигантские выражения обычными средствами, подскажите как сделать грамотно

griz_a

ая вроде вопросов не должна вызывать? Посчитать, что каждое блюдо входит в 2^{n-1} обед легко.
2ая основывается на подсчете суммы биномиальных коэффициентов с нечетным индексом. Это 2^{n-1} из бинома ньютона для (1-1)^n
3ья - опять же легко понять сколько раз каждое блюдо входит в обеды.
Сколько четных наборов из n-1 бывает - 2^{n-2} аналогично тому что чуть выше.

Irbis-S

Спасибо большое.
И в самом деле ничего особо сложного, как только сам не догадался
Оставить комментарий
Имя или ник:
Комментарий: