БСЭ. Комбинаторика
Начало Вверх

КОМБИНАТОРИКА, 1) то же, что матем. комбинаторный анализ. 2) Раздел элементарной математики, связанный с изучением количества комбинаций, подчинённых тем или иным условиям, к-рые можно составить из заданного конечного множества объектов (безразлично, какой природы; это могут быть буквы, цифры, к.-л. предметы и т. п.).

Наиболее употребительные формулы К.:

Число размещений. Пусть имеется п различных предметов. Сколькими способами можно выбрать из них т предметов (учитывая порядок, в к-ром выбираются предметы)? Число способов равно

Ат~п(п- 1)(п-2)...(n-т + 1).

Ат наз. числом размещений из n элементов по т.

Число перестановок. Рассмотрим задачу: сколькими способами можно установить порядок следования друг за другом п различных предметов? Число способов равно

Рn=1-2-3...n = n!

(знак n! читается: "n факториал"; оказывается удобным рассматривать также 0!, полагая его равным 1). Рn наз. числом перестановок n элементов.

Число сочетаний. Пусть имеется п различных предметов. Сколькими способами можно выбрать из них т предметов (безразлично, в каком порядке выбираются предметы)? Число способов такого выбора равно
11-5.JPG
 С"1 наз. числом сочетаний из п элементов по т. Числа С"1 получаются как коэффициенты разложения п-й степени двучлена (бинома, см. Ньютона бином):
11-6.JPG
и поэтому они наз. также биномиальными коэффициентами. Осн. соотношения для биномиальных коэффициентов:

11-7.JPG

Числа Ат, Рга и С™ связаны соотношением:
11-8.JPG

Рассматриваются также размещения с повторением (т. е. всевозможные наборы из т предметов п различных видов, порядок в наборе существен) и сочетания с повторением (то же, но порядок в наборе не существен). Число размещений с повторением даётся формулой п'", число сочетаний с повторением - формулой Сmn+m-1

Осн. правила при решении задач К.:

Правило суммы. Пусть нек-рый предмет А может быть выбран из совокупности предметов т способами, а другой предмет В можно выбрать n способами. Тогда имеется т + и возможностей выбрать либо предмет A, либо предмет В.

Правило произведения. Пусть предмет А можно выбрать т способами и после каждого такого выбора предмет В можно выбрать n способами; тогда выбор пары (А, В) в указанном порядке можно осуществить тп способами.

Принцип включения и исключения. Пусть имеется N предметов, к-рые могут обладать п свойствами a1, a2,..., аn. Обозначим через N(ai, аj, ..., аk) число предметов, обладающих свойствами ai, aj, ..., аk и, быть может, к.-л. др. свойствами. Тогда число N' предметов, не обладающих ни одним из свойств, a1, a2, ..-, аn, даётся формулой
11-9.JPG

Лит.: Netto E., Lehrbuch der Combinatorik, 2 Aufl., Lpz.- В., 1927.

В. Е. Тараканов.

Яндекс.Метрика

© (составление) libelli.ru 2003-2016