Большая Советская Энциклопедия (КО) - Большая Советская Энциклопедия "БСЭ" - Страница 183

183

Комбинат бытового обслуживания

Комбина'т бытово'го обслу'живания, см. в ст. Бытовое обслуживание .

Комбинатор гидротурбин

Комбина'тор гидротурби'н, устройство для регулирования взаимного расположения лопастей рабочего колеса и лопаток направляющего аппарата ; применяется в реактивных гидротурбинах двойного регулирования. Наиболее благоприятное для кпд взаимное расположение лопаток и лопастей определяется по диаграмме — комбинаторной кривой. К. г. позволяет получать максимальный кпд турбины при изменении режима её работы (напора, расхода, мощности).

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

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

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

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

  An m =

 

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

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

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

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

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

  Cn m =

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

  (a+b) n =Cn an + Cn 1 an-1 b +Cn 2 an-2 b2   +... + Cn n-1 abn-1 + Cn n bn ,

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

  Cn m =Cn n-m , Cn m  + Cn m+1 = Cn+1 m+1

  Cn + Cn 1 + Cn 2 +...+ Cn n-1 + Cn n = 2n ,

  Cn — Cn 1 + Cn 2 —...+ (—1) n Cn n = 0.

  Числа An m , Pm и Cn m связаны соотношением:

  An m =Pm Cn m .

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

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

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

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

 

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

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

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

Комбинаторная логика

Комбинато'рная ло'гика, ветвь математической логики, изучающая комбинаторы и их свойства. В качестве основных понятий в К. л. выбираются функция и операция применения функции к аргументу (аппликация). Комбинаторами называют члены некоторого класса операций над функциями, замкнутого относительно аппликации. Сформулированное в терминах К. л. понятие «комбинаторно определимой функции» явилось одним из первых способов уточнения понятия алгоритма. Начало К. л. положено работой советского математика М. И. Шейнфинкеля (1924), большая часть результатов принадлежит американскому логику Х. Карри. К. л. находит широкое применение в теории языков программирования.

  Лит.: Яновская С. А., Логика комбинаторная, в кн.: Философская энциклопедия, т. 3, М., 1964; SchonfinkeI М., Uber die Bausteine der mathema-tischen Logik, «Mathematische Annalen», 1924, Bd 92; Curry H. B., Feys R., Combinatory logic, Amst., 1958; Curry H. B., Recent advances in combinatory logic, «Bulletin de la Societe mathematique de Belgique», 1968, t. 20, № 3.