Комбинаторика, задача на раскраски

[parean]

Подскажите пожалуйста правильный подход, которым решается следующая задача:
Есть $n$ белых шаров, лежащих в ряд. Сколькими способами некоторые из них можно покрасить в черный цвет так, чтобы $>k$ шаров черного цвета не лежали вместе. Для конкретных чисел я могу придумать решение, а в общем случае для $n$ и $k$ что-то не получается.

[Shadow]

parean в сообщении #1297472 писал(а):

Для конкретных чисел я могу придумать решение, а в общем случае для n и k что-то не получается.

Ну для $k=2$ - это числа Фибоначчи $F_{n+1}$ Доказать можете? А в общем случае - не знаю.

[parean]

Shadow в сообщении #1297544 писал(а):

parean в сообщении #1297472 писал(а):

Для конкретных чисел я могу придумать решение, а в общем случае для n и k что-то не получается.

Ну для $k=2$ - это числа Фибоначчи $F_{n+1}$ Доказать можете? А в общем случае - не знаю.

Почему? Пусть n=3, k=2, тогда по условию задачи подряд не должно лежать три и более шара, что в данном случае достигается всего одним единственным вариантом: когда все шары покрашены в черный. Значит количество подходящих вариантов 8-1=7, а 7 вообще не число Фибоначчи.

[grizzly]

parean в сообщении #1297580 писал(а):

Почему?

Имелось в виду для $k=1$.

[waxtep]

Shadow в сообщении #1297544 писал(а):

А в общем случае

можно посмотреть здесь http://mathworld.wolfram.com/Fibonaccin-StepNumber.html

[Pphantom]

parean, оформляйте формулы (даже очень маленькие) правильно. Один раз я их исправил за Вас, но не надо считать это нормой.

[parean]

Shadow в сообщении #1297544 писал(а):

parean в сообщении #1297472 писал(а):

Для конкретных чисел я могу придумать решение, а в общем случае для n и k что-то не получается.

Ну для $k=2$ - это числа Фибоначчи $F_{n+1}$ Доказать можете? А в общем случае - не знаю.

Получилось, что для $k=1$ это $F_{n+2}$, но да, могу.
База индукции есть, она проверяется в лоб.
ИП: Пусть есть выписанные в столбик все возможные раскраски $k$ шаров. Мы записываем рядом ещё один, точно такой же столбик, и в первом столбике добавляем к каждой раскраске слева ещё один белый шар, а во втором ещё один чёрный, получая тем самым все возможные раскраски $k+1$-ого шара. Так как по условию белый шар никак не уменьшает и не увеличивает количество допустимых вариантов, в первом столбике их столько же, сколько есть допустимых раскрасок для $k$ шаров. Во втором столбике черный шар уменьшает количество вариантов, если до его добавления самым левым шаром тоже был черный. Значит нас интересуют только те варианты, где самый левый шар в раскраске из $k$ элементов был белым, а это совпадает по ранее описанному с количеством раскрасок $k-1$-ого шара. Итого, на $k+1$ шаге искомое число есть сумма двух предыдущих. Эти же рассуждения легко обобщаются на общий случай, нужно только смотреть на большее количество предыдущих раскрасок, текущая сумма равна сумме k предыдущих. Спасибо за помощь.

-- 15.03.2018, 22:37 --

Pphantom в сообщении #1297607 писал(а):

parean, оформляйте формулы (даже очень маленькие) правильно. Один раз я их исправил за Вас, но не надо считать это нормой.

Прошу прощения, впредь буду иметь ввиду.

-- 15.03.2018, 22:38 --

waxtep в сообщении #1297601 писал(а):

Shadow в сообщении #1297544 писал(а):

А в общем случае

можно посмотреть здесь http://mathworld.wolfram.com/Fibonaccin-StepNumber.html

Спасибо! Очень легко всё, оказывается.