|
|
Большая Советская Энциклопедия (цитаты)
|
|
|
|
|
Комбинаторика | Комбинаторика (далее К) 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, nm + nm+1 = n+1m+1
n0 + n1 + n2 +...+ nn-1 + nn =2n,
n0 — n1 + 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.
В. Е. Тараканов. |
Для поиска, наберите искомое слово (или его часть) в поле поиска
|
|
 |
 |
 |
|
|
|
Новости 12.01.2025 15:13:18
|
|
|
|
|
|
|
|
|
|
|
