Número de Dedekind
# Número de Dedekind

En combinatoria, los números de Dedekind son una sucesión entera de rápido crecimiento cuyo nombre se dio póstumamente en honor a Richard Dedekind, quien las definió por primera vez en 1897. El número de Dedekind M(n) corresponde, equivalentemente, a lo siguiente:

* El número de funciones booleanas monótonas de n variables.
* El número de anticadenas de subconjuntos de un conjunto de n elementos.
* El número de elementos en un retículo distributivo libre con n generadores.
* El número de juegos simples irredundantes definibles sobre n jugadores.
* El número de hipergrafos minimales completos, definibles sobre un conjunto base de cardinalidad n.
* El número de familias de Sperner sobre un conjunto de n elementos.

Encontrar una expresión matemática de forma cerrada para M(n) se conoce como el Problema de Dedekind. Aunque existen aproximaciones asintóticas que estiman este número, y una expresión exacta en forma de sumatoria, el cómputo de M(n) sigue siendo ineficiente, y sus valores exactos sólo se conocen para valores n ≤ 9.

## Ejemplo

Para n = 2, existen seis funciones booleanas monótonas y seis anticadenas de subconjuntos del conjunto de dos elementos {x,y}:

* La función f(x,y) = falso, que ignora sus valores de entrada y siempre retorna falso, corresponde a la anticadena vacía Ø.
* La conjunción lógica f(x,y) = x ∧ y corresponde a la anticadena { {x,y} }, que contiene al conjunto {x,y}.
* La función f(x,y) = x, que ignora su segundo argumento y retorna el primero, corresponde a la anticadena { {x} } que contiene al conjunto {x}.
* La función f(x,y) = y, que ignora su primer argumento y retorna el segundo, corresponde a la anticadena { {y} } que contiene al conjunto {y}.
* La disyunción lógica f(x,y) = x ∨ y corresponde a la anticadena { {x}, {y} }, que contiene a los dos conjuntos {x} e {y}.
* La función f(x,y) = verdadero, que ignora sus valores de entrada y siempre retorna verdadero, corresponde a la anticadena {Ø} que contiene sólo al conjunto vacío.

## Valores conocidos

Los valores exactos de los números de Dedekind se conocen para 0 ≤ n ≤ 9. La siguiente tabla muestra tales números, junto con el año y la publicación en que fueron calculados:

| n | Número M(n) | Año |
| - | - | - |
| 0 | 2 | 1940 |
| 1 | 3 | 1940 |
| 2 | 6 | 1940 |
| 3 | 20 | 1940 |
| 4 | 168 | 1940 |
| 5 | 7 581 | 1940 |
| 6 | 7 828 354 $\approx 7.83\times 10^{6}$ | 1946 |
| 7 | 2 414 682 040 998 $\approx 2.41\times 10^{12}$ | 1965 y 1976 |
| 8 | 56 130 437 228 687 557 907 788 $\approx 5.61\times 10^{22}$ | 1991 |
| 9 | 286 386 577 668 298 411 128 469 151 667 598 498 812 366 $\approx 2.86\times 10^{41}$ | 2023 |
| (sucesión A000372 en OEIS) |||

Si n es un número par, entonces M(n) también debería serlo. El cálculo de M(5) = 7581 fue el contraejemplo que desaprobó una conjetura realizada por Garrett Birkhoff que decía que M(n) es siempre divisible por (2n - 1)(2n - 2).

## Fórmula con sumatoria

Andrzej Kisielewicz en 1988 demostró la siguiente fórmula para los números de Dedekind:

    $M(n)=\sum _{k=1}^{2^{2^{n}}}\prod _{j=1}^{2^{n}-1}\prod _{i=0}^{j-1}\left(1-b_{i}^{k}b_{k}^{k}\prod _{m=0}^{\log _{2}i}(1-b_{m}^{i}+b_{m}^{i}b_{m}^{j})\right),$

donde

    $b_{i}^{k}=\left\lfloor {\frac {k}{2^{i}}}\right\rfloor -2\left\lfloor {\frac {k}{2^{i+1}}}\right\rfloor .$

Sin embargo, esta fórmula no es útil para el cómputo de los valores de M(n) para n grandes, debido al gran número de términos en la sumatoria.

## Asíntotas

El logaritmo de los números de Dedekind puede ser estimado exactamente mediante las cotas

    ${n \choose \lfloor n/2\rfloor }\leq \log _{2}M(n)\leq {n \choose \lfloor n/2\rfloor }\left(1+O\left({\frac {\log n}{n}}\right)\right).$

La inecuación de la izquierda cuenta el número de anticadenas en que cada conjunto tiene exactamente $\lfloor n/2\rfloor$ elementos, y la inecuación derecha fue demostrada por Kleitman y Markowsky.

A. D. Korshunov encontró en 1981 una estimación aún mejor:

    $M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor }\exp a(n)$

para n par, y

    $M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor }\exp(b(n)+c(n))$

para n impar, donde

    $a(n)={n \choose n/2-1}(2^{-n/2}+n^{2}2^{-n-5}-n2^{-n-4}),$
    $b(n)={n \choose (n-3)/2}(2^{-(n+3)/2}-n^{2}2^{-n-6}-n2^{-n+3}),$

y

    $c(n)={n \choose (n-1)/2}(2^{-(n+1)/2}+n^{2}2^{-n-4}).$

La principal idea detrás de estas estimaciones, es que en la mayoría de las anticadenas, todos los conjuntos tienen tamaños muy cercanos a n/2. Para n = 2, 4, 6 y 8, la fórmula de Korshunov provee una estimación imprecisa por un factor de 9.8%, 10.2%, 4.1%, y -3.3%, respectivamente.

