Число n-местных монотонных булевых функций

[В.П.]

Коровьев писал(а):

luitzen писал(а):

Обозначим число монотонных функций от n переменных через $\psi(n)$. Помню, что

$$2^ {C^{[n/2]}_{\;\;\;n}}<\psi(n) < 3^ {C^{[n/2]}_{\;\;\;n}}$$

, где $[\alpha]$ — целая часть числа $\alpha$. Проблема нерешённая, довольно престижная и носит имя Дедекинда.

Вроде бы в каком-то из «Кибернетических сборников» много боролись за улучшение верхней оценки.

Завтра постараюсь подыскать ссылки или вспомнить побольше

Предлагаю гнать вопрошающего в шею. Сам он интересоваться таким вопросом не может, преподаватель ему его тоже задать не мог. Следовательно, издевается.

Да, именно эта оценка сверху и с низу приведена у Гаврилова в "Сборнике задач по дискретной математике"
Жаль только, что решение не приведено, дескать, докажите, а как - не знаю. Решения-то не приведено.

Асимптотика числа монотонных этой величины была получена А.Д.Коршуновым примерно 25 лет назад. Подробности можно прочитать в его недавнем обзоре о монотонных булевых функциях в "Успехах мат. наук". Соавтор Гаврилова по известному сборнику задач А.А.Сапоженко несколько лет назад в "Математических вопросах кибернетики" опубликовал новое более короткое и ясное доказательство этой асимптотики (имелись сомнения в корректности предыдущего доказательства). Вопрос о точной формуле для числа монотонных функций от n-переменных смысла не имеет, так как нет ни малейших оснований предполагать, что эта функция выражается как композиция элементарых.