title: Número de Dedekind
text: # 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.
  
  