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: thumb|derecha|350px|Gráfica de los números de Dedekind hasta n = 8, donde se aprecia el crecimiento exponencial de la sucesión.

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 1946. 7 2 414 682 040 998 1965. Citado por Wiedemann, 1991. y 1976. 8 56 130 437 228 687 557 907 788 1991 9 286 386 577 668 298 411 128 469 151 667 598 498 812 366 2023

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:

donde

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

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

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

para n par, y

para n impar, donde

y

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..

Referencias

Categoría:Sucesiones de números enteros Categoría:Lógica matemática Categoría:Teoría de retículos Categoría:Teoría de hipergrafos Categoría:Juegos cooperativos Dedekind Categoría:Combinatoria enumerativa