Дискретная математика (1). Лекция Составные высказывания

• Название: Лекция Составные высказывания
• Дата: 05.09.2022
• Размер: 2.15 Mb.
• Имя файла: Дискретная математика (1).doc
• Тип: Лекция; #662788
• страница: 12 из 16

Размещения.

Размещениями из m-элементов по n называются соединения, каждое из которых содержит n элементов, взятых из данных m и которые отличаются друг от друга или элементами, или их порядком.

Предполагается, что элементы водном размещении не повторяются.

Формула числа размещений без повторений.

Размещения из m по одному. Очевидно, что их число: А =m

Составим размещения по 2:

-размещений (m-1)

m-строк

Итого: А =m(m-1)

Размещения по 3: В каждой строке будет (m-2) размещений
А ²_m -строк

Ясно, что А = А (m-2)=m(m-1)(m-2)

А = m(m-1)(m-2)(m-3)

………………………………

А = m(m-1)(m-2)….(m-(n-1)) ( * )

Пример. В группе 21 студент. Требуется выбрать старосту, профорга и физорга. Сколькими способами это можно сделать?

Решение:

Каждая тройка студентов может отличаться от другой тройки или распределением обязанностей, или хотя бы одним из студентов, то есть мы должны вычислить число размещений из 21 по 3:

m=21, n=3.

А =21*20*19=7980.

Другой вид формулы числа размещений.

Умножим числитель и знаменатель формулы ( * ) на (m-n)! Получим
А = , или
А =

Каждое размещение содержит одно и то же количество элементов, взятых из данных m.

Перестановки.

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

Их число обозначается :

=А =n*(n-1)*(n-2)…..2*1, то есть =n!

Пример:

Сколькими способами могут сесть 6 человек на 6-местную лавочку?

Решение:

В данном случае каждое расположение лиц на лавочке отличается от другого расположения только порядком. Поэтому мы имеем дело с перестановками:

=6!=720.

Сочетания.

Сочетания - это размещения, каждое из которых отличается от других хотя бы одним элементом.

Другими словами: Сочетания - это соединения, содержащие n элементов из данных m, отличающиеся хотя бы одним элементом.

Число сочетаний С . Если мы имеем m- элементов, и из них составим всевозможные сочетания по n и внутри каждого произведем перестановку, то получим размещения.

С * = А отсюда

С = =

Пример. В группе 20 студентов. Требуется выбрать 5 делегатов на конференцию. Сколькими способами это можно сделать?

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

С = =15504.