Большая Советская Энциклопедия (цитаты)

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

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

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

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

  Anm =  

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

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

  n = 1Ч2Ч 3... n= n!

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

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

  nm =

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

  (a+b) n=n0 an + n1 an-1b +n2an-2b2  +... + nn-1abn-1 + nn bn,

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

  nm=nn-m, n+ nm+1 = n+1m+1

  n0 + n1 + n2 +...+ nn-1 + nn =2n,

  n0n1 + n2 —...+ (—1) nnn = 0.

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

  Anm=m nm.

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

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

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

  Принцип включения и исключения. Пусть имеется предметов, которые могут обладать n свойствами a1, a2,..., an. Обозначим через (ai, aj,..., ak) число предметов, обладающих свойствами ai, aj,..., ak и, быть может, какими-либо другими свойствами. Тогда число " предметов, не обладающих ни одним из свойств, a1, a2,..., an, дается формулой

   = — (a1)(a2) —... — (an) + (a1, a2) + (a1, a3) +... + (an-1, an) — (a1, a2, a3) —... — (an-2, an-1, an) +... +(—1) n (a1,..., an)

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

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


Для поиска, наберите искомое слово (или его часть) в поле поиска


Новости 29.03.2024 07:34:45