birmaga.ru
добавить свой файл

1
Урок: Элементы комбинаторики

Комбинаторика занимается изучением объектов, составленных из элементов конечных множеств по определенным правилам соединения или сцепления таких объектов. Объекты, составленные из таких элементов, называются комбинаторными.
Основные задачи комбинаторики

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

2. Найти (построить) комбинаторный объект, обладающий заданными свойствами.

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

4. Определить количество комбинаторных объектов с заданными свойствами (позволяет оценить долю подходящих объектов во множестве всех комбинаторных объектов).
Основные комбинаторные правила

1. Правило птичьих гнезд.

Если имеется n+1 объект, который требуется разместить в n позициях, то при любом способе размещения объектов в позициях, хотя бы в одном окажется не менее 2-х объектов.

2. Правило сложения.

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

3. Правило умножения.

Пусть даны конечные множества , содержащие соответственно m и n элементов. Пусть вначале из множества A выбирается один (произвольный) элемент, после этого выбирается один (произвольный) элемент из множества В. Тогда число возможных комбинаций вида , , построенных в указанном выше порядке (т.е. ), равно .

Упорядоченные конечные множества.

Размещения. Перестановки. Сочетания.

Определение 1. Конечное множество, содержащее элементов, называется упорядоченным, если каждому элементу этого множества поставлено в соответствие одно и только одно число 1,2,…,, т.е. все элементы этого множества перенумерованы последовательно числами 1,2,…,.

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

Обозначим число размещений из элементов по символами , а через – произведение , т.е. = . При этом предполагаем, что .


Теорема 1. , .

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

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

Определение 3. Упорядоченное множество из элементов называется перестановкой этого множества.

Таким образом, различные перестановки множества из элементов отличаются лишь порядком элементов.

Обозначим – число перестановок множества из элементов. Как очевидное следствие из теоремы 1 вытекает следующая теорема.

Теорема 2. .

Определение 4. Произвольное неупорядоченное – элементное подмножество неупорядоченного множества, содержащего различных элементов (), называется сочетанием из элементов по .


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

Теорема 3. .

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

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