Цель: Изучить основные понятия комбинаторики
План:
1. Метод математической индукции.
2. Перестановки
3. Размещения
4. Сочетания
5. Разбиения
6. Вопросы для контроля знаний и подведения итога прочитанной лекции
1. Метод математической индукции.Любое конечное множество можно задать перечислением его элементов А - {а1 а2 ..., аp}. До сих пор нас не интересовал порядок следования элементов, и, например множества {а1 а2 ..., аp} и {а2, а1 а3,..., ар} мы не различали. В дальнейшем нам будет важен порядок, в котором записаны элементы. Множество, в котором задан порядок следования элементов, называется упорядоченным. Таким образом, если множество упорядочено, то каждому элементу приписан свой номер, и можно говорить «первый элемент», «второй элемент» и т.д. Можно сказать также, что в упорядоченном множестве каждому элементу отведено место, на котором он помещается среди других элементов этого множества.
Теорема (Метод математической индукции). Если 1) некоторое утверждение справедливо для k = 1, 2) из справедливости утверждения для произвольного натурального k следует его справедливость для k + 1, то это утверждение справедливо для всякого натурального n.
Доказательство. Предположим противное, т.е. что при выполнении обоих условий для некоторых натуральных чисел наше утверждение не выполняется. Пусть т — наименьшее из этих чисел. Это значит, что, во-первых, т > 1, и, во-вторых, для m - 1 наше утверждение выполняется, а для m - уже нет. Но это противоречит второму условию. Следовательно, числа т с указанным свойством не существует. Метод математической индукции доказан.
Одним из основных инструментов обработки дискретной информации является теория перечисления или комбинаторный анализ, или кратко комбинаторика. В частности, почти вся теория вероятностей построена по следующей схеме: комбинаторный анализ задачи (проблемы) - теоремы о вероятностях - дискретное распределение - предельная теорема - непрерывное распределение - дополнительные теоремы - другие родственные непрерывные распределения. Поэтому каждое дискретное распределение имеет свой (или свои) непрерывный аналог, т.е. непрерывное распределение.
В связи с этим необходимо знание комбинаторного анализа, основные элементы которого представлены ниже.