Комбинаторные задачи. Перестановки.

        Комбинаторные задачи. Перестановки.

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

Правило умножения (основная формула комбинаторики)

Общее число N способов, которыми можно выбрать по одному элементу из каждой группы и расставить их в определенном порядке (то есть получить упорядоченную совокупность (а,b,с,d)), равно:      N = n_1· n₂…n_k

Пример 1.

Монету подбросили 3 раза. Сколько различных результатов бросаний можно ожидать?

Решение

Первая монета имеет n₁ = 2 альтернативы – либо орел, либо решка. Для второй монеты также есть n₂ = 2  альтернативы и т.д., т.е. n₁ = n₂ = n₃ = 2.

Искомое количество способов: N = n₁ = n₂ = n₃ = 2³ = 8

Правило сложения

Если любые две группы А_i и A_j не имеют общих элементов, то выбор одного элемента или из A₁, или из A₂, …или из A_k можно осуществить 

N = n₁ + n₂ + …+ n_k способами.

Пример 2.

На полке 30 книг, из них 20 математических, 6 технических и 4 экономических. Сколько существует способов выбора одной математической или одной экономической книги.

Решение

Математическая книга может быть выбрана    n₁ =20 способами, экономическая – n₂ = 4 способами.

По правилу суммы существует N = n₁ + n₂ = 20 + 4 = 24 способа выбора математической или экономической книги.

Факториалом числа "n" (условное обозначение n!- читается как "эн" - факториал) называется произведение чисел от 1 до "n".

В общем виде формулу для нахождения факториала можно записать так:

n! = 1 · 2 · 3 · 4 · ... · (n - 2) · (n - 1) · n

Например:

1!=1

2!=1·2=2

3!=1·2·3=6

4!=1·2·3·4=24 и тому подобное.

Примечание:

Факториал определён только для целых неотрицательных чисел.

0! = 1

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

Пример 3.

Сколькими способами можно рассадить 4 человек за одним столом?

Решение

Каждый вариант рассадки отличается только порядком участников, то есть является перестановкой из 4 элементов: Р₄ = 4! = 1· 2· 3· 4 = 24

Пример 4. Упростить:  =  = 13· 12 · 11 = 1716

Пример 5. Упростить: 12·11! = 12!

Пример 6. Упростить:  =  =  =  =  =  = 1

Задание:

1. Сколькими способами можно рассадить четверых детей на четырёх стульях в столовой детского сада?

2. Сколькими способами можно установить дежурство по одному человеку в день среди семи учащихся группы в течение 7 дней?

3. Упростить: ; ; ;

Познавательные статьи:



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману