## Euler Numbers via Eulerian Numbers

This is a little curiosity I discovered several years ago.

The Euler numbers $E_k$ are the coefficients in the Maclaurin expansion of hyperbolic secant: $\text{sech } t = \sum_{k=0}^{\infty} E_k \frac{t^k}{k!}.$

The Eulerian numbers $\left< n \atop k \right>$ count the number of permutations on $n$ elements with $k$ ascents; i.e., the number of permutations $(\pi_1, \pi_2, \ldots, \pi_n)$ of $\{1, 2, \ldots, n\}$ such that $\pi_i < \pi_{i+1}$ for exactly $k$ values of $i$.  Because of the similarity of their names authors mentioning one are often careful to emphasize that they are not referring to the other [1, p. 514; 2, p. 559].

It turns out that there is a simple relationship between Euler numbers and Eulerian numbers.  We’ll prove this with generating functions.  Let $A_n$ denote the following alternating row sum of the Eulerian numbers: $A_n = \sum_{k=0}^n (-1)^{n-k} \left< n \atop k \right>$.   With $\left< 0 \atop 0 \right> = 1$, the first several numbers in the sequence of $A_n$ values are $1, -1, 0, 2, 0, -16, 0, 272, 0, -7936$.  The binomial transform of these alternating row sums of Eulerian numbers is the Euler numbers:

Equation (1): $\displaystyle E_n = \sum_{k=0}^n \binom{n}{k} A_k.$

Proof: The exponential generating function (egf) of the Euler numbers is, as we mentioned above, $\text{sech } t$, or $2/(e^t+e^{-t})$.  The Eulerian numbers have the following bivariate generating function [4, p. 149]:
$\displaystyle \sum_{n=0}^{\infty} \sum_{m=0}^{\infty} \left< n \atop m \right> x^m \frac{t^n}{n!} = \frac{1-x}{e^{(x-1)t}-x}.$
Thus the egf of the sequence $\{A_n\}$ is
$\displaystyle \sum_{n=0}^{\infty} A_n \frac{t^n}{n!} = \sum_{n=0}^{\infty} \sum_{m=0}^{\infty} (-1)^{n-m} \left< n \atop m \right> \frac{t^n}{n!} = \displaystyle \sum_{n=0}^{\infty} \sum_{m=0}^{\infty} (-1)^m \left< n \atop m \right> \frac{(-t)^n}{n!} = \frac{2}{e^{2t}+1}.$
The egf of the binomial transform of a sequence is the egf of the sequence multiplied by $e^t$ [5].  Thus the egf of $\sum_{k=0}^n \binom{n}{k} A_k$ is $2e^t/(e^{2t}+1) = 2/(e^t+e^{-t})$,  which is the egf of the Euler numbers.

Equation (1) can be expressed in terms of the inverse binomial transform, too, simply by inverting it [5].  We have
Equation (2):$\displaystyle \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} E_k = \sum_{k=0}^n (-1)^{n-k} \left< n \atop k \right>,$

or the slightly simpler

Equation (3): $\displaystyle \sum_{k=0}^n (-1)^k \binom{n}{k} E_k = \sum_{k=0}^n (-1)^k \left< n \atop k \right>.$

Incidentally, Jordan [3, p. 300] contains an expression having the form of Equation (1), but he does not identify the numbers appearing where the $A_k$ do as alternating row sums of Eulerian numbers.  It is also easy to show that the $A_n$ are the coefficients in the expansion of $1-\tanh t$ as an egf.    Finally, $(-1)^n E_{2n}$ is the number of alternating permutations of $\{1, 2, \ldots, 2n\}$; that is, permutations $(\pi_1, \pi_2, \ldots, \pi_{2n})$  such that $\pi_1 > \pi_2 < \pi_3 > \pi_4 < \cdots > \pi_{2n}$ [4, p. 154].

So, I’ll end this post with a question: Can Equations (1), (2), or (3) be proved combinatorially, by finding a relationship between ascents and alternating permutations?

References

1.  Charalambos A. Charalambides, Enumerative Combinatorics, CRC Press, 2002.
2.  Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994.
3.  Charles Jordan, Calculus of Finite Differences, 3rd ed., Chelsea, 1965.
4.  Kenneth H. Rosen (ed.), Handbook of Discrete and Combinatorial Mathematics, CRC Press, 2000.
5.  Michael Z. Spivey and Laura L. Steil, The $k$-binomial transforms and the Hankel transform, Journal of Integer Sequences 9 (2006), Article 06.1.1.