дискретная-математика - Неравенство о количестве монотонных функций

Будем доказывать неравенство в виде $%|M_{n+2}|\le|M_n|^22^{2^n}$% при $%n\ge0$%. Пусть $%f(X,x_{n+1},x_{n+2})$% -- монотонная функция от $%n+2$% переменных, где $%X$% есть сокращённое обозначение для последовательности $%x_1,\ldots,x_n$%. Фиксация значений любых переменных даёт монотонную функцию. Тем самым, функции $%f(X,0,1)$% и $%f(X,1,0)$% монотонны, и каждая из них может принимать не более $%|M_n|$% значений. Пара таких функций принимает не более $%|M_n|^2$% значений.

Из монотонности функции $%f$% следуют неравенства $%f(X,0,0)\le f(X,0,1)\le f(X,1,1)$%. Аналогичные неравенства верны и для случая $%f(X,1,0)$%, но их мы привлекать не будем.

При отсутствии таких неравенств, значения для $%f(X,0,0)$% и $%f(X,1,1)$% выбираются при каждом фиксированном наборе $%X$% четырьмя способами. Покажем, что в нашей ситуации способов не более двух. Действительно, если $%f(X,0,1)=0$%, то $%f(X,0,0)=0$% определяется однозначно, а $%f(X,1,1)$% может принимать два значения. А если $%f(X,0,1)=1$%, то всё наоборот: $%f(X,1,1)=1$% определяется однозначно, а $%f(X,0,0)$% может принимать два значения.

Таким образом, для каждого из $%2^n$% наборов вида $%X$% мы имеем два способа задания значений $%f(X,0,0)$% и $%f(X,1,1)$%. Всего получается не более $%2^{2^n}$% способов задать эти значения по всем наборам. Полученная информация однозначно задаёт $%f$%. Перемножая две величины по правилу произведения, имеем верхнюю оценку в неравенстве.