Число Дедекинда
- Числа Дедекинда — быстро растущая последовательность целых чисел, определенных Ричардом Дедекиндом в 1897 году.
- Число Дедекинда M(n) представляет собой число монотонных булевых функций от n переменных.
- Эквивалентно, M(n) является числом антицепей подмножеств множества из n элементов и числом элементов в свободной дистрибутивной решетке с n образующими.
- Известны точные асимптотические оценки M(n) и точное выражение в виде суммирования.
- Задача Дедекинда по вычислению значений M(n) остается сложной, точные значения M(n) найдены только для n ≤ 9.
- Числа Дедекинда подсчитывают элементы в свободных дистрибутивных решетках и на единицу больше, чем число абстрактных симплициальных комплексов на множестве из n элементов.
- Точные значения чисел Дедекинда известны при 0 ≤ n ≤ 9, и для больших n формула суммирования бесполезна из-за большого количества членов в суммировании.
- Логарифм чисел Дедекинда может быть точно оценен с помощью различных оценок.
Полный текст статьи: