Придумал задачку по комбинаторике

forester_200

Сколькими способами можно разложить в линию [math]$n$[/math] шаров белого и синего цвета так, чтобы никакие два синих не стояли рядом.
Вроде, формулировка простая, а вот "школьное" решение придумать не удалось.

Vlad128

Для подогрева интереса
:(

forester_200

Ок, убираю ответ :)

Vlad128

А, ну вообще такие задачи — это классика олимпиадного программирования, они все почти решаются динамикой. Просто если ставить ее математически, то да, замкнутая формула. Но метод относительно школьный (объяснить школьнику никакой сложности не составляет, нам показывали этот прием в школе).

var24

См. вывод статистики Ферми-Дирака.

forester_200

Я тоже в школе был знаком с методом, которым получается основное соотношение. Но он всё-таки посложнее, чем какие-нибудь факториальчики, числа сочетаний, задачки на расстановку предметов и т.п., которые худо-бедно проходятся в обычной, не физико-математической, школе. Так что понятие "школьности" тут весьма относительное, согласен.

griz_a

Это классическая задача, в задачнике Зубкова, кажется, есть, да и на форуме всплывала когда-то.
Решение линейного рекуррентного соотношения, кстати, вполне школьный метод.

forester_200

Ну, значит, можно записываться в классики

forester_200

См. вывод статистики Ферми-Дирака.
Нельзя ли поподробнее, мой Повелитель Снов? (с)

griz_a

Можно зафиксировать число синих шаров и считать, что мы расставляем k синих шаров по n+1-k местам (между белыми шарами и слева и справа от них).
То есть ответ будет
[math]$$\sum\limits_{k=0}^{[(n+1)/2]} C_{n+1-k}^k,$$[/math]
но дальше эта сумма хорошо считается только рекуррентно, афаик.
Это, в принципе, неудивительно, в комбинаторике сплошь и рядом в простеньких задачах совершенно несчитаемые суммы.

var24

Извини, я неправильно понял условие. Это решение для жестко заданных количеств шаров разного цвета (n синих и m белых, например а у тебя N - суммарное, как я понимаю. Т.е. мне нужно будет еще найти сумму по всем вариантам разбиения шаров на два класса.
А для фиксированного случая выводится просто — вначале кладем белые шары и ищем как разместить синие по полученным "ящикам".

forester_200

Я шёл таким же путём. Но про рекуррентное соотношение подумал после того, как посчитал 5-6 примеров этой суммы. Был удивлён, что эта сумма принимает значения, равные... :cool:

iri3955

Любое число однозначно кодируется через систему исчисления Фибоначчи, причём никакие 2 единицы не стоят рядом.
Значит ответ - n+1-е число Фибоначчи.
Ну, либо да, можно то же самое получить рекуррентно

forester_200

Извини, я неправильно понял условие.
Нее, дружище, это я не очень чётко написал условие. Можно было сформулировать так, чтобы не возникало "смысловых галлюцинаций", но было бы длиннее и корявее :)

forester_200

Ахрененно! :D :D :D :D :D :D :D

gera2707

шаров белого и синего цвета
а почему белого и синего, а не белого и чёрного?
Оставить комментарий
Имя или ник:
Комментарий: