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

H(m,k) (big numerators) (lower left is (1,1))
00000046416180096
0000092685121604143184117760
0000130482669331456313140962230272
00011215657612895718481858484224
00522461881362082624912
0151749129321
1111111

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

h(m,k) (rounded rationals) (lower left is (1,1))
0000000000000000.36788
000000000000000.367895.8861
00000000000000.367905.518343.962
0000000000000.367915.150538.444203.32
000000000000.367954.782933.295164.87651.17
00000000000.368014.415428.513131.58486.301529.8
0000000000.368154.048124.100103.08354.731043.52723.6
000000000.368423.681520.05778.985251.67688.841680.13741.8
00000000.368973.315816.38258.943172.70437.20991.322061.83999.5
0000000.370112.951813.07942.581113.79264.54554.151070.51937.83326.1
000000.372482.590810.14629.53371.248150.79289.66516.36867.401388.32134.5
00000.377552.23497.586119.42941.76379.590138.92226.74351.06520.89746.221038.0
0000.388891.88775.398411.89922.39037.87759.36587.855124.35169.84225.34291.84370.34
000.416671.55563.58106.568710.54915.53221.52028.51236.50745.50455.50266.50178.50191.500
00.50001.25002.12503.06254.03135.01566.00787.00398.00209.001010.00011.00012.00013.00014.000
1.01.01.01.01.01.01.01.01.01.01.01.01.01.01.01.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) ) -> 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

a(q,j) (polynomial coefficients) (lower left is (0,0))
000000000001
0000000000155
0000000001451375
0000000013691520460
000000012858210950200013
0000001213505460846931340493
000001151962492324034389636245525
0000110100101510899124908153186520090840
0001645355309429596309602352311043384451
001317100694545348082470328505733159313287
011520109689505342048391641403669745618341
1012944265185414833133496133496114684570

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