A055215 A path-counting array, read by rows: T(i,j)=number of paths from (0,0) to (i-j,j) using steps (1 unit right and 1 unit up) or (1 unit right and 2 units up).

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 3, 2, 1, 1, 1, 2, 3, 4, 2, 1, 1, 1, 2, 3, 5, 4, 2, 1, 1, 1, 2, 3, 5, 7, 4, 2, 1, 1, 1, 2, 3, 5, 8, 8, 4, 2, 1, 1, 1, 2, 3, 5, 8, 12, 8, 4, 2, 1, 1, 1, 2, 3, 5, 8, 13, 15, 8, 4, 2, 1, 1, 1, 2, 3, 5, 8, 13, 20, 16

Offset: 1

Author

Clark Kimberling, May 07 2000

Keywords

• nonn
• tabl
• walk

Comments

If m >= 1 and n >= 2, then T(m+n-1,m) is the number of strings (s(1),s(2),...,s(n)) of nonnegative integers satisfying s(n)=m and 1<=s(k)-s(k-1)<=2 for k=2,3,...,n.

Examples

			7=T(8,5) counts these strings: 0135, 0235, 0245, 1235, 1245, 1345, 2345.
Rows: {1}; {1,1}; {1,1,1}; {1,1,2,1}; {1,1,2,2,1}; ...
		

Links

• C. Kimberling, Path-counting and Fibonacci numbers, Fib. Quart. 40 (4) (2002) 328-338, Example 1D.

Crossrefs

T(2n, n)=A000045(n+1), the Fibonacci numbers.

Formula

T(i, 0)=T(i, i)=1 for i >= 0; T(i, 1)=1 for i >= 1; T(i, j)=T(i-2, j-1)+T(i-3, j-2) for 2<=j<=i-1, i >= 3.