How many different functions we have by only use of $\min$ and $\max$?

Question

We can making many functions of three variable by only use and combining of $\min$ and $\max$ functions. But many of them are not different , like :
$$\min(x,y,z)=\min(x,\min(y,z)),\quad\min(x,\max(x,y)) = \min(x,x) = \max(x,x)$$

How many different functions $\mathbb R ^3 \rightarrow \mathbb R$ of this form we have?

The upper bound of numbers of this functions is $3^{3!}$ . Because there are only $3!$ states for $x , y , z$ like: $ x < y < z$ and $ x < z < y$ and ... and each state gives one of the values of $\{x,y,z\}$ .
And my second question is :

How many different functions $\mathbb R ^n \rightarrow \mathbb R$ of this form we have ?

Answer 1

I think that there are $18$ functions of $3$ variables.

Those functions are $x$, $y$, $z$,

$\max(x, y)$, $\max(x, z)$, $\max(y, z)$, $\min(x, y)$, $\min(x, z)$, $\min(y, z)$,

$\max(x, \max(y, z))$, $\min(x, \min(y, z))$,

$\max(x, \min(y, z))$, $\max(y, \min(x, z))$, $\max(z, \min(x, y))$,

$\min(x, \max(y, z))$, $\min(y, \max(x, z))$, $\min(z, \max(x, y))$,

and $\max(\min(x, y), \min(z, \max(x, y)))$.

This last function simply returns the middle value among $x$, $y$, $z$.

I used Mathematica. I built a list of "basic" functions, i.e.

{x, y, z, Min[x, y], Min[x, z], Min[y, z], Max[x, y], Max[x, z], Max[y, z]} 

Then I combined previous lists of function by taking Min[a,b] and Max[a,b] where a and by were elements of previous list. I deleted duplicated considering the output of the functions on the $6$ permutations of $\{1,2,3\}$.

I stopped (quite soon, actually) when new functions where not arising anymore.

ADDENDUM: I run the same routine for $4$ variables and I got $166$ functions.

Now, searching $4,18,166$ on OEIS we got Sequence A007153, i.e.,

Dedekind numbers: number of monotone Boolean functions or antichains of subsets of an n-set containing at least one nonempty set.

The next terms escalate quickly:

$7579$, $7828352$, $2414682040996$, $56130437228687557907786$

I'm not awake enough (be honest: smart enough) to confirm or deny the connection between this problem and Dedekind numbers, but I see some potential connections.

Answer 2

If we assume we use only binary operators, counting the different functions of $n$ (fixed) variables can be decomposed into 3 steps:

For example, an expression like this one :

$$max(min(a,c),min(b,max(e, max(d f)))) \ \ (1)$$

can be decomposed into

• (a) the choice of a sequence of n-1 coupled parentheses $((a,c) (b (e (d f))))$ (numbered by Catalan number $C_n$: https://en.wikipedia.org/wiki/Catalan_number )

• (b) then the choice of a permutation of the $n$ letters $a,b,c,d,e,f \cdots$ (there are $n!$ of them)

• (c) then an attribution of $n-1$ operators to the different coupled parentheses. ($2^{n-1}$ choices if one only considers the 2 operators min and max).

The resulting number is the product $C_n n! 2^{n-1}$.

Edit: of course, this number is the number of formal expressions such as (1). There are much less different associated functions ; for example, regarding the values they can take $min(a,min(b,c))$ is the same as $min(b,min(a,c))$.

Answer 3

Thanks to Giovanni Resta answer I will prove that $M(n)-2$ different functions of $n$ variable exist; Where $M(n)$ is $n$th number of Dedekind numbers.
At first it's simple to check :

$\max(x,\min(y,z))=\min(\max(x,y),\max(x,z))$ $\min(x,\max(y,z))=\max(\min(x,y),\min(x,z))$

Now we can consider $\max(x,y)$ as $x \vee y$ and $\min(x,y)$ as $x \wedge y$ and then above identities convert to below familiar identities (distributive laws) :

$x \vee (y \wedge z) = (x \vee y) \wedge (x \vee z)$
$x \wedge(y \vee z) = (x \wedge y) \vee (x \wedge z)$

Now number of OP functions with $n$ variable is equal to number of Free distributive lattice with $n$ generators without empty joins and empty meets.

For example for $n=3$ from https://oeis.org/A007153 we have :
a
b
c
a or b
a or c
b or c
a or b or c
a and b
a and c
b and c
a and (b or c)
b and (a or c)
c and (a or b)
(a or b) and (a or c)
(b or a) and (b or c)
(c or a) and (c or b)
a and b and c
(a or b) and (a or c) and (b or c)