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

Комбинаторика – раздел математики занимаются решением двух взаимосвязанных задач: пересчет

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

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

Правило суммы: Если множество Х₁, Х₂…Х_k таковы, что x_i x_j (i≠j, i=j=1…k), то

│х₁∪х₂∪…∪х_k│=│ х₁│+│ х₂│+…+│ х_k│

(│ │= ), при k=2 правило суммы имеет вид: если x у => │х∪у│=│х│+│у│ .

В том случае, когда множество х и у пересекаются, т.е. x у правило суммы принимает вид

│х∪у│=│х│+│у│-│х∩у│. При k=2 правило суммы чаще всего формулируются следующим

образом: если объект х может быть выбран m – способами, а у n – способами, при этом среди этих

выборов нет одинаковых, тогда выбор х или у осуществляется m+n способами.

Правило произведения: Если объект х₁ может быть выбран n₁ – способами, а объект х₂ – n₂

способами…х_k – n_k способами, то выбор упорядоченной совокупности (х₁, х₂,…, х_k) осуществляется (n₁,

n₂,…, n_k) способами. При k=2 правило произведения формулируются следующим

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

осуществляется m*n способами.

Рассмотрим множество Х, │Х│=n, выберем какие-либо k – элементов из множества х, получим

(k, n) – выборка. Элементы в этой выборке могут быть упорядочены, в этом случае выборка

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

тогда выборка – неупорядоченная или сочетание.

Объекты в сочетаниях и размещениях либо не повторяются (выборки без повторений), либо могут

повторятся (выборки с повторением).

– число размещений с повторением из n по k

– размещение без повторений

– сочетание с повторением из n по k

– сочетание без повторений

= n! – размещения без повторений (перестановки)

18. Задачи о числе размещений с повторениями и без. Задача о числе перестановок без повторений.

– число размещений с повторением из n по k

– размещение без повторений

= n! – размещения без повторений (перестановки)

1. Выбирать (выборки) или переставлять (перестановки)?

2. Упорядоченное (размещение) или неупорядоченное (сочетание)? (поменять несколько элементов местами)

3. С повторением или без?

19. Задача о числе сочетаний без повторений и с повторениями.

– сочетание с повторением из n по k

– сочетание без повторений

1. Выбирать (выборки) или переставлять (перестановки)?

2. Упорядоченное (размещение) или неупорядоченное (сочетание)? (поменять несколько элементов местами)

3. С повторением или без?

20. Задача о числе упорядоченных разбиений множества. Задача о числе перестановок с повторениями.

Задача о числе упорядоченных разбиений множества:

Всего во множестве n-элементов, разбиение на два подмножества m₁ и m₂.

R(m₁,m₂)= =

Задача о числе перестановок с повторениями:

21. Полиномиальная формула. Бином Ньютона.

Полиномиальная формула:

( + +…+x_k)ⁿ=

Суммирование производится по всем целочисленным решением уравнения , – полиномиальный коэффициент, вычисляется по формуле

Бином Ньютона:

(x+y)ⁿ=

22. Свойства сочетаний.

1. Симметрия

2. Свойство Паскаля

23. Формула включений исключений.

│ │=│ │+│ │+…+│ │-│ │-…-│ │-…-│ │+│ │+…+│ │- │ │

U\│ │=U-│ │-│ │-…-│ │+│ │+…+│ │+…+│ │-│ │-…-│ │+ │ │

24. Графы. Виды графов: орграфы, мультиграфы, псевдографы. Отношения смежности и инцидентности. Степени вершин в графе и орграфе.

Графом G(V,X) называется упорядоченное множество двух множеств: V – множество вершин, Х – множество ребер, при этом элементы множества Х являются неупорядоченные пары, состоящие из элементов множества V, предполагается, что V – не пустое множество.

Положим, что │V│=n,│X│=m, т.е. граф G содержит m-вершин и n-ребер.

Ребро х={V_i;V_j}, V_i,V_j – концы ребра; х – инцидентно V_i,V_j. V_i,V_j – инциденты ребру х.

Два ребра, имеющих одну и туже вершину называются смежными. Два конца одного и того же

ребра называются смежными вершинами.

Степенью вершины δ(V) называется число ребер, инцидентных этой вершине. Вершина V, для

которой выполняется условие δ(V)=1 называется концевая. Вершина V, для которой выполняется

условие δ(V)=0 называется изолированная.

Если элементами множества Х являются упорядоченные пары, то граф называется

ориентированным.

Если элементами Х является пары с равными элементами, то граф называется графом с петлями

или псевдографом.

Если среди элементов множества Х есть одинаковые пары, то они называются кратными ребрами,

сам граф – мультиграфом, а количество одинаковых ребер – кратностью.

Переопределим понятие степень вершины для орграфа:

Полустепенью исхода из вершины V называется число (V) равное количеству дуг, для которых

V является началом. Полустепенью захода в вершину V называется число (V) равное

количеству дуг, которые заходят в вершину V.

Теорема Эйлера: сумма степеней (полустепеней) всех вершин графа (орграфа) равно удвоенному

числу ребер (дуг).