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

        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-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 свойствами α₁, α₂,..., α_n. Обозначим через N (α_i, α_j,..., α_k) число предметов, обладающих свойствами α_i, α_j,..., α_k и, быть может, какими-либо другими свойствами. Тогда число 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.

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