Связь комбинаторики с различными разделами математики (стр. 5 из 7)
2.2. Общий метод «просеивания» или «пропускания через решето». Решето Сильва – Сильвестра
Формула (6) описывает последовательный процесс пересчёта, называемый решетом Сильва – Сильвестра.
Пример. Рассмотрим множество
и следующие свойства:
четное число,
и А >6, (7)
и 2 < A < 8.
Подсчитаем число элементов А, обладающих свойством
. Обозначим подмножества, соответствующие свойствам Р1, Р2, Р3, через А1, А2, А3. Тогда 
«Просеиваем» сначала А через Р1: CardA1=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).
§3. Разбиение фигур на части меньшего диаметра [1, 2]
Диаметром фигуры F назовём такое расстояние d, что, во-первых, расстояние между любыми двумя точками M и N фигуры F не превосходит d, и, во-вторых, можно отыскать в фигуре F хотя бы одну пару точек A, B, расстояние между которыми в точности равно d.
Примеры:
· Если фигура F представляет собой сегмент круга, ограниченный дугой l и хордой а, то в случае, когда дуга l не превосходит полуокружности, диаметр фигуры F равен а; в случае же, когда дуга l больше полуокружности, диаметр фигуры F совпадает с диаметром всего круга.
· Если фигура F представляет собой многоугольник, то его диаметром является наибольшее из расстояний между вершинами.