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

Упорядоченным называется множество, в котором указан порядок следования элементов.

ПРИМЕР: Множества (a, b, c) и (a, c, b) есть различные упорядо­чен­ные множества, состоящие из одних и тех же трех элементов.

Сформулируем основные правила комбинаторики.

1. Правило суммы. Пусть из множества А элемент а₁ можно выбрать n₁ способами, элемент а₂ – другими n₂ способами, а элемент а₃ – n₃ способами, отличными от предыдущих. Тогда выбор одного из элементов а₁, или а₂, или а₃ можно осуществить (n₁ + n₂ + n₃) способа­ми.

ПРИМЕР: Пусть в корзине содержится 7 апельсинов, 5 бананов и 10 яблок. Тогда выбор одного из фруктов (или апельсина, или банана, или яблока) можно сделать 22 способами (7 + 5 + 10 = 22).

2. Правило произведения. Пусть из множества А элемент а₁ можно выбрать n₁ способами, а после этого выбор элемента а₂ можно осуществить n₂ способами, а после этого выбор элемента а₃ можно осуществить n₃ способами. Тогда все три элемента в указанном порядке могут быть выбраны способами.

ПРИМЕР: Пусть в спортивном велосипеде имеются 3 ведущие звездочки и 4 ведомые. Сколько всего передач имеется в велосипеде?

Очевидно, что каждая передача определяется выбором одной ведущей и одной ведомой звездочки. Следовательно, число всех передач совпадает с числом выборов одного элемента из трех и другого элемента из четырех и равно: 3 ∙ 4 = 12.

Пусть некоторое множество А содержит n элементов. Каждое его упорядоченное подмножество, состоящее из k элементов, называется размещением из n элементов по k элементов. Число всех таких размещений обозначается (читается: «А из эн по ка») и определя­ется по формуле: .

ПРИМЕР: Сколько сигналов можно составить из 6 флажков различного цвета, взятых по два?

Очевидно, что два разноцветных флажка в разном порядке будут соответствовать двум различным сигналам. Поэтому искомое число есть число размещений из 6 по 2, т.е.

Размещение из n элементов по n элементов называется пере­становками из n элементов. Число всех таких перестановок обозначается и определяется по формуле: .

ПРИМЕР: Сколько трехзначных чисел можно образовать из цифр 1, 2 и 3, если каждая из них может входить в изображение числа только один раз?

Очевидно, что искомое число есть число перестановок из 3 элементов, равное: .

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

ПРИМЕР: Сколькими способами можно выбрать два шара из ящика, содержащего 8 шаров?

Очевидно, что искомое число способов будет равно числу сочетаний из 8 элементов по 2 элемента, т.е.

Достаточно несложно (убедитесь в этом сами) показать справедливость еще одной полезной формулы комбинаторики:

.