Большая советсткая энциклопедия Комбинаторика

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

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

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

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

A_n^m =  

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

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

P_n = 1SYMBOL 215 \f "Symbol" \s 12Ч2SYMBOL 215 \f "Symbol" \s 12Ч 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-1b +C_n²a^n-2b²  +... + C_n^n-1ab^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₂,..., SYMBOL 97 \f "Symbol" \s 12a_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.

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