Задачка на пути в квадратной решетке

[jenk1ns]

Доброго времени суток,форумчане.
Столкнулся с такой задачкой
Сколько имеется различных путей от верхнего левого угла решетки до правого нижнего угла квадратной решетки размера 40 на 40,если двигаться можно только в следующий узел справа или ниже.
подскажите какую-нибудь формулу или объясните с чего и куда копать
ЗЫ.Читал про "Числа Шрёдера" и "Числа Деланноя" но они не подходят,совсем уже не знаю с чего начать
Кто знает помогите, пожалуйста!

[ИСН]

40 - это крайне много. Попробуйте начать с доски 2 на 2. Сколько там путей?

-- Чт, 2012-03-29, 23:10 --

Теперь эти числа Деланноя. Да, это не то, но как Вы их нашли? OEIS? Или гуглом по ключевым словам? Каким?

[jenk1ns]

ИСН в сообщении #553588 писал(а):

40 - это крайне много. Попробуйте начать с доски 2 на 2. Сколько там путей?

-- Чт, 2012-03-29, 23:10 --

Теперь эти числа Деланноя. Да, это не то, но как Вы их нашли? OEIS? Или гуглом по ключевым словам? Каким?

я ручками посчитал для 2х2,3х3,4х4 получилось 6,18,32,попытался найти все закономерности,не получилось,но это было пальцем в небо попытки
а про числа Деланноя наткнулся в ходе гугления,вбил "комбинаторика на решетках" и где-то 2-3яя ссылка была в википедию на числа Шредера,а там уже был линк на числа Деланноя

[ИСН]

Ага, ясно. Ну так вот, про те числа забудьте, потому что Ваша задача гораздо проще, а вот что бы такого посоветовать... а, знаю! Возьмите эту решётку и тупо подпишите в каждом узле число способов, коими туда можно придти. В самом верхнем левом будет стоять цифра 1 (ничего не делал, вот и пришёл - 1 способ). В соседних с ним - тоже по 1. А дальше - - -

[Dan B-Yallay]

Или можно еще вот как:

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