Лекции Просолупов

Рисунок 5: Треугольник Паскаля

крайних в каждой строке, является суммой двух элементов, под которыми он стоит.

§17. Связь сочетаний и (0,1)-векторов

С каждым сочетанием из по можно связать вектор из нулей и единиц, в котором число единиц равно : позиции единиц указывают числа, которые должны войти в сочетание. Другими словами, установлено взаимооднозначное соответствие между множеством сочетаний из по и множеством (0,1)-векторов длины с единицами.

В свою очередь, каждый (0,1)-вектор длины с единицами соответствует пути на прямоугольной решетке (рис. 6) длины − и высоты . Можно сопоставить каждому шагу

31

Рисунок 6: Выбор пути на прямоугольной решетке

вниз единицу, а каждому шагу вправо — ноль. Тогда произвольному пути в шагов из точки (0, 0) в точку ( − , ) взаимно-однозначно соответствует (0,1)-вектор длины с единицами. Таким образом, мы получили взаимно-однозначное соответствие между множеством сочетаний из по

и множеством путей на прямоугольной решетке.

Заметим, что все множество путей из точки (0, 0) в точку ( − , ) складывается из множества путей из (0, 0) в ( − , − 1) с последним шагом из ( − , − 1) в ( − , ) и множества путей из (0, 0) в ( − −1, ) с последним шагом из ( − −1, ) в ( − , ) (рис. 7). Тогда количество путей

Рисунок 7: Все пути в точку ( − , ) складываются из двух групп

32

формулы (5).

§18. Перебор сочетаний

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

Пусть 1, 2, ..., — числа из множества {1, 2, ..., }, вошедшие в сочетание, причем 1 < 2 <

... < . Пусть в начальный момент времени сочетание состоит из первых чисел: = , = 1, . Далее, на каждом шаге будем просматривать вектор ( 1, 2, ..., ), начиная с , и искать первую такую компоненту , которую можно увеличить (нельзя увеличить , если он равен ;−1, если он равен − 1 и так далее). Если такой компоненты не найдется, алгоритм завершает свою работу. В противном случае, пусть — такое наибольшее число, что < − + . Увеличим

на единицу, а для всех , = + 1, , присваиваем значения = + ( − ). Повторяем процесс нужное число раз.

Пример 18.1 . Рассмотрим, как работает алгоритм для = 5 и = 3.

1)Сначала = ( 1, 2, 3) = (1, 2, 3).

2)Увеличиваем 3: = (1, 2, 4).

3)Увеличиваем 3: = (1, 2, 5).

4)3 больше увеличить нельзя. Увеличиваем 2 и переназначаем значение 3: = (1, 3, 4). Далее аналогично

5)= (1, 3, 5)

6)= (1, 4, 5)

7)= (2, 3, 4)

8)= (2, 3, 5)

9)= (2, 4, 5)

10)= (3, 4, 5)

Таким образом, мы перебрали все сочетания из 5 по 3.

§19. Бином Ньютона

Положим ∏ ? = 1.

Утверждение 19.1 . Пусть 1, 2, ..., — независимые переменные. Обозначим

= { 1, 2, ..., }. Тогда

33

и те, которые не содержат:

=̂+1(1 + 1)(1 + 2)...(1 + ̂) + (1 + 1)(1 + 2)...(1 + ̂) =

=(1 + ̂+1) · (1 + 1)(1 + 2)...(1 + ̂).

Следствие 19.2 . (формула бинома Ньютона)

Более часто используемой формой формулы бинома Ньютона является следующее уравнение:

Формулы (7) и (7′) эквивалентны. Действительно, с одной стороны формула (7)

является частным случаем формулы (7 ′).

С другой стороны, можно показать, что формула (7 ′) является следствием

что и требовалось доказать.

34

Что словесно можно сформулировать как "число всех подмножеств - элементного множества равно 2 ". Этот факт нам уже знаком.

Следствие 19.4 . Пусть > 0. Тогда

( )

Это равенство можно прочитать, например, как "суммарная мощность множества всех нечетных подмножеств множества равна суммарной мощности всех его четных подмножеств". Другими словами, число подмножеств четной и нечетной мощности совпадает.

Замечание 19.5 . (Дельта-функция) Отметим, что по следствию 19.4, если рассматривать выражение ∑ =0(−1) ( ) как функцию от на множестве целых чисел, мы получим дельта-функцию — функцию, которая принимает значение 1

только в одной точке и 0 во всех остальных:

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

( )

Доказательство. 1) Для начала докажем, что из формулы (10) следует (11). Пусть

35

Для следующего перехода сделаем замену переменной индексирования во второй сумме. Положим = − . Тогда = − , − = − − . В то время как

индекс пробегал все значения от до , индекс будет пробегать значения от− до нуля. Поскольку операция сложения на множестве вещественных чисел коммутативна (неважен порядок суммирования), будем считать, что переменная проходит значения от нуля до − . Тогда получим:

36

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

что и требовалось доказать.

2) Доказательство, что из формулы (11) следует (10), проводится аналогично. Читатель может сделать это самостоятельно.

Пример 19.7 . Пусть даны значения 0 = 2, 1 = 1, 2 = 5, 3 = −2, 4 = 3 и верна формула (10). Воспользуемся формулой (11) для вычисления значений :

( )

Для подстановки правильных биномиальных коэффициентов в эту формулу будет удобно воспользоваться треугольником Паскаля, как он представлен на рисунке 5.

В каждой строке для данного там выписаны все необходимые нам коэффициенты.

Теперь проверим правильность нахождения значений с помощью формулы (10)

37

=2 + 4 · (−1) + 6 · 5 + 4 · (−16) + 39 = 3.

Как видно, значения получены правильно.

38

Лекция 5. Мультимножества, мультиномиальная формула, число разбиений множества

§20. Мультимножества

Пусть дано некоторое множество = { 1, 2, ..., }, | | = .

Тогда мультимножество имеет вид = {11, 20, 32, 41, 53}. То есть элементы 1 и 4 входят в мультимножество по одному разу, элемент 3 входит в него 2 раза, элемент 5 — три раза и элемент 2 множества не входит в мультимножество. Мощность мультимножества равна | | = 1 + 0 + 2 + 1 + 3 = 7.

Как можно видеть, мультимножество над множеством — это неупорядоченная выборка с повторениями (сочетание с повторениями).

39

Утверждение 20.5 . Пусть , N.

Доказательство. Справа в формуле (12) стоит мощность множества всех подмножеств мощности множества мощности + − 1. Рассмотрим множество

то есть 1, 2, ..., задают некоторое мультимножество мощности над множеством

{1, 2, ..., }.

Аналогично показывается обратное соответствие. Слева в формуле (12) стоит число мультимножеств мощности множества мощности . Рассмотрим

произвольное мультимножество мощности над множеством {1, 2, ..., }. Не

умаляя общности, считаем, что элементы мультимножества расположены в порядке неубывания и выполнена формула (**).

Положим по определению = + − 1, = 1, . Тогда

1 = 1 ≥ 1;= + − 1 ≤ + − 1;

+1 − = +1 + ( + 1) − 1 − ( + − 1) = +1 − + 1 > 0,

= 1, − 1.

Следовательно, выполняется условие (*).

Таким образом, установлено взаимно-однозначное соответствие между множеством сочетаний из + − 1 по и множеством мультимножеств мощности

над множеством из элементов. Следовательно, мощности этих множеств равны.

40