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

Соединения - это группы элементов некоторого конечного множества.

В элементарной алгебре рассматриваются 3 вида соединений: размещения, перестановки и сочетания [2]-[5]. Остановимся на вопросе о подсчёте числа таких комбинаций.

Размещения - упорядоченные m-элементные подмножества данного множества из n элементов (m<n), отличающиеся друг от друга порядком следования элементов или хотя бы одним элементом. Например, из 3-х цифр 7,8,9 можно составить 3 числа по одной цифре: 7, 8, 9 , - шесть чисел по 2 цифры:

Число всех возможных комбинаций из n элементов по m обозначается (arrangement(фр.) - размещение) и вычисляется по формуле:

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

(1.2)

Например,

и т.д.

Сочетания - неупорядоченные m-элементные соединения из n элементов данного множества, отличающиеся хотя бы одним элементом. Число различных сочетаний из n элементов по m обозначается символом (combinare (лат.) - соединять).

(1.3)

Например,

Используя основное свойство числа сочетаний , мы упростим вычисления

.

Кроме этого свойства числа сочетаний часто используется следующее:

.

Кроме того, принята, по определению, запись:

Задачи

Задача №1. В розыгрыше первенства страны по футболу приняло участие 16 команд. Сколькими способами могут быть распределены золотые и серебряные медали?

Решение. Золотую медаль может получить одна из 16 команд. После чего одна из 15 команд может иметь серебряную медаль. Общее число способов, которыми могут быть распределены золотая и серебряная медали, равно (правило произведения).

Задача №2. В кафе предлагают 5 первых блюд, 6 вторых и 4 третьих. Сколькими способами можно составить обед?

Решение. Согласно правилу произведения число способов равно

.

Задача №3. В классе изучают 10 предметов. В понедельник 6 уроков (все уроки разные). Сколькими способами можно составить расписание на понедельник?

Решение. Здесь нужно воспользоваться формулой размещения из 10 элементов по 6:

.

Задача №4. Сколькими способами можно разделить 6 шоколадок 14 лицам? (1 место - 1 плитка).

Решение.

1. Все плитки различны. Число способов равно числу размещений из 14 по 6:

.

2. Все плитки одинаковы. Число способов равно числу сочетаний из 14 по 6:

Задача №5. В группе 20 мальчиков и 20 девочек. Все умеют петь, танцевать, декламировать. Сколькими способами можно составить дуэты из учащихся групп?

Решение. Число способов выбрать из 20 мальчиков певца, танцора и декламатора равно числу размещений из 20 по 3 - . Аналогично из 20 девочек: . Общее число способов выбора дуэтов певцов, танцоров и декламаторов по правилу произведения равно способов.

Задача №6. Необходимо укомплектовать экипаж космического корабля в составе: командир корабля, I его помощник, II его помощник, 2 бортинженера, 1 врач. Командующая тройка может быть отобрана из 25 готовящихся к полёту лётчиков; 2 бортинженера - из 20 специалистов, в совершенстве знающих устройство космического корабля; врач - из числа 8 медиков. Сколькими способами можно укомплектовать экипаж корабля?

Решение.

.

Задача №7. Из 30 последовательных натуральных чисел: 1, 2, 3, … 30 выбирают 3 числа так, чтобы их сумма была чётной. Сколько способов такого выбора?

Решение. Сумма трёх чисел чётная, если все они чётные или из трёх 2 нечётные и 1 чётное. Например,

2 + 4 + 6 =12 и 3 + 5 + 2 = 10.

Следовательно, число способов необходимого выбора равно сумме числа сочетаний из 15 чётных чисел по 3 и числа сочетаний из 15 нечётных чисел по 2, умноженного на число чётных, т.е. 15.

.

Задача №8. Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли взять друг друга?

Решение. Один из способов показан на рисунке, а общее число способов равно числу перестановок из восьми:

?

?

?

?

?

?

?

?

рис.1

Задача №9. На тренировках занимаются 12 баскетболистов. Сколько разных стартовых пятёрок может образовать тренер?

Решение. Т.к. нас интересует только состав, то имеем:

 
< Пред   СОДЕРЖАНИЕ   Скачать   След >