atze@UNI-PADERBORN.DE (Ralf Klasing) (05/23/91)
I'm desperately looking for a closed formula of the
following recurrence relation
A(0,0) = 1
A(0,i) = 0 for all i <> 0
A(1,0) = A(1,1) = 1
A(1,i) = 0 for all i <> 0,1
A(i,k) = A(i-1,k) + A(i-2,k-1) for all i >= 2
This relation is similar to the recursive definition
of binomial coefficients, but it looks like it is a
lot harder to tackle.
If somebody can help me with this problem or can give
me an appropriate reference, I would be very grateful.
Thanks a lot in advance
Ralf Klasing
------------------------------------------------------
+ Ralf Klasing +
+ Department of Mathematics and Computer Science +
+ University of Paderborn, Germany +
+ E-mail: Ralf.Klasing@uni-paderborn.de +
------------------------------------------------------bdm659@csc.anu.edu.au (05/24/91)
In article <9105231143.AA25697@dali.uni-paderborn.de>, atze@UNI-PADERBORN.DE (Ralf Klasing) writes: > I'm desperately looking for a closed formula of the > following recurrence relation > > A(0,0) = 1 > A(0,i) = 0 for all i <> 0 > A(1,0) = A(1,1) = 1 > A(1,i) = 0 for all i <> 0,1 > > A(i,k) = A(i-1,k) + A(i-2,k-1) for all i >= 2 If C(n,k) denotes the binomial coefficients, taken to be 0 except where 0 <= k <= n, then A(i,k) = C(i-k,k-1) + C(i-k,k). Derivation: The number of paths from (0,0) to (x,y) using steps of size (1,0) and (2,1) is C(x-y,y) as you can see by noting that there must be y steps of the second kind and x-y steps altogether. Now think of your problem geometrically. A(i,k) is the number of paths starting at one of the points in S = {(0,0),(1,0),(1,1)} and finishing at the point (i,k), with the restriction that only the first point of the path lies in S. The latter restriction can be dropped if point (1,0) is also dropped, as paths beginning (0,0)-(1,0)-... cover those which start at (1,0). Hence we have the total number of paths from (0,0) to (i,k), which is C(i-k,k) plus the total number from (1,1) to (i,k), which is C(i-k,k-1). Brendan.
noe@sunc6.cs.uiuc.edu (Roger Noe) (05/24/91)
In article <1991May24.105457.1@csc.anu.edu.au> bdm659@csc.anu.edu.au writes: >If C(n,k) denotes the binomial coefficients, taken to be 0 except >where 0 <= k <= n, then A(i,k) = C(i-k,k-1) + C(i-k,k). Which is of course just C(i-k+1,k). This assumes that A(i,0)=1, the unspecified boundary condition not covered by the recurrence relation. -- Roger Noe roger-noe@uiuc.edu Department of Computer Science noe@cs.uiuc.edu University of Illinois 40:06:39 N. 88:13:41 W. Urbana, IL 61801 USA