Given number $n$ variables $a_1, a_2, \dots, a_n$. How many way can we place $>$, $=$ between them ?
For example, for $n = 3$ (Let's call $a_1 = x, a_2=y, a_3=z$ for convenient). There are 13 way: $$x = y = z;\ x = y > z;\ x > y = z;\ x > y > z;\ x > z > y;\ x = z > y;\ y > x = z;\ y > x > z;\ y > z > x;\ y = z > x;\ z > x = y;\ z > x > y;\ z > y > x.$$
For $n$ small enough, I can count it by brute-force, but what about for a large $n$. Is there a formula ? How can I get it ?
Thank you.
The number of ways $n$ objects can be weakly ordered is the $n$-th Ordered Bell Number or $n$-th Fubini-number $a(n)$.
These can be calculated using the Stirling numbers of the first kind: $S(n,k)$ is the number of ways to partition a set of $n$ elements in $k$ disjoint subsets. So if we sum over the number of $=$-groups in the ordering, there are $S(n,k)$ ways to partition the $n$ element into groups such that all elements in one group are equal, and $k!$ ways to order these groups by $>$-signs. Thus
$$a(n) = \sum_{k=0}^n k! S(n,k)$$ By using formulas for the Stirling numbers we get another unexpected identity: $$a(n) = \frac{1}{2}\sum_{m=0}^\infty \frac{m^n}{2^{m}}$$