2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Что-то вроде обобщения одной из интерпретаций чисел Каталана
Сообщение02.11.2008, 18:24 


21/06/08
17
Дан прямоугольник, с целочисленными сторонами равными $m,n\in\mathbb{N}$, разделённый на единичные квадраты.
Требуется найти явную формулу, $f_{m,n}$,находящию количество различных путей, из левого-нижнего угла до верхнего-правого, делая следующие ходы $\rightarrow,\uparrow,\nearrow$.
Найти значение производящей функции:
$1+\sum_{n=1}^{\infty}f_{n,n}x^{n}$

 Профиль  
                  
 
 Re: Что-то вроде обобщения одной из интерпретаций чисел Ката
Сообщение02.11.2008, 22:40 
Заслуженный участник


27/06/08
4063
Волгоград
Erken1 писал(а):
Дан прямоугольник, с целочисленными сторонами равными $m,n\in\mathbb{N}$, разделённый на единичные квадраты.
Требуется найти явную формулу, $f_{m,n}$,находящию количество различных путей, из левого-нижнего угла до верхнего-правого, делая следующие ходы $\rightarrow,\uparrow,\nearrow$.
Пусть $n\ge m$. Тогда $$f(m,n)=\sum_{i=0}^{m-1}C_{m+n-2-i}^iC_{m+n-2-2i}^{m-1-i}$$.

 Профиль  
                  
 
 
Сообщение03.11.2008, 08:49 


21/06/08
17
Спасибо.Можно ли увидеть обоснование данной формулы, и насколько я знаю, существует гораздо более приемлемая формула.

 Профиль  
                  
 
 
Сообщение03.11.2008, 13:19 
Заслуженный участник


27/06/08
4063
Волгоград
Erken1 писал(а):
Спасибо.Можно ли увидеть обоснование данной формулы,

Я рассуждал "в лоб". Суммируем число маршрутов: не содержащих ходов по диагонали, содержащих 1 диагональный ход, ... , m-1 диагональный ход.
Если, например, диагональных ходов k. то общее число ходов - n+m-2-k. Из них надо выбрать k диагональных, а из оставшихся - m-1-k вертикальных (считаем, что m - высота прямоугольника).
Цитата:
и насколько я знаю, существует гораздо более приемлемая формула.

Возможно. Я упрощать не пытался.

 Профиль  
                  
 
 
Сообщение03.11.2008, 20:30 


21/06/08
17
Можно интерпретировать данные числа,как коэффициенты,при степенях $x^my^n$,в сумме $1+\sum_{k=1}^{\infty}(1+x+y+xy)^{k}$

 Профиль  
                  
 
 
Сообщение03.11.2008, 21:18 
Модератор
Аватара пользователя


11/01/06
5710
Erken1 писал(а):
Можно интерпретировать данные числа,как коэффициенты,при степенях $x^my^n$,в сумме $1+\sum_{k=1}^{\infty}(1+x+y+xy)^{k}$

Тогда уж
$$\sum_{k=0}^{\infty} (x+y+xy)^k = \frac{1}{1-x-y-xy}$$

 Профиль  
                  
 
 
Сообщение04.11.2008, 05:34 


21/06/08
17
maxal писал(а):
Erken1 писал(а):
Можно интерпретировать данные числа,как коэффициенты,при степенях $x^my^n$,в сумме $1+\sum_{k=1}^{\infty}(1+x+y+xy)^{k}$

Тогда уж
$$\sum_{k=0}^{\infty} (x+y+xy)^k = \frac{1}{1-x-y-xy}$$

Это я к тому, что задача уже решена... :)

 Профиль  
                  
 
 
Сообщение04.11.2008, 14:10 
Заслуженный участник


27/06/08
4063
Волгоград
Erken1 писал(а):
Можно интерпретировать данные числа,как коэффициенты,при степенях $x^my^n$,в сумме $1+\sum_{k=1}^{\infty}(1+x+y+xy)^{k}$

Они какие-то бесконечные получаются...
Вот если брать коэффициенты при $x^my^n$ в сумме $\sum_{k=0}^{\infty}(x+y+xy)^{k}$, тогда они свопадут с моими, после очевидных поправок, связанных с тем, что я считал маршруты, пролегающие по клеткам, а не по узлам разбиения.

 Профиль  
                  
 
 
Сообщение04.11.2008, 20:21 


21/06/08
17
извиняюсь...конечно же, сумма должна выглядеть как у вас.
Просто опечатка.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group