Дипломная работа: Связь комбинаторики с различными разделами математики
Итак, двумя геометрически различными способами три одинаковые мухи могут усесться в вершинах правильного пятиугольника.
Задача 6. Сколькими способами можно раскрасить вершины куба в два цвета (красный и синий) так, чтобы вершин каждого цвета было поровну?
Решение. Для решения этой задачи воспользуемся задачей 1. Пусть М
множество всевозможных по-разному раскрашенных кубов одного размера, положение
которых в пространстве фиксировано. Тогда по формуле 
nk (k1, k2, …, kn) = 
получим |M| = 
28
(4,4) = 
= 70 по-разному
раскрашенных кубов. Так как нам нужно раскрасить вершины в два цвета (4 - в
красный, 4 - в синий), то минимальное количество циклов в перестановке должно
быть равно двум. Поэтому все перестановки 1) – 24) (задача 1) имеют неподвижные
точки. В результате в группе G имеется:
1 перестановка типа <1, 1, 1, 1, 1, 1, 1, 1>,
6 перестановок типа <4, 4>,
9 перестановок типа <2, 2, 2, 2>,
8 перестановок типа <1, 1, 3, 3>.
Тогда перестановка типа <1, 1, 1, 1, 1, 1, 1, 1>
имеет 
28 (4,4)
= 
= 70 неподвижных точек.
Каждая перестановка типа <4, 4> имеет (по принципу умножения Р2
=2∙1= 2 неподвижные точки. Для каждой перестановки типа <2, 2,
2, 2> имеется 
24
(2, 2) = 
= 6 неподвижных
точек. Каждая перестановка типа <1, 1, 3, 3> имеет (по принципу
умножения) Р2 =2∙1∙2∙1= 4 неподвижные
точки. По лемме Бернсайда получаем 
(1∙70+
6∙2 + 9∙6 + 8∙4) = 7.
Итак, семью способами можно раскрасить вершины куба в два цвета так, чтобы вершин каждого цвета было поровну.
Задача 7. Сколькими различными способами можно грани куба раскрасить в четыре цвета так, чтобы все четыре цвета присутствовали в раскраске каждого куба?
Решение. Для решения этой задачи воспользуемся задачей 3. Пусть М
множество всевозможных по-разному раскрашенных кубов одного размера, положение
которых в пространстве фиксировано. Тогда по принципу умножения: первую грань
можно раскрасить 4 способами, вторую – тремя, третью – двумя, четвёртую – одним
способом, пятую – четырьмя, шестую – четырьмя способами. Получим |M| = 4∙3∙2∙1∙4∙4
= 384. Найдём
геометрически различные способы раскраски. Для этого используем описанные в
задаче 3 разложения в произведение циклов всех перестановок из группы G вращений куба. Так как в раскраске
куба должны присутствовать четыре разных цвета, то минимальное количество
циклов в перестановке должно быть равно четырём. Поэтому перестановки 1), 3),
4), 6), 7), 9) – 23) в задаче 3 неподвижных точек не имеют. Таким образом,
неподвижные точки имеют 3 перестановки типа <1, 1, 2, 2> и 1 перестановку
типа <1, 1, 1, 1, 1, 1>. Определим количество неподвижных точек для
перестановок каждого типа. Для перестановки типа <1, 1, 1, 1, 1, 1>
имеем по принципу умножения Р4 = 4∙3∙2∙1∙4∙4
= 384 неподвижные точки. Для каждой перестановки типа <1, 1, 2, 2> по
принципу умножения имеется Р4 = 4∙3∙2∙1 = 24 неподвижные
точки. По лемме Бернсайда получаем 
(1∙384+3∙24)
= 19.
Итак, существует 19 различных способов раскраски граней куба в 4 цвета так, чтобы все 4 цвета присутствовали в раскраске каждого куба.
§ 2. «Метод просеивания» [4]
Познакомимся с наиболее общим методом пересчёта,
который можно назвать «методом просеивания» или «комбинаторным просеиванием»: с
любым свойством P можно
связать его расщепление на некотором множестве A, в соответствии с которым A разбивается на две части: подмножество А1,
образованное элементами, обладающими свойством Р, и А2,
образованное элементами, не обладающими свойством Р, т. е. обладающими
свойством 
. Выбирая свойства
подходящим образом, можно последовательным просеиванием пересчитать
подмножества с наложенными на них теми или иными ограничениями.
2.1. Формула включения и исключения
Пусть А – конечное множество и 
. Будем обозначать через 
дополнение А1
по отношению к А, а через Card A
число элементов в А.
Тогда
.
Если 
и 
, то
(1)
.
Покажем, что формула (1) обобщается на случай n подмножеств 
, i=1, 2, ... n:
(2)
Действуем по индукции. Имеем
(3)
Предположим, что (2) выполняется для случая n-1 подмножеств Ai, i=1, 2,…,n-1:
(4)
Рассмотрим следующие подмножества множества An:
Применяя (4) с A=An, имеем
(5)
Подставляя (5) и (4) в (3), получаем (2). Таким образом, с учётом (1) формула (2) доказана по индукции. Эту формулу называют формулой включения и исключения. Часто её представляют в таком виде:
(6)
Формулы (2) и (6) играют основную роль в перечислении
подмножеств, обладающих заданными свойствами. Посмотрим на эти формулы с другой
точки зрения. Пусть элементы 
обладают
свойством Pi, i=1, 2, …,n. Тогда мы скажем, что подмножество 
обладает свойством 
. Таким образом, если
элементы А могут обладать n различными свойствами, то число элементов А, обладающих k указанными свойствами и не
обладающих n-k остальными, дается формулой (6).
2.2. Общий метод «просеивания» или «пропускания через решето». Решето Сильва – Сильвестра
Формула (6) описывает последовательный процесс пересчёта, называемый решетом Сильва – Сильвестра.
Пример. Рассмотрим множество
и следующие свойства:
четное число,
и А >6, (7)
и 2 < A < 8.
Подсчитаем число элементов А, обладающих
свойством 
. Обозначим подмножества,
соответствующие свойствам Р1, Р2, Р3, через
А1, А2, А3. Тогда
«Просеиваем» сначала А через Р1: Card A1=6. Затем просеиваем А1
через Р2 и Р3: 
,
. Просеиваем 
через Р3:
Итак, 
Формула (6) не позволяет, однако, перечислить элементы
искомого множества. Находим его, выписывая последовательно: 
, 
, 
. Разумеется, для множества
с небольшим числом элементов проще выписать искомое подмножество, однако это
трудно сделать при большой мощности множества.
2.3. Использование общего метода решета в теории чисел
Теорема 1. Пусть А={1, 2, …,n} и а1, а2, …,
аr, 
, i=1, 2, …,r, попарно взаимно просты. Количество
целых чисел k таких,
что 0 < k
≤ n, ai не делит k, i=1, 2, …,r, равно
(8)
Доказательство. Обозначим 
и
выпишем формулу (2):
(9)
Имеем
Card A=n,
Card Ai=
, i=1, 2, …,r,
, i≠j, i, j=1,
2, …,r,
∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ (10)
= 
.
Подставляя (10) в (9), получаем (8).
Пример. Пусть 
, а1=3,
а2=7, а3=8.
Количество целых чисел, не превосходящих 35 и не делящихся ни на 3, ни на 7, ни на 8, равно
Рассмотрим другие приложения.
Количество целых чисел k таких, что
0
< k ≤ n, (k, n)=1, 
,
обозначают через φ(n) и называют функцией Эйлера.
Теорема 2. Пусть 
. Тогда
, (11)
где произведение берётся по всем простым делителям аi числа n.
Доказательство. Так как все ai делят n и взаимно просты, то имеем
=
.
По формуле (8)
т.е. получаем (11).
Пример. Пусть n=84. Простыми делителями 84 являются 2, 3, 7; поэтому
Функция Мёбиуса. Представим (11) в другом виде, используя функцию Мёбиуса μ(n), определяемую следующим образом:
μ(1)=1;
μ(n)=0, если n делится на квадрат простого числа;
μ(а1а2…аr)=(-1)r, если ai – различные простые множители, i=1, 2, …,r.
Преобразуем равенство (11), используя функцию Мёбиуса:
Тогда
, (12)
где суммирование производится по всем k, делящим n (включая 1).
Пример. Имеем
μ(1)=1, 
, 
,
, 
,
, 
,
, 
,
, 
, 
При n=84 формула (12) даёт
Решето Эратосфена. Известен следующий способ перечисления простых чисел pi, pi≤ n: вычисляется 
и из последовательности 2,
3, …, n вычеркиваются последовательно все
числа, кратные 2, затем кратные 3, …, кратные c. Оставшиеся числа и есть искомые.
Используя теорему 2, можно получить следующую формулу
пересчёта. Если через M(n) обозначить количество простых чисел q таких, что 
, то в силу (8)
M(n)=
(13)
где pi -, i=1, 2, …,r, - простые числа, не превосходящие 
(- 1 в правой части
добавляется, так как 1 не считается простым).
В силу (12)
M(n)= 
, (14)
где суммирование в (14) производится по всем простым делителям n (включая 1).
Пример. Сколько простых среди чисел 2, 3, …, 84? Имеем 
=9. Простыми числами между
2 и 9 будут 2, 3, 5, 7. Согласно (13)
Таким образом, имеется всего 19 + 4 = 23 простых числа среди 2, 3, …, 84. Решето Эратосфена перечисляет их: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83.
Расширения данной темы: иногда подмножества не выделяются, а фиксируется число свойств, которыми обладают их элементы. Для этого случая можно вывести формулу, используя формулу (6).
