Размещение элементов множества. Число размещений Аn. Примеры.

Размещением из n элементов множества Х по k элементам назовем любой упорядоченный набор элементов множества Х.

Если выбор элементов множества У из Х происходит с возвращением, т.е. каждый элемент множества Х может быть выбран несколько раз, то число размещений из n по k находится по формуле (размещения с повторениями). Если же выбор делается без возвращения, т.е. каждый элемент множества Х можно выбирать только один раз, то количество размещений из n по k обозначается и определяется равенством

Частный случай размещения при n = k называется перестановкой из n элементов. Число всех перестановок из n элементов равно

Пусть теперь из множества Х выбирается неупорядоченное подмножество У (порядок элементов в подмножестве не имеет значения). Сочетаниями из n элементов по k называются подмножества из k элементов, отличающиеся друг от друга хотя бы одним элементом. Общее число всех сочетаний из n по k обозначается и равно

При решении задач комбинаторики используют следующие правила: Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно m + n способами.

Правило произведения. Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке может быть выбрана m*n способами.

Размещение из n элементов по r есть упорядоченный набор, состоящий из r различных элементов, взятых из n-элементного множества M.

Обозначим через ArM множество всех размещений из М по r и через Arn – число всех размещений из n элементов по r.

Пример: M = (а,b,с); A1M = {(а), (b). (с)}; A2M = {(а,b),(а,с), (b,с),(b,а),(с,а),(с,b)}; A13 = |A1M| = 3; A23 = | A2M | = 6.

В размещениях, перестановках, сочетаниях элементов некоторого n-элементного множества могут допускаться повторы элементов. Будем называть их размещениями, перестановками, сочетаниями с повторами. Обозначим через A’rM, P’rM, C’rM – множества всех размещений, перестановок, сочетаний множества М с повторами, а через A’rn, P’rn, C’rn- их числа соответственно. Иногда чтобы подчеркнуть число элементов конфигурации, говорят: r-размещение, r-сочетание, r-перестановка. Например, если M={a,b,c}, то C’2M = {(а,а),(b,b),(с,с),(а,b),(а,с),(b,с)}; C’23 = |C’2M| = 6; A’2M =

{(а,а),(b,b),(с,с),(а,b),(а,с),(b,с),(b,а),(с,а),(с,b)}; A’23 = 9.

Размещения, перестановки, сочетания, составленные из элементов некоторого множества M, называются комбинаторными конфигурациями из множества М. Всякая конфигурация (а1, а2,…,аr) множества М лежит в декартовом произведении MхMх…хM, состоящем из r сомножителей. Мощности множеств комбинаторных конфигураций называются комбинаторными числами.

Amn= m·(m−1)·(m−2) …(m−(n−1)) - Общее число размещений из m элементов в группах по n обозначается Amn. Это число равно произведению n последовательных целых чисел, из которых наибольшее равно m.

4. Сочетание (подмножества) элементов множества. Число сочетаний . Примеры.

В комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данного множества, содержащего n различных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Так, например, наборы (3-хэлементные сочетания, подмножества,k=3) {2, 1, 3} и {3, 2, 1} 6-тиэлементного множества {1, 2, 3, 4, 5, 6} (n=6) являются одинаковыми (однако, как размещения были бы разными) и состоят из одних и тех же элементов {1,2,3}.

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