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.

Advertisements
This entry was posted in combinatorics. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s