![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Рассмотрим множество , состоящее из N элементов:
}.
Попробуем закодировать любое его подмножество двоичной последовательностью, состоящей из 0 и 1: если элемент входит в подмножество, то первая цифра последовательности равна 1, если нет – 0. Точно также поступаем для второго элемента, третьего и т.д. Для каждого подмножества получаем свою последовательность из
нулей и единиц. Так, в рассмотренном выше примере получим следующие последовательности для каждого из восьми рассмотренных подмножеств:
пустое множество – 000;
одноэлементные подмножества – 100, 010, 001;
двухэлементые подмножества – 110, 011, 101;
трехэлементное подмножество – 111.
Таким образом, каждому подмножеству соответствует своя двоичная последовательность длины , а каждой такой последовательности – свое подмножество. Количество двоичных последовательностей длины
мы уже считали ранее, когда изучали правило умножения – их будет
. Значит, и подмножеств будет ровно столько же:
количество подмножеств N -элементного множества = .
Дата публикования: 2015-03-26; Прочитано: 931 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!