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

Комбинаторика, 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^{2 ?}+... + 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.
? В. Е. Тараканов.