Задано множество $%X:|X|=n$%. Сколько существует последовательностей $%(X_1,...,X_k)$% подмножеств множества $%X$% таких, что $%X_1\bigcap...\bigcap X_k=0$%?

Последняя формула означает, что пересечение множеств $%X_1, ..., X_k$% есть пустое множество.

Объясните, пожалуйста, как решить эту задачку. Здесь нужно применить правило произведения.

задан 24 Июн '14 23:01

изменен 25 Июн '14 11:16

Deleted's gravatar image


126

10|600 символов нужно символов осталось
3

Перенумеруем элементы множества $%X$% числами от $%1$% до $%n$%. С каждой последовательностью подмножеств вида $%(X_1,\ldots,X_k)$% свяжем таблицу размером $%k\times n$%, заполненную нулями и единицами по следующему правилу. На пересечении $%i$%-й строки и $%j$%-го столбца пишем $%1$%, если $%j$%-й элемент множества $%X$% принадлежит множеству $%X_i$%, и пишем $%0$%, если не принадлежит.

Ясно, что по последовательности подмножеств мы можем однозначно заполнить такую таблицу, и обратно: если дана таблица из нулей и единиц, то она даёт нам полную информацию о каждом из подмножеств последовательности.

Способов заполнения таблицы имеется всего $%2^{kn}$%. Нам подходят такие и только такие заполнения, для которых никакой элемент не принадлежит всем подмножествам сразу, то есть в таблице нет столбцов, состоящих из одних единиц. Поэтому, если мы будем заполнять таблицу по столбцам, то значение столбца выбирается теперь не $%2^k$% способами, а $%2^k-1$% способом. Так поступаем последовательно с каждым из $%n$% столбцов, и правило произведения даёт нам ответ $%(2^k-1)^n$%.

ссылка

отвечен 24 Июн '14 23:50

Вы очень понятно объяснили! Спасибо.

(25 Июн '14 7:52) Silence
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×851

задан
24 Июн '14 23:01

показан
381 раз

обновлен
25 Июн '14 7:52

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru