|
Сколько функций от переменных x1,x2,...,xn содержит множество L∪T0 ∪T1? задан 29 Май '17 16:11 
bycha601 |
|
В $%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
|