Здравствуйте. Помогите, пожалуйста, решить такую задачу: http://cs408526.vk.me/v408526293/833a/G0lb9WvoF_4.jpg

Заранее спасибо

задан 23 Дек '13 21:01

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

Пусть $%Y=X_1\cap X_2\cap\cdots\cap X_k$%, где $%|Y|=l$%. Подмножество $%Y$% можно выбрать $%C_n^l$% способами. Положим $%Y_i=X_i\setminus Y$% для всех $%i$% от $%1$% до $%k$%. Тогда пересечение $%Y_1\cap Y_2\cap\cdots\cap Y_k$% пусто, и все $%Y_i$% являются подмножествами $%m$%-элементного множества, где $%m=n-l$%. Для фиксированного $%Y$% мы будем иметь столько последовательностей $%(X_1,X_2,\ldots,X_k)$%, сколько имеется последовательностей $%(Y_1,Y_2,\ldots,Y_k)$% с пустым пересечением, где все $%Y_i$% можно считать подмножествами заданного $%m$%-элементного множества $%\{a_1,\ldots,a_m\}$%.

Для каждого $%j$% от $%1$% до $%m$% рассмотрим множество всех индексов $%i$% от $%1$% до $%k$% таких, что $%a_j\in Y_i$%. Это множество может быть любым подмножеством в $%\{1,2,\ldots,k\}$% кроме самого этого множества, так как пересечение пустое, и никакой элемент вида $%a_j$% не принадлежит всем множествам последовательности. Поэтому для для каждого $%j$% от $%1$% до $%m$% последовательно загадаем одно из $%2^k-1$% подмножеств в $%\{1,2,\ldots,k\}$% (кроме самого этого множества), что можно сделать $%(2^k-1)^m$% способами. В итоге последовательность подмножеств будет однозначно определена.

В итоге получается $%T(n,k,l)=C_n^l(2^k-1)^{n-l}$%.

ссылка

отвечен 23 Дек '13 21:31

Спасибо большое!

(23 Дек '13 21:43) Jen94

@Jen94: и Вам спасибо -- хорошая комбинаторная задача!

(23 Дек '13 21:51) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,476

задан
23 Дек '13 21:01

показан
398 раз

обновлен
23 Дек '13 21:51

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

по почте:

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

по RSS:

Ответы

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

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