3
$\begingroup$

Let's say there are two variables $x$ and $y$. Here are the possible inequalities:

(i) $x<y$
(ii) $x>y$
(iii) $x=y$

So, there are $3$ possible inequalities. But let's say there are $n$ variables $x_1,x_2,x_3,x_4,\cdots,x_n$. How many possible distinct inequalities are there?

I assume this problem requires combinatorics , but I am not sure how to apply them in this problem.

Edit: Maybe this problem can be related with coin arranging (point me if I am wrong)

First of all , we can arrange coins (where order matters).But ,we will also allow for the coins to stack on top of each other.In the stacks (There can be multiple stacks) , order doesn't matter.Stacks will be represented with parenthesis.

For $1$ coin , there is $1$ way to arrange them.

  1. $1$ $[x_1]$

For $2$ coins , there are $3$ ways to arrange them.

  1. $12$ $[x_1 < x_2]$
  2. $21$ $[x_1 > x_2]$
  3. $(12)$ $[x_1 = x_2]$

For $3$ coins , there are $13$ ways to arrange them.

  1. $123$ $[x_1 < x_2,x_2 < x_3,x_3 > x_1]$
  2. $132$ $[x_1 < x_2,x_2 > x_3,x_3 > x_1]$
  3. $213$ $[x_1 > x_2,x_2 < x_3,x_3 > x_1]$
  4. $231$ $[x_1 > x_2,x_2 < x_3,x_3 < x_1]$
  5. $312$ $[x_1 < x_2,x_2 > x_3,x_3 < x_1]$
  6. $321$ $[x_1 > x_2,x_2 > x_3,x_3 < x_1]$
  7. $(12)3$ $[x_1 = x_2,x_2 < x_3,x_3 > x_1]$
  8. $3(12)$ $[x_1 = x_2,x_2 > x_3,x_3 < x_1]$
  9. $1(23)$ $[x_1 < x_2,x_2 = x_3,x_3 > x_1]$
  10. $(23)1$ $[x_1 > x_2,x_2 = x_3,x_3 < x_1]$
  11. $2(13)$ $[x_1 > x_2,x_2 < x_3,x_3 = x_1]$
  12. $(13)2$ $[x_1 < x_2,x_2 > x_3,x_3 = x_1]$
  13. $(123)$ $[x_1 = x_2,x_2 = x_3,x_3 = x_1]$

I thought of thinking of stacks as variables that are equal.And a variable being left/right to another variable corresponding to a varialbe less than/ greater than another variable.So my thought is..

number of ways to arrange $n$ coins = number of distinct inequalities for $n$ variables.(Hope this helps)

$\endgroup$
5
  • $\begingroup$ you need to define the possible inequalities between the n variables, are we only allowing inequalities of the form $x_i ><= x_j$ or can we also have things like $x_i > x_j + x_k$ ? $\endgroup$ Feb 17, 2021 at 5:22
  • $\begingroup$ no , we are not allowing the second case. $\endgroup$ Feb 17, 2021 at 5:31
  • 5
    $\begingroup$ Is this what you are looking for? en.wikipedia.org/wiki/Ordered_Bell_number, more detail at oeis.org/A000670 $\endgroup$ Feb 17, 2021 at 6:09
  • $\begingroup$ Do you count $a<b$ and $b>a$ as distinct inequalities or not ? $\endgroup$
    – user65203
    Feb 17, 2021 at 9:51
  • 1
    $\begingroup$ Your coin analogy is not helpful Why don't you write the inequalities explicitly in the case of three variables ? $\endgroup$
    – user65203
    Feb 17, 2021 at 11:31

2 Answers 2

1
$\begingroup$

As Mike Earnest commented, these are ordered Bell numbers or Fubini numbers, and OEIS A000670 shows many ways to calculate them, though not a closed form.

My preference would be with a recursion, letting $f(n,k)$ be the number of orderings of $n$ variables involving $k$ distinct values. When you introduce the $n$th variable, you can

  • either introduce it to an ordering of $n-1$ variables with $k$ distinct values by matching it to one of the existing distinct values

  • or introduce it to an ordering of $n-1$ variables with $k-1$ distinct values by matching it to one of the $k$ gaps between, before or after the existing distinct values

So $$f(n,k)=k\big(f(n-1,k) + f(n-1,k-1)\big)$$

and you can start with $f(1,1)=1$ and $f(1,k)=0$ for $k\not=1$, or from $f(0,0)=1$ and $f(0,k)=0$ for $k\not=0$.

You then get a table like this

$$\begin{matrix} & k& 0& 1& 2& 3& 4& 5& 6& 7& 8& & \text{Sum}\\ n& & & & & & & & & & & & \\ 0& & 1& 0& 0& 0& 0& 0& 0& 0& 0& & 0\\ 1& & 0& 1& 0& 0& 0& 0& 0& 0& 0& & 1\\ 2& & 0& 1& 2& 0& 0& 0& 0& 0& 0& & 3\\ 3& & 0& 1& 6& 6& 0& 0& 0& 0& 0& & 13\\ 4& & 0& 1& 14& 36& 24& 0& 0& 0& 0& & 75\\ 5& & 0& 1& 30& 150& 240& 120& 0& 0& 0& & 541\\ 6& & 0& 1& 62& 540& 1560& 1800& 720& 0& 0& & 4683\\ 7& & 0& 1& 126& 1806& 8400& 16800& 15120& 5040& 0& & 47293\\ 8& & 0& 1& 254& 5796& 40824& 126000& 191520& 141120& 40320& & 545835\\ \end{matrix}$$

with the final column giving the result you want

$\endgroup$
2
  • $\begingroup$ I have also read that wiki article according to the suggestion of @Mike_Earnest.But I couldn't really understand how ordered bell numbers relate to such a problem (due to my lack of number theory and combinatorics knowledge).I might have to study it more deeply.@Henry thanks for your response. $\endgroup$ Feb 17, 2021 at 13:28
  • $\begingroup$ What you are counting are "weak orderings" so while the Bell numbers count possible equivalence relations or partitions of a set, the ordered Bell numbers also count how these partitions can be ordered $\endgroup$
    – Henry
    Feb 17, 2021 at 13:32
-1
$\begingroup$

To make an inequality, you need two of the variables and one of three operators, so $n (n-1) 3.$ Notice that the order of the variables matters, so you do not divide by two.

$\endgroup$
6
  • $\begingroup$ Then according to you $n=2$ should give $6$ inequalities? $\endgroup$
    – V.G
    Feb 17, 2021 at 5:44
  • $\begingroup$ @LightYagami Yes. $\endgroup$
    – Igor Rivin
    Feb 17, 2021 at 5:45
  • $\begingroup$ If I plug in n=2 , then I will get 6 inequalities. half of the 6 inequalities are copies of the other half. For example , x1 < x2 is the same as x2 > x1. $\endgroup$ Feb 17, 2021 at 5:46
  • $\begingroup$ But clearly according to OP we have only $x<y$, $y<x$ and $x=y$. What are the other three? $\endgroup$
    – V.G
    Feb 17, 2021 at 5:46
  • $\begingroup$ @LightYagami The OP did not say anything about the variables being lexicographically ordered, so what's wrong with $y<x?$ $\endgroup$
    – Igor Rivin
    Feb 17, 2021 at 14:49

You must log in to answer this question.

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