Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л

N= .

Перечислительная комбинаторика или теория перечислений изучает числа способов построения кортежей из элементов конечного множества. Простейшими такими кортежами являются размещения, перестановки, сочетания.

Пусть А — конечное множество, состоящее из п элементов.

Размещениями из п элементов множества А по k называются кортежи длины k, состоящие из различных элементов n-элементного множества А, отличающиеся один от другого как самими элементами, так и их порядком. Число таких размещений обозначается (буква А от французского слова arrangement — размещение). Размещениям соответствует схема выбора k элементов из n-элементного множества без возвращения. При этом необходимо совершить k действий, причем первое действие можно совершить п способами, второе способами и т. д., k-e действие способами. Согласно комбинаторному правилу умножения, получим формулу: .

Если умножить и разделить полученное выражение на получим:

где называется факториалом числа п (читается n-факториал). Отметим, что и т.д.

Пример 2.1. Для множества выпишем все размещения из трех элементов по два: .

Число размещений определяется по формуле

.

Перестановками из элементов множества А называются кортежи длины , состоящие из различных элементов n-элементного множества А. Эти кортежи будут отличаться друг от друга только порядком следования элементов, поскольку в каждом из них встречаются по одному разу все элементы множества А. Перестановки обозначаются (от английского слова permutation— перестановка). Поскольку , то число перестановок вычисляется по формуле .

Пример 2.2. Для множества выпишем все возможные перестановки из трех элементов: .

Число перестановок определяется по формуле

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

Число сочетаний по k меньше числа размещений из п элементов по k в раз, т. е.

.

Таким образом, имеем

.

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

Пример 2.3. Для множества выпишем все сочетания из трех элементов по два: .

Число сочетаний определяется по формуле

.

Непосредственной проверкой легко доказать следующие тождества:

a) , где .

Действительно:

.

б) .

Данное тождество доказывается аналогичным образом:

С числами связано функциональное тождество, называемое формулой бинома Ньютона. Известные из элементарной математики формулы сокращенного умножения:

можно переписать с использованием сочетаний так:

.

В общем случае справедливо тождество, известное как биномом Ньютона:

,

Где коэффициенты называются биномиальными коэффициентами.

Если положить то из формулы бинома Ньютона вытекает соотношение: — формула суммы биномиальных коэффициентов.

Если положить в биноме Ньютона , то

.

Поскольку , то биномиальные коэффициенты, равноотстоящие от концов в формуле бинома Ньютона, равны.

Все приведенные формулы для размещений, сочетаний и перестановок справедливы в том случае, когда п элементов множества А различны. Если же некоторые элементы повторяются, то в этом случае рассматриваются комбинации с повторениями, число которых вычисляется по другим формулам.

Размещениями с повторениями из п элементов по k называются кортежи длины k, составленные из п — элементного множества А. Число этих кортежей обозначают и равно

Черта указывает на возможность повторения элементов в размещении.

Пример 2.4. Для множества вычислим количество размещений с повторениями, т.е. определим, сколько пятизначных номеров можно составить из элементов множества ? Такими номерами являются кортежи длины 5, составленные из семиэлементного множества, где схема выбора состоит в выборе 5 элементов из семиэлементного множества с возвращением, т.е. для каждого из пяти элементов есть семь способов выбора, т. е. .

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

.

Пример 2.5. Сколько вариантов слов можно получить, переставляя буквы в слове «математика»? Слово «математика» является кортежем длины 10, имеющем состав (2, 3, 2,1,1,1) (буква «м» входит два раза, буква «а» входит 3 раза, буква «т» входит два раза, буквы «е», «и», «к» входят по одному разу). Таким образом, число вариантов, возникающих при перестановках букв, равно

.

Рассмотрим сочетания с повторениями. Пусть имеются предметы п видов и из них составляется набор, содержащий k элементов, т. е. различными исходами будут всевозможные наборы длины k, отличающиеся составом, и при этом отдельные наборы могут содержать повторяющиеся элементы. Такие наборы называются сочетаниями с повторениями, а их общее число определяется формулой:

.

Пример 2.6. Сколько наборов из 7 пирожных можно составить, если в продаже имеются 4 сорта?

Искомое число равно .