5
$\begingroup$

In this interview, Ira Gessel mentions the following results:

Result 1: Let $B_n$ denote the $n^{\text{th}}$ Bernoulli number. Define the series $$B(x) = \sum_{n=2}^{\infty} \frac{B_nx^{n-1}}{n(n-1)}.$$ Let $v_n$ be the sequence of reals with such that the series $$F(x) = \sum_{n=1}^{\infty} \frac{v_nx^n}{n!}$$ satisfies $$F\left(\sqrt{2x - 2(\log(1+x))}\right) = x.$$ Then we have $$e^{B(x)} = \sum_{n=0}^{\infty} \frac{v_{2n+1}x^n}{2^n n!}.$$

Result 2: Let $s_n$ be the number of strongly connected, directed graphs with vertex set $\{1, \dots, n\}$. Let $t_n$ be the number of strongly connected tournaments with vertex set $\{1, \dots, n\}$. Let $$T(x) = \sum_{n=1}^{\infty} \frac{2^{\binom{n}{2}}t_n x^n}{n!}.$$ Then $$\log\left(\frac{1}{1-T(x)}\right) = \sum_{n=1}^{\infty} \frac{s_nx^n}{n!}.$$

Result 3: Let $A_n(t)$ denote the $n^{\text{th}}$ Eulerian polynomial. Then $$\frac{A_n(t)}{(1-t)^{n+1}} = \sum_{k=0}^{\infty} k^nt^k.$$

My Question: What are the references for the proofs of results 1 through 3 above?

$\endgroup$
3
  • $\begingroup$ These are all pretty well-known (certainly Result 3 is very very well-known). Did you make an effort to look up any of these? For example, reading the Wikipedia pages you linked to? $\endgroup$ Commented May 12 at 18:31
  • 6
    $\begingroup$ Are Results 1 and 2 really well-known? On the other hand, Result 3 is a basic result in enumerative combinatorics going back to Carlitz and Riordan in 1953. It should appear in any book on the subject, such as my Enumerative Combinatorics, vol. 1, second ed., Prop. 1.4.4. $\endgroup$ Commented May 12 at 18:43
  • $\begingroup$ @RichardStanley okay I admit I only looked at Result 3 when I made that comment (and indeed it is on the Wikipedia page). I guess Ira can explain 1 & 2, although 2 looks like a basic exponential theorem thing. $\endgroup$ Commented May 12 at 18:47

1 Answer 1

11
$\begingroup$

Result 1 can be found in N. G. de Bruijn, Asymptotic Methods in Analysis, Dover, New York, 1981, p. 71.

Result 2 follows from a formula of E. M. Wright, though he didn't state it in this form. A discussion of this formula, with a generalization, can be found in Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, Discrete Math. 343 (2020), 112041, 14 pp. https://doi.org/10.1016/j.disc.2020.112041. See Proposition 8. The arXiv version is https://doi.org/10.48550/arXiv.1909.01550.

As Sam and Richard noted, Result 3 is well known. It is equivalent to Euler's definition of the Eulerian polynomials. The combinatorial interpretation of the Eulerian polynomials is a special case of a much more general result of MacMahon, though I don't think that MacMahon recognized this special case as being noteworthy, nor did he connect it with Euler's work.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .