Мегаобучалка Главная | О нас | Обратная связь


О числе к-элементных подмножеств n - элементного множества



2015-11-27 1804 Обсуждений (0)
О числе к-элементных подмножеств n - элементного множества 0.00 из 5.00 0 оценок




 

Обозначим через - число различных k-элементных подмножеств n-элементного множества.

Теорема.

=n!/k!(n-k)!, если kn.

Прежде чем доказывать теорему, покажем выполнение следующей леммы:

(k+1)= (n-k).

Доказательство.

Пусть М={a(1),a(2),...,a(n)}- произвольное n-элементное множество. Перепишем все k-элементные подмножества этого множества. Их согласно нашим обозначениям . Рассмотрим таблицу 1.

 

{...} {...,.},{...,.},...,{...,.}
{...} {...,.},{...,.},...,{...,.}
. . . . . . . . .
{...} {...,.},{...,.},...,{...,.}

 

Здесь слева ( во втором столбце) перечислены все k-элементные подмножества n-элементного множества М. Справа (в третьем столбце) приведены k+1 элементные подмножества множества М, которые строятся следующим образом: берется k-элементное множество из соответствующего левого столбца и к нему добавляется элемент из множества М, которого нет в соответствующем k-элементном множестве из левого столбца. Очевидно, что в каждой строке будет по (n-k) (k+1)-элементных множеств, отсюда всех k+1-элементных множеств в правой части таблицы будет (n-k) . Лемма будет доказана, если мы покажем, что в правой части таблицы находятся все k+1 - элементные подмножества множества М ( их по нашим обозначениям ) и каждое из них встречается ровно k+1 раз.

Покажем, что в правой части таблицы есть все k+1 -элементные подмножества множества М. Действительно, рассмотрим произвольное k+1 элементное подмножество множества М, которое обозначим через А={а’(1), a’(2),...,a’(k),a(k+1)}. Обозначим через В={a’(1),a’(2),...,a’(k)} k-элементныое подмножество. По построению это множество есть среди множеств правой части таблицы, т.к. в правой части таблицы присутствуют все k-элементные подмножества множества М. Так как элемент a’(k+1) М, то при построении k+1 - элементных множеств в правой части таблицы этот элемент будет обязательно добавлен к множеству В, а тем самым в правой части таблицы будет построено множество А.

Покажем, что в правой части таблицы каждое k+1 -элементное множество присутствует ровно k+1 раз. Действительно, пусть А={а’(1), a’(2),...,a’(k),a(k+1)} - произвольное k+1элементное множество. Рассмотрим совокупность из k+1 его k -элементных подмножеств: С(s), s=1,2,...,k+1, где С(s) - k-элементное множество, которое получается из множества А удалением из него элемента a’(s). Все k-элементные множества С(s) встречаются в левой части таблицы. Пометим строки таблицы, соответствующие этим множествам. Этих строк будет k+1.

Покажем, что в каждой непомеченной строке в правой части нет множества А, а в каждой помеченной строке в правой части присутствует лишь одно множество А.

Если бы в правой части непомеченной строки присутствовало множество А, то это бы означало, что в левой части этой строки было бы одно из множеств С(s), т.е. строка была бы помечена.

Возьмем произвольную помеченную строка, соответствующую множеству С(s). Тогда при построении k+1- элементных множеств в этой строке мы должны были включить в строящееся множество и элемент a’(s), тем самым построить множество А.

Лемма доказана.

Доказательство теоремы.

Теорему будем доказывать индукцией по k. Базис индукции k=0. Имеем =n!/n!0!=1, что верно, так как 0-элементное множество лишь одно, а именно пустое множество .

Пусть утверждение теоремы верно для любого k, 0kn-1. Покажем, что теорема верна и для k+1.

Действительно,

=(n-k)n!/(k+1)(n-k)k!=n!/(k+1)!(n-k-1)!,

что доказывает теорему.

 




2015-11-27 1804 Обсуждений (0)
О числе к-элементных подмножеств n - элементного множества 0.00 из 5.00 0 оценок









Обсуждение в статье: О числе к-элементных подмножеств n - элементного множества

Обсуждений еще не было, будьте первым... ↓↓↓

Отправить сообщение

Популярное:
Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы...
Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1804)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.009 сек.)