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. Понятие перестановки с повторениями. Теорема о числе перестановок с повторениями.

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

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

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

Теорема.

Пусть S – множество, содержащее n неразличимых объектов. Тогда количество различных перестановок, образованных выборов k элементов с повторением, равно n^k.

19. Понятие сочетания. Теорема о числе сочетаний из n элементов по k. Свойства сочетаний.

Понятие сочетания

Пусть дано n-элементное множество. Любое k-элементное подмножества множества A называется k-сочетанием n-элементного множества.

Теорема о числе сочетаний из n элементов по k

Теорема.при k£n.

Доказательство. Из одного k-сочетания можно получить k! k-размещений n-элементного множества, потому что k элементов можно упорядочить k! способами. Поскольку каждое k-размещение есть не что иное, как упорядоченное k-сочетание, то всего k-размещений будет . С другой стороны k-размещений имеется .

Получили равенство или , и отсюда получаем искомую формулу: . Теорема доказана.

Так, , что согласуется с непосредственным подсчётом 2-сочетаний.

Число сочетаний без повторений

Теорема: Число сочетаний без повторений C_n^r = n!/(r! (n-r)!).

Доказательство: Каждому r-сочетанию (а1, a2,…, ar) n-элементного множества соответствует r! перестановок. Тогда число размещений A_n^r = C_n^r r! откуда и следует требуемая формула.

Свойства сочетаний.

1)

2)

3)

4)

5)

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

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

Сочетанием с повторениями называются наборы, в которых каждый элемент может участвовать несколько раз.

Теорема о числе сочетания с повторениями

Теорема.

Количество различных сочетаний из k объектов по n равно

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

21. Понятие размещения. Теорема о числе размещений.

Понятие размещения

В комбинаторике размещением называется расположение «предметов» (объектов) на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размеще́нием (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных же n элементов.

Теорема: число размещений n различных элементов по k различным позициям есть

или, в терминах факториалов,

Примечание: заметим, что в случае, когда число мест, по которым размещают предметы, совпадает с количеством самих предметов, т. е. когда , рассматриваемая задача становится задачей о числе перестановок. В нашем случае при этом мы получаем в знаменателе дроби ноль факториал, и для того, что бы разные формулы, соответствующие одной и той же задаче, приводили к одинаковым результатам, полагают, что .