задача по дискре

zzzXAXAXAzzz

найти число монотонных функций от n переменных, принимающих 1 на 8 наборах. Сколько всего монотонных функций?

Trewester

точное число неизвестно. есть только оценки.
нарисуй все наборы в виде огурца, дальше станет ясно, сколько их

kolyan

можно воспользоваться тем, что СДНФ не содержит отрицаний, но все равно для произвольного n точного числа не получить

zzzXAXAXAzzz

точное число неизвестно. есть только оценки.

за количество монотонных функций согласен, нашел только оценки, а вот количество монотонных с 1 на восьмью наборах оценить можно числом, зависящем от n.
у меня такие соображение. Расписать СДНФ, там будет 8 элементов. Теперь надо воспользоваться монотонностью функции, т.е. как-то "сократить" количество наборов, на которых она 1. На наборе 1....1 она точно 1.
Далее, скорее всего она должна принимать 1 на наборах, в которых на i-ом месте 0, а остальные 1... Количество таких наборов можно подсчитать через биномиальный коэффициент. Но так ли это? Не будет ли проблем со сравнимостью?
Есть еще одна проблема, подсчитать это для 3<=n<=8. Тут такая теория уже не прокатит... Надо усложнять...

griz_a

Далее, скорее всего она должна принимать 1 на наборах, в которых на i-ом месте 0, а остальные 1... Количество таких наборов можно подсчитать через биномиальный коэффициент. Но так ли это? Не будет ли проблем со сравнимостью?

А это почему?
Какая-нибудь
0 0 1 ...1 = 1
0 1......1 = 1
1 0 1....1 = 1
1 1 1....1 = 1
Ну и еще на четырех наборах так же. У нее не может быть более 000 в единчном наборе, если я правильно понял условие.
С тремя нулями таких функций C^{3}_{n}
Если там нет наборов с 1 на трех нулях, то
а) один набор с двумя нулями и 4 с одним
б) два набора с двумя нулями.
Первое выбирается С^{6}_{n}*C^{2}_{6}
Второе C^{4}_{n}*3

CokpaT

ну так что, что-нибудь получилось?
Число монотонных функций от n переменных не посчитать. И не оценить (во всяком случае, вряд ли это попросят от студента на экзамене).
У меня, вот, такие соображения:
Если монотонная функция принимает значение 1 на некотором наборе, то она принимает значение 1 на всех бОльших наборах.
Нас интересуют функции, принимающие значение 1 на 8 наборах. Будем искать такие функции сл. обр.: задаем значение 1 на каких-то наборах (наборах типа 1 и в силу монотонности значение 1 обязательно принимается еще на каких-то наборах (наборах типа 2).
Будем считать, что n "достаточно большое".
а) Наборы типа 1 обязательно должны иметь не более трех нулей.
б) если набор типа 1 имеет 3 нуля, то наборов типа 2 ровно 7 штук. Т.е. функция определяется некоторым набором с 3 нулями. Т.обр. получаем слагаемое "число сочетаний из n по 3"
в) Наборы типа 1 имеют от 1 до 2 нулей. Тогда надо подумать, как отследить, как пересекаются множества наборов типа 2 в предпоследнем слое.
г) Все наборы типа 1 имеют ровно 1 нуль. Тогда функция задается семью наборами с 1 нулем, т.е. добавляется слагаемое "число сочетаний из n по 7".
Вот как-то так.

CokpaT

а) один набор с двумя нулями и 4 с одним
б) два набора с двумя нулями.
Первое выбирается С^{6}_{n}*C^{2}_{6}
Второе C^{4}_{n}*3
во-первых, есть еще в) семь наборов с 1 нулем.
во-вторых, два набора с двумя нулями не дают 8 наборов.

griz_a

Понял, сорри, наспех вчера написал %)
Причем был уверен, что про 7 по 1 я написал
Оставить комментарий
Имя или ник:
Комментарий: