Количество монотонных булевых функций

[Dreimon]

Можете посоветовать литературу по данному вопросу? Интересует асимптотика, и вообще материал по данному вопросу. Очень тяжело что-либо найти по этой теме.

[Vince Diesel]

На английском полно ссылок. Сама последовательность A014466.
Асимптотика:

Цитата:

In 1981, Korshunov derived asymptotically matching upper and lower
bounds on M(n), which means the ratio of the bounds approaches 1 as
n increases. These bounds give the following approximate expression
for M(n) if n is even:
_ _
C(n) | / -n/2 2 -n-5 -n-4 \ |
M(n) ~ 2 exp| c(n) ( 2 + n 2 - n 2 ) |
|_ \ / _|

where C(n) is the middle binomial coefficient again, and c(n) is the
neighboring binomial coefficient. For example, the 6th row of binomial
coefficients is 1 6 15 20 15 6 1, so we have C(6)=20 and c(6)=15. A
similar expression applies for odd n. This formula gives the
approximate values listed below

n M(n) Korshunov's approximation
--- ----------------------- ---------------------------
2 6 6.59
4 168 185.19
6 7828354 8151600.62
8 56130437228687557907788 5.4279E+22