### 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

 1 1 1 1 1 1 1 1 1 1 2 5 14 42 132 429 -1 1 1 3 14 84 594 4719 -1 -2 1 1 4 30 330 4719 1 -5 -3 1 1 5 55 1001 1 14 -14 -4 1 1 6 91 -1 42 84 -30 -5 1 1 7 -1 -132 594 330 -55 -6 1 1 1 -429 -4719 4719 1001 -91 -7 1

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 OEIS for the zigzag diagonal.

A Somos-4 Number Wall

 1 1 1 1 1 1 1 1 1 1 3 8 23 68 207 644 -1 2 -1 5 15 137 943 7544 -1 -3 3 -5 20 -68 697 2050 1 -6 -6 7 -4 68 -663 8627 1 14 -26 5 23 29 211 -1414 -1 37 101 -89 96 59 129 1405 -1 -105 519 355 -629 307 314 -65 1 -312 -3036 5084 -2986 -4945 -919 1529

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

 1 1 1 1 1 1 1 1 1 0 1 0 3 0 12 0 -1 1 -1 3 -9 36 -144 660 -1 0 2 0 9 0 252 0 1 -2 4 6 9 63 441 5271 1 0 -14 0 33 0 546 0 -1 7 -49 -77 -121 286 -676 10036 -1 0 210 0 -1111 0 4420 0 1 -30 900 3030 10201 -17170 28900 109820

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

 1 1 1 1 1 1 1 1 1 3 12 55 273 1428 -1 2 3 21 251 4011 77112 -1 -7 11 26 386 11967 571797 1 -30 -101 170 646 19323 1427994 1 143 -1391 -3621 7429 45885 2677545 -1 728 24284 -137914 -342631 920460 9304650

File translated from TEX by TTH, version 3.82.
On 11 Dec 2014, 00:37.