Связь комбинаторики с различными разделами математики

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

В фигуре может существовать и много пар точек, расстояние между которыми равно d: в случае эллипса такая пара точек только одна, в случае квадрата их две, в случае правильного треугольника – три, в случае круга таких пар бесконечно много.

Постановка задачи: Круг диаметра d нельзя разбить на две части, диаметр каждой из которых будет меньше d, но можно разбить на три такие части (рис. 4(а, б)).

Тем же свойством обладает равносторонний треугольник со стороной d. Но имеются фигуры, которые можно разбить на две части меньшего диаметра (рис. 5(а, б)).

 Скачать реферат