Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose $A_n(x)$ denotes the Euler 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.


share|cite|improve this question
up vote 4 down vote accepted

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)$.

share|cite|improve this answer
A very late thanks, Brian. :) – Koji Hamada Apr 22 '12 at 22:55

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)}.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.