Block walking and counting subsets A Delanoy path in the fir

(Block walking and counting subsets) A Delanoy path in the first quadrant is a walk that uses any of 3 kinds of steps: Up (0,1), Right (1,0), and Diagonal (1,1) . Let D(x,y) be the number of Delanoy paths from (0,0) to (x,y)

a) Find a recurrence relations that give D(x,y) in terms of a smaller values.

b) Find the number of Delannoy paths from (0,0) to (7,3).

c) Find a formula for D(n,1), where n is any whole number.

Solution

a) When at point (x,y) we can reach it from (x-1,y) by going to the right

from (x,y-1) by going up

from (x-1,y-1) by going diagonally

Assuming, x>=1,y>=1

So,

D(x,y)=D(x-1,y)+D(x,y-1)+D(x-1,y-1) ,x>=1,y>=1

If x=0,y>=1 ie we are on the y axis so there is only one way to get there just going up and up from origin

D(0,y)=1

If y=0,x>=1 we are on x axis so there is only one way to get there by going only right

D(x,0)=1

b)

D(7,3)

=D(6,3)+D(7,2)+D(6,2)

=D(6,2)+D(5,3)+D(5,2)+D(6,2)+D(6,1)+D(7,1)+D(5,1)+D(5,2)+D(6,1)

=D(7,1)+2D(6,2)+2D(6,1)+D(5,3)+2D(5,2)+D(5,1)

=D(7,0)+D(6,0)+2D(6,2)+3D(6,1)+D(5,3)+2D(5,2)+D(5,1)

=2+5D(6,1)+D(5,3)+4D(5,2)+3D(5,1)

=2+5D(6,0)+5D(5,0)+D(5,3)+4D(5,2)+8D(5,1)

=12+D(4,2)+D(4,3)+5D(5,2)+8D(5,1)

=12+8D(5,0)+8D(4,0)+8D(4,1)+D(4,2)+D(4,3)+5D(5,2)

=28+5D(5,1)+13D(4,1)+6D(4,2)+D(4,3)

=28+5D(4,0)+5D(5,0)+18D(4,1)+6D(4,2)+D(4,3)

=38+18D(3,0)+18D(4,0)+18D(3,1)+7D(4,2)+D(3,3)+D(3,2)

=74+18D(3,0)+18D(2,0)+18D(2,1)+7D(4,2)+D(3,3)+D(3,2)

=110+18D(1,0)+18D(2,0)+18D(1,1)+7D(4,2)+D(3,3)+D(3,2)

=110+18+18+18*3+7D(4,2)+D(3,3)+D(3,2)

=200+7D(4,2)+D(3,3)+D(3,2)

=200+7D(4,1)+8D(3,2)+7D(3,1)+D(3,3)

=200+7D(4,0)+7D(3,0)+14D(3,1)+8D(3,2)+D(3,3)

=214+14D(3,0)+14D(2,0)+14D(2,1)+8D(2,2)+8D(3,1)+8D(3,1)+D(3,3)

=242+14D(2,1)+8D(2,2)+16D(3,1)+D(3,3)

=242+22D(2,1)+8D(1,1)+8D(1,2)+16D(2,1)+16D(3,0)+16D(2,0)+D(3,3)

=242+38D(2,1)+8*3+8D(1,2)+16+16+D(3,3)

=274+38D(1,0)+38D(2,0)+38D(1,1)+8D(1,1)+8D(0,2)+8D(0,1)+D(3,3)

=350+38*3+8*3+8+8+D(3,3)

=504+D(2,2)+D(3,2)+D(2,3)

=504+3D(2,2)+D(3,1)+D(2,1)+D(1,3)+D(1,2)

=504+3D(1,1)+4D(1,2)+4D(2,1)+D(3,1)+D(1,3)

=504+3*3+5D(1,2)+5D(2,1)+D(2,0)+D(3,0)+D(0,3)+D(0,2)

=517+10D(1,1)+5D(0,2)+5D(0,1)+5D(2,0)+5D(1,0)

=517+30+20

=567

c)

Case 1:n=0

D(n,1)=D(0,1)=1

Case 2:n>0

D(n,1)=D(n-1,1)+D(n,0)+D(n-1,0)=D(n-1,1)+2

D(n,1)=2+2+D(n-2,1)=2*2+D(n-2,1)

D(n,1)=2*(n-1)+D(1,1)=2n-2+3=2n+1

D(n,1)=2n+1