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.
(Latex version) or
(PDF version) or
(PostScript gz version)
Back to my math page
Back to my home page
Last Updated Thu Dec 11 2014
Michael Somos
<ms639@georgetown.edu>
Michael Somos
"http://grail.eecs.csuohio.edu/~somos/"