¿Cuántos diferentes funciones tenemos por sólo usan de $\min$ y $\max$?

Question

Podemos hacer muchas de las funciones de tres variables sólo por el uso y la combinación de $\min$ $\max$ funciones. Pero muchos de ellos no son diferentes , como :
$$\min(x,y,z)=\min(x,\min(y,z)),\quad\min(x,\max(x,y)) = \min(x,x) = \max(x,x)$$

Cómo muchas funciones diferentes $\mathbb R ^3 \rightarrow \mathbb R$ de esta forma tenemos?

El límite superior de los números de esta función es $3^{3!}$ . Porque no sólo se $3!$ estados para $x , y , z$ como: $ x < y < z$ $ x < z < y$ ... y que cada estado le da a uno de los valores de $\{x,y,z\}$ .
Y mi segunda pregunta es :

Cómo muchas funciones diferentes $\mathbb R ^n \rightarrow \mathbb R$ de esta forma tenemos ?

Answer 1

Creo que hay $18$ funciones de $3$ variables.

Esas funciones son $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))$,

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

Esta última función simplemente devuelve el valor medio entre $x$, $y$, $z$.

He utilizado Mathematica. He elaborado una lista de los "básicos" de las funciones, es decir,

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

A continuación, he combinado las listas anteriores de la función de toma Min[a,b] y Max[a,b] donde a y por elementos de la lista anterior. He eliminado duplicado teniendo en cuenta la salida de las funciones de la $6$ permutaciones de $\{1,2,3\}$.

Me detuve (muy pronto, en realidad) cuando las nuevas funciones, cuando no surjan más.

ADDENDUM: Puedo ejecutar la misma rutina para $4$ variables y conseguí $166$ funciones.

Ahora, la búsqueda de $4,18,166$ en OEIS tenemos Secuencia A007153, es decir,

Dedekind números: número de monotonía funciones Booleanas o antichains de subconjuntos de un n-conjunto que contiene al menos un conjunto no vacío.

El próximo términos escalar rápidamente:

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

Yo no soy lo suficientemente despierto (ser honesto: lo suficientemente inteligente) para confirmar o denegar la conexión entre este problema y Dedekind números, pero veo que algunos posibles conexiones.

Answer 2

Gracias a Giovanni Resta respuesta voy a probar que $M(n)-2$ diferentes funciones de $n$ variable existe; Donde $M(n)$ $n$th número de Dedekind números.
Al principio es fácil de comprobar :

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

Ahora podemos considerar $\max(x,y)$ $x \vee y$ $\min(x,y)$ $x \wedge y$ y, a continuación, por encima de las identidades de convertir a continuación familiares identidades (distributiva, leyes) :

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

Ahora el número de OP funciones con $n$ variable es igual al número de Libre distribución de celosía con $n$ generadores sin vacío une y vacía cumple.

Por ejemplo, para $n=3$ a partir de https://oeis.org/A007153 tenemos :
un
b
c
a o b
a o c
b o c
a o b o c
a y b
a y c
b y c
una y (b o c)
b y (a o c)
c y (a o b)
(a o b) y (a, b, c)
(b o a) y (b o c)
(c, o) y (c o b)
a y b y c
(a o b) y (a, b, c) y (b o c)

Answer 3

Si asumimos que sólo utilizamos operadores binarios, contando las diferentes funciones de $n$ (fija) de las variables pueden ser descompuestos en 3 pasos:

Por ejemplo, una expresión como esta :

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

se puede descomponer en

• (a) la elección de una secuencia de n-1, junto a la de los paréntesis $((a,c) (b (e (d f))))$ (numeradas por los catalanes número $C_n$: https://en.wikipedia.org/wiki/Catalan_number )

• (b) a continuación, la elección de una permutación de las $n$ cartas de $a,b,c,d,e,f \cdots$ (hay $n!$ de ellos)

• (c) a continuación, una atribución de $n-1$ a los operadores de los diferentes junto paréntesis. ($2^{n-1}$ opciones si sólo se considera el 2 operadores min y max).

El número resultante es el producto de $C_n n! 2^{n-1}$.

Edit: por supuesto, este número es el número de expresiones formales tales como (1). Hay mucho menos para diferentes funciones asociadas ; por ejemplo, en relación con los valores que pueden tomar $min(a,min(b,c))$ es lo mismo que $min(b,min(a,c))$.