Question

How to solve dellanoy numbers combinotrics minimum time complexcity?

Answer 1

The Delannoy number D(a,b) can be defined as the numbers of paths on Z2 from (0,0) to (a,b)using only steps (0,1), (1,0) and (1,1).
It is straightforward to see that they follow the recursion (using either first-step or last step analysis, for example):D(a,b)=D(a−1,b)+D(a,b−1)+D(a−1,b−1),

where D(0,b)=D(a,0)=1.
I came to wonder if closed-form formulas existed for those numbers (actually, it was a riddle presented to me). The formula I came up with first fixes the number of diagonal steps in a given path, then counts the number of arrangements with a multinomial coefficient. This gives:D(a,b)=a∧b∑i=0(a+b−ia−i,b−i,i).

However, a second formula is mentioned on MathWorld:D(a,b)=a∧b∑i=02i(ai)(bi),

and I was wondering if it had a similarly simple combinatorial interpretation.

I THINK IT WILL HELP YOU DEAR
THANKU