[seqfan] Re: Rook path generates A006189 Number of paths on square lattice?

Alois Heinz heinz at hs-heilbronn.de
Sat Oct 30 04:37:04 CEST 2010

```Am 29.10.2010 04:30, schrieb David Scambler:
> The description of A006189 is vague, but a rook generates the same 8 terms given.
Look at A006192, which has a similar definition.  So you are probably
right.
> Count of self-avoiding rook paths on a 3xn board from (0,0) to (0,n) generates 1,3,11,38,126..., apparently = A006189(n+2), i.e. offset 1 rather than 3.
This has gf: -(x^3+2*x^2-x+1)*x / (x^4+2*x^3-3*x^2+4*x-1)

1, 3, 11, 38, 126, 415, 1369, 4521, 14933, 49322, 162900,
538021, 1776961, 5868903, 19383671, 64019918, 211443426,
698350195, 2306494009, 7617832221, 25159990673, 83097804242,
274453403400, 906458014441, 2993827446721, 9887940354603,
32657648510531, 107860885886198, 356240306169126, 1176581804393575

Alois

> 3 x 1 a(1) = 1
>    1  0  0
>
> 3 x 2 a(2) = 3
>    1  0  0 :   1  2  0 :   1  2  3
>    2  0  0 :   4  3  0 :   6  5  4
>
>
> 3 x 3 a(3) = 11
>    1  0  0 :   1  0  0 :   1  4  5 :   1  0  0 :   1  2  0 :   1  2  0
>    2  0  0 :   2  3  0 :   2  3  6 :   2  3  4 :   0  3  0 :   0  3  4
>    3  0  0 :   5  4  0 :   9  8  7 :   7  6  5 :   5  4  0 :   7  6  5
>
>    1  2  0 :   1  2  3 :   1  2  3 :   1  2  3 :   1  2  3
>    4  3  0 :   8  7  4 :   0  0  4 :   0  5  4 :   6  5  4
>    5  0  0 :   9  6  5 :   7  6  5 :   7  6  0 :   7  0  0
>
>
> If anyone has the reference H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178 I would be interested to know what the original motivation for this sequence was, and to determine whether, in fact, this is the same sequence as that generated by the rook paths.
>
> Thanks, dave

```