# How to calculate combinations count for this problem

I will explain my question using simple example, cause I don't know to descrive it properly. If we have 2 numbers $\{a,b\}$, by comparing them, we get 3 possible combinations: $$a>b, \hspace{3pt} a<b, \hspace{3pt} a=b$$ For 3 numbers $\{a,b,c\}$ we get, $$b<a>c, \hspace{3pt} b>a<c, \hspace{3pt} a<b>c, \hspace{3pt} a>c<b, \hspace{3pt} \hspace{3pt} a=b=c, \hspace{3pt} a=b>c, \hspace{3pt} etc...$$

How to calculate how many combinations exist for n numbers.

• If we follow your leading example, the one with $3$ numbers is false... We should find : $a<b<c, a<b=c, a<c<b, b<a<c, b<a=c, b<c<a, c<a<b, c<a=b, c<b<a$ – BusyAnt Jul 23 '15 at 13:35
• If you call $a$ and $b$ "$2$ numbers" then implicitly you accept that $a\neq b$. If you want to include the possibility that $a=b$ then you must speak of $2$ symbols that both stand for a number (possibly both for the same). Strangely when it comes to $3$ numbers you seem to accept tacitly that the numbers are distinct. – drhab Jul 23 '15 at 13:35
• In your first example : are you aware that $a>b$ and $b<a$ mean the same thing? – BusyAnt Jul 23 '15 at 13:37
• @BusyAnt it was typo, fixed – Alex Burtsev Jul 23 '15 at 13:40
• These are the ordered Bell numbers, aka Fubini numbers. No known closed form. – André Nicolas Jul 23 '15 at 13:46

If I understand the problem correctly, these are the ordered Bell numbers, aka the Fubini numbers. Perhaps the cleanest formulation of the problem is that we have $n$ (distinct) runners in a race, and we want to count the number $a(n)$ of possible orders of finish, including ties.
There are useful recurrences, ways to express $a(n)$ as sums, and asymptotics, but no known closed form.
Put the n numbers in any order. There are $(n-1)$ spaces between the numbers in which you have to put signs. There are 3 signs to choose from for each space. Therefore, the solution is 3^(n-1).
• If we rigourously follow this reasoning, we would find $3^{n-1}$, not $3\times (n-1)$. Furthermore, eventhough this answer is "lexically" correct, it would not make much sens, mathematically speaking. – BusyAnt Jul 23 '15 at 13:48