Four Numerical Triangles in Nexus

# Four Numerical Triangles in Nexus

### Leonard Smiley, University of Alaska Anchorage

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

1. 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 {nn+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.)
2. 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.)
3. GS-Permutations. A slightly revisionist presentation of some counting problems answered by the Second-order Eulerian Numbers.Mapping links:(none from 3.)
4. 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.)
5. Pez problem. A "story problem" intended as a mnemonic for the Golliwog numbers, and as a change of pace. Mapping links: (5.->4)
1. "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.

## Cast of Characters

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.

### Second-order Eulerian triangle = A008517

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

### Triangle of differences of reciprocal powers of unity (or 'Golliwog numbers') = A008969

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)
```

### Triangle of associated Stirling numbers of the second kind = A008299

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}}
```

### The 'forgotten' triangle = A??????

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)
```

## Genealogy

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

```Rp(z)= SUMn>=1  nn-p * (zn)/n!
```

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

Also R0(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) * SUMk=0 to k=m <<m,k>> Tk
```

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

```R-m(z)= (1+Z)m+1 * SUMk=1 to k=m {{m+k,k}} Zk
```

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

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

```Rm(z)= SUMk=1 to k=m (-1)k-1 g(m,k) Tk
```

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

## 'New' Triangles

Now the change to variable Z transforms the T-polynomials for Rm(z) to rational functions of Z which may be written

```Rm(z)= (1+Z)-m SUMk=1 to k=m h(m,k) Zk
```

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.3679 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.3 1529.8 0 0 0 0 0 0 0 0 0 0.36815 4.0481 24.1 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.7 437.2 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.4 1388.3 2134.5 0 0 0 0 0.37755 2.2349 7.5861 19.429 41.763 79.59 138.92 226.74 351.06 520.89 746.22 1038 0 0 0 0.38889 1.8877 5.3984 11.899 22.39 37.877 59.365 87.855 124.35 169.84 225.34 291.84 370.34 0 0 0.41667 1.5556 3.581 6.5687 10.549 15.532 21.52 28.512 36.507 45.504 55.502 66.501 78.501 91.5 0 0.5 1.25 2.125 3.0625 4.0313 5.0156 6.0078 7.0039 8.002 9.001 10 11 12 13 14 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

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) ) -> 0+ as m -> infinity
```
The sequence P[k] may be taken to be polynomial of degree k-1. The polynomials defined by P[k](n) = pk-1(n) have nonnegative integer coefficients and satisfy the recurrence

```                           p0 = 1 ; p1 = n ; pq = (n+q-1) pq-1 + (q-1) pq-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 pq-2.

If we denote the coefficient of nj in pq(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 Dq as the sequence of constant terms of the pq. Also the coefficient of xq-1 in pq is a triangular number. The columns reveal other properties of interest: the alternating sum pq(-1) = (-1)q and the sum pq(1) = A000255(q)=Dq+Dq+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.

## References

[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