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

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

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

R(m₁,m₂)= =

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

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

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

( + +…+x_k)ⁿ=

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

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

(x+y)ⁿ=

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

1. Симметрия

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

3.

4.

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

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

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

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

Графом 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.

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

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

Операции над графами.

1. Одноместные (унарные):

а) удаление ребра, при этом множество вершин сохраняется

б) добавление ребра

в) добавление вершины, которую можно связать с некоторыми ребрами

г) удаление вершины совместно с инцидентными ей ребрами

д) стягивание ребра – удаление пары смежных вершин и добавление новой вершины, смежной с теми вершинами, которые были смежны хотя бы с одной из удаленных вершин.

е) дополнение графа – дополнением графа Г является граф Г ', который дополняет исходный граф до полного.

2. Бинарные

а) объединением G₁(V_1,X₁) и G₂(V_2,X₂) является G₁∪ G₂(V₁∪ V₂; X₁∪ X₂)

б) пересечение G₁(V_1,X₁) и G₂(V_2,X₂) является G₁∩ G₂(V₁∩ V₂; X₁∩ X₂)