Take the 2-minute tour ×

Suppose you are given a set of $N$ objects and a strict total ordering relation $<$ satisfying the standard properties (from wikipedia):

  • transitivity: $a < b$ and $b < c$ implies $a < c$
  • trichotomy: exactly one of $a<b$, $b < a$, and $a = b$ is true
  • the relation is a strict weak order, where the associated equivalence is equality

The question is: how many possible orderings can there be on the $N$ objects?

For example, for a set $\{a, b\}$ where $N = 2$, there are 3 possible orderings: $a < b$, $b < a$, and $a = b$.

In general, how many orderings are there as a function of $N$?

share|improve this question
One way to answer this kind of question is to compute the first few values and then look the sequence up in the Online Encyclopedia of Integer Sequences, oeis.org In this case, the first thing that comes up when you type 1,3,13 in is oeis.org/A000670 which is what you want. –  Gerry Myerson May 12 '11 at 7:32
@Gerry - Thanks! –  dsg May 12 '11 at 7:38
add comment

3 Answers

up vote 6 down vote accepted

Let $a_n$ denote the answer. I claim that

$$\sum_{n \ge 0} \frac{a_n}{n!} z^n = \frac{1}{2 - e^z}.$$

To see this, write the RHS as $\frac{1}{1 - (e^z - 1)}$, or

$$\sum_{k \ge 0} (e^z - 1)^k.$$

Then I claim that the coefficient of $\frac{z^n}{n!}$ in $(e^z - 1)^k$ is precisely the number of ways to weakly order $n$ objects such that there are $k$ equivalence classes. This is equivalent to the number of ways to partition $n$ objects into $k$ non-empty subsets in order, so you can prove this by using identities for Stirling numbers, but it actually follows directly from basic properties of exponential generating functions: $e^z - 1$ is the generating function for non-empty sets, so $(e^z - 1)^k$ is the generating function for $k$-tuples of non-empty sets.

The generating function above shows that one can't expect, say, a formula in terms of a bounded number of binomial coefficients or anything especially nice like that. However, $\frac{1}{2 - e^z}$ is a meromorphic function, and the pole closest to the origin is at $z = \log 2$. This turns out to imply, after some computations, that

$$\frac{a_n}{n!} \sim \frac{1}{2 (\log 2)^{n+1}}$$

and one can even precisely write down the rest of the terms in the asymptotic expansion. For example, the next poles are at $z = \log 2 \pm 2 \pi i$, so the next term in the asymptotic expansion is $$\frac{a_n}{n!} \sim \frac{1}{2 (\log 2)^{n+1}} + \frac{\cos (n+1) \theta}{r^{n+1}}$$

where $r = \sqrt{(\log 2)^2 + 4 \pi^2}, \theta = \arctan \frac{2\pi}{\log 2}$. It actually follows from the fact that all of the other terms are much smaller than this that the first term in the above estimate has exponentially small error. For example, the largest value in the OEIS is $$\frac{a_{18}}{18!} = 528.793...$$

whereas $$\frac{1}{2 (\log 2)^{19}} = 528.794...$$

For more on these kinds of techniques, see Flajolet and Sedgewick's Analytic Combinatorics.

share|improve this answer
thanks! A lot of cool pointers here to deeper concepts that I will now go and learn! –  dsg May 13 '11 at 12:08
add comment

Promoting my comment to an answer: this sequence is oeis.org/A000670. I believe the description there gives the formula in user9325's answer, as well as the generating function and an asymptotic formula in Qiaochu's answer (but by no means everything in Qiaochu's answer).

share|improve this answer
add comment

If you know Stirling numbers, you can just choose a number $k$, divide the $N$ objects in $k$ clusters of equal objects ($S(N,k)$ possibilites) and then sort the clusters ($k!$ possibilities) which gives:


share|improve this answer
add comment

Your Answer


