Соответствия, сравнения, количества
Ошибка.
Попробуйте повторить позже
состоящее из 
элементов. Сколькими способами можно выбрать в 
два подмножества 
и 
так,
чтобы
и 
не пересекались;
содержалось бы в множестве 
Подсказка 1, а
Попробуем сначала выбрать множество, равное объединению множеств A и B, а из него выберем подмножество A. Как тогда восстановить множество B?
Подсказка 2, а
Верно! Множество B однозначно восстанавливается, как разность двух множеств. Чтобы найти количество способов выбрать A, зафиксируем d — мощность объединения D множеств A и B. Количество множеств D находится легко, как число сочетаний. А как найти количество множеств A?
Подсказка 3, а
Верно! Это просто количество различных подмножеств множества D. Теперь необходимо просуммировать получившееся выражения для d = 0, ..., n. Чему равна эта сумма?
Подсказка 1, б
Когда мы считаем количество подмножеств у какого-нибудь множества, то для каждого элемента выбираем одно из двух состояний: состоит он в множестве или нет. Можно ли сделать что-нибудь похожее для нашей задачи?
Подсказка 2, б
Верно! Всего есть три состояния: элемент содержится в множествах A и B; содержится в B, но не в A и не входит ни в A, ни в B. Каково тогда способов выбрать множества A и B?
(a) Будем выбирать подмножества 
и 
следующим образом: сначала выберем множество 
мощности 
и
выберем из него подмножество 
Тогда 
Для каждого 
существует 
способов выбрать множество 
Для каждого выбранного 
существует 
способов выбрать
множество 
а множдество 
задастся однозначно. Получается, что для каждого 
мы имеем 
случаев.
Просуммируем по всем 
и получим:
(b) Этот пункт можно решить аналогично предыдущему (сказав, что достаточно выбрать непересекающиеся множества 
и 
но мы сделаем немного иначе.
Для каждого элемента 
имеется 
состояния: 
не лежит ни в 
ни в 
лежит в 
но не в 
лежит и в
и в 
Тогда, поскольку определение состояния каждого элемента однозначно задает нам 
и 
и наоборот, то мы получаем, что
всего случаев будет 
оба пункта
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
