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,9

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.

Links

Table of n, a(n) for n=1..87.

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

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.

Example

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}; ...

Crossrefs

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

Sequence in context: A344318 A289944 A366747 * A239550 A058398 A091499

Adjacent sequences: A055212 A055213 A055214 * A055216 A055217 A055218

Keyword

nonn,tabl,walk

Author

Clark Kimberling, May 07 2000

Status

approved