Считать что сочетание переходит в. Комбинаторика: основные правила и формулы

КОМБИНАТОРИКА

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

Правила сложения и умножения в комбинаторике

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В - n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.

Пример 1.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?

Решение

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n 1 способами, второе действие n 2 способами, третье - n 3 способами и так до k-го действия, которое можно выполнить n k способами, то все k действий вместе могут быть выполнены:

способами.

Пример 2.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?

Решение

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.

Сочетания без повторений. Сочетания с повторениями

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?

Пример 3.

Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?

Решение

Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:

.

Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?

.

Пример 4.

В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

Решение

Т.к. среди 7 пирожных могут быть пирожные одного сорта, то число способов, которыми можно купить 7 пирожных, определяется числом сочетаний с повторениями из 7 по 4.

.

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

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

Пример 5.

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

Решение.

В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно вы б рать и разместить по m различным местам m из n предметов, с реди которых есть одинаковые?

Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера- составить каталог. Сколько различных пятизначных номеров может составить мальчик?

Перестановки без повторений . Перестановки с повторениями

Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?

Пример 7.

Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?

Решение

Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.

Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k < n), т. е. есть одинаковые предметы.

Пример 8.

Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?

Решение

Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно

ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ "КОМБИНАТОРИКА"

НЕУПОРЯДОЧЕННЫЕ УПОРЯДОЧЕННЫЕ РАЗБИЕНИЯ С ФИКСИРОВАННЫМИ РАЗМЕРАМИ ЧАСТЕЙ

Цель: Изучить на практике методику расчета числа перестановок без повторений и с повторениями

Задание 4 () .

Задание 5 (начисло перестановок с повторениями).

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

Задание 7 () .

Задание 4 (начисло перестановок без повторений) .

Сколько различных n n штук цифр: 1,3,5,7,9?

ЧИСЛО ПЕРЕСТАНОВОК БЕЗ ПОВТОРЕНИЙ. КРАТКАЯ ТЕОРИЯ

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

Пример. Перестановки из 3 различных элементов а, b и с: аbс, bса, саb, сbа, bас, асb.

Число всех перестановок из п различных элементов (обозначается Р п) есть Р п = 1 2 3 ... n = п ! (п ! читается "эн-факториал").

В таблице ниже приведены числовые значения факториалов первых натуральных чисел и нуля.

Таблица. Значения факториалов первых натуральных чисел и нуля.

КОНЕЦ ТЕОРИИ.

Решение.

В задании 4 n =5, ибо переставляются местами всевозможными способами n =5 штук различных цифр: 1,3,5,7,9. При этом каждой новой перестановке цифр соответствует новый телефонный номер (натуральное число). Поэтому искомое число различных телефонных номеров равно числу различных перестановок без повторений из n =5 штук различных элементов.

Согласно теории, искомое число равно Р 5 = 5!= 120 различных 5– значных телефонных номеров.

Ответ: 120 различных 5– значных телефонных номеров.

Задание 5 (на число перестановок с повторениями.)

Сколько различных n – значных телефонных номеров (натуральных чисел) можно написать, переставляя следующий набор n штук цифр: 1,1,1,3,3,5?

ЧИСЛО ПЕРЕСТАНОВОК С ПОВТОРЕНИЯМИ. КРАТКАЯ ТЕОРИЯ

Перестановки с повторениями

Перестановками с повторениями из т элементов n различных типов, среди которых k 1 одинаковых элементов 1-го типа, k 2 одинаковых элементов 2-го типа, ... , k n одинаковых элементов п -го типа (k 1 + k 2 + ... + k п = m ) , называются их последовательности, отличающиеся только порядком входящих в них элементов.

Пример. Перестановки из 3 элементов, среди которых 2 одинаковых элемента типа а и 1 элемент типа b: ааb, аbа, bаа.

Число перестановок из т элементов, среди которых k 1 - одинаковых элементов 1-го типа, k 2 одинаковых элементов2-го типа,..., k п - одинаковых элементов n -го типа [обозначается Р (m ; k 1 ,k 2 ,..., k п) ] равно:

Р (m ; k 1 ,k 2 ,..., k п) = т!/ (k 1 !k 2 !... k п !).

Для примера перестановок с повторениями из 3 элементов, среди которых 2 одинаковых типа а и 1 элемент типа b, имеем Р (m=3 ; k 1 =2,k 2 =1) = 3!/ (2 !1!).

КОНЕЦ ТЕОРИИ.

Решение.

В задание 5 m =6, ибо переставляются местами всевозможными способами m =6 штук различных цифр: 1,1,1,3,3,5, среди которых есть повторяющиеся (одинаковые). При этом каждой новой перестановке цифр соответствует новый телефонный номер (натуральное число). Поэтому искомое число различных телефонных номеров равно числу различных перестановок с повторениями из m =6 штук элементов, среди которых k 1 =3 одинаковых элементов 1-го типа (цифра 1), k 2 =2 одинаковых элементов2-го типа (цифра 3), k 3 =1одинаковых элементов 3 -го типа (цифра 5), равно Р (m ; k 1 ,k 2 ,..., k п) = т!/ (k 1 !k 2 !... k п !), Р (6; 3, 2, 1) = 6!/(3! 2! 1!)= =60.

Ответ: Р (6; 3, 2, 1) = 60, т. е 60 различных вариантов 6– значных телефонных номеров (6-значных чисел), содержащих цифру 1 трижды, 3 -дважды и 5 - один раз.

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

Сколько всего вариантов можно получить, разбивая группу из пяти человек (из пяти солдат) на три подгруппы - две подгруппы по два человека (по два автоматчики) и одна подгруппа из одного человека (из одного пулеметчика)?

НЕУПОРЯДОЧЕННЫЕ РАЗБИЕНИЯ. КРАТКАЯ ТЕОРИЯ

Неупорядоченное разбиение n -элементного множества X - это любое семейство {X 1 , X 2 ,…, X k }, где 1≤k≤п; X 1 , X 2 ,…, X k - непустые попарно непересекающиеся подмножества множества X , объединение которых равноX.

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

Пример. Для множества {а,b,с} неупорядоченное разбиение это, например, {{а},{b,с}}. Причем {{а},{b,с}}={{b,с},{а}}.

Для множества с п элементами обозначим через D (n ; k 1 , k 2 ,…, k n) число всех таких неупорядоченных разбиений, в которых есть k 1 подмножеств с одним элементом, k 2 подмножеств с двумя элементами и т.д., где k 1 ≥0, k 2 ≥0,…, k n ≥0; k 1 +2 k 2 +…+n k n = n.

КОНЕЦ ТЕОРИИ.

Решение.

Каждый вариант- это неупорядоченное разбиение { Иванов, Петров, Сидоров, Андреев, Борисов }. Множество из 5 элементов Один из вариантов разбиения {{Иванов, Петров}, {Сидоров, Андреев}, {Борисов}}

Имеем п = 5, k 1 =1, k 2 =2, k 3 =0, k 4 =0, k 5 =0 (так как по условию нет подгрупп из трех, четырех, пяти человек).

Ответ: 15 вариантов.

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

Сколькими способами можно выбрать из десяти солдат трех пулеметчиков, трех гранатометчиков и четырех автоматчиков (3 пулеметчика 3 гранатометчика 4 автоматчика, всего 10 солдат)?

УПОРЯДОЧЕННЫЕ РАЗБИЕНИЯ. КРАТКАЯ ТЕОРИЯ

Упорядоченным разбиением конечного множества X с n элементами называется любой кортеж вида <X 1 , X 2 ,…, X k >, где 1 ≤k ≤n ; X 1 , X 2 ,…, X k - непустые попарно непересекающиеся, подмножества множества X, объединение которых равно X.

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

Пример. Для множества {а,b,с} упорядоченное разбиение это, например, кортеж <{{а},{b,с}} >. Причем <{{а},{b,с}}> ¹<{{b,с},{а}} >.

Для множества с п элементами обозначим через E (n ; m 1 , m 2 ,…, m k ,) число всех таких упорядоченных разбиений на подмножества X 1 , X 2 ,…, X k , содержащие m 1 , m 2 ,…, m k , где m 1 ≥0, m 2 ≥0,…, m k ≥0; m 1 + m 2 +…+ m k = n.

Число всех упорядоченных разбиений <X 1 , X 2 ,…, X k > множества с п элементами на подмножества X 1 , X 2 ,…, X k , содержащие m 1 , m 2 ,…, m k , элементов соответственно. определяется по полиномиальной формуле

где m 1 ≥1, m 2 ≥1,…, m n ≥1; m 1 + m 2 +…+m k = n.

КОНЕЦ ТЕОРИИ.

Решение.

В задании имеем упорядоченное разбиение < X 1 , X 2 , X 3 > множества с десятью элементами, где X 1 - подмножество пулеметчиков, Х 2 - подмножество гранатометчиков, Х 3 - подмножество автоматчиков;

поэтому п = 10, m 1 = 3, т 2 , = 3, т 3 = 4.

Тогда всего есть

Ответ: 4200 вариантов

Перестановка – это комбинация элементов из N разных элементов взятых в определенном порядке. В перестановке важен порядок следования элементов, и в перестановке должны быть задействованы все N элементов.

Задача : Найти все возможные перестановки для последовательности чисел 1, 2, 3.
Существуют следующие перестановки:

1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1

Перестановки без повторений

Количество перестановок для N различных элементов составляет N! . Действительно:

• на первое место может быть помещен любой из N элементов (всего вариантов N ),
• на вторую позицию может быть помещен любой из оставшихся (N-1) элементов (итого вариантов N·(N-1) ),
• если продолжить данную последовательность для всех N мест, то получим: N·(N-1)·(N-2)· … ·1 , то есть всего N! перестановок.

Рассмотрим задачу получения всех перестановок чисел 1…N (то есть последовательности длины N ), где каждое из чисел входит ровно по 1 разу. Существует множество вариантов порядка получения перестановок. Однако наиболее часто решается задача генерации перестановок в лексикографическом порядке (см. пример выше). При этом все перестановки сортируются сначала по первому числу, затем по второму и т.д. в порядке возрастания. Таким образом, первой будет перестановка 1 2 … N , а последней — N N-1 … 1 .

Рассмотрим алгоритм решения задачи. Дана исходная последовательность чисел. Для получения каждой следующей перестановки необходимо выполнить следующие шаги:

• Необходимо просмотреть текущую перестановку справа налево и при этом следить за тем, чтобы каждый следующий элемент перестановки (элемент с большим номером) был не более чем предыдущий (элемент с меньшим номером). Как только данное соотношение будет нарушено необходимо остановиться и отметить текущее число (позиция 1).
• Снова просмотреть пройденный путь справа налево пока не дойдем до первого числа, которое больше чем отмеченное на предыдущем шаге.
• Поменять местами два полученных элемента.
• Теперь в части массива, которая размещена справа от позиции 1 надо отсортировать все числа в порядке возрастания. Поскольку до этого они все были уже записаны в порядке убывания необходимо эту часть подпоследовательность просто перевернуть.

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

Реализация на С++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include
using namespace std;

{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int *a, int n)
{
int j = n - 2;
while (j != -1 && a[j] >= a) j--;
if (j == -1)
return false; // больше перестановок нет
int k = n - 1;
while (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1;
while (l swap(a, l++, r--);
return true;
}
void Print(int *a, int n) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3);
cout << num++ << ": " ;
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl;
}
int main()
{
int n, *a;
cout << "N = " ;
cin >> n;
a = new int [n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
Print(a, n);
while (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return 0;
}

Результат выполнения

Перестановки с повторениями

Особого внимания заслуживает задача генерации перестановок N элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n 1 , n 2 ... n k , где элемент n 1 повторяется r 1 раз, n 2 повторяется r 2 раз и т.д. При этом n 1 +n 2 +...+n k =N . Если мы будем считать все n 1 +n 2 +...+n k элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n 1 +n 2 +...+n k)! . Однако среди этих перестановок не все различны. В самом деле, все r 1 элементов n 1 мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n 2 , n 3 и т. д. В итоге имеем r 1 ! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n 1 . Таким образом, всякая перестановка может быть записана r 1 !·r 2 !·...·r k ! способами. Следовательно, число различных перестановок с повторениями равно

Для генерации перестановок с повторениями можно использовать алгоритм генерации перестановок без повторений, приведенный выше. Введем повторяющийся элемент в массив a. Ниже приведен код программы для генерации перестановок с повторениями (изменен только код функции main() ).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include
using namespace std;
void swap(int *a, int i, int j)
{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int *a, int n)
{
int j = n - 2;
while (j != -1 && a[j] >= a) j--;
if (j == -1)
return false; // больше перестановок нет
int k = n - 1;
while (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
while (l swap(a, l++, r--);
return true;
}
void Print(int *a, int n) // вывод перестановки
{
static int num = 1; // номер перестановки
cout.width(3); // ширина поля вывода номера перестановки
cout << num++ << ": " ;
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl;
}
int main()
{
int n, *a;
cout << "N = " ;
cin >> n;
a = new int [n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
a = 1; // повторяющийся элемент
Print(a, n);
while (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return 0;
}

Результат работы приведенного выше алгоритма:

Подсчитаем в MS EXCEL количество сочетаний из n элементов по k. С помощью формул выведем на лист все варианты сочетаний (английский перевод термина: Combinations without repetition).

Сочетаниями из n различных элементов по k элементов называются комбинации, которые отличаются хотя бы одним элементом. Например, ниже перечислены ВСЕ 3-х элементные сочетания, взятые из множества, состоящего из 5 элементов {1; 2; 3; 4; 5}:

(1; 2; 3); (1; 2; 4); (1; 2; 5); (1; 3; 4); (1; 3; 5); (1; 4; 5); (2; 3; 4); (2; 3; 5); (2; 4; 5); (3; 4; 5)

Примечание : Это статья о подсчете количества сочетаний с использованием MS EXCEL. Теоретические основы советуем прочитать в специализированном учебнике. Изучать сочетания по этой статье - плохая идея.

Отличие Сочетаний от Размещений

Вывод всех комбинаций Сочетаний

В файле примера созданы формулы для вывода всех Сочетаний для заданных n и k.

Задавая с помощью количество элементов множества (n) и количество элементов, которое мы из него выбираем (k), с помощью формул можно вывести все Сочетания.

Задача

Автовоз может перевозить по 4 легковые машины. Необходимо перевезти 7 разных машин (LADA Granta, Hyundai Solaris, KIA Rio, Renault Duster, Lada Kalina, Volkswagen Polo, Lada Largus). Сколькими различными способами можно заполнить первый автовоз? Конкретное место машины в автовозе не важно.

Нам нужно определить число Сочетаний 7 машин на 4-х местах автовоза. Т.е. n=7, а k=4. Оказывается, что таких вариантов =ЧИСЛКОМБ(7;4) равно 35.

Произвольным образом сопоставим маркам машин числовые значения и сделаем сокращения названий марок: LADA Granta (LG=1), Hyundai Solaris (HS=2), …

Перестановки - это комбинации, состоящие из одних и тех же элементов и отличающиеся только порядком расположения этих элементов. Возьмем n различных элементов a 1 , a 2 , a 3 , … a n ; будем переставлять эти элементы всевозможными способами, оставляя без изменения число элементов и меняя только порядок их расположения. Обозначим общее число полученных таким образом перестановок P(n). P - первая буква французского слова permutation - перестановка.

Составив таблицу перестановок для n элементов и применив (n - 1) раз правило произведения, получим число всех возможных перестановок:

P(n) = n (n -1) (n - 2) … 3 2 1 = n!

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

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

Решение: т.к. все люди различны и их комбинации различаются только порядком следования, то мы имеем перестановки без повторений. Определим их число:

Р(6) = 6! = 1 2 3 4 5 6 = 720.

Перестановки с повторениями

Рассматривая различные перестановки, мы предполагали, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам.

Если среди n элементов есть n 1 элементов одного вида, n 2 элементов другого вида и т.д., n k элементов к-го вида, то имеем перестановки с повторениями, их число:

Где n 1 +…+n k = n.

Задача: сколько различных «слов» можно составить из букв слова ДЕД, МАТЕМАТИКА.

Решение: имеем перестановки с повторениями.

А) ДЕД n=3, k=2, n 1 =2, n 2 =1

P 3 (2, 1) = 3!/(2! 1!) = 6 / 2 = 3;

Б) МАТЕМАТИКА n=10, k=6, n 1 =2, n 2 =3, n 3 =2, n 4 =n 5 =n 6 =1

P 10 (2,3,2,1,1,1)=10!/(2! 3! 2!)=2 4 5 6 7 9 10 = 134 400.

Размещения

Размещения без повторений.

Размещениями называют комбинации, составленные из n данных элементов по k элементов (k<=n, k>0), которые отличаются либо составом элементов, либо порядком расположения элементов. Обозначаются размещения A n k . А - первая буква французского слова arrangement , что в переводе означает "размещение", "приведение в порядок". Число всех возможных размещений находится по формуле:

Задача: расписание одного дня состоит из двух пар. Определить число вариантов расписания при выборе из пяти дисциплин, если не может быть одинаковых пар.

Решение: имеем размещения без повторений из пяти элементов по два, из число: .

Размещения с повторениями.

Пусть существуют n различных элементов. Выберем из них m штук, действуя по следующему принципу: возьмем любой элемент, но не будем устанавливать его в какой-либо ряд, а просто запишем под номером 1 его название, сам же элемент вернем к остальным элементам. Затем опять из всех n элементов выберем один, запишем его название под номером 2 и снова вернем элемент обратно. Будем выполнять эти операции, пока не получим m названий. Размещения с повторениями вычисляются по формуле:

Задача: сколько четырехзначных номеров можно составить из 10 цифр?

Решение: имеем размещения с повторениями из 10 элементов по 4, их число: .

Сочетания

Сочетания без повторений.

Сочетаниями называют комбинации, составленные из n различных элементов по k (k =< n) элементов, которые отличаются хотя бы одним элементом. Сочетания обозначаются: C n k C - первая буква французского слова combinasion - сочетание.

Составим из n элементов всевозможные сочетания по k элементов в каждом. Их будет C n k . Внутри каждого сочетания, состоящего из k элементов, образуем всевозможные комбинации, учитывающие порядок следования в них элементов. Таких комбинаций будет P k , т.к. мы в нашем сочетании образовываем перестановки. Всего различных комбинаций из n элементов по k в каждой, отличающихся друг от друга либо составом (элементами), либо порядком их следования, будет C n k P k . Но такие комбинации называются размещениями. Таким образом, A n k = C n k P k , тогда:

Задача: в шахматном турнире участвует 7 человек; сколько партий будет сыграно, если между любыми двумя участниками должна быть сыграна партия?

Решение: имеем сочетания без повторений из 7 элементов по 2; их число: .

Сочетания с повторениями.

Если в сочетаниях некоторые элементы (или все) могут оказаться одинаковыми, то такие сочетания называются сочетаниями с повторениями. Их число определяется по формуле: .

Задача: сколько наборов из 7 пирожных можно составить, если в продаже имеется 4 сорта пирожных?

Решение: имеем сочетания с повторениями из четырех по 7 по, их число: .

3. Графы.. 2

3.1. Основные понятия. 2

3.1.1. История теории графов. 2

3.1.2. Определения. 3

3.1.3. Смежности и инцидентность. 4

3.1.4. Изоморфизм графов. 5

3.2. Представление графов в ЭВМ.. 6

3.2.1. Требования к представлению графов. 6

3.2.2. Матрица смежности. 7

3.2.3. Матрица инциденций. 7

3.3. Геометрическая реализация графов. 8

3.4. Маршруты, цепи, циклы.. 8

3.4.1. Определения. 8

3.4.2. Эйлеровы графы.. 9

3.4.3. Гамильтоновы графы.. 10

3.5. Заключение. 12

Графы

Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое примене­ние в программировании. Дело в том, что тео­рия графов предоставляет очень удобный язык для описания программных (да и многих других) моделей.

Этот тезис можно пояснить следующей аналогией. Понятие отношения также можно полностью выразить через понятие множества. Однако независимое определение понятия отношения удобнее - введение специальных терминов и обозначений упрощает изложение теории и делает ее более понятной.

То же относится и к теории графов. Стройная система специальных терминов и обозначений тео­рии графов позволяют просто и доступно описывать сложные и тонкие вещи.

Особенно важно наличие наглядной графической интерпретации понятия графа. Само название «граф» подразумевает наличие графической ин­терпретации. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказатель­ства и сложные формулы.

Основные понятия

История теории графов

Теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.

1. Задача о Кенигсбергских мостах. Обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку (рис. 3.1). Эта задача была решена Эйлером в 1736 году.

Рис. 3.1. Иллюстрация к задаче о Кенигсбергских мостах

2. Задача о трех домах и трех колодцах. Имеется три дома и три колодца. Про­вести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 3.2). Эта задача была решена Куратовским в 1930 году.

Рис. 3.2. Иллюстрация к задаче о трех домах и трех колодцах

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

Определения

Графом G(V,E) называется совокупность двух множеств - непустого множества V (множества вершин ) и множества Е неупорядоченных пар различных элемен­тов множества V (Е - множество ребер ).

G(V,E): , E VxV.

Число вершин графа G обозначим р, а число ребер – q.

р(G) = |V| q(G) = |E|.

Часто рассматриваются следующие родственные графам объекты.

1. Если элементами множества Е являются упорядоченные пары, то граф назы­вается ориентированным (или орграфом ). В этом случае элементы множества V называются узлами, а элементы множества - дугами (G(V, )).

2. Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей , а граф назы­вается графом с петлями (или псевдографом).

3. Если Е является не множеством, а набором, содержащим несколько одинако­вых элементов, то эти элементы называются кратными ребрами , а граф назы­вается мультиграфом .

Обычно граф изображают диаграммой : вершины - точками (или кружками), ребра - линиями.

Рис. 3.4. Ориентированный граф с петлей и кратными ребрами.

Рис. 3.5. Неориентированный граф с петлей.

Смежность и инцидентность

Пусть v 1 , v 2 - вершины, е = (v 1 , v 2) - соединяющее их ребро. Тогда вершина v 1 и ребро е инцидентны , вершина v 2 и ребро е также инцидентны. Два ребра, инцидентные одной вершине, называются смежными ; две вершины, инцидентные одному ребру, также называются смежными.

Степенью вершины v графа G(V,E) называется число ребер, инцидентных данной вершине. Обозначение: .

Вершина, имеющая степень 0 называется изолированной, имеющая степень 1 – висячей.

Пример. Для графа, изображенного на рис. 3.5: вершина 3 – изолированная, вершины 1 и 4 - висячие.

Пример. Для графа, изображенного на рис. 3.3.

Ребро e 1 инцидентно вершинам v 1 и v 2 . Вершина v 1 инцидентна ребрам e 1 и e 2 . Ребра e 1 и e 2 – смежны. Вершины v 1 и v 2 – смежны.

P(G)=3, q(G)=5.

Т.о. можно заметить, что .

Теорема Эйлера : .

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

Изоморфизм графов

Говорят, что два графа G 1 (V 1 ,E 1) и G 2 (V 2 ,E 2) изоморфны (обозначается G 1 ~ G 2), если существует биекция h: V 1 V 2 , сохраняющая смежность.

Графы рассматриваются с точностью до изоморфизма.

Три внешне различные диаграммы, приведенные на рис. 3.6, являются диаграм­мами одного и того же графа К 3,3 .

Рис. 3.6. Диаграммы изоморфных графов

Числовая характеристика, одинаковая для всех изоморфных графов, называется инвариантом графа . Так, p(G) и q(G) - инварианты графа G.

Не известно никакого набора инвариантов, определяющих граф с точностью до изоморфизма.

Рис. 3.8. Диаграммы неизоморфных графов с совпадающими инвариантами

Представление графов в ЭВМ

Следует подчеркнуть, что конструирование структур данных для пред­ставления в программе объектов математической модели - это основа искус­ства практического программирования. Мы приводим два различных базовых представления графов.

Выбор наилучшего представления определяется требова­ниями конкретной задачи. Более того, при решении конкретных задач исполь­зуются, как правило, некоторые комбинации или модификации указанных пред­ставлений, общее число которых необозримо. Но все они, так или иначе, основаны на тех базовых идеях, которые описаны в этом разделе.

Требования к представлению графов

Известны различные способы представления графов в памяти компьютера, кото­рые различаются объемом занимаемой памяти и скоростью выполнения опера­ций над графами.

Представление выбирается, исходя из потребностей конкрет­ной задачи. Далее приведены два из наиболее часто используемых представле­ния.

Указанные представления пригодны для графов и орграфов, а после некоторой модифи­кации также и для псевдографов, мультиграфов.

Представления иллюстрируются на конкретных примерах графа G и орграфа D, диаграммы которых представлены на рис. 7.10.

Рис. 3.9. Диаграммы графа (слева) и орграфа (справа), используемых в качестве примеров

Матрица смежности

Представление графа с помощью квадратной булевской матрицы

отражающей смежность вершин, называется матрицей смежности, где

Матрица инциденций

Представление графа с помощью матрицы Н: array of 0..1 (для оргра­фов Н: array of -1..1), отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа:

а для ориентированного графа

Главная » Упражнения » Считать что сочетание переходит в. Комбинаторика: основные правила и формулы