. We subtract 1 to cancel out the empty partition of 0 counted by the product on the right but not by H(m, u). Continuing with the right hand side of (14), we get The sum appearing in the right hand side of (15) is the antiderivative of sec u = i≥0 E 2i u 2i /(2i)! that vanishes at u = 0; this antiderivative is ln(tan u + sec u). Therefore H(m, u) + 1 = (tan u + sec u) m.
Hence we have It is straightforward to verify that the right hand sides of (13) and (16) agree, and thus Equating the coefficients of u n /n! on both sides of (17) completes the proof of the theorem.
In the terminology of [11,Sec. 4.5], Theorem 4.3 states that the polynomialsÂ n (t) are thef n -Eulerian polynomials.

Eulerian polynomials and symmetric functions
The results of the previous section can be tied to the theory of symmetric functions. Let us recall some basics. For a composition γ = (γ 1, γ 2,..., γ k ), the monomial quasisymmetric function M γ (x 1, x 2,...) is defined by Let π(γ) denote the partition obtained by rearranging the parts of γ in non-increasing order. Then for a partition λ, the monomial symmetric function m λ (x 1, x 2,...) is defined as Let f (x) be a function given by the formal power series f (x) = 1 + n≥1 a n x n n!.
Define the symmetric function g f,n (x 1, x 2,...) by g f,n := γ|=n n γ · a γ 1 a γ 2 · · · · M γ = λ⊢n n λ · a λ 1 a λ 2 · · · · m λ, where by γ |= n and λ ⊢ n we mean that γ and λ are a composition and a partition of n, respectively. This function can be thought of as the generating function for numbers like α n (S) orα n (S) (the number of permutations σ ∈ S n with D(σ) ⊆ S orD(σ) ⊆ S, respectively). Our first step is to express g f,n in terms of the power sum symmetric functions p k (x 1, x 2,...) = x k i. Consider the generating function Then we have Then from (19) we have Since the power sum symmetric functions p λ = p λ 1 p λ 2 · · ·, with λ ranging over all partitions of positive integers, form a basis for the ring of symmetric functions, the transformation p n → b n p n u n /(n − 1)!, where u is regarded as a scalar, extends to a homomorphism of this ring. Applying this homomorphism to the well-known identity where λ ranges over all partitions of positive integers, we obtain from (21) that Comparing the coefficients of u n in (18) and (22), we conclude the following: Two special cases related to earlier discussion are f (x) = e x and f (x) = tan x + sec x. For f (x) = e x, we have b 1 = 1, b 2 = b 3 = · · · = 0, and hence g f,n = p n 1. In the case of f (x) = tan x + sec x, we have thus the coefficient at p λ in the expression of Proposition 5.1 coincides with the coefficient in the term for λ in the definition of the polynomialf n (m) of Theorem 4.3. These observations lead to the following restatements of the classical identity (12) and Theorem 4.3.
It is an interesting problem to prove Proposition 5.2 without referring to the results of Section 4. Observe that for γ = (γ 1, γ 2,..., γ k ) |= n, we have M γ (1 m ) = m k, the number of monomials x γ 1 i 1 x γ 2 i 2 · · · x γ k i k where 1 ≤ i 1 < · · · < i k ≤ m, which are the monomials in the definition of M γ that evaluate to 1.
It would also be of interest to relate the observations of this section to Schur functions. One possibility is to consider the following generalization of the complete homogeneous symmetric function. Let ϕ f be the homomorphism of the ring of symmetric functions defined by p n → b n p n /(n − 1)!, where the b i's are as in equation (20). Let

The alternating Eulerian numbers
In this section we give a recurrence relation that allows to construct a triangle of alternating Eulerian numbersÂ(n, k) introduced in Section 4. (Recall thatÂ(n, k) denotes the number of permutations in S n with k − 1 alternating descents.) The first few rows of this triangle are given in The following lemma provides a way to compute alternating Eulerian numbers given the initial conditionÂ(n, 1) = E n. Proof. First, suppose that k is even. The left hand side of the equation counts the number of ways to split the elements of [n] into two groups of sizes i and n−i, arrange the elements in the first and the second group so that the resulting permutations have j and k − j alternating descents, respectively, and writing down the second permutation after the first to form a permtutation of [n]. This permutation has either k or k+1 alternating descents, depending on whether an alternating descent is produced at position i. For a permutation σ ∈ S n withî(σ) = k, there are exactly n + 1 − k ways to produce σ by means of the above procedure, one for every choice of i ∈D(σ) ∪ {0, n}. Similarly, for σ ∈ S n such thatî(σ) = k + 1, there are exactly k + 1 ways to produce σ, one for every choice of i ∈D(σ). The identity follows.
As for odd k, the same argument is valid, except that the quantityÂ(n−i, k−j +1) in the left hand side should be interpreted as the number of ways to arrange the elements of the second group to form a permutation with k − j alternating ascents, which become alternating descents when the two permutations are concatenated.
Recall the generating function F (t, u) = n,k≥1Â (n, k) · t k u n n! introduced in Section 4. An alternative way to express F (t, u) and obtain the result of Theorem 4.2 is by solving a partial differential equation arising from the recurrence of Lemma 6.1.
Proposition 6.2. The function F (t, u) is the solution of the partial differential equation with the initial condition F (0, u) = tan u + sec u.
Proof. SinceÂ(n, 0) = 0 for all n, the left hand side of (23) is n! times the coefficient of t k u n in F (t, u) 2, which we denote by [t k u n ]F 2. The right hand side of (23) is where F t and F u denote partial derivatives of F with respect to t and u. Equating the above with n! · [t k u n ]F 2 proves (24).

The generating function for the alternating descent set statistic
Besides the generating polynomials for the alternating descent statistic, another natural generating function to consider is one counting permutations by their alternating descent set. We begin by stating some well-known facts about the analogous generating function for the classical descent set statistic.
Fix a positive integer n. For a subset S ⊆ [n − 1], define the monomial u S in two non-commuting variables a and b by u S = u 1 u 2 · · · u n−1, where where β n (S) is the number of permutations in S n with descent set S. The polynomial Ψ n (a, b) is known as the ab-index of the Boolean algebra B n. A remarkable property of Ψ n (a, b) (and also of ab-indices of a wide class of posets, including face lattices of polytopes) is that it can be expressed in terms of the variables c = a + b and The polynomial Φ n (c, d) has positive integer coefficients, for which several combinatorial interpretations have been found. Here we give one that will help establish a connection with the alternating descent set statistic. We proceed with a definition. Let SS n be the set of simsun permutations in S n whose last element is n. (Thus SS n is essentially the set of simsun permutations of [n − 1] with an n attached at the end.) It is known that | SS n | = E n.
For a permutation σ ∈ SS n, define the (c, d)-monomial cd(σ) as follows: write out the descent set of σ as a string of pluses and minuses denoting ascents and descents, respectively, and then replace each occurrence of " -+ " by d, and each remaining plus by c. This definition is valid because a simsun permutation has no consecutive descents. For example, consider the permutation 423516 ∈ SS 6. Its descent set in the above notation is " -+ + -+ ", and thus cd(423516) = d c d.
Proof