Большая Советская Энциклопедия (КО)

Комбинаторика

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

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

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

A_n ^m =

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

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

P_n = 1Ч2Ч 3... n= n!

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

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

C_n ^m =

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

(a+b) ⁿ =C_n ⁰ aⁿ + C_n ¹ a^n-1 b +C_n ² a^n-2 b² +... + C_n ^n-1 ab^n-1 + C_n ⁿ bⁿ ,

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

C_n ^m =C_n ^n-m , C_n ^m + C_n ^m+1 = C_n+1 ^m+1

C_n ⁰ + C_n ¹ + C_n ² +...+ C_n ^n-1 + C_n ⁿ = 2ⁿ ,

C_n ⁰ — C_n ¹ + C_n ² —...+ (—1) ⁿ C_n ⁿ = 0.

Числа A_n ^m , P_m и C_n ^m связаны соотношением:

A_n ^m =P_m C_n ^m .

Рассматриваются также размещения с повторением (т. е. всевозможные наборы из m предметов n различных видов, порядок в наборе существен) и сочетания с повторением (то же, но порядок в наборе не существен). Число размещений с повторением даётся формулой n^m , число сочетаний с повторением — формулой C^m _{n +m -1} .

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

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

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

= N—N (a₁ ) — N (a₂ ) —... —N (a_n ) + N (a₁ , a₂ ) + N (a₁ , a₃ ) +... + N (a_n-1 , a_n ) — N (a₁ , a₂ , a₃ ) —... — N (a_n-2 , a_n-1 , a_n ) +... +(—1) ⁿ N (a₁ ,..., a_n )

Лит.: Netto E. Lehrbuch der Combinatorik, 2 Aufl., Lpz. — B., 1927.

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