2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Рекуррентное соотношение двух переменных
Сообщение04.07.2018, 12:49 


24/01/17
21
Подскажите, что можно сделать с этим рекуррентным соотношением (желательно найти его нерекуррентный вид), чтобы увеличить скорость его вычисления:
$
\begin{array}{l}
 f(n,m) = 1+f(n-1,m-1)+f(n,m-1) \\
 f(0,m) = f(n,0) = 0
\end{array}.$

выходит, что $f(n,m)$ есть количество узлов в совершенном бинарном дереве высотой $m$, число левых поворотов до которых (считая от вершины) меньше $n$.

 Профиль  
                  
 
 Re: Рекуррентное соотношение двух переменных
Сообщение04.07.2018, 13:19 


21/05/16
4292
Аделаида
По реккурентности, получается что $f(1,2)=1+f(0,1)+f(1,1)=1+1+f(0,0)+f(1,0)=2$. А у вас, eugensk, 1.

 Профиль  
                  
 
 Re: Рекуррентное соотношение двух переменных
Сообщение04.07.2018, 13:19 
Аватара пользователя


14/12/17
1471
деревня Инет-Кельмында
$f(n,m) = 2^m-1 \text{, при } n \ge m \ge 0$ (спасибо, kotenok gav, вот теперь всё правильно :)

При $n<m$ выходит что-то сложное, не могу сообразить.

 Профиль  
                  
 
 Re: Рекуррентное соотношение двух переменных
Сообщение04.07.2018, 13:22 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Aael в сообщении #1324318 писал(а):
Подскажите, что можно сделать с этим рекуррентным соотношением
Посмотрите A180975 с ссылками, может что-то ещё полезное попадётся.

 Профиль  
                  
 
 Re: Рекуррентное соотношение двух переменных
Сообщение04.07.2018, 15:07 


24/01/17
21
grizzly, спасибо большое. Собственно, здесь Michael Boardman. The Egg-Drop Numbers (DOI: 10.2307/3219201) приводится доказательство (через производящую функцию) того, что
$$\displaystyle f(n, m)=\sum_{k=1}^{n}C_m^k$$

Еще в вестнике бгу нашел статью, там рассказывают про РС $q(m,n)=q(m-1,n)+q(m-1,n-1)=C^m_n$ и приводят несколько методов решения РС многих переменных (правда немного другого вида, без свободных коэффициентов). Попробую походить по ссылкам, поискать методы для общего вида. Спасибо еще раз!

 Профиль  
                  
 
 Re: Рекуррентное соотношение двух переменных
Сообщение17.07.2018, 15:39 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Aael
Ещё больше информации можно найти в этом обсуждении на MO..

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

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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