Введение в прикладную комбинаторику, Кофман А. (984071), страница 2
Текст из файла (страница 2)
Число латинских прямоугольников размера г Х л. Число нормализованных латинских прямоугольников размера г Х и. Многозначное отображение А в А. Отображение, обратное к ГА. Граф, определенный на Е Х Е. Множество дуг, исходящих из подмножества А. Множество дуг, заходящих в подмножество А. Граф, определенный на Е Х Е посредством отобра- жения Г или посредством множества Ц его дуг. Граф, дополнительный к 6. ПУть, пРоходЯший чеРез веРшины ХЧ Хгм.
° ., Хгл. Транзитивное замыкание. Пара элементов, находящихся в отношении стро- гого порядка. Пара элементов, находящихся в отношении нестро- гого порядка. Число внутренней устойчивости графа О. Число внешней устойчивости графа О. Множество ребер графа. Неориентированный граф, соотнесенный графу О = = (Е, Ц). Цепь в графе. Степень вершины Хь Хроматическое число неориентированного графа 6. Верхняя грань подмножества А. Нижняя грань подмножества А. Верхняя грань (А, В). Нижняя грань (А, В).
Латинская композиция последовательностей з1 и зз. Значение пути через вершины. Значение пути через дуги. Оптимум. Максимум. Минимум. Пропускная способность разреза. Простой граф с множествами Х и У и отобра- жением Г. Вулево сложение. Характеристическая булева функция подмножества А, Сравнение по модулю и. Сложение по модулю 2.
Поле Галуа характеристики р. ГЛАВА1 ПЕРЕСЧЕТ. ПРИМЕНЕНИЕ ПРОИЗВОДЯЩИХ ФУНКЦИЙ $1. Введение Мы начнем с таких хорошо известных понятий, как размещения, перестановки и сочетания; далее читатель подробно познакомится здесь также с производящими функциями, которые дают возможность систематизировать пересчеты в комбинаторике. Затем напомним вкратце теорию конечноразностных операторов. Понятие производящей функции можно ввести с помощью так называемого г-преобразования, эквивалентного в некотором смысле преобразованию Лапласа, но относящегося к случаю счетных множеств, образующих последовательности. Некоторые последовательности играют важную роль: числа Стнрлинга, числа Белла, последовательность полиномов Белла, формула Бруно; они будут выписаны в явном виде.
Все эти понятия непосредственно используются во многих задачах пересчета, но, к сожалению, они, вообще говоря, мало распространены. 2. Теоретико-множественное произведение. онятие и-выборки Пусть заданы г множеств (конечных или нет) Ен', Е'), ... Е~'~, причем Е "и= Еш Егз' Е'з' ..., Е" ~ Е". Упорядоченная совокупность (2.2) называется г-выборкой '), и множество всех таких г-выборок Р„ ') Как правило, зто понятие будет использоваться для обозначения злемента теоретико-мвожественного произведения, размерность которого не фнКсирована (размерность — число сомножителей в произведении).
9 называется теоретико-множественным произведением или произведением г множеств Е' ~, Е"', ..., Е". Это теоретико-множественное произведение обозначается Р=Е(')ХЕ("Х ХЕы~ (2.3) В дальнейшем будут рассматриваться и теоретико-множественные произведения более специального вида: Р=ЕХЕХ ... ХЕ=В', (2.4) г раз где Š— конечное множество. Если Еь Еи ..., Е~ — элементы Е, то будем обозначать г-выборки из Р следующим образом: Р =(Ео ЕР ..., Е~). (2.5) Напомним, что г-выборка есть не множество, а элемент теоретико-множественного произведения.
Вот почему мы используем для обозначения г-выборки круглые скобки, а не фигурные, которые обычно служат для обозначения совокупности элементов, образующих множество. В г-выборке каждый элемент, называемый также компонентой, может повторяться, но порядок компонент фиксирован раз и навсегда. Говорят, что Ез — первая, Е; — вторая, ..., Е~— г-я компонента в г-выборке (2.5).
$3. Размещения. Сочетания Рассмотрим конечное множество Е с числом элементов (Е( = и (и ) О) н образуем следующее теоретнко-множественное произведение: (3.1) Р=Е ХЕ Х ... ХЕ. г раз равны, или эквивалентны, тогда и только тогда, когда Еа, = Ев,, Еа, = Евн ..., Еа, = Ев,. (33) Упорядоченная 2-выборка называется также двойкой, упорядоченная 3-выборка — тройкой. ') Здесь автор г-выборку (2.2) называет просто упорядоченной г-выборкой. (Прим.
ред.) Исходя из Р, введем два понятия. Упорядоченные г-выборки. г-выборку, которая определена в 5 2 формулой (2.2) и в которой порядок компонент фиксирован по определению, будем называть упорядоченной г-выборкой *). Говорят, что две упорядоченные г-выборки Р„=(Е,, Е„, ..., Е„) и Ра (Еа, Еа, ..., Ев ) (3.2) Упорядоченная г-выборка называется также размещением иэ и элементов по г (и = [Е[). Когда г = п, это размещение называется перестановкой п элементов. Неупорядоченные г-выборки.
Неупорядоченнал г-выборка не есть г-выборка в смысле данного выше определения. Если в определении упорядоченной г-выборки не учитывать порядок компонент, то мы приходим к неупорядоченной г-выборке, которую будем обозначать Р„=[Е«, Ег, ..., Е!!. (3 А) Говорят, что две неупорядоченные г-выборки равны, или эквивалентны, если каждая из них состоит из одних и тех же элементов Е, взятых одно и то же число раз.
Неупорядоченная 3-выборка называется также парой, неупорядоченная 3-выборка — триадой "). Неупорядоченная г-выборка называется также сочетанием из п элементов по г (и = [ Е[). Пример, Пусть Е=[А, В, С, О[ и Р=Ер',ЕХЕХЕХ рс',Е=Еа. Тогда Р = (А, А, С, А, О), Р =Р„РтчьР, Р = [А, А, С, А, О[, Р, = Р„ = Рт. Р,=(А,А,С, А, О), Р = (А, С, А, А, О), Р„ = [А, А, С, А, О[, Рт = [А, С, А, А, О), (3.5) *) В оригинале для упорядоченных 2-выборки и 3-выборки употребляются соответственно термины «совр!е» и «1бр!е», а для неупорядоченных 2-выборки и 3-выборки — термины «ране» и «Ьге!ап». !Прим перев ) *') Относительно этих терминов см. примечание к $ 4 на стр.
16 (Прах« перев.) 11 Метод последовательного пересчета упорядоченных г-выборок, обладающих заданным свойством. Прежде чем описать общие алгебраические методы перечисления и пересчета **) упорядоченных или неупорядоченных г-выборок, напомним некоторые классические приемы и результаты. Пусть Я= [ЄЄ..., Рн[, где () с Е'()Е !=п) — множество г-выборок Р„обладающих заданным свойством. Подсчитаем их число, обозначая его через У(п, г) =[их).
Обозначим через Р«(Е« Е» Еа ) (3.6) г-выборку, принадлежащую Е'. Чтобы определить )т'(п, г), подсчитаем число ))1! элементов Е,„которые могут быть взяты для образования первой компоненты г-выборки Р (если такая Р„ существует), затем число Лгх элементов Еч, которые могут быть взяты для образования второй компоненты г-выборки Р, когда первые компоненты уже известны; действуя дальше аналогично, доходим до У,. Получаем Ж (и, г) = М,Мз ... )т',, (3.7) Число упорядоченных г-выборок с повторением (размещения с повторением). Определим число упорядоченных г-выборок. Каждую нз компонент Е... Е„,, ..., Е„выбираем п различными способами (и = ( Е ~ ).
Имеем Л1,=5(т= ... — — Л'„=И. (3.8) Из (3.7) получаем У (и, г) = 51,Л'т... М, = и'. (3.9) Следовательно, существует и' упорядоченных г-выборок с повторением. Например, если Е = (А, В, С, О, Е), то можно образовать 5з = 125 упорядоченных 3-выборок: (А, А, А), (А, А, В), (А, А, С), (А, А, О), (А, А, Е), (А, В, А), (А, В, В), (А, В, С), (А, В, О), ,,(Е, Е, Е). (3.10) Число упорядоченных г-выборок без повторения (размещения без повторения).
Определим число упорядоченных г-выборок, которые можно образовать, выбирая первую компоненту Есч и различными способами (и =) Е(, и)~г), вторую компоненту Е„, (и — !) различными способами из оставшихся элементов, ..., г-ю компоненту Е„(и — г+ 1) различными способами из оставшихся элементов. Имеем Л1,=п, Ут п — 1, ..., Лт,=п — г+!. В силу (3.7) У(и, г)=М,Мз... М,=и(п — 1) ... (и — г+1) -- — -~- А„' '), (3.11) В частности, при п=г М(п, и) Ааа п1, (3.12) Число А„"называют числом пврвстановок из п элементов и обозначают Р„= п!. (3.13) Например, если Е = (А, В, С, О, Е), то можно образовать 5 4 3 = 60 следующих упорядоченных 3-выборок без повторения: (А, В, С), (А, В, О), (А, В, Е), (А, С, О), ..., (Е, О, С).
(3.14) ') Это число обозначается также (я),. 12 Число неупорядоченных г-выборок с повторением (сочетания с повторением). Поскольку формула (3.7) не может быть использована, так как рассматриваются неупорядоченные г-выборки, мы применим другой метод. Пусть У(п, г) — число неупорядоченных г-выборок с повторением из Е", где ~ Е !=п. Мы покажем, что У(п, г) =си+„-ь (3.15) где (3,!8) При г = 1 формула (3.15) справедлива, так как С„=п и существует в точности и неупорядоченных г-выборок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
