Лекция № 4. Пересчёт.

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

Основные задачи:

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

2)пересчёт (Если необходимо выделить все элементы множества, обладающим заданным свойствам.

3)оптимизация (Если на исходном конечном множестве определена некоторая целевая функция и нас интересует те элементы множества, которые доставляют минимум или максимум этой функции).

4)вопросы существования комбинаторных комбинаций.

5)алгоритмы построения комбинаторной конфигурации.

Правило суммы.

Пусть Х1…Хк – конечные попарно не пересекающиеся множества, т.е. ХI принадлежит Xj при Iнеравныеj.

Пусть IXI=m, IYI=n.

Если объект х может быть выбран m способами, а объект y – другими n способами.

Правило произведения.

Пусть IXI=m, IYI=n.

Если объект х может быть выбран m способами и после каждого из таких выборов объект y, в свою очередь, может, выбран n способами то выбор упорядоченной пары (x,y) может быть осуществлён m на n способами.

Пусть задано множество Х={х1…хn} Набор элементов: называется выборкой объёма r из n элементов или иначе (n,r)-выборка.

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

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

Упорядоченная (n,r) выборка, в которой элементы могут повторяться, называются (n,r)-размещения с повторением.

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

Х={1,2,3} n=3 r=2

1)составим размещения без повторений

(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)

2)размещения с повторениями

(1,2),(1,3),(2,1),(2,3),(3,1),(3,2),(1,1),(2,2),(3,3)

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

Число (n,r) размещениями с повторениями обозначим Aиндекс n и степень r с чертой

Число различных размещений с повторениями из n элементов по r определяется по формуле

Aиндекс n и степень r с чертой=n в степени r.

Число различных размещений без повторений из n элементов по r вычисляется по формуле

Aиндекс n и степень r = n1/(n-r)! При r<=n

Aиндекс n и степень r =0 при r>n

n!=1*2*3…*n 0!=1

(n,n) размещение без повторений называется перестановкой множества X и обозначается Pn.

Число различных перестановок без повторений из n элементов вычисляется по формуле:

Pn=n!

Х={1,2,3} n=3

1)составим перестановки множества X

(1,2,3,),(1,3,2,),(2,1,3),(2,3,1,),(3,1,2,),(3,2,1,)

2)размещения с повторениями

Р3=n!=1*2*3=6

Вывод: различаться порядком элементов

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

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

Х={1,2,3} n=3 r=2

1)составить сочетания без повторения из 3 элементов по 2.

{1,2},{2,3},{3,1}

2)составить сочетания с повторениями

{1,2},{2,3},{3,1},{3,1},{2,1},{3,2}

Вывод: сочетания различаться элементами.

Число сочетаний без повторений n элементов по r вычисляться по формуле

С из n по r = n!/(n-r)!*r! при r<=n

С из n по r=0 при r>n

Число сочетаний с повторениями из n элементов по r вычисляется по формуле

С из n по r c чертой =С из n+r-1 по r

Пусть Х-конечное множество,IXI=n

Множества {X1…Xk} – разбиение Х:

Пересечение Х1=X XiпересекаетXj = 0 при iне=J IXiI=mi i=1,2,…k

Причём n=n

Pn(n1….nk)=n!/n1!...*nk!

Если формула для вычисления числа перестановок с повторением из n элементов , среди которых n1 равны между собой,n2 равны между сjбой,…,nk равны между собой и n=n1+n2…nk.

Сn1*n2….*nk)=n!/n1!...*nk!

Свойство комбинаторных конфигураций, размещений, перестановок и сочетаний.