Sequences to analyze

Fri May 4 22:09:41 CEST 2001

Richard Guy wrote [in refernence to my question concerning sequences]:
> 
> I hesitated to answer this, as I had only negative
> things to say, but I also find I have something
> positive, so some of you may like to read on.
> 
> Negative things first:  David is so experienced in
> this that I hesitated to ask, have you tried differences,
> sequence fans, number walls, superseeker, ... ?  and `where
> did they come from?'

Fine.  Here are the sequences I am working on.  They are unrestricted
walks on variously restricted portions of the square grid.

I rediscovered and extended A005566.  The EIS contains no formula, so
I worked out the formula, after which I promptly found the same formula
as eq. 14 of your excellent JIS paper  "Catwalks, Sandsteps, and Pascal
Pyramids".

I also rediscovered and extended A001700, and added the walks
interpretation.  A001700 already has a formula in the EIS.

Other walk variants produced new sequences A000001 through A000004.  I
worked out a formula and recurrence for A000003 and A000004, but I am
stymied by A000001 and A000002.

------------------------------------------------------------------------
A005566 %N Walks of length n on square lattice, starting at origin, staying in
first quadrant
A005566 %S 1,2,6,18,60,200,700,2450,8820,31752,116424,426888,1585584,5889312,
A005566 %T 22084920,82818450,312869700,1181952200,4491418360,17067389768,
A005566 %U 65166397296,248817153312,953799087696,3656229836168,14062422446800
A005566 %F a(n) = binomial(n, [n/2])*binomial(n+1, [(n+1)/2])

------------------------------------------------------------------------
A001700 %S
1,3,10,35,126,462,1716,6435,24310,92378,352716,1352078,5200300,20058300,
A001700 %T 77558760,300540195,1166803110,4537567650,17672631900,68923264410,
A001700 %U
269128937220,1052049481860,4116715363800,16123801841550,63205303218876
A001700 %C Walks of length n on square lattice, starting at origin, staying in
first and second quadrants

------------------------------------------------------------------------
A000001 %N Walks of length n on square lattice, starting at origin, staying in
first and third quadrants
A000001 %S
1,4,12,44,144,528,1808,6676,23536,87568,315136,1180680,4314560,16263896,
A000001 %T 60138816,227899484,850600944,3238194560,12177384544,46542879384,
A000001 %U 176110444736,675431779856,2568878867200,9882068082112,37747540858240

------------------------------------------------------------------------
A000002 %N Walks of length n on square lattice, starting at origin, staying in
first, second, and third quadrants
A000002 %S 1,4,14,54,200,776,2940,11466,43980,172170,665544,2612764,10154144,
A000002 %T 39949000,155864280,614260062,2403739140,9486263092,37209147800,
A000002 %U 147012850512,577741491404,2284848892872,8993216244896,35595538140656

------------------------------------------------------------------------
A000003 %N Walks of length n on square lattice, starting at origin, staying on
points with x+y >= 0.
A000003 %S 1,2,8,24,96,320,1280,4480,17920,64512,258048,946176,3784704,14057472,
A000003 %T 56229888,210862080,843448320,3186360320,12745441280,48432676864,
A000003 %U 193730707456,739699064832,2958796259328,11342052327424,45368209309696
A000003 %F a(n) = 2^n*binomial(n, [n/2]);

------------------------------------------------------------------------
A000004 %N Walks of length n on square lattice, starting at origin, staying on
points with x >= 0, y <= x
A000004 %S 1,2,7,21,78,260,988,3458,13300,47880,185535,680295,2649570,9841260,
A000004 %T 38470380,144263925,565514586,2136388436,8392954570,31893227366,
A000004 %U 125515281892,479240167224,1888770070824,7240285271492,28569774314536
A000004 %F a(0) = 1, a(2n) = a(2n-1)*(12n+2)/(3n+1), a(2n+1) =
a(2n)*(4n+2)/(n+1).

> This last raises a rather
> metaphysical question.  How is a sequence defined?
> If it arises in some obscure context, it may never
> (what, never?) occur in any other, so that is its
> definition.  Fibonacci numbers are defined by ...
> Catalan numbers are defined by ...  But you get the
> picture.

Currently, the EIS models the definition of an integer sequence
more or less as follows:

    - exactly one name (%N) = definition
    - zero or more formulae (%F) = mathematical observations
    - zero or more comments (%C) = descriptive observations

I tend to think the actual descriptive attributes of an integer
sequence are closer to

    - zero or more names = descriptive names
    - zero or more interpretations = descriptive definitions
    - zero or more formulae = mathematical defintions
    - zero or more comments = descriptive or mathematical observations

One or more definition (interpretation of formula) must be present.

For example, let's look at A000045, the Fibonacci numbers.  In the
EIS, we have

    name: Fibonacci numbers: F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1, F(2) =
1, ...
    comment: F(n+1) = number of binary sequences of length n that have no
consecutive
              0's; F(n+2) = number of subsets of {1,2,...,n} that contain no
              consecutive integers (Clark Kimberling, ck6 at cedar.evansville.edu).
    comment: F(n+1) is also the number of tilings of a 2xn rectangle by 2x1
dominos -
              Ahmed Fares (ahmedfares at my-deja.com), Feb 24 2001
    comment: These numbers are also the positive solutions of
              z=2xy^4+(x^2)y^3-2(x^3)y^2-y^5-(x^4)y+2y for x,y >= 0. (See
              Ribenboim, page 193.) When x=a(n), y=a(n+1), and z>0 then
              z=a(n+1). - Jud McCranie (jud.mccranie at mindspring.com), Apr 18
2001
    formula: Paulo Ribenboim, The New Book of Prime Number Records, Springer,
1996.
              F(n)=((1+sqrt(5))^n-(1-sqrt(5))^n)/(2^n*sqrt(5)). G.f.
x/(1-x-x^2).

Notice how we have shoehorned a description and a formula into the name.

IMHO, a better organization of this information:

    name: Fibonacci numbers
    formula: F(0) = 0; F(1) = 1; F(n) = F(n-1) + F(n-2) (n >= 2).
    formula: F(n) = ((1+sqrt(5))^n-(1-sqrt(5))^n)/(2^n*sqrt(5)).
    formula: G.f: x/(1-x-x^2).
    formula: F(n+1) = SUM(0 < j <= [n/2]; binomial(n-j, j))
    formula: [0 1; 1 1]^n [0 1] = [F(n); F(n+1)]
    interpretation:
        F(n+1) = number of binary sequences of length n that have no consecutive
0's...
    interpretation:
        F(n+2) = number of subsets of {1,2,...,n} containing no consecutive
values...
    interpretation:
        F(n+1) = number of tilings of 2xn rectangle with 2x1 dominoes...
    interpretation:
        F(n+1) = partitions of n into parts of size 1 and 2.
    interpretation:
        Positive elements are the solutions to
z=2xy^4+(x^2)y^3-2(x^3)y^2-y^5-(x^4)y+2y for x,y >= 0...
    comment:
	x | F(n) ==> x | F(kn).

The sequence name is now simply "Fibonacci numbers".  In other sequences, the
name could be omitted or several names included.  No name is pre-eminent, but
they might be listed in order or preference or commonality.

The formulae each define the sequence mathematically.

The interpretations also define the sequence.

Other, non-definitive observations are comments.