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.
Why does $\frac{1}{2}A_n(2)$ count the number of ordered set partitions?
2 Answers
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
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)$.
-
1A very late thanks, Brian. :) – 2012-04-22
Start from the bivariate generating function of the Eulerian numbers: $G(z, u) = \frac{u-1}{u-\exp((u-1)z)}.$ This gives for $A_n(2)$ by substitution the generating function $\frac{1}{2-\exp(z)} = \frac{1}{1-(\exp(z)-1)}.$ But ordered set partitions are the species $\mathfrak{S}(\mathfrak{P}_{\ge 1}(\mathcal{Z}))$ which means they have generating function $\frac{1}{1-z} \circ (\exp(z)-1) = \frac{1}{1-(\exp(z)-1)}.$