25.Основные комбинации и формулы для их подсчета

Основными комбинациями, рассматриваемыми в комбинаторике, являются комбинации без повторений и с повторениями. Это перестановки, размещения и сочетания.

Пусть некоторое множество X состоит из n элементов. Будем переставлять элементы этого множества всевозможными способами, оставляя неизменным их число и меняя лишь их порядок. Получим различные упорядоченные множества, составленные из n элементов множества X. Каждая из полученных комбинаций (в т. ч. и первоначальная) носит название перестановки. Общее число перестановок из n элементов обозначается Pn и вычисляется по формуле:

где n! («эн факториал») – это произведение всех натуральных чисел от 1 до n, т. е. n! = 1 · 2 · 3 ·. . . · n. Следует отметить, что 0! = 1.

Каждое упорядоченное подмножество n-элементного множества X, состоящее из k элементов, называется размещением из n элементов по k элементов. Через Ak n обозначают число всех размещений из n элементов по k (читается: «A из n пo k»). Для числа размещений справедлива формула:

Кортеж длины k, составленный из элементов n-элементного множества X, называют размещением с повторениями из n элементов по k. Число таких кортежей обозначают Ak n и вычисляют по формуле:

Сочетанием из n элементов по k элементов называется каждое неупорядоченное k-элементное подмножество множества X, состоящего из n элементов. Число всех сочетаний из n элементов по k элементов обозначается C k n («C («цэ») из n по k»). Для числа сочетаний справедливы формулы:

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

Примеры:

1. Пусть в группе 25 студентов. Сколькими способами могут быть выбраны из этой группы три делегата на конференцию?

Последовательность выбора делегатов не играет роли, поэтому здесь необходимо составить из имеющихся 25 элементов множества студентов различные трехэлементные подмножества. Это сочетания из 25 по 3:

2. Сколько существует способов распределения призовых мест на олимпиаде среди 25 участников? Необходимо составить различные упорядоченные трехэлементные подмножества из элементов 25-элементного множества. Это размещения без повторений из 25 по 3:

3. Сколькими способами можно составить список из 25 студентов?

В задаче необходимо найти число различных упорядоченных множеств из 25 элементов, т. е. число перестановок из 25 элементов:

4. Сколькими способами группе студентов из 25 человек могут быть выставлены экзаменационные оценки в ведомости, если известно, что неудовлетворительной оценки не получил никто?

Все удовлетворительные оценки – это 4, 5, 6, 7, 8, 9, 10. Их семь. Значит, необходимо составить различные кортежи длины 25 из элементов семиэлементного множества. Число таких кортежей – это число размещений с повторениями из семи элементов по 25: