[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
>
> >
>
INVERT([0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946]);
> > 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,
195025,470832,1136689,2744210,6625109,15994428,38613965,
93222358,225058681,543339720,1311738121,3166815962,
7645370045,18457556052,44560482149
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
sqrt(2).
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
Grand
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:
/
__ __ / /\ /\
__/ \ / / / /\/ \
HHU HHD UHH UUU UUD UDU UDD
/ \ \
\__ \/ \/\ \/ \
\
DHH DUU DUD DDU DDD
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
http://www.research.att.com/~njas/doc/eigen.ps
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
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946],
and INVERT as defined for Maple in
http://www.research.att.com/~njas/sequences/transforms.txt
interprets the first term of its argument list
as having offset n=1.
Q.E.D.
That INVERT(A019590);, where A019590 is
the characteristic function of "n is either 1 or 2":
[1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,...]
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)
by the DEFINITION of INVERT.
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.
Yours,
Antti Karttunen
More information about the SeqFan
mailing list