Michael Somos

Number Walls in Combinatorics

Number Walls in Combinatorics

September 20, 2000

The fundamental equation is
x = y-y2 = z-z3 .
First, expand y as a series in x giving
y = 1x +1x2 +2x3 +5x4 +14x5 +42x6 +
the generating function for Catalan numbers. Its number wall has a zigzag diagonal of all ones.

A Catalan Number Wall

11111111
11251442132429
-111314845944719
-1-2114303304719
1-5-3115551001
114-14-411691
-14284-30-5117
-1-132594330-55-611
1-429-471947191001-91-71

Now expand y as a series in z giving
y = 1z +1z2 +1z3 +3z4 +8z5 +23z6 +
the generating function of a sequence related to Catalan and Motzkin numbers. Its number wall has a Somos-4 sequence diagonal. See sequence A006769 in Sloane's EIS for the zigzag diagonal.

A Somos-4 Number Wall

11111111
11382368207644
-12-15151379437544
-1-33-520-686972050
1-6-67-468-6638627
114-2652329211-1414
-137101-8996591291405
-1-105519355-629307314-65
1-312-30365084-2986-4945-9191529

Next expand z as a series in x giving
z = 1x +1x3 +3x5 +12x7 +55x9 +
the generating function for ternary trees. Its number wall including zero coefficients has one diagonal sequence A005161 enumerating a symmetry class of alternating sign matrices invariant under vertical and horizontal reflections.

A Ternary Tree Number Wall with zeros

11111111
101030120
-11-13-936-144660
-1020902520
1-2469634415271
10-1403305460
-17-49-77-121286-67610036
-102100-1111044200
1-30900303010201-1717028900109820

Furthermore, its number wall without zero coefficients has one diagonal sequence A051255 enumerating a symmetry class of planar partitions and another diagonal sequence A005156 enumerating a symmetry class of alternating sign matrices invariant under vertical reflection.

A Ternary Tree Number Wall

1111111
11312552731428
-12321251401177112
-1-7112638611967571797
1-30-101170646193231427994
1143-1391-36217429458852677545
-172824284-137914-3426319204609304650





File translated from TEX by TTH, version 3.40.
On 10 Jul 2003, 18:58.

(Latex version) or (PDF version) or (PostScript gz version)
Back to my math page
Last Updated Sat Mar 25 23:49 EST 2006
Michael Somos <somos@grail.cba.csuohio.edu>
WWW URL: "http://grail.cba.csuohio.edu/~somos/"