Основные понятия комбинаторики

Основные понятия комбинаторики

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

Множества и операции над ними.

Пересечением множеств и называется множество , состоящие из элементов, которые принадлежат как , так и .

Пример 1. - множество чётных чисел меньших 10, - множество делителей числа 24, тогда множество состоит из чисел принадлежащих и первому множеству и второму.

Пример 2. - множество прямоугольников, - множество ромбов, тогда множество - квадратов.

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

Пример 3.

Пример 4. - множество прямоугольных треугольников, - множество равнобедренных треугольников, тогда множество -……...

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

Пример 5.

Диаграммы Эйлера – Венна

Если каждый элемент множества является в то же время элементом множества , то говорят, что - часть, или, иначе, подмножество множества .

В этом случае пишут:

Например, множество квадратов является подмножеством ромбов, а множество ромбов - подмножеством множества параллелепипедов.

Множество натуральных чисел, делящихся на 10, является подмножеством множества чётных натуральных чисел.

Простейшие комбинаторные задачи можно решать методом перебора возможных вариантов.

Пример 1. Четыре студента группы изучают математику- Яна, Настя, Наташа, Андрей. На математическую олимпиаду требуется послать двух студентов. Сколькими способами это можно сделать?

Яна	Настя	Наташа
Настя Наташа Андрей	Наташа Андрей	Андрей

Пример 2. В меню столовой три первых блюда А₁,А₂,А₃, два вторых В₁,В₂, и три сока С₁,С₂,С₃. Сколько вариантов комплексного обеда можно составить из этих блюд?

Решение. Составляем схему возможных вариантов.

А₁		А₂		А₃
В₁	В₂	В₁	В₂	В₁	В₂
С₁,С₂,С₃	С₁,С₂,С₃	С₁,С₂,С₃	С₁,С₂,С₃	С₁,С₂,С₃	С₁,С₂,С₃

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

Например, упорядоченное множество образуют 33 буквы русского алфавита; множество студентов группы, если за порядок принять список журнала,…

Пример 3. В посёлке имеется 5 светофоров. Каждый может находиться в одном из трёх состояний (гореть красным, зелёным или жёлтым светом). Сколькими способами можно зажечь все светофоры?

12 3 4 5 Следующая ⇒