Смекни!
smekni.com

Связь комбинаторики с различными разделами математики (стр. 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 < kn, 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 < kn, (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, pin: вычисляется

и из последовательности 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 представляет собой многоугольник, то его диаметром является наибольшее из расстояний между вершинами.