Элементы комбинаторики — размещения, перестановки, сочетания с повторами и без повторов


Определение: Перестановка n-элементного множества М есть упорядоченный набор длины n, составленный из попарно различных элементов множества М. Обозначим через множество всех перестановок из n элементов и через Рn число всех перестановок из n элементов. Например, если M = {а,b,с}, то РM = {(а,b,с), (а,с,b), (b,а,с). (b,с.а), (с,а,b), (с,b,а)}; Рn =3!= 6.

Определение: Сочетание из n элементов по r элементов в каждом сочетании есть r-элементное подмножество в n-элементном множестве М. Обозначим через множество всех сочетаний из n элементов по r и через Crn число всех сочетаний из n элементов по r. Например, если M = {а,b.с}, то С1M = {(а), (b), (с)}; C2M = {(а,b),(а,с),(b,с)}; С13 = |С1M | = 3; С23=|С2M|= 3.

Определение: Размещение из 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 сомножителей. Мощности множеств комбинаторных конфигураций называются комбинаторными числами.


Комментарии запрещены.




Статистика