Why does $\frac{1}{2}A_n(2)$ count the number of ordered set partitions?

Question

Suppose $A_n(x)$ denotes the Eulerian polynomial. Is there a combinatorial proof that $\frac{1}{2}A_n(2)$ counts the number of ordered set partitions? By this I mean a set partition of a set of $n$ elements with a linear ordering on its blocks.

Answer 1

You have an extra factor of $\frac12$: it should be simply $A_n(2)$.

Let $\pi$ be a permutation of $[n]$, say $\pi=p_1\dots p_n$. Let $A(\pi)=\{i:p_i<p_{i+1}\}$, the set of ascents of $\pi$, and let $D(\pi)=\{i:p_i>p_{i+1}\}$, the set of descents of $\pi$. From $\pi$ we can generate $2^{|A(\pi)|}$ ordered permutations of $[n]$ as follows.

The coarsest ordered partition generated by $\pi$ is obtained by breaking $\pi$ immediately after each descent. For example, if $n=5$ and $\pi=34152$, the descents are $2$ and $4$, and the coarsest partition is $\{3,4\},\{1,5\},\{2\}$. The other ordered partitions generated by $\pi$ are those obtained by breaking the non-singletons arbitrarily while preserving the order of their elements. In this example we end up with four ordered partitions altogether:

$$\begin{align*} &\{3,4\},\{1,5\},\{2\}\\ &\{3,4\},\{1\},\{5\},\{2\}\\ &\{3,4\},\{1,5\},\{2\}\\ &\{3\},\{4\},\{1\},\{5\},\{2\} \end{align*}$$

Similarly, the permutation $34125$ produces these eight ordered partitions:

$$\begin{align*} &\{3,4\},\{1,2,5\}\\ &\{3\},\{4\},\{1,2,5\}\\ &\{3,4\},\{1\},\{2,5\}\\ &\{3\},\{4\},\{1\},\{2,5\}\\ &\{3,4\},\{1,2\},\{5\}\\ &\{3\},\{4\},\{1,2\},\{5\}\\ &\{3,4\},\{1\},\{2\},\{5\}\\ &\{3\},\{4\},\{1\},\{2\},\{5\} \end{align*}$$

In this construction each descent of $\pi$ is a required break point between pieces of the partition, and each ascent of $\pi$ is a potential break point, so $\pi$ generates $2^{|A(\pi)|}$ ordered partitions.

Conversely, start with an ordered partition of $[n]$. Within each part list the elements in increasing order; removing the braces from this standard form then yields a permutation of $[n]$ that generates the ordered partition. E.g., the ordered partition $\{4,1,5\},\{3\},\{2\}$ of $[5]$ has standard form $\{1,4,5\},\{3\},\{2\}$ and is generated by the permutation $14532$. Moreover, no other permutation of $[n]$ generates the partition, since the procedure for generating ordered partitions always generates them in standard form.

The number of permutations of $[n]$ with $k$ ascents is given by the Eulerian number $\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle$, and each of these permutations generates $2^k$ ordered partitions of $[n]$, so the $n!$ permutations of $[n]$ generate altogether

$$\sum_{k=0}^{n-1}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle 2^k\tag{1}$$

ordered partitions of $[n]$. On the other hand, $$A_n(t)=\sum_{k=0}^{n-1}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle t^k$$ (see here, for instance), and the expression in $(1)$ is clearly $A_n(2)$.