Обозначим k-ый элементарный симметрический многочлен от n переменных через Qk(x1,...,xn). Чему равно Qk(1,2,4,...,2^{n-1})?
Некая туманная подсказка: это число связано с числом плоскостей размерности k в конечном векторном пространстве размерности n над полем из двух элементов. У меня формула получилась при помощи подсчета функции Мёбиуса линейного матроида, ассоциированного с этим векторным пространством, двумя разными способами, однако тут есть и другое решение. Искомые числа, назовем их a_{k,n} можно естественным образом записать в треугольник, типа треугольника Паскаля, причем можно вывести правило, позволяющее из двух вышестоящих получить следующее (как в случае с биномиальными коэффициентами), однако это правило выглядит несколько сложнее. Такие правила называются грамматиками Дика. Похожее правило возникает и при подсчете k-мерных плоскостей в n-мерном бинарном пространстве.
Комментариев нет:
Отправить комментарий