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

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

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

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

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

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

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

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

Pn = 1․2․ 3... n= n!

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

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

Cnm = Комбинаторика. Рис. 2

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

(a+b) n=Cn0 an + Cn1 an-1b +Cn2an-2b2 +... + Cnn-1abn-1 + Cnn bn,

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

Cnm=Cnn-m, Cnm + Cnm+1 = Cn+1m+1

Cn0 + Cn1 + Cn2 +...+ Cnn-1 + Cnn =2n,

Cn0Cn1 + Cn2 —...+ (—1) nCnn = 0.

Числа Anm, Pm и Cnm связаны соотношением:

Anm=Pm Cnm.

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

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

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

Принцип включения и исключения. Пусть имеется N предметов, которые могут обладать n свойствами α1, α2,..., αn. Обозначим через Ni, αj,..., αk) число предметов, обладающих свойствами αi, αj,..., αk и, быть может, какими-либо другими свойствами. Тогда число N' предметов, не обладающих ни одним из свойств, α1, α2,..., αn, даётся формулой

Комбинаторика. Рис. 3

= N—N1) — N2) —... —Nn) + N1, α2) + N1, α3) +... + Nn-1, αn) — N1, α2, α3) —... — Nn-2, αn-1, αn) +... +(—1) n N1,..., αn)

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

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

Источник: Большая советская энциклопедия на Gufo.me


Значения в других словарях

  1. Комбинаторика — См. Комбинаторный анализ. Математическая энциклопедия
  2. комбинаторика — Комбин/ато́р/ик/а. Морфемно-орфографический словарь
  3. комбинаторика — орф. комбинаторика, -и Орфографический словарь Лопатина
  4. комбинаторика — КОМБИНАТОРИКА -и; ж. [лат. combinare — соединять] Раздел математики, изучающий все возможные способы простейших перестановок элементов, цифр, каких-л. данных. Толковый словарь Кузнецова
  5. комбинаторика — [< лат. combinare соединять, сочетать] – отдел математики, изучающий приёмы вычисления числа различных соединений (комбинаций): перестановок, размещений, сочетаний, составляемых при определённых условиях из данных предметов; например... Большой словарь иностранных слов
  6. комбинаторика — комбинаторика ж. Раздел математики, изучающий различного рода соединения элементов: перестановки, сочетания, размещения. Толковый словарь Ефремовой
  7. КОМБИНАТОРИКА — КОМБИНАТОРИКА — раздел математики, в котором изучаются простейшие "соединения". Перестановки — соединения, которые можно составить из n предметов, меняя всеми возможными способами их порядок; число ихРазмещения — соединения... Большой энциклопедический словарь
  8. комбинаторика — КОМБИНАТОРИКА, и, ж. Раздел дискретной математики, изучающий всевозможные сочетания и расположения предметов. | прил. комбинаторный, ая, ое. К. анализ. Толковый словарь Ожегова