Найти число функций из $%P_2(n)$%, существенно зависящих от переменной $%x_1$%, степень AНФ которых равна 2.

задан 1 Июн '15 15:48

изменен 1 Июн '15 16:07

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
1

Функции, о которых здесь идёт речь, представимы полиномом Жегалкина степени не выше двух, то есть $%f(x_1,\ldots,x_n)=a+\sum\limits_{i=1}^na_ix_i+\sum\limits_{i < j}^na_{ij}x_ix_j$%. Коэффициентов у такого многочлена имеется $%1+n+C_n^2=\frac{n^2+n+2}2$%. Соответственно, функций такого вида имеется $%2^\frac{n^2+n+2}2$%. Нам подходят не все из них, поэтому надо учесть ограничения.

Прежде всего, нам не подходят функции, не зависящие существенно от $%x_1$%. Поэтому $%n\ge1$%, и надо вычесть количество функций от $%n-1$% переменной, то есть заменить в формуле $%n$% на $%n-1$%, получая $%2^\frac{n^2-n+2}2$%. Помимо этого, надо вычесть число функций, для которых у полинома Жегалкина отсутствуют члены второй степени. Такие полиномы имеют вид $%f(x_1,\ldots,x_n)=a+\sum\limits_{i=1}^na_ix_i$%, и их количество равно $%2^{n+1}$%.

При этом надо учесть, что некоторые полиномы мы учитывали дважды. Это все полиномы не выше первой степени, не зависящие от $%x_1$%. Их количество равно $%2^n$%, и эту величину надо прибавить. Итоговый ответ будет такой: $%2^\frac{n^2+n+2}2-2^\frac{n^2-n+2}2-2^n$%.

ссылка

отвечен 2 Июн '15 2:36

Оказался быстрее меня на несколько минут)

(2 Июн '15 2:40) sleepless_study

@sleepless_study: исправлять ничего не надо, потому что мы вычитали $%2^{n+1}$%, а потом прибавляли $%2^n$%. Это значит, что в итоге вычиталось $%2^n$%.

(2 Июн '15 2:58) falcao

@falcao догадалась и тут же удалила

(2 Июн '15 3:02) sleepless_study
10|600 символов нужно символов осталось
0

Мне кажется, что тут надо от числа всех функций степени 2: $%2^n \cdot 2^{С_n^2}$% отнять функции в полином которых не входит $%x_1$%: $%2^n \cdot (2^{C_{n-1}^2}-1)$%.

ссылка

отвечен 2 Июн '15 2:40

изменен 2 Июн '15 22:45

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

@sleepless_study: тут учитывается ещё условие, что степень равна 2, то есть хотя бы один квадратичный член должен присутствовать.

В показателе степени двойки должно быть $%1+n+C_n^2$%, так как есть ещё свободный член.

(2 Июн '15 2:45) falcao

@falcao идея была в том, чтобы сразу учесть, что степень 2 должна сохраниться, поэтому $%2^n2^{С_n^2}$%: $%2\cdot 2^n \cdot (2 \cdot 2\cdot2 \cdot ... \cdot 1)$%, где за единицу отвечает коэффициент стоящий перед одним из квадратных членов, но видимо тут я погорячилась.

(2 Июн '15 3:12) sleepless_study
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,866

задан
1 Июн '15 15:48

показан
958 раз

обновлен
2 Июн '15 3:12

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru