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
Offset: 0
Examples
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.
Crossrefs
The sequence T(2n, n)/2 for n=1, 2, 3, ... is A006013.
Programs
-
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. */
Extensions
Definition corrected by Franklin T. Adams-Watters, Mar 10 2011
Comments