0
$\begingroup$

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.

$\endgroup$
9
  • $\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, 2015 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, 2015 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, 2015 at 13:37
  • $\begingroup$ @BusyAnt it was typo, fixed $\endgroup$
    – Alex Burtsev
    Jul 23, 2015 at 13:40
  • 3
    $\begingroup$ These are the ordered Bell numbers, aka Fubini numbers. No known closed form. $\endgroup$
    – André Nicolas
    Jul 23, 2015 at 13:46

2 Answers 2

Reset to default
3
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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).

$\endgroup$
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, 2015 at 13:48

Not the answer you're looking for? Browse other questions tagged .