[seqfan] Proved: A000129 = INVERT(A000045)

Antti Karttunen Antti.Karttunen at iki.fi
Fri Dec 12 07:14:08 CET 2003

I wrote last night, on this SeqFan mailing list:

 > Christian wrote:
 > > Date: Mon, 08 Dec 2003 11:07:11 -0800
 > > From: Christian G. Bower <bowerc at usa.net>
 > > To: seqfan at ext.jussieu.fr
 > > Subject: Re: [[seqfan] Few INVERT transforms requested. A000045 --> 
A000129, how ?]
 > > Like John Laymen, I'm not using the Maple procedure, but rather my own
 > > program
 > >

 > > I get:
 > > A000129 Pell Numbers

(Note here that I think Christian's program interprets the offsets in 
different way
from Neil's Maple-implementation of INVERT, with the former thinking
that the first term of the list is a(0), while Neil's program
interprets it as a(1). This is important to remember below.)

 > ...
 > > Don't have time to do proofs right now. Since Pell numbers are 
defined by
 > > simple recurrence, should be easy to convert to a g.f. and thus show
 > > equivalence to the transformations.
 > ... maybe I will find a combinatorial proof instead, starting for
 > example from that "left factors of Grand Schroder Paths"
 > interpretation of A000129.

YES, actually it's quite simple, after a good night's sleep.
So we have:

ID Number: A000129 (Formerly M1413 and N0552)
URL:       http://www.research.att.com/projects/OEIS?Anum=A000129
Sequence:  0,1,2,5,12,29,70,169,408,985,2378,5741,13860,33461,80782,
Name:      Pell numbers: a(0) = 0, a(1) = 1; for n > 1, a(n) = 2*a(n-1) 
+ a(n-2).
              Also denominators of continued fraction convergents to 
Comments:  Number of lattice paths from (0,0) to the line x=n-1 
consisting of
              U=(1,1), D=(1,-1), and H=(2,0) steps (i.e. left factors of 
              Schroder paths); for example, a(3)=5, counting the paths 
H, UD, UU, DU,
              and DD. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 
27 2002

We can draw those five paths of length 2 given by Emeric, as
(we mark the single, undividable horizontal element -- as HH)

             /         \
  --   /\   /    \/     \
  HH   UD   UU   DU    DD

For paths of the length 3, we get the following twelve paths:

       __    __   /     /\        /\
  __/    \  /    /     /     /\/    \

         /       \     \
  \__  \/   \/\   \/    \

The recurrence given follows by similar reasoning
as the recurrence for Fibonacci numbers (A000045),
which can be defined in the similar way, but using only
the steps HH & U  OR  HH & D. It is easy to see that such
"fibo-paths" would be these tilings in disguise:
F(n+1) = number of tilings of a 2 X n rectangle by 2 X 1 dominoes.
where Fibonacci numbers: F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) =1,
F(2) = 1, ...

In Sloane's & Bernstein's article 
the transformation INVERT is defined as:
 1+SUM b_n x^n = 1/(1 - SUM a_n x^n); n=1..inf
b_n is the number of ordered arrangements of postage stamps
of total value n that can be formed if we have a_i types
of stamps of value i, i>= 1.
This, in terms of our "paths" or "sequences" translates to
"b_n is the number of sequences of sequences of total length n,
when the number of sequences of length n is given by a_n."

Now, of the above paths, let's interpret D, not as "D" for "Down",
but as "D" for "Delimiter" (marked here as :), and we get:
For the total length l=2:

  HH   U:   UU   :U    ::

For the total length l=3:

  HHU   HH: UHH  UUU   UU:   U:U  U::

  :HH   :UU :U:  ::U   :::

Then insert one extra-element . (of length 1)
to the front of each of the delimited parts:

  .HH   .U:.   .UU   .:.U    .:.:.

  .HHU   .HH:.  .UHH    .UUU     .UU:.   .U:.U   .U:.:.
  .:.HH  .:.UU  .:.U:.  .:.:.U   .:.:.:.

after which we can remove the zero-length delimiters:

  .HH     .U.  .UU    ..U   ...

  .HHU   .HH.  .UHH  .UUU   .UU.   .U.U   .U..
  ..HH   ..UU  ..U.  ...U   ....

So now we have a sequence of 1 to l+1 dot-prefixed "fibo-paths"
the sum of whose lengths is l+1, where the number of
dot-prefixed fibo-paths is F(1)=1 (only . itself), F(2)=1 (only .U),
F(3)=2 (.UU and .HH), F(4)=3 (.UUU, .UHH, .HHU), i.e. the
Fibonacci numbers, but with an index one less than
with the ordinary fibo-paths without the prefix.

Thus, using the above definition of INVERT, the number
of above sequences of dot-prefixed fibo-sequences (= A000129)
is INVERT(A000045); when A000045 is given as
and INVERT as defined for Maple in
interprets the first term of its argument list
as having offset n=1.

That INVERT(A019590);, where A019590 is
the characteristic function of "n is either 1 or 2":
gives [1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,...]
(Fibonacci numbers shifted twice left)
is also obvious from the definition of INVERT,
and the fact that we are using only one path-segment of the
length 1, and one path-segment of the length 2,
when constructing the fibo-paths.

TO RECAPITULATE: if the sequence Ayyyyyy gives the paths of length n formed
from the set of allowed path-segments Y where the number
of allowed segments of length n is Axxxxxx[n],
then Ayyyyyy can be computed as INVERT(Axxxxxx)

FURTHERMORE: if we add to the set of allowed segments of the length 1
a special segment X, distinct from the other ones, (so that we have
Axxxxxx[1]+1 allowed path-segments of unit length) then as in the above
example, we can interpret it as a "delimiter" element,
and the resulting sequence Ayyyyyy' is INVERT(RIGHT(Ayyyyyy))
where the transformation RIGHT shifts the sequence one step right,
prepending it with 1. If we add two distinct path-segments
to the set of allowed unitary segments, then the result
is INVERT(RIGHT(INVERT(RIGHT(Ayyyyyy)))), et caetera.


Antti Karttunen

More information about the SeqFan mailing list