Тема. Комбинаторика

Лекция 1. Введение в комбинаторику. Некоторые области применения задач комбинаторики. Перестановки и сочетания.

Введение в комбинаторику

Представителям самых различных специальностей приходится решать задачи, в которых рассматриваются те или иные комбинации, составленные из букв, цифр, объектов. Вот некоторые примеры:

•задача составления расписания,

•в химии: рассмотрение всевозможных связей между атомами и молекулами,

•решение транспортных задач,

•планы реализации какой-либо продукции,

•задачи составления и декодирования шифров. Определение. Область математики, в которой изучаются вопро-

сы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из данных объектов, называется

комбинаторикой.

Комбинаторика является частью науки Дискретная математика. На рис. 1 показаны части Дискретной математики.

Рисунок 1. Разделы Дискретной математики.

Перестановки и сочетания

Рассмотрим множество A={a1,…,an}.

Определение. Набор элементов ai1 ,...,air A называется выборкой объема r из n элементов или (n,r) - выборкой.

3

Рисунок 2. Виды выборки.

Определение. Упорядоченная выборка без повторений называется перестановкой из n элементов по r . P(n,r) - число различных перестановок.

Определение. Упорядоченная выборка с повторениями называ-

ется перестановкой с повторениями из n элементов по r. ˆ -

P(n,r)

число различных перестановок с повторением.

Замечание. Иногда в литературе перестановки в случае r<n называются размещениями из n элементов по r.

Определение. Неупорядоченная (n,r) - выборка без повторений называется сочетанием из n элементов по r. Cnr - число различных

сочетаний.

Определение. Неупорядоченная (n,r) -выборка с повторениями

называется сочетанием с повторениями из n элементов по r. ˆ r -

Cn

число различных сочетаний с повторениями.

Пример 1.1. Пусть A={a,b,c}, r=2. Перестановки: ab, ac, ba, bc, ca, cb; P(3,2)=6. Перестановки с повторением: aa, ab, ac, ba, bb, bc,

4

Лемма 1.1. P(n, r) = n(n −1)...(n − r +1) = (n −n!r)! =(n)r .

Доказательство. 1-й элемент выбираем из всех n, 2-й – из (n-1) оставшихся и т.д. r -й выбираем из (n-r+1) элементов.

Следствие. P(n,n)=n! - число различных перестановок всех элементов A.

Доказательство. Каждый из r элементов выбираем из всех n элементов.

Доказательство: Все перестановки можно разбить на группы, в каждой из которых перестановки отличаются только порядком элементов. Число перестановок в каждой группе есть r!. Следова-

Доказательство: Каждому сочетанию с повторением можно поставить в соответствие вектор x(n, r) длины (n+r-1) из r нулей и

(n-1) единицы такой, что число нулей между (i-1)-ой и i-ой единицей равно числу элементов ai из A в сочетании с повторением.

Пример 1.2. A={a,b,c,d,e}, r=4. aabc ↔ x = (00101011)

acce ↔ x = (01100110)

Построенное соответствие является взаимно однозначным. Количество векторов с указанными свойствами равно числу способов

расположения r нулей на (n+r-1) месте, т.е. Cnr+r −1 . По свойству Cnk =Cnn−k , для числа сочетаний с повторениями верна формула

Лекция 2. Биномиальные коэффициенты. Бином Ньютона. Треугольник Паскаля.

Биномиальные коэффициенты

По определению число сочетаний Cnr – это число различных r- 5

элементных подмножеств n-элементного множества. Числа Cnr

встречаются в формулах решения многих комбинаторных задач. Основная формула для числа сочетаний

позволяет получить ряд простых тождеств. Рассмотрим некоторые из них.

Теорема 2.1. Cnr = Cnn−r . Доказательство.

= Cnr Cni−−rr .

6