COMPLETION OF A SEQUENCE OF CARLITZ

John C. Beebee and Leonard M. Smiley

Department of Mathematical Sciences, University of Alaska Anchorage, Anchorage, Alaska 99508

Abstract. The exponential generating functions of {n^{n±m}}_{n≥1} are given as rational functions of the “tree function” and then of the “endofunction function”.

April 20, 1999

1. A Transformed Sequence

The variable λ = T (z) = ∑_{n≥1} n^{n−1} \frac{z^{n}}{n!} has been used extensively in the analysis of random mappings and random graphs[JKLP][FO]. As formal power series, z = λe^{−λ}, an identity known, in essence, to Euler. For integer values of m we define G_{m}(λ) := R_{m}(z) := ∑_{n≥1} n^{n−m} \frac{z^{n}}{n!} . We derive a doubly infinite sequence:

…
G_{4}(λ) =  −\frac{1}{24}λ^{4} + \frac{11}{36}λ^{3} − \frac{7}{8}λ^{2} + λ
G_{3}(λ) =  \frac{1}{6}λ^{3} − \frac{3}{4}λ^{2} + λ
G_{2}(λ) =  −\frac{1}{2}λ^{2} + λ
G_{1}(λ) =  λ
G_{0}(λ) =  \frac{λ}{1 − λ}
G_{−1}(λ) =  \frac{λ}{(1 − λ)^{3}}

G_{−2}(λ) =  \frac{λ(1 + 2λ)}{(1 − λ)^{5}}

G_{−3}(λ) =  \frac{λ(1 + 8λ + 6λ^{2})}{(1 − λ)^{7}}
…

The notation ⟨⟨{n \atop k}⟩⟩ for the “second-order Eulerian” numbers has been standardized in [GKP ] (Table 270). We note the occurrence of this triangle of numbers in the sequence. Specifically we have the following transform for nonnegative m:

G_{−m}(λ) := ∑_{n≥1} n^{n+m} \frac{z^{n}}{n!} = \frac{λ}{(1 − λ)^{2m+1}} ∑_{k=0}^{m}⟨⟨{m \atop k}⟩⟩λ^{k}

This is the main result in Carlitz [C]. Combinatorial interpretations of ⟨⟨{n \atop k}⟩⟩ were subsequently given by Riordan[R] and Gessel and Stanley [GS].

We will discover the upper triangle (the coefficients of the polynomials G_{m}(λ), m > 0), noting that the numbers therein have appeared previously in combinatorial settings, and we will give two rules, one for calculating the line above, and one for calculating the line below, \underline{any} given line in the sequence. The method is rudimentary.

Typeset by AMS-TEX

Theorem. G_{m+1}(λ) = ∫_{0}^{λ} G_{m}(ρ)\frac{1−ρ}{ρ} dρ.

Proof. The only “step” is to substitute u = ρe^{−ρ} at the right time:

G_{m+1}(λ) = R_{m+1}(z) = ∫_{0}^{z} R_{m}(u)\frac{du}{u} = ∫_{0}^{λ} R_{m}(ρe^{−ρ})\frac{1 − ρ}{ρ} dρ = ∫_{0}^{λ} G_{m}(ρ)\frac{1 − ρ}{ρ} dρ.

Corollary 1. G_{m−1}(λ) = \frac{λ}{1−λ}G′_{m}(λ).

Proof. The proof is immediate. This result is equivalent to some calculations of Carlitz in [ ].

Corollary 2. If m > 0, G_{m}(λ) is a polynomial of degree m without constant term. If we write G_{m}(λ) = ∑_{k=1}^{m}(−1)^{k−1}g(m, k)λ^{k}, then k · g(m, k) = g(m − 1, k) + g(m − 1, k − 1) for m > 1.

Proof. Immediate. We note also that the coefficient of λ in G_{m}(λ), m > 0, is always 1.

2. Extended Remark.

Consider the recurrence relation

k · g(m, k) = g(m − 1, k) + g(m − 1, k − 1)

for m, k ≥ 1 where we initialize by g(m, k) = 0 if k > m, and g(m, 1) = 1. Since this is our definition, the verification of the following formulas is routine.(Compare with the appendices in [DB] and [Quad])

The unique solution may be expressed as a sum of “Egyptian Fractions”:

g(m, k) = \frac{1}{k!} ∑_{1≤i_{1}≤i_{2}≤···≤i_{m−k}≤k} \frac{1}{i_{1}i_{2} ⋯ i_{m−k}}

An alternative form is in the shape of an iterated difference of f(x) = \frac{1}{x^{m−k+1}} :

g(m, k) = \frac{1}{k − 1!} ∑_{j=0}^{k−1} \binom{k − 1}{j}\frac{(−1)^{j}}{(j + 1)^{m−k+1}}

and once again the recurrence relation and its boundary conditions are easily checked. Generating functions for the g(m, k)’s also follow by this method:

g(m, k) = [z^{m−k}] ∏_{p=1}^{k} \frac{1}{p − z}

which may also be written in a “connection coefficient” formula:

\frac{1}{(x + 1)(x + 2) ⋯ (x + k)} = ∑_{n=0}^{∞}(−1)^{n}g(k + n, k)x^{n}

providing a link between the g(m, k) and the signless Stirling cycle numbers.

A “hypercube” polynomial integral yields the same numbers:

g(m, k) = \frac{1}{(k − 1)!} ∫_{0}^{1} ∫_{0}^{1} ⋯ ∫_{0}^{1}(1 − x_{1}x_{2} ⋯ x_{m−k+1})^{k−1}dx_{1} dx_{2} ⋯ dx_{m−k+1}

since it evaluates to the iterated difference form above after applying the binomial theorem. Other formulas may be obtained by introducing generalized harmonic numbers.

The rational number g(m, k) has the “natural denominator” (k!)^{m−k+1}. The corresponding numerators N(m, k) form a triangle of integers generated by

N(m, k) = [z^{m−k}] ∏_{p=1}^{k} \frac{1}{1 − \frac{k!}{p}z}

and previously tabulated and studied in [DKB] (cf. [Smi]).

3. A Fractional Linear Transform

If λ is the “tree variable”, then

ζ = Z(z) = ∑_{n≥1} n^{n} \frac{z^{n}}{n!} = \frac{λ}{1 − λ}

is the “endofunction variable”. When we express R_{m}(z) = G_{m}(λ) in terms of ζ a beautiful phenomenon occurs: Carlitz’ rational functions (m nonpositive) become polynomials in ζ with integer coefficients strongly related to the triangle of numbers called “associated Stirling numbers of the second kind” by Riordan or “second-order Stirling numbers” by Fekete[F]. The sequence H_{m}(ζ) = R_{m}(z) = G_{m}(λ) becomes

…
H_{4}(ζ) =  \frac{ζ(1 + \frac{17}{8}ζ + \frac{14}{9}ζ^{2} + \frac{7}{18}ζ^{3})}{(1 + ζ)^{4}}

H_{3}(ζ) =  \frac{ζ(1 + \frac{5}{4}ζ + \frac{5}{12}ζ^{2})}{(1 + ζ)^{3}}

H_{2}(ζ) =  \frac{ζ(1 + \frac{1}{2}ζ)}{(1 + ζ)^{2}}

H_{1}(ζ) =  \frac{ζ}{1 + ζ}
H_{0}(ζ) =  ζ
H_{−1}(ζ) =  ζ(1 + ζ)^{2}
H_{−2}(ζ) =  ζ(1 + ζ)^{3}(1 + 3ζ)
H_{−3}(ζ) =  ζ(1 + ζ)^{4}(1 + 10ζ + 15ζ^{2})
…

In the notation of [F], G_{−m}(λ) = (1 + ζ)^{m+1} ∑_{k=1}^{m}\{\{{m+k \atop k} \}\}ζ^{k} (for m nonnegative). This provides relatively tidy relations between second-order Eulerian and second-order Stirling numbers (cf. [Smi]).

The ζ expressions for positive m contain a triangle of rational numbers h(m, k) related to the numbers g(m, k) studied above. Here we note that these coefficients satisfy the recurrence

k · h(m, k) = h(m − 1, k) + (m − k + 1) · h(m, k − 1).

The “natural denominator” for h(m, k) is (1!2! … k!)^{m−k+1}. More on this “numerical triangle” may be found in [Smi].

Conclusion

The interplay between the Mobius transformation λ ↔ ζ and the combinatorial numbers in the rational expressions for R_{m}(z) is quite pleasant. It seems unlikely that the other functions in the sequence would serve as nicely as “variables”. A combinatorial interpretation for the h(m, k)’s independent of this interplay is desirable.

References

[C] L. Carlitz, The Coefficients in an Asymptotic Expansion, Proc. Amer. Math. Soc. 16 (1965), 248-252.

[F] A. Fekete, Apropos “Two Notes on Notation”, Amer. Math. Monthly 101 (1994), 771-778.

[FO] Ph. Flajolet and A. Odlyzko, Random Mapping Statistics, Advances in Cryptology - Eurocrypt ’89, Lecture Notes in Computer Science 434 (1990), Springer-Verlag, 329-354.

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

[GKP] R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics (Second, ed.), Addison-Wesley, Reading, MA, 1994.

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

[Quad] Ph. Flajolet, G. Labelle, L Laforest, and B. Salvy, Hypergeometrics and the cost structure of quadtrees, Random Structures Algorithms 7 (1995), 117-144.

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

[Smi] L. Smiley, A Forgotten Triangle, (submitted to J. Integer Seq.).

Len Smiley, Dept. of Mathematical Sciences, UAA, Anchorage AK 99508

   E-mail address: smiley@math.uaa.alaska.edu

John Beebee, Dept. of Mathematical Sciences, UAA, Anchorage AK 99508

   E-mail address: afjcb@math.uaa.alaska.edu