Приведем основные правила комбинаторики.

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

Перестановкой n элементов множества называется их комбинация, отличающаяся порядком расположения.

В комбинаторике принято обозначение: если в множестве имеется n элементов, то П_n — число перестановок элементов этого множества.

Рассмотрим конкретные множества:

n = 0: П₀ = 1 - по определению;

n = 1: П₁ = 1;

n = 2: есть множество {1,2}, возможны числа 12 и 21, значит, П₂ = 2;

n = 3: сколько различных трехзначных чисел можно составить из множества {1, 2, 3}?

Начнем с тех, которые начинаются с 1: 123, 132, затем с 2: 213, 231 и
с 3: 312 и 321. Всего получается 6 чисел. Это значит, что П₃ = 6.

Можно предположить, что П_n = n ´ П_n-1

И это действительно так. Эта формула называется рекуррентной, так как позволяет вычислять значение очередной величины через предыдущее.

Применяя эту формулу для множества n элементов последовательно, начиная с первого, получим:

П_n = n ´(n-1)´(n-2)´…´ 3 ´ 2 ´ 1 = 1 ´ 2 ´ 3 ´…´ n;           П_n =n!

Для нахождения числа перестановок в Excel используется специальная функция - ФАКТР.

Упражнения:

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

2. Сколько различных восьмизначных чисел можно составить из цифр
1, 2, 3, 4, 5, 6, 7, 8?

Сколько различных комбинаций букв можно составить из всех букв слова «бухгалтер»?

4. Сколько различных слов можно составить из всех букв слова:
1) «колобок»; 2) «пудель» (если принять, что с «ь» слова не начинаются).

Вычислить

1	2	3

 

Сочетания

Пример: какие наборы можно составить из различного количества предметов, если всего их 4 — шампанское, печенье, конфеты, апельсины?

Были составлены наборы из 1 предмета, из 2, из 3, из 4, на основе исходных 4 предметов. Иначе можно сказать: были составлены подмножества из 1, 2, 3, 4 предметов, из 4 элементов данного множества. Такие подмножества называются сочетаниями.

По одному предмету	По два предмета	По три предмета	По четыре предмета
Ш	Ш, А	Ш, А, П	Ш, А, П, К
А	Ш, К	Ш, А, К
П	Ш, П	П, К, А
К	К, П	П, К, Ш
	К, А
	П, А
Всего 4	Всего 6	Всего 4	Всего 1

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

Формула для вычисления числа сочетаний:

Для нахождения числа сочетаний в Excel используется функция — ЧИСЛКОМБ. В функции ЧИСЛКОМБ (число; число_выбранных) должны быть заданы следующие параметры: число -число объектов n; число_выбранных - число объектов в каждой комбинации m.

Упражнения:

Сколько различных списков дежурных из 5 человек можно составить в группе из 25 человек?

Сколько различных букетов из 9 цветков можно составить из 15 полевых ромашек?

Размещения

Допустим, что есть ткань трех цветов: Красная, Синяя, Белая. Какие сочетания по 2 цвета можно составить? Следующие:

{К; С}, {С; Б}, {К; Б}.