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

Значение слова Комбинаторика по Ефремовой:
Комбинаторика - Раздел математики, в котором изучаются различного рода соединения элементов: перестановки, сочетания, размещения.

Комбинаторика в Энциклопедическом словаре:
Комбинаторика - раздел математики, в котором изучаются простейшие''соединения''. Перестановки - соединения, которые можно составить из nпредметов, меняя всеми возможными способами их порядок; число ихРазмещения- соединения, содержащие по m предметов из числа n данных, различающиесялибо порядком предметов, либо самими предметами; число ихСочетания -соединения, содержащие по m предметов из n, различающиеся друг от друга,по крайней мере, одним предметом; число ихКОМБИНАТОРНЫЙ АНАЛИЗ - раздел математики, в котором изучаются вопросы,связанные с размещением и взаимным расположением частей конечногомножества объектов произвольной природы.

Определение слова «Комбинаторика» по БСЭ:
Комбинаторика - 1) то же, что математический Комбинаторный анализ. 2) Раздел элементарной математики, связанный с изучением количества комбинаций, подчинённых тем или иным условиям, которые можно составить из заданного конечного множества объектов (безразлично, какой природы; это могут быть буквы, цифры, какие-либо предметы и т.п.).
Наиболее употребительные формулы К.:
Число размещений. Пусть имеется n различных предметов. Сколькими способами можно выбрать из них m предметов (учитывая порядок, в котором выбираются предметы)? Число способов равно
A_n^m = n(n−1)(n−2)...(n−m+1).
A_n^m называют числом размещений из n элементов по m.
Число перестановок. Рассмотрим задачу: сколькими способами можно установить порядок следования друг за другом n различных предметов? Число способов равно
P_n = 1·2· 3... n = n!
(знак n! читается: «n факториал»; оказывается удобным рассматривать также 0!, полагая его равным 1). P_n называют числом перестановок n элементов.
Число сочетаний. Пусть имеется n различных предметов. Сколькими способами можно выбрать из них m предметов (безразлично, в каком порядке выбираются предметы)? Число способов такого выбора равно

Cnm =

n(n−1)(n−2)...(n−m+1) 1·2·3·...·m

=

n! m!(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ⁿ⁻¹ + 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_n+m−1^m.
Основные правила при решении задач К.:
Правило суммы. Пусть некоторый предмет A может быть выбран из совокупности предметов m способами, а другой предмет В можно выбрать n способами. Тогда имеется т + n возможностей выбрать либо предмет A, либо предмет В.
Правило произведения. Пусть предмет A можно выбрать m способами и после каждого такого выбора предмет В можно выбрать n способами; тогда выбор пары (А, В) в указанном порядке можно осуществить m + n способами.
Принцип включения и исключения. Пусть имеется N предметов, которые могут обладать n свойствами α₁, α₂,..., α_n. Обозначим через N (α_i, α_j,..., α_k) число предметов, обладающих свойствами α_i, α_j,..., α_k и, быть может, какими-либо другими свойствами.
Тогда число N предметов, не обладающих ни одним из свойств, α₁, α₂,..., α_n, даётся формулой
N′ = N − N(α₁) − N(α₂) −... −N(α_n) +

+ N (α₁, α₂) + N(α₁, α₃) + ... + N(α_n−1, α_n) −

− N(α₁, α₂, α₃) −... − N(α_n−2, α_n−1, α_n) +

+... +(−1)ⁿ N(α₁,..., α_n)
Лит.: Netto E. Lehrbuch der Combinatorik, 2 Aufl., Lpz. - B., 1927.
В. Е. Тараканов.

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