Бывают странные сближенья - Общество дровосеков Бердичева по изучению Мишны

03:08 pm - Бывают странные сближенья

Понадобилось мне по работе подсчитать, сколько бывает разных булевских функций от N переменных, описываемых деревом из узлов типа AND с произвольными инверсиями на узлах. Навскидку-то верхнюю границу оценить просто: берем число Каталана от N-1 (количество узлов в графе), да умножаем на 2^2N-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.