Recursive function for finding number of equivalence classes

Question

I have $n$ elements that can be ordered using $>, <, =$. The question is how to best calculate (in computer terms) the number of possible such orderings. For example, for $n=2$ the possible orders are:

• $a<b$
• $a=b$
• $b<a$

So $f(2)=3$. Similarly, $f(3)=13$.

This can clearly be done with recursion using dynamic programming. The number of orderings is equivalent to the number of difference equivalence classes for subsets of the element set. I was not able to think of a good recursive solution, and found the following one:

$f(n)=1+\sum\limits_{i=1}^{n-1}(\binom{n}{i}f(n-i))$

It seems to work for the small numbers I could try on. Can anyone point me to the intuition for how this answer was reached? Usually with dynamic programming one would write each set as the sum of two expressions: when the element is "taken" in the current step, and when it isn't (like in the knapsack problem). This logic appears to fail here, as the $1$ represents the one equivalence class where all elements are equivalent.

Answer 1

You are looking for the OEIS sequence A000670 (Fubini numbers or ordered Bell numbers) and much information about computing it and combinatorial interpretations is there.

Answer 2

(This is a comment, not an answer.)

These appear to be related to the Bell numbers, which count the number of partitions of a set (see http://mathworld.wolfram.com/BellNumber.html or https://en.wikipedia.org/wiki/Bell_number).

They satisfy the recurrence $B_{n} =\sum_{k=0}^{n-1} \binom{n-1}{k}B_k =\sum_{k=0}^{n-1} \binom{n-1}{k}B_{n-1-k} $.