A047000 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

A047000

Array T read by diagonals; T(h,k)=number of paths consisting of steps from (0,0) to (h,k) such that each step has length 1 directed up or right and no step touches the line y=x/2 except at the endpoints.

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 2, 1, 1, 1, 4, 5, 2, 2, 1, 1, 5, 9, 7, 4, 3, 1, 1, 6, 14, 16, 7, 3, 4, 1, 1, 7, 20, 30, 23, 7, 7, 5, 1, 1, 8, 27, 50, 53, 30, 14, 12, 6, 1, 1, 9, 35, 77, 103, 83, 30, 12, 18, 7, 1, 1, 10, 44, 112, 180, 186, 113, 30, 30

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,8

COMMENTS

Touches here includes the case where a step touches the line at a midpoint.

LINKS

Table of n, a(n) for n=0..74.

EXAMPLE

Diagonals (starting on row #0): {1}; {1,1}; {1,1,1}; {1,2,2,1}; {1,3,2,1,1}; ...

T(2,3) = 5; the 5 allowed paths to (2,3) are UUURR, UURUR, UURRU, URUUR, and URURU.

PROG

(PARI) T(h, k)=if(h==0 || k==0, 1, T(h-1, k)*(h-1!=2*k)+T(h, k-1)*(h!=2*k-2 && h!=2*k-1)) /* Inefficient. */