Основные комбинаторные конфигурации

1. Среди основных задач комбинаторики выделяют следующие: пересчет, перечисление, классификация и оптимизация. Если требуется определить количество элементов, обладающих некоторым свойством или совокупностью свойств, то это задача пересчета. Если при этом необходимо указать список элементов, то это задача перечисления. Если пересчет приводит к слишком большим числам, то отказываются от соответствующего перечисления и только классифицируют элементы с помощью какого-нибудь соотношения, - и тогда это задача классификации. В некоторых задачах на множестве решений можно ввести функцию величины и относительно этой функции рассматривать задачу оптимизации: найти экстремум функции на определенном множестве объектов, либо указать все или некоторые объекты, для которых достигается экстремальное значение.

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

Набор (множество или кортеж) элементов 

составленный из элементов множества  , называется выборкой объема k из n элементов,или (n,k –выборкой).Выборки, различающиеся составом элементов, всегда считаются различными.

Выборка называется упорядоченной,если порядок элементов в ней задан (т.е. она представляет из себя кортеж). Две упорядоченные выборки, различающиеся только порядком следования элементов, считаются различными. Если порядок элементов в выборке несуществен, то выборка называется неупорядоченной.

Упорядоченная (n,k)-выборка, в которой элементы могут повторяться, называется (n,k)-размещением с повторениями,или размещением с повторениями из n элементов по k.Если элементы (n,k)-выборки попарно различны, то она называется (n, k)- размещением без повторений,или размещением без повторений из n элементов по k.

ГЛАВА 5     Комбинаторика

Предмету комбинаторики не так просто дать краткое исчерпывающее определе­ние. В некотором смысле слово «комбинаторика» можно понимать как синоним термина «дискретная математика», то есть исследование дискретных конечных математических структур.

Вычисления на дискретных конечных математических струк­турах, которые часто называют комбинаторными вычислениями, требуют комби­наторного анализа для установления свойств и выявления оценки применимости используемых алгоритмов. Рассмотрим элементарный жизненный пример.

Пример

Пусть некоторое агентство недвижимости располагает базой данных из п запи­сей, причем каждая запись содержит одно предложение (что имеется) и один запрос (что требуется) относительно объектов недвижимости. Требуется найти все такие пары записей, в которых предложение первой записи совпадает с запро­сом второй, и, наоборот, предложение второй записи совпадает с запросом пер­вой. (На бытовом языке это называется подбором вариантов обмена.) Допустим, что используемая СУБД позволяет проверить вариант за одну миллисекунду. Нетрудно сообразить, что при «лобовом» алгоритме поиска вариантов (каждая запись сравнивается с каждой) потребуется (п* (п — 1))/2 сравнений. Если п = 100, то все в порядке — ответ будет получен за 4,95 секунды. Но если п = 100 000 (более реальный случай), то ответ будет получен за 4 999 950 секунд, что соста­вляет без малого 1389 часов и вряд ли может считаться приемлемым. Обратите внимание, что мы оценили только трудоемкость подбора прямых вариантов, а существуют еще варианты, когда число участников сделки больше двух ...

Этот пример показывает, что комбинаторные вычисления требуют предваритель­ного анализа и количественной оценки исходных задач и используемых алго­ритмов. Задачи обычно оцениваются с точки зрения размера, то есть общего количества различных вариантов, среди которых нужно найти решение, а алго­ритмы оцениваются с точки зрения сложности.При этом различают сложность по времени (или временную сложность), то есть количество необходимых шагов алгоритма, и сложность по памяти (или ёмкостную сложность), то есть объем памяти, необходимый для работы алгоритма.

Во всех случаях основным инструментом такого анализа оказываются формулы и методы, рассматриваемые в этой главе.

5.1. Комбинаторные конфигурации

Во многих практических случаях возникает необходимость подсчитать количе­ство возможных комбинаций объектов, удовлетворяющих определенным усло­виям. Такие задачи называются комбинаторными. Разнообразие комбинаторных задач не поддается исчерпывающему описанию, но среди них есть целый ряд особенно часто встречающихся, для которых известны способы подсчета.

5.1.1. Комбинаторные задачи

Для формулировки и решения комбинаторных задач используются различные модели комбинаторных конфигураций. Рассмотрим следующие две наиболее по­пулярные.

1. Дано п предметов. Их нужно разместить по m ящикам так, чтобы выполнялись заданные ограничения. Сколькими способами это можно сделать?

2. Рассмотрим множество функций

F:X®Y,     где |Х| = n,|Y| = m, X = {1,...,n}.

 Не ограничивая общности, можно считать, что

Y={1,…,m},F=<F(1),…,F(n)>,1

Сколько существует функций F, удовлетворяющих заданным ограничениям?

ЗАМЕЧАНИЕ —————————————————————————————————————

Большей частью соответствие конфигураций, описанных на «языке ящиков» и на «язы­ке функций», очевидно, поэтому доказательство правильности способа подсчета (вывод формулы) можно провести на любом языке. Если сведение одной модели к другой не очевидно, то оно включается в доказательство.

5.1.2. Размещения

Число всех функций (при отсутствии ограничений), или число всех возможных способов разместить п предметов по m ящикам называется, числом размещений и обозначаетсяU(m,n).

ТЕОРЕМА    U (т, п) = т^п.

ДОКАЗАТЕЛЬСТВО

Каждый из n предметов можно разместить m способами.

Пример

При игре в кости бросаются две кости и выпавшие на верхних гранях очки скла­дываются. Какова вероятность выбросить 12 очков? Каждый возможный исход соответствует функции F: {1,2} ® {1,2.3,4,5,6} (аргумент — номер кости, ре­зультат — очки на верхней грани).

Таким образом, всего возможно U(6,2) = б² = 36 различных исходов. Из них только один (6 + 6) дает двенадцать очков. Вероятность 1/36.

5.1.3. Размещения без повторений

Число инъективных функций, или число всех возможных способов разместить п предметов по m ящикам, не более чем по одному в ящик, называется числом размещений без повторений и обозначается A(m,n) или [т]п, или (m)n.

ТЕОРЕМА    

ДОКАЗАТЕЛЬСТВО

Ящик для первого предмета можно выбрать m способами, для второго — т — 1 способами, и т. д. Таким образом,

По определению считают, что A(m,n) :=0 при n>m и  A(m,0):=1.

Пример

В некоторых видах спортивных соревнований исходом является определение участников, занявших первое, второе и третье места. Сколько возможно раз­личных исходов, если в соревновании участвуют n участников? Каждый воз­можный исход соответствует функции F: {1,2,3} ® {l..n} (аргумент — номер призового места, результат — номер участника). Таким образом, всего возможно A(n,3) = n(n — 1)

(n — 2) различных исходов.

5.1.4. Перестановки

Число взаимнооднозначных функций, или число перестановок п предметов, обо­значается Р(п).

ТЕОРЕМА    Р(n) = n!

ДОКАЗАТЕЛЬСТВО

Р(n) = А(n,n) = n • (n - 1) • • • • • (n - n + 1) = n • (n - 1) •. . . • 1 = n!.

Пример

Последовательность e= (E1,...,E_m) непустых подмножеств множества Е

(eÌ 2Е, Ei Ì Е, Ei ¹ Ø) называется цепочкой в Е, если

"i Î l..m - 1 Ei Ì Ei+1&Ei ¹ Ei+1.

Цепочка  e называется полной цепочкой в Е, если |e| = |Е|. Сколько существует полных цепочек? Очевидно, что в полной цепочке каждое следующее подмноже­ство Ei+1 получено из предыдущего подмножества Ei добавлением ровно одного элемента из Е и, таким образом, |E1| = 1, |Е2| = 2, ..., |Еm| = |Е| = m. Следова­тельно, полная цепочка определяется порядком, в котором элементы Е добавля­ются для образования очередного элемента полной цепочки. Отсюда количество полных цепочек — это количество перестановок элементов множества Е, рав­ное m!.

5.1.5. Сочетания

Число строго монотонных функций, или число размещений n неразличимых предметов по m ящикам, не более чем по одному в ящик, то есть число способов выбрать из m ящиковn ящиков с предметами, называется числом сочетаний и обозначается

ТЕОРЕМА    

ДОКАЗАТЕЛЬСТВО

1. Число размещений без повторений нужно разделить на число перестановок, поскольку предметы неразличимы.

2. Число сочетаний является числом строго монотонных функций, потому что
строго монотонная функция F: 1..n ® 1..m определяется набором своих

    зна­чений, причем 1  F(l) < • • • < F(n)  m. Другими словами, каждая строго
монотонная функция определяется выбором n чисел из диапазона 1..m.

   Та­ким образом, число строго монотонных функций равно числу n-элементных
подмножеств m-элементного множества, которое, в свою очередь, равно числу
способов выбрать n ящиков с предметами из m ящиков.               

По определению С(m, n): = 0 при n > m.

Пример

В начале игры в домино каждому играющему выдается 7 костей из имеющихся 28 различных костей. Сколько существует различных комбинаций костей, которые игрок может получить в начале игры? Очевидно, что искомое число равно числу 7-элементных подмножеств 28-элементного. Имеем:

5.1.6. Сочетания с повторениями

Число монотонных функций, или число размещений п неразличимых предме­тов по m ящикам, называется числом сочетаний с повторениями и обозначается V(m, n).

ТЕОРЕМА V(m,n)=C(n+m-1,n).

ДОКАЗАТЕЛЬСТВО

Монотонной функции

f : {1, . . . , n} ® {1, . . . , m}

однозначно соответствует стро­го монотонная функция

f': {1,...,п} ®  {1, . .. ,n+ m - 1}.

Это соответствие устанавливается следующей процедурой.

f'(1) : =f(1) { первые элементы совпадают }

 for i from 2 to n do

 if f(i) = f(i - 1) then

  f’(i) = f(i - 1) +1{плато}

 else

f'(i) : = f'(i - 1) + f(i) - f(i - 1) { подъем }
end if
end for

Пример

Сколькими способами можно рассадить п вновь прибывших гостей среди m го­стей, уже сидящих за круглым столом? Очевидно, что между m сидящими за круглым столом гостями имеется т промежутков, в которые можно рассаживать вновь прибывших.

Таким образом, это можно сделать

КОМБИНАТОРНЫЙ АНАЛИЗ

комбинаторная математика, комбинаторика,- раздел математики, посвященный решению задач выбора ирасположения элементов нек-рого, обычно конечного, множества в соответствии с заданными правилами.Каждое такое правило определяет способ построения нек-рой конструкции из элементов исходногомножества, называемой комбинаторной конфигурацией. Поэтому можно сказать, что целью К. а. являетсяизучение комбинаторных конфигураций. Это изучение включает в себя вопросы существованиякомбинаторных конфигураций, алгоритмы их построения, оптимизацию таких алгоритмов, а также решениезадач перечисления, в частности определение числа конфигураций данного класса. Простейшими примерамикомбинаторных конфигураций являются перестановки, сочетания и размещения.

Множество Xиз пэлементов наз. n-м ножеством; любое его m-подмножество,наз. сочетанием объемат. Число сочетаний объема тиз празличных элементов равно

Имеет место формула:

обычно называемая формулой бинома Ньютона. Числа наз. биномиальными коэффициентами.Упорядоченное m-подмножество наз. размещением объема т. Число размещений объема тиз празличныхэлементов равно

При т= п размещение представляет собой перестановку элементов множества X, причем число такихперестановок равно Р(п) = п!

Возникновение основных понятий и развитие К. а. шло параллельно с развитием других разделовматематики, таких, как алгебра, теория чисел, теория вероятностей, с к-рыми К. а. тесно связан. Ещематематикам Древнего Востока были известны формула, выражающая число сочетаний через биномиальныекоэффициенты, и формула бинома Ньютона с натуральным показателем п. С мистическими целямиизучались магические квадраты3-го порядка. Рождение К. а. как раздела математики связано с трудами Б.Паскаля (В. Pascal) и П. Ферма (P. Fermat) по теории азартных игр. Этн труды, составившие основу теориивероятностей, одновременно содержали принципы определения числа комбинаций элементов конечногомножества, устанавливая тем самым ставшую затем традиционной связь К. а. с теорией вероятностей.

Большой вклад в систематическое развитие комбинаторных методов был сделан Г. Лейбницем (G. Leibniz) вего диссертации "Ars Combinatoria" ("Комбинаторное искусство"), где, по-видимому, впервые появился термин"комбинаторный". Большое значение для становления К. а. имела работа Я. Бернулли (J. Bernoulli) "Arsconjectandi" ("Искусство предположений"), посвященная основным понятиям теории вероятностей, гдеобстоятельно изложен ряд комбинаторных понятий и указаны их применения для вычисления вероятностей.Можно считать, что с появлением работ Г. Лейбница и Я. Бернулли комбинаторные методы выделились всамостоятельную часть математики.

Большой вклад в развитие комбинаторных методов сделал Л. Эйлер (L. Euler). В его работах по разбиениям икомпозициям натуральных чисел на слагаемые было положено начало одному из основных методовперечисления комбинаторных конфигураций - методу производящих функций.

Возрождение интереса к К. а. относится к 50-м гг. 20 в. в связи с бурным развитием кибернетики и дискретнойматематики и широким использованием электронно-вычислительной техники. В этот период активизировалсяинтерес к классическим комбинаторным задачам.

На формирование направлений исследований в дальнейшем оказывают влияние два фактора. С однойстороны, выбор объектов исследований, с другой стороны - формулировка целей исследования, зависящая вконечном счете от сложности изучаемых объектов. Если исследуемая комбинаторная конфигурация имеетсложный характер, то целью исследования является выяснение условий ее существования и разработкаалгоритмов построения.

Большой развивающийся раздел К. а. составляет теория блок-схем (см. также [2], [3], [10]); основныепроблемы этого раздела связаны с вопросами классификации, условиями существования и методамипостроения нек-рых классов блок-схем. Частным случаем блок-схем являются так наз. уравновешенныенеполные блок-схемы, или (b, v, r, k,l)-конфигурации, к-рые определяются как совокупности из bk-подмножествнек-рого v-множества, называемых блоками, с условием, что каждый элемент появляется в r блоках, а каждаяпара элементов - в l блоках. При b=vи, следовательно, r=k(b, v, r, k,l)-конфигурацня наз. (v, k,l)-конфигурацией,или симметричной уравновешенной неполной блок-схемой. Даже для (v, k,l)-конфигураций вопрос онеобходимых и достаточных условиях их существования остается пока (1978) открытым. Для существования(v, k,l)-конфигураций необходимо, чтобы при vчетном k-l было квадратом, а при vнечетном уравнение

имело решение в целых числах х, у, z, одновременно не равных нулю.

При v=n²+n+1, k=n+1, l=1 (v, k,l)-конфигурация представляет собой проективную плоскость порядка и,являющуюся частным случаем конечной геометрии, содержащей конечное число точек и прямых с заданнымиусловиями их инцидентности. Каждой проективной плоскости порядка п-1 можно поставить во взаимнооднозначное соответствие полное множество из п-1 попарно ортогональных латинских квадратов порядка п.Для существования проективной плоскости порядка и необходимо, чтобы при n=1, 2 (mod 4) существовалицелые числа аи b, удовлетворяющие равенству n=а ²+b².

Вопрос о существовании проективных плоскостей порядка прешен положительно только для п=р^a, где р-простое, а a - натуральное числа. Даже для n=10 этот вопрос является открытым (1978). К этому кругувопросов относится результат, связанный с опровержением гипотезы Эйлера о несуществовании парыортогональных латинских квадратов порядка n=4k+2, k=1, 2, ... (см. Комбинаторные задачи).

Другое направление К. а. связано с выбора теоремами. В основе целого ряда результатов этого направлениялежит теорема Ф. Холла о существовании системы различных представителей (трансверсали) семействаподмножеств (Х ₁, ..., Х _n )множества X, т. е. системы элементов ( х ₁,..., х _п )такой, что х _i О Х и х _i неравно х _jпри i неравно j:трансверсаль существует тогда и только тогда, когда для любых i₁, ... , i_k таких, что  справедливо неравенство  где |Y|- число элементов в множествеY. Из теоремы Ф. Холла вытекает теорема о существовании латинского квадрата, состоящая в том, что любойлатинский прямоугольник размера   можно дополнить до латинского квадратапорядка п. Другое следствие теоремы Ф. Холла: любую неотрицательную матрицу А= ||a_ij||, i, j=1, ..., п, такую,что

можно представить в виде

где П ₁, ..., П _s - матрицы подстановки порядка пи  Из теоремы Ф. Холла следует такжетеорема о том, что минимальное число строк и столбцов неотрицательной матрицы, содержащих всеположительные элементы, равно максимальному числу элементов, попарно не расположенных в одной и тойже строке или в одном и том же столбце. Экстремальное свойство частично упорядоченных множеств,аналогичное этой теореме, устанавливает теорема, утверждающая, что минимальное числонепересекающихся цепей совпадает с объемом максимального подмножества, состоящего из попарнонесравнимых элементов. Экстремальный характер носит и следующая теорема: если для n-множества Xсоставить все (ⁿ_r )сочетаний по r элементов и разбить их на кнепересекающихся классов, то для целоготсуществует число п ₀=п ₀( т, r, k )такое, что при найдется подмножество из тэлементов дляк-рого все (^m_r )сочетаний принадлежат одному классу.

Экстремальной является задача коммивояжера, заключающаяся в составлении кратчайшего маршрутапосещения пгородов с возвращением в исходный пункт при условии, что расстояния между городамиизвестны. Эта задача имеет приложения к изучению транспортных сетей. Комбинаторные задачиэкстремального характера рассматриваются в теории потоков в сетях и в теории графов.

Значительную часть К. а. составляют перечислительные задачи. При их решении либо указывается методперебора комбинаторных конфигураций из данного класса, либо определяется их число, либо делается то идругое. Типичные результаты перечислительных задач: число подстановок степени пc k циклами равно |S(n,к)|, где S(n, к)- числа Стирлинга 1-го рода, определяемые равенством

число разбиений множества из пэлементов на кподмножеств равно числу Стирлинга 2-го рода

число размещений тразличных предметов в празличных ячейках, когда пустых ячеек нет, равно п!s( т, п).Полезным инструментом для решений перечислительных задач является пер. <манент матрицы. Перманентматрицы А =||а _ij||,i=1, ..., п, j=1, ..., т,с элементами из нек-рого кольца определяется равенством

где суммирование производится по всевозможным размещениям объема пиз тразличных элементов.

Число трансверсалей нек-рого семейства подмножеств конечного множества равно перманентусоответствующей матрицы инцидентности.

К вычислению перманентов сводится целый класс задач по определению числа перестановок сограниченными позициями. Эти задачи для удобства иногда формулируются как задачи о расстановкевзаимно неатакующих фигур на шахматной доске размером  С определением перманентов нек-рыхклассов матриц связаны варианты задачи о димерах, возникающей при изучении явления адсорбции изаключающейся в определении числа способов объединения атомов в двухатомные молекулы на нек-ройповерхности. Ее решение может быть также получено через пфаффианы - некоторые функции от матриц,близкие к определителям. Проблема о числе латинских прямоугольников (квадратов) также связана сразработкой эффективных методов вычисления перманентов нек-рых (0, 1)-матриц.

Для вычисления перманентов применяется формула:

Имеется большое число неравенств, дающих оценку величины перманента в нек-рых классах матриц.Представляет интерес определение экстремальных значений перманента в определенных классахнеотрицательных матриц, однако эта задача не решена (1978) даже для (О, 1)-матриц с заданным значениемчисла единиц в строках и столбцах. К этой проблеме примыкает гипотеза Ван дер Вардена о том, чтоминимум перманента дважды стохастической матрицы порядка правен n!/nⁿ, подтвержденная только дляположительно полуопределенных матриц.

Большую роль в решении перечислительных задач играет метод производящих функций. Производящаяфункция  ставится в соответствие последовательности (а ₀, a₁,...) с элементами изнек-рого поля и рассматривается как формальный степенной ряд. При таком определении производящиефункции эффективно используются для решения перечислительных задач параллельно с методамирекуррентных соотношений и конечно разностных уравнений. При получении асимптотических формул вкачестве производящих функций обычно используются аналитические функции действительного иликомплексного переменного. В последнем случае для отыскания выражений коэффициентов применяютинтегральную формулу Коши.

Имеются результаты в направлении возможной унификации методов перечисления, связанные срассмотрением так наз. алгебр инцидентности и использованием функции Мёбиуса на частичноупорядоченных множествах (см., напр., [10]). При решении перечислительных задач существенную рольиграет формализация понятия неразличимости объектов. Использование для этих целей понятияэквивалентности объектов относительно нек-рой группы подстановок в сочетании с применением методапроизводящих функций было положено в основу так наз. теории перечисления Пойа (см. [10]). Сущность этойтеории состоит в следующем. Рассматривается Y^x - множество конфигураций

f:X ->Y,| Х| = т, |Y|= n.

На множестве Xдействует группа подстановок А, определяющая на Y^X отношение эквивалентности , при к-ром  если существует такое  что f(a(x))=f₁(x). для всех  Каждому ставится в соответствие характеристика [y] = (х ₁, . . ., х _k), где s_i, i=l, ..., k,- элементы абелевой группы.Характеристика конфигурации f задается равенством

Если a(s₁,..., s_k) - число элементов с заданным значением характеристики и b_m(s₁,..., s_k) - числонеэквивалентных конфигураций 

то основная теорема Пойа утверждает, что

где Zесть циклический индекс группы А, определяемый равенством

C(j₁, ..., j_m; А )-число элементов циклового класса {1^j12^j2 ...т ^j т} группы А. Эта теорема основана на леммеБернсайда: число классов эквивалентности N(А), определяемых на множестве Xгруппой подстановок А,дается формулой

где j₁(a) - число единичных циклов  Теория Пойа имеет применения при решении перечислительныхзадач теории графов и перечислении углеродных химических соединений. Имеется обобщение теории Пойана случай, когда эквивалентность конфигураций определяется двумя группами Gи Н, действующими на XиYсоответственно (см. [4] и [10]). В таком виде она применяется, напр., для определения числа неизоморфныхабстрактных автоматов.

Если X={1, ..., т}, Y={a₁, . .., а _п} и а: где а,- используется а _j раз в качестве образа, то выражение

наз. первичной спецификацией а. Если числа a₁, a₂, ..., a_n содержат b₀ нулей, b₁ единиц и т. д., то выражение

наз. вторичной спецификацией. При нек-рой специализации групп Gи Н, определяющих эквивалентностьконфигураций можно указать способ построения производящих функций для перечислениянеэквивалентных конфигураций. Этот способ, называемый общей комбинаторной схемой, подразделяется начетыре частных случая в соответствии с тем, принимают группы G и H значения единичной Еилисимметрической S_n групп соответствующих степеней. Эти частные случаи являются моделями длябольшинства известных комбинаторных схем (см. [9], [10]).

1. Коммутативный несимметричней случай: G=S_m, H=E. Моделирует схемы сочетаний, заполненийодинаковых предметов в различные ячейки п др. Производящая функция для перечисления неэквивалентныхконфигураций а таких, что

имеет вид:

2. Некоммутативный несимметричный случай: G=E, Н-Е. Моделирует схемы размещений, заполненийразличимых предметов в различные ячейки и др. Производящая функция для перечисления неэквивалентныхконфигураций sтаких, что

имеет вид:

3. Коммутативный симметричный случай: G=5_m, H=S_n. Моделирует схемы заполнения одинаковых предметовв одинаковые ячейки, перечисления разбиений натуральных чисел и др. Перечисление конфигураций а таких,что

основано на использовании производящей функции вида:

4. Некоммутативный симметричный случай: G=E, H=S_n. Моделирует схемы разбиений конечных множеств наблоки, заполнения различимых предметов в одинаковые ячейки и др. Перечисление конфигураций а таких,что

основано на использовании производящей функции вида:

Значительное место в К. а. занимают асимптотические методы. Они применяются как для упрощения сложныхконечных выражений при больших значениях входящих в них параметров, так и при получении приближенныхформул обходными путями, когда точные формулы неизвестны. Комбинаторную задачу перечислительногохарактера иногда удобно сформулировать как задачу отыскания характеристик распределения нек-ройслучайной величины. Такая интерпретация дает возможность применять развитый аппарат теориивероятностей, а для отыскания асимптотик - предельные теоремы. Детальному исследованию с этих позицийподвергнута классическая схема случайных размещений предметов в ячейки, случайные разбиениямножеств, цикловая структура случайных подстановок, а также различные классы случайных графов, включаяграфы отображений (см. [8], [9]).

Вероятностный подход применяется при изучении комбинаторных свойств симметрических групп и полугрупп.Исследовано предельное распределение порядка случайного элемента симметрической группы S_n при  а также асимптотика вероятности порождения ее случайными элементами. Для нек-рых классовслучайных неотрицательных матриц изучались распределения числа нулевых линий в матрице иперманентов, даны оценки вероятности примитивности таких матриц. Для доказательства существованиякомбинаторных конфигураций без их конструирования иногда используется нек-рый специфическийвероятностный прием. Сущность этого приема заключается в установлении существования конфигурации безее конструирования с помощью оценки вероятности нек-рого события (см. [7]).

Лит.:[1] Риордан Дж.. Введение в комбинаторный анализ, пер. с англ., М., 1963; [2] Райзер Г.-Д ж.,Комбинаторная математика, пер. с англ., М., 1966; [3] Холл М., Комбинаторика, пер. с англ., М., 1970; [4]Прикладная комбинаторная математика, сб. статей, пер. с англ., М., 1968; [5] Xарари Ф., Теория графов, пер. сангл., М., 1973; [6] Харари Ф., Иалмер Э., Перечисление графов, пер. с англ., М., 1977; [7] Эрдёш П., СпенсерДж., Вероятностные методы в комбинаторике, пер. с англ., М., 1976; [8] Колчин В. Ф., Чистяков В. П., в кн.:Итоги науки и техники. Теория вероятностей. Математическая статистика. Теоретическая кибернетика, т. 11,М., 1974, с. 5-45; [9] Сачков В. Н., в кн.: Вопросы кибернетики. Тр. семинара по комбинаторной математике, М.,1973, с. 146-64; [10] его же, Комбинаторные методы дискретной математики, М., 1977.

В. Н. Сачков.

Скачано с www.znanio.ru