Раздел 1_РЕД_2. I. основы теории множеств. Системы счисления комбинаторика

• Название: I. основы теории множеств. Системы счисления комбинаторика
• Анкор: Раздел 1_РЕД_2.doc
• Дата: 29.11.2017
• Размер: 9.96 Mb.
• Имя файла: Раздел 1_РЕД_2.doc
• Тип: Документы; #10536
• страница: 16 из 17

5.5. Перестановки и размещения без повторений групп одинаковых объектов

Пусть на n местах располагают n объектов, которые, в отличие от обычных перестановок, образуют s групп одинаковых объектов. В каждой группе i (1 £ i £ s) число объектов обозначим k_i. При этом k_i ³ 1, k₁ + k₂ + … + k_s = n). С качественной точки зрения перемена местами одинаковых объектов не изменяет набор объектов.

Формула для подсчета общего количества N(C(А)) вариантов всех различных получаемых комбинаторных множеств C(А) может быть получена следующим образом. Вначале предполагаем, что все объекты для размещения различны. При этом получаем: . Затем применяем s раз правило учета сходства и различия к группам одинаковых объектов. После деления N(C(А)) на факториалы чисел k₁, k₂, …, k_s, получим итоговую расчетную формулу:



Пример 1. В финал соревнований вышли 6 участников. Определить число всех различных возможных вариантов победителей олимпиады, если организаторы планируют присудить 1 первое, 2 вторых и 3 третьих места. Порядок участников, занявших одинаковое место, не важен.

Решение. Задача сводится к определению количеств перестановок, в которых есть группы одинаковых объектов – участники, занявшие одинаковое (с точки зрения награды) место. Ее параметры:

s = 3 (по результатам финала будут выделены 3 различных группы участников): k₁ = 1 (первое место), k₂ = 2 (второе место), k₃ = 3 (третье место),

n = 6.

По общей формуле число возможных вариантов победителей и призеров:

N = 6!/(1!×2!×3!)=60.

Ответ: 60.

Пример 2. Определить число всех различных возможных сообщений длиной в 8 букв, в которых содержатся 3 буквы «a», 2 буквы «б», 2 буквы «и», 1 буква «р».

Решение. Задача сводится к расчету числа вариантов перестановок длины n = 8, в которых есть s = 4 группы одинаковых объектов. В них содержатся следующие числа объектов:

k₁ = 3, k₂ = 2, k₃ = 2, k₄ = 1.

По общей формуле число данных сообщений равно: N = 8!/(3!×2!×2!×1!)=1680.

Ответ: 1680.

Если число размещаемых объектов k меньше числа мест n (k < n), то для расчета их общего числа используется аналогичная формула:



Вывод ее аналогичен первой формуле с учетом того, что вместо перестановок вначале определяются размещения без повторений k различных объектов на n местах .

Пример 3. В 8 пронумерованных лунках размещают 2 одинаковых белых и 3 одинаковых черных шара. Найти общее число вариантов размещения.

Решение. В задаче присутствуют две группы одинаковых объектов, в которых числа k₁ = 2, k₂ = 3. Общее число размещаемых шаров k = k₁ + k₂ = 2+3=5. Поэтому задача сводится к определению числа размещений без повторений из 8 по 5 с двумя группами одинаковых объектов (k₁ = 2, k₂ = 3):



Ответ: 560.

5.6. Сочетания

Сочетаниями из n по k называют расположения k одинаковых объектов на n различных местах, когда на одно место можно поместить только один объект. Общее количество N(C(А)) всех таких возможных попарно различных сочетаний обозначают как C(n, k) либо .

Поскольку сочетание из n по k можно представить как частный случай размещения без повторений одной группы одинаковых объектов (s = 1, k = s), то расчет общего числа сочетаний выполняют по формуле



Расчетная формула для сочетаний из n по k выводится из формулы для размещений без повторения с использованием правила учета сходства–различия. Используя в качестве промежуточной формулу для размещений без повторений и обратную схему (рис. 5.6) для правила учета сходства-различия, получим схему на рис. 5.9:



Рис. 5.9. Расчетная схема для расчета числа сочетаний из n по k

Замечание. Все формулы для подсчета чисел основных случаев расположения k объектов в п. 5.3–5.6 выведены при условии, что все n мест, отведенных для размещения объектов, различны. Однако если это условие не выполняется и все n мест одинаковы, то для фиксированного набора объектов при k  n число мест не имеет значения и вариант размещения данного набора только один.

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

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

Решение. В случае 1) получаем подсчета общего числа сочетаний для 4 одинаковых шаров на 7 различных местах:



В случае 2) все возможные варианты размещения одинаковы, поэтому N = 1.

Ответ: 1) 35; 2) 1.

5.7. Понятие вероятности

Пусть некоторая величина a принимает случайно n значений (например, от 1 до n) и общее число рассмотренных значений величины а (объем выборки) равно N. Обозначим количества значений в выборке, равных 1, 2, …, n, соответственно через k₁, k₂, …, k_n. При этом k₁ + k₂ + … + k_n = N.

Вероятностью р_i (i = 1, …, n), имеющей смысл степени повторяемости значения i в общей выборке, называют отношение

р_i = k_i / N.

Для полного набора вероятностей {p₁, p₂,…, p_n} справедливо условие нормирования:

р₁ + р₂ + … + р_n = 1.

Если все значения величины a имеют одинаковые объемы в общей выборке (k₁ = k₂ = … = k_n), а соответственно и одинаковые вероятности р₁ = р₂ = … = р_n = 1 / n, то данные значения называют равновероятными.

Пример 1. Счетчик элементарных частиц регистрирует образование легких частиц в полтора раза чаще тяжелых. Определить вероятности появления легких частиц и тяжелых частиц.

Решение. Обозначим искомые вероятности появления легких частиц и тяжелых частиц через p_л и p_т. Из условия задачи следует, что p_л = 1,5 p_т. Подставляя данное соотношение в условие нормирования (p_л + p_т = 1), получим: p_т + 1,5p_т=1.

Отсюда следует: 2,5 p_т = 1; p_т = 0,4; p_л = 1,5 p_т = 1,5  0,4 = 0,6.

Ответ: p_л = 0,6; p_т = 0,4.

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

1. Какую математическую дисциплину называют комбинаторикой?

2. В чем заключается основная задача комбинаторики?

3. Укажите основные характеристики комбинаторных задач, существенные для подсчета числа вариантов всех комбинаторных объектов, что называют в комбинаторике объемом выборки?

4. Что понимают под сходством-различием размещаемых объектов и выделенных для них мест?

5. Поясните правило сложения.

6. Поясните правило умножения.

7. Поясните правило учета сходства и различия объектов и мест для их расположения при подсчете элементов в комбинаторных множествах.

8. Можно ли применять правило умножения при расчете числа N(C(А)) всех возможных различных наборов вида {a₁, a₂}, у которых 1  a₁  4, 1  a₂  5, a₂ – a₁ = 2?

9. Какой способ порождения комбинаторных множеств называют размещением, по какой формуле производится расчет общего числа различных вариантов размещений из n по m?

10. Какой способ порождения комбинаторных множеств называют перестановкой длины n?

11. Какой способ порождения комбинаторных множеств называют размещением без повторений из n по k?

12. В чем заключается отличие размещений от перестановок и размещений без повторений?

13. По каким формулам производится расчет общего числа различных вариантов перестановок и размещений без повторений?

14. Каким образом может быть применена формула для расчета общего количества размещения без повторения в случае, когда объектов больше, чем мест?

15. Какие способы порождения комбинаторных множеств называют перестановками и размещениями без повторений групп одинаковых объектов?

16. Каким образом могут быть получены расчетные формулы для общего числа комбинаторных объектов в случае перестановок без повторений групп одинаковых объектов?

17. Каким образом могут быть получены расчетные формулы для общего числа комбинаторных объектов в случае размещений без повторений групп одинаковых объектов?

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

19. Какая задача рассматривается при определении вероятности, и каким образом она вводится?

20. В чем заключается условие нормирования вероятностей ?

21. Какие значения случайной величины называют равновероятными?

Практические задания.

1. Автомат случайно с одинаковыми вероятностями генерирует трехзначные десятичные числа, у которых первая цифра выбирается из набора {7, 8, 9}, вторая независимо – из набора {4, 5, 6}, третья независимо – из набора {0, 1, 2, 3, 7, 8, 9}. Найти вероятности появления каждого из таких чисел.

2. На цветовом табло 3 различных позиции. В каждой из них можно использовать один из цветов: красный, синий, зеленый или желтый. Сколько существует различных вариантов заполнения табло при условиях:

а) цвета могут повторяться в различных позициях,

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

3. Сколько существует всего трехзначных целых чисел в системе счисления с основанием 7, у которых в записях присутствуют только нечетные цифры?

4. Красный, зеленый и синий кубики случайно расставляют на пронумерованных клетках квадратной доски размером 33. На одной клетке может быть помещено не более 1 кубика. Какова вероятность выпадения каждого варианта расстановки, если все они равновероятны? Ответ дать формулой.

5. Сколькими способами можно разместить 5 шаров в 8 различных лунках при условии, что 1) все шары одинаковы; 2) все шары различны?

6. На 8 различных местах располагают 3 одинаковых кубика и 5 одинаковых шариков. Сколько существует различных вариантов их расположения?

7. Целочисленная величина принимает четные значения в 3 раза чаще, чем нечетные. Определить вероятность выпадения четных величин и вероятность выпадения нечетных величин.

8. Найти максимальное число мест n, при котором общее число вариантов расположения на них 4 одинаковых объектов не превышает 1000.

9. Найти максимальное число мест n, при котором число вариантов расположения на них (n – 2) различных одинаковых объектов менее 600.

10. Рассчитать максимальное число попарно различных объектов, размещаемых на 4 различных местах не более чем 1300 различными способами.

11. В 2n пронумерованных проточках кольцевой детали устанавливают поочередно детали типов А и В. Число деталей А равно n, деталей B – также n. Найти общее число вариантов их размещения, если детали А попарно различны, а детали типа В одинаковы.

12. Решить задачу 11 в предположении, что все детали В также попарно различны.

13. Сколько различных слов (в том числе – не имеющих смысла) можно получить путем всех возможных перестановок букв в слове «комбинаторика»?

14. Алгоритм обрабатывает пары множеств (порядок в паре не имеет значения) из набора, содержащего 3 одинаковых и 5 попарно различных множеств. Найти общее количество различных способов выбора пар множеств.

15. Множество содержит 4 одинаковых объекта и 4 различных. Сколько существует всех возможных вариантов выборок из данного множества по 6 объектов? Порядок вхождения объектов в выборку не имеет значения.

16. В цехе необходимо расставить 7 новых станков, их которых
3 одинаковы, остальные – различны. Найти общее количество различных вариантов их расстановки на выделенных для этого 8 различных местах.

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

18. Сколько существует различных шестизначных чисел в десятичной системе счисления, у которых в записи:

а) ровно две одинаковых цифры,

б) ровно три одинаковых цифры,

в) не менее четырех одинаковых цифр,

г) не более трех одинаковых цифр?

Ответы дать в виде формул.

19. Рассмотрим множество всех полных перестановок { (1, 2, …
... , n ) }, имеющих равные вероятности. Доказать, что:

а) средневероятный вес вектора инверсий перестановок
_и (d) равен n(n-1)/4;

б) количество всех подстановок, у которых в векторах инверсии встречаются только числа от 0до k включительно, равно
N _k = (k+1)^n-k-1(k+1)!;

в) общее число нулей в векторах инверсий всех полных перестановок длины n равно n!(1 + 1/2 + 1/3 + ... + 1/n);

г) вероятность того, что максимальная компонента вектора инверсий перестановки равна k, выражается числом

р_k = [(k+1)^n-k-1(k+1)! – k ^n-k k!].

7. Доказать, что:

а) число всевозможных частичных перестановок длины k, имеющих ровно один нуль в векторе инверсий, равно ;

б) число всевозможных частичных перестановок длины k, имеющих ровно k – 1 нулей в векторе инверсий, равно



в) общее число нулей в векторах инверсий всех частичных перестановок длины k {^k_n} равно



КОНТРОЛЬНЫЕ ЗАДАНИЯ ПО ТЕМЕ