We introduce three "old friends" to a common relative. We deal in triangles of numbers, 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. A picture of the start of the triangle and a description of a second problem appear in CM. (See the digression below).

Triangle of differences of reciprocals of unity = A008969

We write these as G(m,k). The "g" is for "golliwog" for reasons not fully understood. If we write N=m-k+1, then 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. The triangle is depicted in DKB. If we consider the probability that a k-by-N matrix satisfying (a) satisfies (b) we write $g(m,k)=G(m,k)/(k!)m-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 triangle appear in Fekete.

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

These numbers (h(m,k) seems reasonable) arise from the g(m,k) by the same algebraic transform which relates << >> to {{ }}. An integer triangle H(m,k) is obtained by 'clearing' the denominator (1!2!...k!)^{m-k+1}.

(k+1)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

R_{m}(z)= SUM_{n>=1} n^{n-m} * (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)=U(z), the e.g.f. for the number of endofunctions of a set with n elements.

It was probably known to Euler that U=T/(1-T) and so T=U/(1+U). 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}

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

In a study of R_{m} (for nonnegative m), Beebee and Smiley showed that

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

0 | 0 | 0 | 0 | 0 | 1 | 6 |

0 | 0 | 0 | 0 | 1 | 5 | 15 |

0 | 0 | 0 | 1 | 4 | 10 | 20 |

0 | 0 | 1 | 3 | 6 | 10 | 15 |

0 | 1 | 2 | 3 | 4 | 5 | 6 |

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

0 | 0 | 0 | 0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 | 0 | 0 | 720 |

0 | 0 | 0 | 0 | 0 | 120 | 3708 |

0 | 0 | 0 | 0 | 24 | 444 | 4400 |

0 | 0 | 0 | 6 | 58 | 328 | 1452 |

0 | 0 | 2 | 8 | 22 | 52 | 114 |

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

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

0 | 0 | 0 | 0 | 0 | 1 | 6 |

0 | 0 | 0 | 0 | 1 | 5 | 15 |

0 | 0 | 0 | 1 | 4 | 10 | 20 |

0 | 0 | 1 | 3 | 6 | 10 | 15 |

0 | 1 | 2 | 3 | 4 | 5 | 6 |

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

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

0 | 0 | 0 | 0 | 0 | 1 | 6 |

0 | 0 | 0 | 0 | 1 | 5 | 15 |

0 | 0 | 0 | 1 | 4 | 10 | 20 |

0 | 0 | 1 | 3 | 6 | 10 | 15 |

0 | 1 | 2 | 3 | 4 | 5 | 6 |

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