Сколько функций от переменных x1,x2,...,xn содержит множество L∪T0 ∪T1?

задан 29 Май '17 16:11

изменен 29 Май '17 18:26

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

В $%L$% $%2^{n+1}$% функций, в $%T_0$% и в $%T_1$% по $%2^{2^n-1}$% функций. Каждая линейная функция имеет вид $%c_0+c_1x_1+\cdots+c_nx_n,$% чтобы она сохраняла 0, должно быть $%c_0=0,$% что дает $%2^n$% функций, чтобы она сохраняла 1,должно выполняться условие $%c_0+c_1+\cdots+c_n=1.$% Поэтому первые $% n$% констант можно выбрать произвольно, что дает $%2^{n}$% способов, а последняя константа считается автоматически. Функций, которые сохраняют и 0 и 1, $%2^{2^n-2}.$% Чтобы линейная функция сохраняла 0 и 1, должны одновременно выполняться условия $%c_0=0, c_1+\cdots+c_n=1.$% Поэтому первые $% n-1$% констант можно выбрать произвольно, что дает $%2^{n-1}$% способов, а последняя константа считается автоматически. Применяя формулу включений-исключений, получаем ответ: $%2^{n+1}+2^{2^n}-2^{n+1}-2^{2^n-2}+2^{n-1}=3\cdot2^{2^n-2}+2^{n-1}$% способов.

ссылка

отвечен 29 Май '17 21:09

Можно ещё заметить, что данная формула верна при всех n>=1, а при n=0 отдельно проверяется, что она даёт верный результат (две константы).

(29 Май '17 22:44) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×4,521
×3,701
×160

задан
29 Май '17 16:11

показан
898 раз

обновлен
29 Май '17 22:44

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

по почте:

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

по RSS:

Ответы

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

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