A26674=A26729

[Rob Arthan]

On Wednesday 15 January 2003 12:41 pm, Roland Bacher wrote:
> These sequences, although apparently having different definitions
> seem to be identical. Can this be proven?   Roland Bacher

They are both derived from 2-dimensional arrays (A026670 and A026725) that 
deal with very similar counting problems. You can see that A26674 = A26729 
from the descriptions of these arrays:

A026670 counts the number of paths from the origin to a given point in the 
following diagram extending infinitely to the East and the South:

*+++++++ ....
+*++++++ ....
++*+++++ ....
+++*++++ ....
++++*+++ ....
+++++*++ ....
++++++*+ ....
+++++++* ....
++++++++ ....
  ....   ....

Where a path must go one step East or South but not both at a "+" and may go 
one step East or South or both at a "*". (This is Manhattan taxicab geometry 
including Broadway. I.e., including a street that cuts diagonally across the 
blocks).

A026725 counts the number of paths from the origin to a given point in a 
similar diagram but with the diagonal street moved down one block (or the 
origin moved up one block from Times Square!):

++++++++
*+++++++ ....
+*++++++ ....
++*+++++ ....
+++*++++ ....
++++*+++ ....
+++++*++ ....
++++++*+ ....
+++++++* ....
  ....   ....

A26674 and A26729 deal with the case where the destination is of the form 
(n+1, n) (taking (i, j) to mean i-th row and j-th column). You can see by 
symmetry that the path-counts will be the same. (There are as many routes 
from A to B in Manhattan as there are from B to A - or rather, there would 
be, if you reversed all the one-way streets.)

There appear to be many similar identities between A26670 and A26725 which 
become apparent if you view them formatted as square arrays and can be 
justified by geometrical reasoning. If you don't like geometrical proofs, you 
should be able to prove them by induction using the inductive definitions - 
suitably corrected in the case of A26670, which currently says T(n-1, k-2) 
where it should say T(n-2, k-1), I think.

Rob Arthan (rda at lemma-one.com)