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.

  • $\begingroup$ 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$ $\endgroup$ – BusyAnt Jul 23 '15 at 13:35
  • 2
    $\begingroup$ 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. $\endgroup$ – drhab Jul 23 '15 at 13:35
  • 1
    $\begingroup$ In your first example : are you aware that $a>b$ and $b<a$ mean the same thing? $\endgroup$ – BusyAnt Jul 23 '15 at 13:37
  • $\begingroup$ @BusyAnt it was typo, fixed $\endgroup$ – Alex Burtsev Jul 23 '15 at 13:40
  • 3
    $\begingroup$ These are the ordered Bell numbers, aka Fubini numbers. No known closed form. $\endgroup$ – 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).

  • 1
    $\begingroup$ 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. $\endgroup$ – BusyAnt Jul 23 '15 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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