Лекция 2. Комбинаторика

Цель: Изучить основные понятия комбинаторики

План:

1. Метод математической индукции.

2. Перестановки

3. Размещения

4. Сочетания

5. Разбиения

6. Вопросы для контроля знаний и подведения итога прочитанной лекции

1. Метод математической индукции.Любое конечное множество можно задать перечислением его элементов А - {а₁ а₂ ..., а_p}. До сих пор нас не интересовал порядок следования элементов, и, например множества {а₁ а₂ ..., а_p} и {а₂, а₁ а₃,..., а_р} мы не различали. В дальнейшем нам будет важен порядок, в котором записаны элементы. Множество, в котором задан порядок следования элементов, называется упорядоченным. Таким образом, если множество упорядочено, то каждому элементу приписан свой номер, и можно говорить «первый элемент», «второй элемент» и т.д. Можно сказать также, что в упорядоченном множестве каждому элементу отведено место, на котором он помещается среди других элементов этого множества.

Теорема (Метод математической индукции). Если 1) некоторое утверждение справедливо для k = 1, 2) из справедливости утверждения для произвольного натурального k следует его справедливость для k + 1, то это утверждение справедливо для всякого натурального n.

Доказательство. Предположим противное, т.е. что при выполнении обоих условий для некоторых натуральных чисел наше утверждение не выполняется. Пусть т — наименьшее из этих чисел. Это значит, что, во-первых, т > 1, и, во-вторых, для m - 1 наше утверждение выполняется, а для m -уже нет. Но это противоречит второму условию. Следовательно, числа т с указанным свойством не существует. Метод математической индукции доказан.

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

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