This paper is in the "website" or "haunted house" model. For convenience, here is a table of contents with link maps and notes:

- Four Numerical Triangles. This page. A case is made that three well-known combinatorial number triangles are tightly related to each other as coefficients in transforms of a seminal sequence of exponential generating functions (for {n
^{n+m}}). A fourth triangle is a part of the picture in much the same way that the "forgotten symmetric functions" adhere to the complete,the monomial, and the power sums. Mapping links:(1.-> 2.,3.,4.,5.,A.) - Carlitz-Riordan Identities. Hard evidence of the close relationship between A008517 and A008299. Contains tables for Second-order Eulerian and Second-order Stirling (2nd kind) Numbers. Mapping links:(2.->3.)
- GS-Permutations. A slightly revisionist presentation of some counting problems answered by the Second-order Eulerian Numbers.Mapping links:(none from 3.)
- Golliwog Numbers. Tables and a formula for the numbers called "differences of reciprocal powers of unity" by Florence Nightingale David,
*et al*, and A008969 by EIS. Mapping links:(4.->5.) - Pez problem. A "story problem" intended as a mnemonic for the Golliwog numbers, and as a change of pace. Mapping links: (5.->4)

- "Completion of a Sequence of Carlitz": Not a part of this paper but a necessary reference for the mathematics binding the four triangles. The link leads to a front allowing transmittal in several formats.

We introduce three long-time residents of the EIS to a common relative. We deal in triangles of numbers and their 3-term-recurrences (3tr's), from which a variety of sequences are routinely extracted.

We represent these numbers by <<m,k>> and refer to their geographical positions on or under the ray m=k in the first quadrant of the (m,k) plane. These numbers are the answer to a counting problem devised by Riordan. See our Eulerian digression for more details. They satisfy the 3tr:

<<m,k>> = (k+1) <<m-1,k>> + (2m-k-1) <<m-1,k-1>>

We write these as G(m,k). If we write N=m-k+1, then (k-1)!* G(m,k) answers the question: How many k-by-N matrices are there such that (a) each column is a permutation of {1,2,...,k} and (b) no number is below 1 in every column. David and Barton discover these numbers as coefficients in a solution of their "Golliwog" problem [DB]. We offer an alternative problem, just for fun.
A Golliwog triangle is Table 5.4.1 in [DKB] (a corrected version with comments is offered here). If we consider the probability g that a k-by-N matrix satisfying (a) satisfies (b) we write g(m,k)=(k-1)!*G(m,k)/(k!)^{m-k+1}. Several *divers* formulas for G and g are known and may be found in [BeSm], for instance. The 3tr for g is especially simple:

k g(m,k) = g(m-1,k) + g(m-1,k-1)

These are {{m,k}}. They answer the problem: In how many ways may m distinct objects be separated into k 'true heaps'? A true heap is a collection of at least two objects. The set of k heaps is unordered. The notation we use and a table appear in [Fekete]. There we find

{{m,k}} = k {{m-1,k}} + (m-1) {{m-2,k-1}}

These numbers, h(m,k), arise from the g(m,k) by the same algebraic transform which relates << >> to {{ }}. The situation is analogous to that of the four bases for symmetric functions in which the fourth basis - known as the "forgotten symmetric functions" - arises from automorphisms linking the other three bases together. We have no natural combinatorial interpretation of the numbers h(m,k), but we are hopeful that one will be found. The principal clue is the 3tr:

k h(m,k) = h(m-1,k) + (m-k+1) h(m,k-1)

The DNA evidence linking these four triangles comes from the study of some formal power series with long mathematical pedigrees. Consider

R_{p}(z)= SUM_{n>=1}n^{n-p}* (z^{n})/n!

Then R_{1}(z) = T(z), the exponential generating function for the number of rooted, labelled trees with n vertices (that this count is n^{n-1} goes back to Sylvester, Borchardt, and Cayley).

Also R_{0}(z) = *Z*(z), the e.g.f. for the number of endofunctions of a set with n elements. (Here *Z* should be considered a capital zeta, to agree with [JKLP].)

It was probably known to Euler that *Z* = T/(1-T) and so T = *Z*/(1+*Z*). In the paper introducing <<m,k>>, Carlitz showed that, for nonnegative m

R_{-m}(z)= (T/(1-T)^{2m+1}) * SUM_{k=0 to k=m}<<m,k>> T^{k}

It is quite easy to "change the variable" and verify recurrences to arrive at

R_{-m}(z)= (1+Z)^{m+1}* SUM_{k=1 to k=m}{{m+k,k}}Z^{k}

The interplay of these formulas of course yields some nice combinatorial identities.

In a study of R_{m} (for nonnegative m), Beebee and Smiley [BeSm] showed that the rational functions are actually polynomials:

R_{m}(z)= SUM_{k=1 to k=m}(-1)^{k-1}g(m,k) T^{k}

NOTE: The relationship between g(m,k) and <<m,k>> is not just analogous: a single integral operator takes R_{j}(z) to R_{j+1}(z) for any integer j (this inverts a differential operator of Carlitz and allowed the discovery of the positively subscripted formulas).

Now the change to variable *Z* transforms the T-polynomials for R_{m}(z) to rational functions of *Z* which may be written

R_{m}(z)= (1+Z)^{-m}SUM_{k=1 to k=m}h(m,k)Z^{k}

It is simple to use Carlitz' differential operator to verify

k h(m,k) = h(m-1,k) + (m-k+1) h(m,k-1)

We soon see that an integer triangle may be obtained by clearing the enormous denominator (1!2!...k!)^{m-k+1}. If we call these integers H(m,k) we may display

0 | 0 | 0 | 0 | 0 | 0 | 46416180096 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 0 | 0 | 0 | 9268512 | 1604143184117760 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 0 | 0 | 13048 | 2669331456 | 313140962230272 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 0 | 112 | 156576 | 128957184 | 81858484224 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 5 | 224 | 6188 | 136208 | 2624912 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 1 | 5 | 17 | 49 | 129 | 321 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

1 | 1 | 1 | 1 | 1 | 1 | 1 |

Only row k=2 is familiar: it's a sequence of G.H.Hardy from 1905 used in a proof of Cantor's cardinal inequality (see A000337 for this and other, more combinatorial, references).

In seeking a combinatorial interpretation of the numbers h(m,k), it is natural to create integer triangles such as H(m,k), but other choices for the denominators are possible (for example, John Beebee has noted that 1!2!...m! h(m,k) is also integral).

In examining the forgotten fractions h(m,k) directly, the enormity of the numerators and denominators can be an obstacle. So we produce

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0.36788 |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0.36789 | 5.8861 |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0.36790 | 5.5183 | 43.962 |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0.36791 | 5.1505 | 38.444 | 203.32 |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0.36795 | 4.7829 | 33.295 | 164.87 | 651.17 |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0.36801 | 4.4154 | 28.513 | 131.58 | 486.30 | 1529.8 |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0.36815 | 4.0481 | 24.100 | 103.08 | 354.73 | 1043.5 | 2723.6 |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0.36842 | 3.6815 | 20.057 | 78.985 | 251.67 | 688.84 | 1680.1 | 3741.8 |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0.36897 | 3.3158 | 16.382 | 58.943 | 172.70 | 437.20 | 991.32 | 2061.8 | 3999.5 |

0 | 0 | 0 | 0 | 0 | 0 | 0.37011 | 2.9518 | 13.079 | 42.581 | 113.79 | 264.54 | 554.15 | 1070.5 | 1937.8 | 3326.1 |

0 | 0 | 0 | 0 | 0 | 0.37248 | 2.5908 | 10.146 | 29.533 | 71.248 | 150.79 | 289.66 | 516.36 | 867.40 | 1388.3 | 2134.5 |

0 | 0 | 0 | 0 | 0.37755 | 2.2349 | 7.5861 | 19.429 | 41.763 | 79.590 | 138.92 | 226.74 | 351.06 | 520.89 | 746.22 | 1038.0 |

0 | 0 | 0 | 0.38889 | 1.8877 | 5.3984 | 11.899 | 22.390 | 37.877 | 59.365 | 87.855 | 124.35 | 169.84 | 225.34 | 291.84 | 370.34 |

0 | 0 | 0.41667 | 1.5556 | 3.5810 | 6.5687 | 10.549 | 15.532 | 21.520 | 28.512 | 36.507 | 45.504 | 55.502 | 66.501 | 78.501 | 91.500 |

0 | 0.5000 | 1.2500 | 2.1250 | 3.0625 | 4.0313 | 5.0156 | 6.0078 | 7.0039 | 8.0020 | 9.0010 | 10.000 | 11.000 | 12.000 | 13.000 | 14.000 |

1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 |

We will state without proof some properties of this triangle which we hope will be helpful in finding a combinatorial interpretation. The convergence of the diagonal to the rencontre probability 1/e is evident.

But the rencontre numbers appear again in the asymptotic behavior of the rows. If row k is multiplied by (k-1)! it becomes almost integral in the sense that there is an integer sequence P[k](n), n=1,2,... , whose differences with h(m,k) satisfy

((k-1)! * h(m,k) - P[k](m-k) ) -> 0The sequence P[k] may be taken to be polynomial of degree k-1. The polynomials defined by P[k](n) = p^{+}as m ->infinity

p_{0}= 1 ; p_{1}= n ; p_{q}= (n+q-1) p_{q-1}+ (q-1) p_{q-2}

NOTE: This is very much like the 3tr satisfied by polynomial families orthogonal with repect to some measure, except for the sign of the coefficient of p_{q-2}.

If we denote the coefficient of n^{j} in p_{q}(n) by a(q,j) we find a new and interesting integer triangle

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 55 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 45 | 1375 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 36 | 915 | 20460 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 28 | 582 | 10950 | 200013 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 0 | 0 | 0 | 0 | 1 | 21 | 350 | 5460 | 84693 | 1340493 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 0 | 0 | 0 | 1 | 15 | 196 | 2492 | 32403 | 438963 | 6245525 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 0 | 0 | 1 | 10 | 100 | 1015 | 10899 | 124908 | 1531865 | 20090840 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 0 | 1 | 6 | 45 | 355 | 3094 | 29596 | 309602 | 3523110 | 43384451 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 0 | 1 | 3 | 17 | 100 | 694 | 5453 | 48082 | 470328 | 5057331 | 59313287 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

0 | 1 | 1 | 5 | 20 | 109 | 689 | 5053 | 42048 | 391641 | 4036697 | 45618341 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

1 | 0 | 1 | 2 | 9 | 44 | 265 | 1854 | 14833 | 133496 | 1334961 | 14684570 |

Here we see the rencontre numbers D_{q} as the sequence of constant terms of the p_{q}. Also the coefficient of x^{q-1} in p_{q} is a triangular number. The columns reveal other properties of interest: the alternating sum p_{q}(-1) = (-1)^{q} and the sum p_{q}(1) = A000255(q)=D_{q}+D_{q+1}= the number of permutations of 1,...,q+1 having exactly 1 "succession" ...i i+1....

I dedicate the open questions of interpreting h(m,k) and a(q,j)(pedestrian though they may be) to the memory of G.-C. Rota, an inspirational mathematician.

[DB] David,F.N., Barton,D.E., *Combinatorial Chance*, Hafner, New York, 1962

[DKB] David,F.N.; Kendall,M.G.; Barton,D.E., *Symmetric Function and Allied Tables*, Cambridge U. Press, London, 1966

[Fek] Fekete. A, *Apropos "Two Notes on Notation"*, Amer. Math. Monthly, **101**,(8) 771-778 (1994)

[GS] Gessel, I., Stanley, R., *Stirling Polynomials*, J. Comb. Theory, Ser. A, **24**, 24-33 (1978)

[JKLP] Janson S., Knuth, D.E., Luczak, T., and Pittel, B. *The Birth of the Giant Component*, Random Structures Algorithms **4**, 231-358, (1993)

[BS4P] Riordan, J., *The Blossoming of Schroeder's Fourth Problem*, Acta Math.,**137**, 1-16 (1976)

Len Smiley Created: Sat Apr 10 09:39:30 AKDT 1999 Last modified: Wed Nov 21 03:07:10 AKST 2001