Таблицы Брадиса

Следовательно, подмножеств из четного числа

Следовательно, подмножеств из четного числа

Элементы математики в задачах - Г. А. Мерзон

б) Перенесем слагаемые со знаком «-» в правую часть равенства:

(п Т + (п Т+••• = (п Т + (п т+•

Заметим, что в левой части равенства стоит число подмножеств п- элементного множества, состоящих из четного числа элементов, а в правой — из нечетного. Таким образом, в задаче требуется доказать, что количество подмножеств, состоящих из четного числа элемен­тов, равно количеству подмножеств, состоящих из нечетного числа элементов. Фиксируем какой-то элемент а. Поставим в соответствие множествам, не содержащим этот элемент, их объединение с множе­ством {а}, а множествам, содержащим этот элемент, — их разность с {а}. Заметим, что при этом каждому подмножеству из четного числа элементов поставлено в соответствие подмножество из нечет­ного числа элементов, и наоборот. При этом разным подмножествам поставлены в соответствие разные. Следовательно, подмножеств из четного числа элементов столько же, сколько из нечетного.

&   Постройте явно это отображение для множества всех подмно­жеств множества из трех элементов.

п!

.кУ к!(п - к)!

Указание. Найдите сначала число упорядоченных к-элементных под-

множеств -элементного множества.

Решение. Найдем сначала число способов выбрать упорядоченный к-элементный набор из п-элементного множества. Первый эле­мент можно выбрать способами; для каждого из этих способов

существует (п - 1) способ выбора второго элемента (так как выбранный первым элемент уже выбирать нельзя); для каждого выбора первых двух элементов существует ровно (п - 2) способа выбрать третий и т. д. Следовательно, способов такого выбора ровно п{п — 1)... (гг — Тс + 1) = , ГС'. Осталось заметить, что из каждого