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

Обозначим через - число различных 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)!,

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