Вопрос 15.

Отношения линейного и частичного порядка

Отношением порядка на мн-ве А называют отношением линейного порядка, если оно связано на А, т.е. для любых х, y из А

либо xR,y либо x=y, либо yRx.

Отношение порядка, не являющееся линейным, называют отношением частичного порядка.

Пример:

Отношение «меньше» на мн-ве действительных чисел есть отношение линейного порядка.

Отношение включения на совокупности подмножеств данного мн-ва М является частичным порядком, если М содержит не менее двух различных элементов.

Вопрос 16.

Комбинаторная задача: правило суммы.

Слово комбинация происходит от латинского combino – соединяю. Действительно, при получении любой комбинации мы составляем ее из отдельных элементов, последовательно соединяя их друг с другом. С этой точки зрения число – это комбинация цифр, слово – это комбинация букв, меню – комбинация блюд и т.д.

При получении комбинации мы прежде всего выбираем, какие элементы в нее войдут, а затем располагаем их в определенном порядке. Иногда сам порядок элементов в комбинации не имеет значения, а иногда наоборот – комбинации отличаются друг от друга только порядком. Главная задача комбинаторики – подсчет числа комбинаций.

Правило сложения: Пусть объект А мы можем выбрать из множества m  способами, а объект В можно выбрать n  способами, то объект «А+В» можно выбрать m+n  способами.

Рассмотрим пример – пусть в одном ящике есть m  шариков, а во втором ящике – n  шариков. Сколькими способами можно вытащить шарик из одного этих ящиков. Очевидно, что ОДИН шарик можно достать m+n  способами.

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

1 эл. – n_1, 2 эл. – n_2, …., k эл. – n_k

Число способов, которыми можно выбрать 1 эл. или 2 эл. …. или k эл. равно n₁ + n₂ + …. + n_k

Пример 1: 5 каранд. и 7 фл.: 5 + 7 = 12

Пример 2: Посчитаем с помощью правила сложения количество слов в азбуке Морзе, длина которых не превышает четырех символов. Для подсчета разделим все такие слова на четыре класса: длины 1, 2, 3 и 4 символа. Посчитаем количество слов в каждом классе:

• длины 1 – 2 слова;

• длины 2 – слова;

• длины 3 – слов;

• длины 4 – слов.

Сложим все эти количества и получим ответ: слов.

Вопрос 17.

Комбинаторная задача: правило произведения

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

Если нам нужно сформировать комбинацию из элементов и при этом первый элемент в комбинации можно выбрать способами, после чего второй элемент – способами, после чего третий – способами и так далее, то всего таких комбинаций будет

Пример 1.

5 каранд. и 7 фл.: 5 · 7 = 35

Пример 2.

Сколько трехзначных чисел можно составить их цифр 0….5

а ) с повторениями

5 × 6 × 6 = 180

б) без повторения

5 × 5 × 4 = 100

(задача с рукопожатиями)

Пусть объект А выбирается m  способами, объект В выбирается n  способами, то оба объекта можно выбрать mn  способами. Все очень просто – каждый из m способов выбора объекта А комбинируется с каждым из n способов выбора объекта В, то есть количество способов просто умножается друг на друга.

Рассмотрим простой пример: сколько чисел можно составить из цифр 0,1,2,3,4,5,6,7,8,9, если число должно быть двузначным? Можно составить 90 чисел – первую цифру числа (объект А) можем выбрать 9 способами, так как число не может начинаться с нуля. Вторую цифру числа (объект В) можем выбрать 10 способами, так как у нас есть 10 цифр. Итого получается 9∗10=90 чисел.