Как найти количество непересекающихся ломаных?

[Ktina]

Имеется целочисленная решётка. Нужно найти количество непересекающихся ломаных длины $n$, выходящих из данной точки. Легко найти верхнюю границу: $\frac{4}{3}\cdot 3^n$, поскольку для первого звена 4 варианта, для последующих - не более трёх (имеется в виду, что ломаная может проходить только по линиям решётки).

А как найти точную формулу?

[Aleksandr Pavlovich]

Легко предложить вариант нижней границы: $2^n$ - ломаные со звеньями идущими только вправо или вверх.

Но я сомневаюсь, что можно найти точную формулу.
Как бы её можно было получить?
Например вряд ли получится индукцией по $n$, т.к. есть не самопересекающиеся ломаные, к которым невозможно добавить ещё одно звено.

[Профессор Снэйп]

А я условие не до конца понял.

Что значит "непересекающиеся"? Вот если бы было "несамопересекающиеся", всё было бы понятно. А так...

Верно ли, что надо найти максимально возможное количество ломаных, которые имеют конец в данной точке и не имеют других общих точек? Или требуется нечто другое?

[Ktina]

Профессор Снэйп в сообщении #568084 писал(а):

А я условие не до конца понял....

...Верно ли, что надо найти максимально возможное количество ломаных, которые имеют конец в данной точке и не имеют других общих точек?

Да, именно это. Просто сформулировала неудачно.

-- 06.05.2012, 19:58 --

Aleksandr Pavlovich в сообщении #568082 писал(а):

Легко предложить вариант нижней границы: $2^n$ - ломаные со звеньями идущими только вправо или вверх.

Это не совсем верно. Две различные ломаные указанного вида могут иметь общую точку (отличную от той, из которой они обе исходят).

[Профессор Снэйп]

Ktina в сообщении #568086 писал(а):

Да, именно это. Просто сформулировала неудачно.

Ну тогда ответ $4$

[Ktina]

Профессор Снэйп в сообщении #568089 писал(а):

Ktina в сообщении #568086 писал(а):

Да, именно это. Просто сформулировала неудачно.

Ну тогда ответ $4$

Значит, я что-то напутала. Пойду ещё подумаю над переформулировкой условия.

-- 06.05.2012, 20:11 --

Всё-таки, придётся заменить на "несамопересекающихся".

[Профессор Снэйп]

Ktina в сообщении #568090 писал(а):

Всё-таки, придётся заменить на "несамопересекающихся".

Да, я тоже думаю, что так вернее.

Единственное, что пока ясно - ответ кратен четырём Может, кроме начальной точки ещё и направление первого звена стоит зафиксировать? Впрочем, это всё несущественно... А задача, похоже, сложная. Не уверен, что там есть какая-то простая формула.

Можно при малых $n$ вычислить значения перебором, а потом в OEIS последовательность поискать

[Ktina]

Профессор Снэйп в сообщении #568095 писал(а):

Можно при малых $n$ вычислить значения перебором, а потом в OEIS последовательность поискать

Я об этом думала, но где гарантия, что в нём кронштейн летит прибитый найденная последовательность отразит решение?

[Профессор Снэйп]

Ktina в сообщении #568100 писал(а):

...где гарантия, что найденная последовательность отразит решение?

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

[Ktina]

Профессор Снэйп в сообщении #568103 писал(а):

Ktina в сообщении #568100 писал(а):

...где гарантия, что найденная последовательность отразит решение?

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

Вот она, родимая: https://oeis.org/A001411