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

23.04.2012 | Автор: admin

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

Определение: Сочетание из n элементов по r элементов в каждом сочетании есть r-элементное подмножество в n-элементном множестве М. Обозначим через множество всех сочетаний из n элементов по r и через C^r_n число всех сочетаний из n элементов по r. Например, если M = {а,b.с}, то С¹_M = {(а), (b), (с)}; C²_M = {(а,b),(а,с),(b,с)}; С¹₃ = |С¹_M | = 3; С²₃=|С²_M|= 3.

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

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

Пример: M = (а,b,с); A¹_M = {(а), (b). (с)}; A²_M = {(а,b),(а,с), (b,с),(b,а),(с,а),(с,b)}; A¹₃ = |A¹_M| = 3; A²₃ = | A²_M | = 6.

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

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