0,4

a(i,j) is the number of paths from (i,i) to (j,j) using steps of length (0,1), (1,0) and (1,1), not passing above the line y=x nor below the line y=x/2. The Hamburger Theorem implies that we can use this table to calculate the number of domino tilings of an Aztec 3-pillow (A112833). To calculate this quantity, let P_n = the principal n X n submatrix of this array. If J_n = the back-diagonal matrix of order n, then A112833(n)=det(P_n+J_nP_n^(-1)J_n).

C. Hanusa (2005). A Gessel-Viennot-Type Method for Cycle Systems with Applications to Aztec Pillows. PhD Thesis. University of Washington, Seattle, USA.

Alois P. Heinz, Rows n = 0..140, flattened

The number of paths from (0,0) to (3,3) staying between the lines y=x and y=x/2 using steps of length (0,1), (1,0) and (1,1) is a(0,3)=5.

Triangle begins:

1;

1, 1;

2, 2, 1;

5, 5, 2, 1;

16, 16, 6, 2, 1;

57, 57, 21, 6, 2, 1;

224, 224, 82, 22, 6, 2, 1;

934, 934, 341, 89, 22, 6, 2, 1;

4092, 4092, 1492, 384, 90, 22, 6, 2, 1;

b:= proc(x, y, k) option remember;

`if`(y>x or y<x/2, 0, `if`(x=k, `if`(y=k, 1, 0),

b(x, y-1, k)+b(x-1, y, k)+b(x-1, y-1, k)))

end:

a:= (n, k)-> b(n, n, k):

seq(seq(a(n, k), k=0..n), n=0..12); # Alois P. Heinz, Apr 26 2013

b[x_, y_, k_] := b[x, y, k] = If[y>x || y<x/2, 0, If[x == k, If[y == k, 1, 0], b[x, y-1, k] + b[x-1, y, k] + b[x-1, y-1, k]]]; a[n_, k_] := b[n, n, k]; Table[ Table[ a[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Mar 06 2015, after Alois P. Heinz *)

See also A112833-A112844 and A114293-A114299.

Sequence in context: A187307 A280785 A204851 * A333724 A178518 A299499

Adjacent sequences: A114289 A114290 A114291 * A114293 A114294 A114295

nonn,tabl

Christopher Hanusa (chanusa(AT)math.binghamton.edu), Nov 21 2005

approved