Задача на комбинаторику

paha73

Есть полоска длиной 2k+p (k,p - натуральные числа
Есть покрывашки длиной k (их много).
Полоску надо покрыть покрывашками так, чтоб покрывашки не вылезали за края полоски, не совпадали при наложении, но могли пересекаться
сколько способов покрыть полоску покрывашками?

stm25972421

в такой постановке - бесконечно много.

zuzaka

кхм, читай внимательно

sagemma

Видимо, имелось в виду, что край покрывашки должен находиться на целом расстоянии от края полоски.

lilith000007

Все верно
можно так порыть:

__
__
__
__

а можно так:

__
__

причем увеличивая площадь наложение, можно добfвлять ещё фигнюшек
Нужно видимо добавить условие, что длинна пересечения должна быть натуральным числом

zuzaka

Я так полагаю, там возможны лишь натуральные шаги?

paha73

ну конечно только натуральные,
иначе в чем бы был смысл задачи?

tvm131

только рекуррентная формула получается

Sander

какая конкретно?
//
, кстати, если смотреть на общую формулу, как на 2^{k+p}-f(p
то f(p)>=2^p. Вот так.

lilith000007

Такой вопрос :
эти наложения одинаковые?

____ ____
____
и
____ ____
____

plugotarenko

Я бы немного уточнил.
2^{k+p-1}-f(p где то f(p)<=2^p.

tvm131

n(2k+p)=2^(p+k-1)-(сумма по t от 0 до p-1) (n(t+k)*2^(p-1-t
где n(x) - колво покрывающих расположений полосок длины k на полоске длины x

Sander

реккурентная формула:
F(2k+p)=F(2k+p-1)+F(2k+p-2)+...+F(2k+p-k)

tvm131

это разные наложения

Sander

хм.
если p=0,то кол-во покрытий равно 2^{k-1}
У тебя вроде меньше получается.
ты точно правильно посчитал?

tvm131

перепутал п и к. Исправился

Sander

Почему F(2k+p)=F(2k+p-1)+F(2k+p-2)+...+F(2k+p-k) ?
Рассмотрим покрытие.Рассмотрим первую маленькую полоску.
Уберем ее.
Следующая полоска должна начинаться с одной из след. клеток: 2,3,...,k+1.
Если начинается с 2-й, то вариантов таких "до-покрытий" F(2k+p-1
если с 3-й, то --- F(2k+p-2) и т.д.
надеюсь более-менее понятно.

paha73

ага, спасибо
Оставить комментарий
Имя или ник:
Комментарий: