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

С другой стороны, можно сначала

С другой стороны, можно сначала

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

Найдем количество подмножеств, попавших в класс А1. Все такие подмножества содержат числа {1,..., 1} и еще к — I чисел из множе­ства {I + 2,..., п + к + 1}. Следовательно, всего таких подмножеств (П + \ . Отсюда следует доказываемое равенство.

б)  Найдем двумя способами количество подмножеств множества {1,2,..., п} с одним отмеченным элементом. С одной стороны, мы можем сначала выбрать подмножество, а затем в нем выбирать от­меченный элемент. Если мы выбрали к-элементное подмножество, то отмеченный элемент в нем можно выбрать к способами. Следова­тельно, число способов выбрать С-элементное подмножество с одним отмеченным элементом равно к^к). Суммируя по всем к, получаем левую часть доказываемого равенства.

С другой стороны, можно сначала выбрать отмеченный элемент, а потом выбирать содержащее его множество. Отмеченный элемент можно выбрать п способами. При любом выборе отмеченного элемен- гл      та подмножеств, содержащих его, будет ровно 2"-1. Следовательно,                                                  _гх_

искомое число способов равно правой части доказываемого равен­ства.

в) Найдем двумя способами количество способов в п-элементном множестве выбрать непересекающиеся к-элементное и (т — к)-эле- ментное подмножества. С одной стороны, мы можем выбрать сначала первое подмножество, а потом из оставшихся элементов выбрать второе подмножество. При этом способе получаем, что искомое число равно левой части доказываемого равенства.

С другой стороны, можно сначала выбрать объединение этих подмножеств, а потом из элементов объединения выбрать первое множество. При этом способе получаем, что искомое число равно правой части доказываемого равенства.