Выборки. Основные комбинаторные объекты (типы выборок)

Исходным в комбинаторике является интуитивно ясное понятие выборки (синонимы – «расстановки», «комбинации», «соединения»), как набора k элементов из некоторого исходного множества, причем наборы могут быть как упорядоченными, так и неупорядоченными, с повторениями элементов и без повторений. Известно, что k-выборка из некоторого множества представляет собой комбинацию из к элементов этого множества. Выборки, в которых все элементы различны, называют выборками без повторений, в отличие от выборок с повторениями, в которые могут входить одинаковые элементы. Выборка называется упорядоченной, если существенным является не только состав элементов в ней, но и порядок их расположения. Две упорядоченные k-выборки считаются различными, если они отличаются либо составом элементов, либо порядком их расположения. Например, упорядоченные выборки (a,b) и (b,a) считаются различными, хотя и составлены из одних и тех же элементов. Выборка называется неупорядоченной, если порядок следования элементов в ней не существенен. Так, {a,b} и {a,b} считаются одной и той же неупорядоченной выборкой. Фигурные и круглые скобки подчеркивают отличие неупорядоченной выборки от упорядоченной .

Комбинаторику интересуют результаты отбора (построения выборок) и упорядочения элементов, выраженные в комбинаторных числах. Если после выбора элемент из множества удаляется (его нельзя еще раз выбрать) – это выборка без повторений. Если после выбора элемент из множества не удаляется и его можно выбрать еще раз – это выборка с повторениями. Если в выборках важен порядок элементов – это перестановки. Если же выборки с разным порядком элементов считаются одинаковыми – это сочетания. 

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

Обозначим знаком p отношение упорядоченности. Тогда запись apb означает, что a предшествует b, а ab - a предшествует или совпадает с b.

a₁ pa₂ pKpa_r a₁  a₂ K a_r  

r-перестановка r-перестановка r-сочетание r-сочетание

без повторений c повторениями без повторений с повторениями из n-множества из n-множества из n-множества из n-множества

P_nr P_nr C_nr C_nr

Теорема 1. Число перестановок без повторений

Число r-перестановок без повторений из элементов n-множества равно P_n^r  n(n 1)(n 2)K(n  r 1).

Следствие 1. Число перестановок n предметов равно:

P_nⁿ  n(n 1)(n 2)K321 n!.

Следствие 2. P_n^r  n!  . (nr)!

Следствие 3. При r>n P_n^r  0 (в перестановках с повторениями r не может быть больше n, так как мы не можем из n-множества забрать более, чем n элементов).

По определению, P_n⁰  0!1 (ноль предметов можно выбрать из n предметов единственным способом – ничего не выбирать).

Теорема 2. Число перестановок с повторениями

Число r-перестановок с повторениями из n-множества равно P_n^r n^r .

В перестановках с повторениями r может быть больше n, так как при выборе элемента мы не удаляем его из множества и можем выбрать еще раз.

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

Число r-сочетаний без повторений из n-множества равно

                                                                                                r      Pnr              n!

Cn             . r!          r!(n  r)! Следствие 1.

Свойство симметричности для числа сочетаний без повторений: C_n^r  C_n^nr .

Следствие 2. C_n⁰ 1, т.к. C_nⁿ 1 

Следствие 3. При r>n C_n^r  0 (в сочетаниях с повторениями r не может быть больше n, так как мы не можем из n-множества забрать более, чем n элементов).

Числа C_n⁰,C_n¹,C_n²,K,C_nⁱ ,K,C_n^n2,C_n^n1,C_nⁿ являются коэффициентами бинома Ньютона (a+b)ⁿ:

abn C_n0an C_n1an1b1KC_ni anibi KC_nn1a1bn1C_nnbn

Поэтому     числа          сочетаний   без    повторений          еще   называют биномиальными коэффициентами. 

Теорема 4. Число сочетаний с повторениями

Число r-сочетаний с повторениями из n-множества равно

Ñnr Cnrr1 Cnnr11  (n  r 1)!. r!(n 1)!