15. Постановка комбинаторной задачи

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

Задача заключается в указании точного числа, выраженного через n и k, таких наборов.

Такие задачи, по – видимому, впервые были изложены в сочинении «Диссертация о комбинаторном искусстве» («Dissertatio de Arte combinatoria») немецкого математика Готфирда Вильгельма Лейбница (1646-1716), изданного в 1666 году, отсюда и их название – комбинаторные.

16. Выборка с возвращением и без возвращения

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

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

При этом, будем считать, что каждый шар имеет свой номер от 1 до n включительно. Поэтому выборка из k шаров может быть записана в виде ( ), где а₁ есть номер первого извлеченного шара, а₂-второго, ..., а_k –номер шара, извлеченного на последнем, k -том шаге.

Рассматриваем два случая.

I. Выбор с возвращением. Извлечение шаров производится с возвращением в исходное положение: после каждого извлечения шара урна в прежнем содержании возобновляется. Это соответствует подбрасыванию монеты (урна состоит из двух «шаров» – Г (герб) и Р (решетка), а при каждом подбрасывании – «извлечении шара» – снова появляется Г или Р) и бросанию игральной кости (урна состоит из шести «шаров» – очков 1,2,3,4,5,6 и при каждом бросании на верхней грани игральной кости снова появляется одно из них).

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

Итак, из урны с n шарами извлекли k шаров и составили набор или выборку ( ) , о которой также будем говорить, «выборка объема k из генеральной совокупности объема n», или, коротко, «выборка из n по k» .

17. Выборки неупорядоченные и упорядоченные

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

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

Поэтому речь идет о выборках одинакового состава. Рассмотрим, например, выборки (1,3,1) и (1,1,3). Они одинакового состава: шар с номером 1 извлечен два раза (также говорят "кратности 2"), шар с номером 3 извлечен один раз. Они различаются порядком в выборке извлеченных шаров: если в обеих выборках при первом шаге выборки были извлечены шары с номером 1, то при втором шаге уже извлечены разные шары – в первой выборке шар с номером 3, во второй – шар с номером 2.

Тем самым, выборки одинакового состава разделяются на два вида:

А) Неупорядоченные выборки как выборки без учета расположения его элементов – две выборки равны (одинаковы или тождественны), если каждый элемент одной выборки с учетом его количества (кратности) в том же количестве содержится в другом и наоборот.

Таким образом, выборки (1,3,1) и (1,1,3) как неупорядоченные выборки тождественны и при счете числа выборок учитываются как одна выборка.

В) Упорядоченные выборки как выборки в которых, помимо состава, учитывается также порядок следования элементов в выборке. При этом, выборки разного состава и выборки одного состава, но разного порядка следования элементов объявляются как различные.

Таким образом, выборки (1,3,1) и (1,1,3) как упорядоченные выборки различны и при счете числа выборок учитываются как две выборки.

Подведем итоги.

Выборки – это k-членные (некоторые члены их которых могут повторяться) наборы из генеральной совокупности.

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