c**********e
发帖数: 2007 | 1 Let f(m,n) is an integer function, which satisfies the following
f(m, k)=0 for k<0;
f(k, n)=0 for k<0;
f(0,0)=1;
f(m, n)=f(m-2,n)+f(m-1,n)+f(m-1,n-1)+f(m,n-2)+f(m,n-1) for m>0 or n>0
The definition for negative integers is only for notational convenience.
The function is essentially on non-negative pairs of (m,n).
Any simplication for f(m,n)? | g*****k
发帖数: 623 | 2 It looks like some chess movements?
【在 c**********e 的大作中提到】
: Let f(m,n) is an integer function, which satisfies the following
: f(m, k)=0 for k<0;
: f(k, n)=0 for k<0;
: f(0,0)=1;
: f(m, n)=f(m-2,n)+f(m-1,n)+f(m-1,n-1)+f(m,n-2)+f(m,n-1) for m>0 or n>0
: The definition for negative integers is only for notational convenience.
: The function is essentially on non-negative pairs of (m,n).
: Any simplication for f(m,n)?
| c**********e
发帖数: 2007 | 3 No. It is actually rabbit jump problem.
Remember a rabbit can jump up ladder 1 or 2 steps each time. How many ways
can the rabbit jump for n steps? The solution is given by Fibonicci f(n)=f(n
-1)+f(n-2).
Now the rabbit has a 2-D ladder to jump.
【在 g*****k 的大作中提到】
: It looks like some chess movements?
| g*****k
发帖数: 623 | 4 If that is the case, how come
f(m, 0) = 1?
(n
【在 c**********e 的大作中提到】
: No. It is actually rabbit jump problem.
: Remember a rabbit can jump up ladder 1 or 2 steps each time. How many ways
: can the rabbit jump for n steps? The solution is given by Fibonicci f(n)=f(n
: -1)+f(n-2).
: Now the rabbit has a 2-D ladder to jump.
| x******a
发帖数: 6336 | 5 是不是2^nFib(n)?
(n
【在 c**********e 的大作中提到】
: No. It is actually rabbit jump problem.
: Remember a rabbit can jump up ladder 1 or 2 steps each time. How many ways
: can the rabbit jump for n steps? The solution is given by Fibonicci f(n)=f(n
: -1)+f(n-2).
: Now the rabbit has a 2-D ladder to jump.
| l******i
发帖数: 1404 | 6 你说的很对，这是一类问题。
但是没法用一元linear recurrence的解法（通过给特征多项式求根得到recurrence form）
Hint:
Functions defined on n-grids can also be studied with PDE.
Given: f(m,n)=f(m-2,n)+f(m-1,n)+f(m-1,n-1)+f(m,n-2)+f(m,n-1);
=> f(m+2,n+2)=f(m,n+1)+f(m+1,n+2)+f(m+1,n+1)+f(m+2,n)+f(m+2,n+1);
f_x(m,n) = f(m+1,n)-f(m,n)
f_y(m,n) = f(m,n+1)-f(m,n)
f_xy(m,n) = f(m+1,n+1)-f(m,n+1)-f(m+1,n)+f(m,n)
f_xx(m,n) = f(m+2,n)-2*f(m+1,n)+f(m,n)
f_xxy(m,n) = f(m+2,n+1)-2*f(m+1,n+1)+f(m,n+1)-f(m+2,n)+2*f(m+1,n)-f(m,n)
f_yy(m,n) = f(m,n+2)-2*f(m,n+1)+f(m,n)
f_yyx(m,n) = f(m+1,n+2)-2*f(m+1,n+1)+f(m+1,n)-f(m,n+2)+2*f(m,n+1)-f(m,n)
f_xxyy(m,n) = f_xx(m,n+2)-2*f_xx(m,n+1)+f_xx(m,n)
= f(m+2,n+2)-2*f(m+1,n+2)+f(m,n+2)-2*f(m+2,n+1)+4*f(m+1,n+1)
-2*f(m,n+1)+f(m+2,n)-2*f(m+1,n)+f(m,n)
用以上formula凑一个PDE，然后解这个PDE就可以了。
ways
f(n)=f
(n
【在 c**********e 的大作中提到】
: No. It is actually rabbit jump problem.
: Remember a rabbit can jump up ladder 1 or 2 steps each time. How many ways
: can the rabbit jump for n steps? The solution is given by Fibonicci f(n)=f(n
: -1)+f(n-2).
: Now the rabbit has a 2-D ladder to jump.
| c**********e
发帖数: 2007 | 7 You are right. I have corrected the boundary condition.
【在 g*****k 的大作中提到】
: If that is the case, how come
: f(m, 0) = 1?
:
: (n
| l******n
发帖数: 9344 | 8 对于1d情形，一元linear recurrence的解法和用你说的pde方法是一样的，那个特征多
项式就是ODE的特征多项式。你的这个方法，那个pde解不出来吧
form）
【在 l******i 的大作中提到】
: 你说的很对，这是一类问题。
: 但是没法用一元linear recurrence的解法（通过给特征多项式求根得到recurrence form）
: Hint:
: Functions defined on n-grids can also be studied with PDE.
: Given: f(m,n)=f(m-2,n)+f(m-1,n)+f(m-1,n-1)+f(m,n-2)+f(m,n-1);
: => f(m+2,n+2)=f(m,n+1)+f(m+1,n+2)+f(m+1,n+1)+f(m+2,n)+f(m+2,n+1);
: f_x(m,n) = f(m+1,n)-f(m,n)
: f_y(m,n) = f(m,n+1)-f(m,n)
: f_xy(m,n) = f(m+1,n+1)-f(m,n+1)-f(m+1,n)+f(m,n)
: f_xx(m,n) = f(m+2,n)-2*f(m+1,n)+f(m,n)
| l******i
发帖数: 1404 | 9 我只知道大概这样弄，大牛有何高见？
【在 l******n 的大作中提到】
: 对于1d情形，一元linear recurrence的解法和用你说的pde方法是一样的，那个特征多
: 项式就是ODE的特征多项式。你的这个方法，那个pde解不出来吧
:
: form）
| c**********e
发帖数: 2007 | 10 This does not work. You can try 1-D case first.
form）
【在 l******i 的大作中提到】
: 你说的很对，这是一类问题。
: 但是没法用一元linear recurrence的解法（通过给特征多项式求根得到recurrence form）
: Hint:
: Functions defined on n-grids can also be studied with PDE.
: Given: f(m,n)=f(m-2,n)+f(m-1,n)+f(m-1,n-1)+f(m,n-2)+f(m,n-1);
: => f(m+2,n+2)=f(m,n+1)+f(m+1,n+2)+f(m+1,n+1)+f(m+2,n)+f(m+2,n+1);
: f_x(m,n) = f(m+1,n)-f(m,n)
: f_y(m,n) = f(m,n+1)-f(m,n)
: f_xy(m,n) = f(m+1,n+1)-f(m,n+1)-f(m+1,n)+f(m,n)
: f_xx(m,n) = f(m+2,n)-2*f(m+1,n)+f(m,n)
| l******i
发帖数: 1404 | 11 PDE term here means Partial Difference Equation, NOT partial differential
equation. Sorry for the confusion.
Here is a good introductory book:
http://www.amazon.com/Difference-Equations-Advances-Mathematics
【在 l******n 的大作中提到】
: 对于1d情形，一元linear recurrence的解法和用你说的pde方法是一样的，那个特征多
: 项式就是ODE的特征多项式。你的这个方法，那个pde解不出来吧
:
: form）
|
|
