Математика и информатика. Филимонова Л.В - 24 стр.

                                        24

1. Постройте граф отношения, обладающего указанными ниже свой-
    ствами:
   а) рефлексивность и транзитивность;
   б) антисимметричность;
   в) рефлексивность, симметричность и транзитивность.
2. Какие отношения эквивалентности можно задать на множестве
    N (R)? Какими еще свойствами они обладают?
8. Изобразить на координатной плоскости прямое произведение N×R.

   § 4. Элементы комбинаторики. Соединения без повторений
        и с повторениями. Правила суммы и произведения.

      Комбинаторика – теория соединений – изучает некоторые опе-
рации над конечными множествами, как упорядочение множества и
разбиение множества, интересуется расположением элементов в мно-
жестве, выясняет, сколькими способами можно расположить элемен-
ты множества в том или ином порядке. Это приводит к понятиям пе-
рестановок, размещений и сочетаний. Основными задачами комбина-
торики являются: 1) определение вида соединения; 2) подсчет числа
соединений.

                     п.1 Соединения без повторений
      Пусть дано множество М, состоящее из n элементов.
      Опр. 4.1.1 Перестановки – всевозможные упорядоченные мно-
жества, составленные из всех элементов данного множества. Число
всевозможных перестановок из n элементов обозначают Рn и находят
по формуле
                              Рn= n!   (1),
где n!= 1⋅2⋅3⋅ … ⋅n, 0!=1 по определению.
      Пример 4.1.1. Сколько перестановок можно составить из трех
букв а, в, с?
Решение: Р3=1⋅2⋅3=6. Действительно: авс, вас, асв, сав, вса, сва.♦
       Пример 4.1.2. Сколькими способами можно переставить буквы
в слове «треугольник»?
      Решение: Т.к. все буквы в данном слове разные, т.е. нет повто-
рений, то можно воспользоваться формулой (1): Р11=11!=39916800.♦
      Опр. 4.1.2 Размещениями из n по m называются всевозможные
упорядоченные подмножества, содержащие m элементов из данных n.
Обозначаются и вычисляются по формуле:
                            n!
                 Аnm =            = n(n − 1)(n − 2)...(n − m + 1).   (2).
                         (n − m)!
     Пример 4.1.3. Сколько можно составить четырехзначных чисел,
содержащих различные цифры из 5 цифр.
     Решение: Четырехзначное число – это упорядоченная последо-