Тишинуша Гамимеря (spamsink) wrote,
Тишинуша Гамимеря
spamsink

Category:

Бывают странные сближенья



Понадобилось мне по работе подсчитать, сколько бывает разных булевских функций от N переменных, описываемых деревом из узлов типа AND с произвольными инверсиями на узлах. Навскидку-то верхнюю границу оценить просто: берем число Каталана от N-1 (количество узлов в графе), да умножаем на 22N-1 (количество возможных вариантов инверсий). Скажем, для N=6 получится 42*2048 = 86016. Но это сильно верхняя граница, поскольку не учитывает симметричность и ассоциативность операции AND.

Написал программку (около 80 строк вышло, зато легко читается), запустил - для N=6 вышло 25216 (таки существенно меньше, чем 86016, что приятно), для N=5 - 2880.

Ну, раз такое дело, глядь "2880,25216" в oeis.org, а это уникальный результат, описываемый как "число графов из n узлов на круге без пересечения дуг" или "число путей по квадратной решетке, остающихся строго ниже главной диагонали". Кто бы мог подумать.

This entry was originally posted at https://spamsink.dreamwidth.org/1073253.html. Please comment there using OpenID.
Tags: work
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 1 comment