16. Теорема о числе подмножеств n-элементного множества

Теорема

Любое подмножество конечного множества само конечно. Любое надмножество бесконечного множества само бесконечно.

Если множество содержит конечное число элементов, то говорят, что оно конечно, в противном случае множество называется бесконечным. Число элементов конечного множества A называется мощностью множества A и обозначается |A|. В дальнейшем мы будем различать общий (текущий) элемент x множества A, т.е. произвольный элемент, характеризующийся единственным свойством “принадлежать множеству A”, и конкретные элементы a, b, c каждый из которых отличен от других. Множество A, состоящее из элементов a,b,c,... записывается A={a,b,c,...}.

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

Теорема.

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

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

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

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

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

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

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

17. Понятие перестановки. Теорема о числе перестановок n-го элементного множества.

Понятие перестановки

Перестановка - упорядоченная выборка элементов конечного множества, в которой все элементы различны.

Понятие перестановки – это переупорядочение набора объектов, или функция которая задаёт такое переупорядочение которое на множестве устанавливает взаимно однозначное соответствие.

Теорема о числе перестановок n-го элементного множества

Теорема 1. Число всех r- перестановок n- элементного множества, где

n, rÎN, вычисляется по формуле

P(n, r) = n^r= n(n -1)...(n - r + 1)

Доказательство.Первая координата r- перестановки n- элементного множества может быть выбрана n способами, если первая координата выбрана, то вторая координата может быть выбрана n-1 способами, если выбраны первые две координаты, то третья координата может быть выбрана n-2 способами и т.д. до r- ой координаты включительно, которая может быть выбрана n-r+1 способами.

18. Понятие перестановки с повторениями. Теорема о числе перестановок с повторениями.

Определение. Размещения с повторениями, имеющие один и тот же состав и отличающиеся друг от друга лишь порядком компонент, называются перестановками с повторениями данного состава. Их число обозначают символом  P(n₁; n₂; ...; n_m), где n₁ + n₂ + ... + n_m = k.

Теорема 4 (о числе перестановок с повторениями). Пусть n₁, n₂, ..., n_m — целые неотрицательные числа, причем n₁ + n₂ + ... + n_m = k. Число перестановок с повторениями данного состава определяется по формуле

(5)

○ Отведем для элементов размещения с повторениями строку ( ₁;  ₂; ...;  _k) длины k. Среди этих k позиций выберем n1 позиций, на которые поместим элементы первого вида. Это можно сделать   способами. Среди оставшихся k – n₁ позиций выберем n₂ позиций, на которые поместим элементы второго вида (это можно сделать   способами), и т.д. Общее число способов (соответственно, перестановок) по правилу произведения будет равно

Поскольку n₁ + n₂ + ... + n_m = k, то (k – n₁ – ... – n_m)! = 0! = 1.  Следовательно, справедлива доказываемая формула (5). ●

Пример . Сколькими способами можно расставить белые фигуры: 2 коня, 2 слона, 2 ладьи, 1 ферзя и 1 короля на первой линии шахматной доски? ► Для решения задачи найдем число перестановок с повторениями, имеющих заданный состав (2; 2; 2; 1; 1). По формуле (5) получаем, что искомое число перестановок с повторениями равно