# Number of possible inequalities for $n$ variables.

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

(i) $$x
(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)

• 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$ ? Feb 17, 2021 at 5:22
• no , we are not allowing the second case. Feb 17, 2021 at 5:31
• Is this what you are looking for? en.wikipedia.org/wiki/Ordered_Bell_number, more detail at oeis.org/A000670 Feb 17, 2021 at 6:09
• Do you count $a<b$ and $b>a$ as distinct inequalities or not ?
– user65203
Feb 17, 2021 at 9:51
• Your coin analogy is not helpful Why don't you write the inequalities explicitly in the case of three variables ?
– user65203
Feb 17, 2021 at 11:31

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

• 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. Feb 17, 2021 at 13:28
• 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 Feb 17, 2021 at 13:32

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.

• Then according to you $n=2$ should give $6$ inequalities?
– V.G
Feb 17, 2021 at 5:44
• @LightYagami Yes. Feb 17, 2021 at 5:45
• 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. Feb 17, 2021 at 5:46
• But clearly according to OP we have only $x<y$, $y<x$ and $x=y$. What are the other three?
– V.G
Feb 17, 2021 at 5:46
• @LightYagami The OP did not say anything about the variables being lexicographically ordered, so what's wrong with $y<x?$ Feb 17, 2021 at 14:49