Основные характеристики комбинаторных задач

Элементы комбинаторики и теории вероятности

Вопросы для проверки знаний

1. Приведите примеры информации:

а) достоверной и недостоверной; б) полной и неполной; в) ценной и малоценной; г) своевременной и несвоевременной; д) понятной и непонятной; е) доступной и недоступной для усвоения; ж) краткой и пространной.

2. Назовите системы сбора информации, имеющиеся у человека.

3. Назовите основные случаи, когда принимаемый сигнал не содержит полезной информации.

4. От чего зависит информативность сообщения, принимаемого человеком?

5. Назовите три подхода в оценке количественного определения информации и укажите, в чем заключается их смысл.

Комбинаторика предусматривают количественный подсчет элементов множеств, формируемых из одного и того же набора объектов.

С точки зрения подсчета числа вариантов расположения заданного множества объектов на выделенных местах (либо выборки некоторого заданного набора из более широкого множества) существенными являются следующие характеристики задачи:

а) число объектов и число мест для их расположения, обозначим их k и n, параметр k называют объемом выборки,

б) сходство либо различие между размещаемыми объектами,

в) сходство либо различие между выделенными для расположения местами.

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

Пример 1. Рассматривается задача подсчета всех различных вариантов расположения студентов первого курса в актовом зале.

Если существенным признаком для студентов принять только курс обучения, то по нему все они (как объекты размещения) одинаковы. Если же существенными признаками являются паспортные данные, то по ним все студенты различны. Аналогично, если для каждого кресла в актовом зале учитывается его ряд и место в нем, то все места для размещения в задаче подсчета следует считать различными. Если же положение кресел в общем зале не важно, то в задаче все места для размещения будут одинаковы.

Также предварительно рассмотрим основные правила, которые используют при подсчете числа комбинаторных множеств.

Правило сложения. Пусть все множество подсчитываемых сочетаний можно разделить на n частей, содержащих, соответственно, L₁, L₂, …, L_n сочетаний, таким образом, что они не пересекаются друг с другом. Тогда общее число L всех сочетаний, составляющих полное множество, равно сумме данных значений L₁, L₂, …, L_n:

L=L₁+L₂+ …+L_n.

Правило умножения. Рассмотрим последовательное формирование сово­купности из n величин, которые обозначим а₁, а₂,…, а_n. Допустим, независимо от выбора предыдущих величин число вариантов для каждой из последующих постоянно. Обозначим эти числа вариантов выбора для величин а₁, а₂,…, а_n, соответственно, через L₁, L₂, …, L_n. Тогда общее число L всех возможных различных вариантов формирования наборов вида {а₁, а₂,…, а_n}, в которых порядок расположения имеет значение, равно произведению данных значений L₁, L₂, …, L_n:

L({а₁, а₂, …, а_n})=L₁(а₁)×L₂(а₂)× …×L_n(а_n).

Пример 2. В комиссии по делам семьи 4 мужчины и 7 женщин. Необходимо избрать руководство комиссии, состоящей из председателя и его заместителя. Определить, сколько существует возможных вариантов избрания руководства, если по положению возможны только 2 сочетания: 1) председатель – мужчина, заместитель – женщина и 2) председатель – женщина, заместитель – мужчина.

Решение. Рассмотрим вначале сочетание 1). На место председателя возможно избрание одного из 4 мужчин (4 возможных значения), на место его заместителя независимо может быть избра­но 7 женщин (7 возможных значений). Порядок расположения имеет значение. Следовательно, по правилу умножения общее число вариантов для сочетания 1) равно 4×7=28.

Для сочетания 2) подсчет числа вариантов аналогичен: 7×4=28.

Общее число вариантов находим по правилу сложения, поскольку сочетания 1) и 2) являются взаимоисключающими.

Ответ. 28+28 = 56.

Учет неразличимости порядка расположения объектов в сочетаниях. Рас­смотрим расположение m объектов а₁, а₂,…, а_m на n различных местах (m£ n). Обозначим через N (а₁, а₂,…, а_m) число расположений для случая, когда все объекты различны. Также рассмотрим случай, когда среди объектов есть группа из s одинаковых (стоящих, например, в начале списка: а₁=а₂=…=а_s). В этом случае общее число всех различных расположений объектов

N (а₁=а₂=…=а_s, а_s+1, …, а_m) = N (а₁, а₂,…, а_m) / s!.

Пример 3. На конференции присутствует 18 делегатов. Определить, сколькими способами можно сформировать из них состав комиссии в составе трех членов в двух случаях:

1) порядок членов комиссии (1-й, 2-й, 3-й) имеет значение и

2) все члены комиссии равноправны.

Решение. Число вариантов выбора первого члена комиссии равно L₁=18, для второго – L₂=17 (поскольку один делегат к этому времени уже занят), для третьего – L₃=16. Если порядок членов комиссии имеет значение (случай 1), то общее число вариантов находим по правилу умножения:

L=L₁×L₂×L₃=18×17×16 = 4896.

В случае 2) порядок расположения объектов не имеет значения и произведение чисел вариантов L₁, L₂, L₃ необходимо дополнительно делить на 3!:

L=L₁×L₂×L₃/3!=(18×17×16)/6=17×16×3=816.

Ответ. 1) 4896; 2) 816.

Рассмотрим основные типовые случаи расчета общего числа вариантов расположений объектов на выделенных местах.

Дата добавления: 2014-01-20