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

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

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

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

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

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

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

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

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

 С"¹ наз. числом сочетаний из п элементов по т. Числа С"¹ получаются как коэффициенты разложения п-й степени двучлена (бинома, см. Ньютона бином):

и поэтому они наз. также биномиальными коэффициентами. Осн. соотношения для биномиальных коэффициентов:

Числа А^т, Р_га и С™ связаны соотношением:

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

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

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

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

Принцип включения и исключения. Пусть имеется N предметов, к-рые могут обладать п свойствами a₁, a₂,..., а_n. Обозначим через N(ai, аj, ..., а_k) число предметов, обладающих свойствами a_i, a_j, ..., а_k и, быть может, к.-л. др. свойствами. Тогда число N' предметов, не обладающих ни одним из свойств, a₁, a₂, ..-, а_n, даётся формулой

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

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