В.А. Носов - Комбинаторика и теория графов (1023552), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Дляn = 1 выход А(1) есть перестановка (1). Пусть для n - 1 алгоритм построил все (n - 1)перестановки чисел 1, 2, … , n - 1. Тогда А(n) действует так.Каждой (n - 1)-перестановке b1, … , bn-1 чисел 1, 2, … , n - 1 ставится в соответствие n перестановок чисел 1, 2, … , n следующим образом:( b1′ ,K , b′n−1 ,1) ,где b ′i = b i + 1, i = 1, n − 1( b1′′,K , b′′n−1 ,2) ,где b ′′i = b i если bi = 139b ′′i = b i + 2если bi ≥ 2.…( b1( n) ,K , b nn−1 ,n) ,где b (i n ) = b i , i = 1, n − 1Корректность данного алгоритма следует из того, что для любого s ∈1, n последовательность b1(s) ,K , b(ns−)1 есть перестановка чисел 1, 2, … , s - 1, s + 1, … , n.Представим теперь алгоритм порождения всех n! перестановок n-множестваА = {1, 2, … , n} , в котором переход от одной перестановки к следующей осуществляется одной транспозицией соседних элементов.

Транспозиция - это перемена местами двухэлементов. Каждый элемент снабжается “направлением”, обозначаемым “→“ или “←“.Число k называется подвижным, если существует меньшее его число, соседнее с ним состороны стрелки.Алгоритм “Перестановки”.Начало - конфигурация← ←←1 2 ... nШаг алгоритма1. Если нет подвижных элементов, то стоп.2. Находится наибольшее подвижное число m3. Число m переставляется с соседним элементом, на которое указываетна-правление m.4. Направления всех элементов k, k > m меняются на противоположные.5. Повторить шаг 1.Проиллюстрируем алгоритм для n = 3.ШагКонфигурацияМаксимальноеподвижное число1←←←32←←←33←←←24→←←35←→←3123132312321231406←←→213нет, стоп41Корректность данного алгоритма устанавливается индукцией по n. Пусть алгоритм правильно работает для n, и покажем его правильность для n + 1.

(Случай n = 1←←←←тривиален). Ясно, что если начинать работу с конфигурации 1 2 ... n n + 1 , что n + 1 максимальное подвижное число, и оно им остается до тех пор, пока не будет получена←←←конфигурация n +1 1 ... n . При этом будут порождены n+1 перестановок, в которыхчисло n+1 занимает места n + 1, n, … , 1. Теперь максимальное подвижное число n, ипереставляются элементы множества 1, 2, … ,n. Теперь снова максимальное подвижноечисло n + 1, после смены его направления оно будет двигаться влево n + 1 раз, порождая→n + 1 перестановок. Когда будет получена перестановка a1 a2 … an n + 1 , число n+1 небудет неподвижным, и алгоритм будет применяться к множеству1, 2, …n, после чего число n + 1 снова становится подвижным.

Таким образом, алгоритмпорождает n + 1 перестановок и применяется к множеству 1, 2, … , n. Когда будет достигнута последняя перестановка чисел 1, 2, … , n, то число n +1 через n + 1 шагов перестанет быть подвижным, и алгоритм останавливается. Общее число шагов алгоритма(n + 1)⋅n! = (n + 1)!.42ГЛАВА II. МЕТОДЫ ПЕРЕЧИСЛЕНИЯ§ 1. Метод включения-исключения.Предположим, что имеется множество X из N элементов. Пусть имеется tсвойств P1, ...

, Pt, так, что любой элемент множества X может обладать или не обладатьлюбым из этих свойств. Пусть N(Pi) - число элементов из X, обладающих свойством Pi .Для любого подмножества свойств { Pi1 , K , Pi r } обозначим N( Pi1 , K , Pi r ) - число элементов из X, обладающих свойствами Pi1 , K , Pi r (возможно также и некоторыми другими свойствами).Теорема 1. Число элементов N(0) множества X, не обладающих ни одним из названных свойств, задается формулойN(0) = S0 - S1 + S2 - … +(-1)tStгде(1)S0 = NSk =∑ N( Pi1 ,K , Pik ),k ∈1, t1≤i1 <...<i k ≤ tФормула (1) называется формулой включения-исключения.♦ Элемент a ∈ X, не обладающий ни одним из указанных свойств учитываетсяодин раз в члене S0 и не входит ни в один из остальных слагаемых правой части (1).Элемент a ∈ X со свойством Pj учитывается один раз в члене S0 и один раз в членеS1 =t∑ i=1 N(Pi ) , причем в члене S0 1 раз, а в члене S1 - 1 раз и общий его вклад равен1 + (-1) = 0.

Элемент a ∈ X, обладающий точно r свойствами Pi1 , K , Pi r (r ≥ 1), учитыва r rется один раз в члене S0 и дает вклад 1, далее   раз в члене S1 и дает вклад -   , затем 1 1 r r r  раз в члене S2 и дает вклад   и, вообще, учитывается   раз в члене Sk и дает 2 2 k rвклад (-1)k   , где k ≤ r. Следовательно, общий вклад элемента a в правую часть (1) kравен r  r r r1 -   +   - … + (-1)k   + … + (-1)r   , = (1 - 1)r = 0 1  2 k rЗначит, правая часть (1) учитывает точно 1 раз каждый элемент, не обладающий ни од43ним из указанных свойств, а всякий другой элемент учитывается 0 раз, следовательно,правая часть (1) равна N(0) .

♦Формула (1) может быть обобщена следующим образом.Теорема 2. Число элементов N(r) множества X, обладающих точно r свойствамииз указанных свойств, дается формулойt r + 1s  r + st-r  N(r) = Sr -  Sr+1 + …+ (-1)  Sr+s+ … + (-1)   St (2) r r  r ♦ В правой части (2) элемент a ∈ X, обладающий точно r свойствами, учитывается 1 раз в первом слагаемом и не учитывается в остальных слагаемых. Пусть теперьэлемент a ∈ X обладает точно k свойствами, r < k ≤ t. Тогда он учитывается в слагаемых r   k  r + 1  k  k  kSr, Sr+1, … , Sk число раз, равное     ,  , K ,     соответственно. r   r   r   r + 1 r   kЗначит общий вклад элемента a ∈ X равен r  k  r + 1  k   r + 2  k k-r  k  k - … + (-1)     +   −  r  r   r   r + 1  r   r + 2 r   k(3) b  c   c  c − a Воспользуемся легко проверяемым тождеством     =    и преобразуем a  b  a  b − aсумму (3). k  k − r  k  k − r  k  k − rk-r  k  k − r  −   +   - … + (-1)    r  0   r  1   r  2  r   k − rСледовательно имеем k  k − r   k − r   k − r k − r  k − r  = 0 −L+ ( −1) +   − k − r  r   0   1   2 Значит, формула (2) учитывает каждый элемент, обладающий точно r свойствами 1 раз,а остальные элементы из X учитываются 0 раз.

♦Дальнейшее обобщение формулы включения-исключения может быть сделаноследующим образом. Предположим, что каждый элемент a ∈ A обладает весом w(a),представляющим собой элемент некоторого поля F. Для любого подмножества свойств{ Pi1 , K , Pi r }обозначим через W( Pi1 , K , Pi r ) сумму весов всех элементов X, обладающихсвойствами Pi1 ,K , Pi r (возможно также и некоторыми другими). Положим44∑ W( Pi1 ,K , Pir ) , W(0) - суммa весов всех элементов из X. Пусть E(r) - суммаW(r) =1≤i1 <...<i r ≤ tвесов всех элементов из X, обладающих точно r свойствами.Теорема 3. Справедлива формула r + 1 r + 2t-r  tE(r) = W(r) -  W(r + 1) +  W(r + 2) - … + (-1)   W(t) (4) r  r  r♦ Доказательство почти дословно повторяет доказательство формулы (2) и потому опускается.

♦Рассмотрим приложения формулы включения-исключения.1. Пусть X1, … , Xn - семейство подмножеств множества X. Tогда справедливотождествоX1 U ... U X n = ∑in=1 X i −∑1≤i< j≤ nX i I X j +L+ ( −1) n −1 X1 I ... I X n(5)♦ Пусть x ∈ X1 U ... U X n . Говорим, что элемент x обладает свойством Pi,i ∈1, n , если x ∈ Xi . Пусть X(0) - число элементов из X1 U ... U X n , не обладающих ниодним из указанных свойств Pi, i ∈1, n . По формуле включения-исключения имеемN(0) =  X1 U ... U X n - ∑in=1 X i +∑1≤i< j≤ nX i I X j +L+ ( −1) n X1 I ...

I X nПоскольку N(0) = 0, то отсюда следует формула (5). ♦2. Пусть X, Y - произвольные множества, X= n, Y= m. Тогда число Wnmсюръективных отображений f : X → Y (n ≥ m) дается формулой. m m mWnm = mn -   ( m − 1) n +   ( m − 2) n −L+ ( −1) n   ( m − m) n 1 2 m(6)♦ На множестве всех отображений f : X → Y введем m свойств P1, … , Pm следующим образом: отображение f : X → Y обладает свойством Pi, если в образ отображения f не входит элемент yi ∈ Y, где Y = {y1, … , ym}. Значит, отображения f : X → Y, необладающие ни одним из указанных свойств P1, … , Pm, есть очевидно сюръективныеотображения.

Далее, имеем следующие соотношения:N = mn - число всех отображений f : X → YN(Pi) = (m - 1)n…N( Pi1 , K , Pi k ) = (m - k)nТеперь по формуле включения-исключения получаем формулу (6).453. Пусть X , Y - произвольные множества, X= k, Y= m. Рассмотрим функцию n переменных f(x1, … , xn) , где xi ∈ X со значениями из множества Y. Переменнаяxi называется фиктивной, если справедливоf(x1, … , xi-1, x′, xi+1, … , xn) = f(x1, … , xi-1, x′′, xi+1, … , xn) , ∀ xi, x′, x′′ ∈ X (6′)Найдем число N0 функций f, f : Xn → Y, не имеющих фиктивных переменных. На множестве всех функций данного вида определим n свойств P1, … , Pn , где свойство Pi означает, что переменная xi фиктивна, i ∈1, n . Ясно, что справедливы соотношенияN = mknN(Pi) = m kn−1N(Pi, Pj) = m kn−2........N( Pi1 , K , Pi t ) = m kn−t........По формуле включения-исключения получаемn  nn−1n−2n −n n n+   mk- … + (-1)n   m kN0 = m k -   m k 1 2 n(6’’)4.

Пусть имеем n-множество X = {x1, … , xn}. Две подстановки ϕ1, ϕ2 множестваX называются толерантными, если для них справедливо: ∃ x ∈ X  ϕ1(x) = ϕ2(x).Не толерантные подстановки ϕ1, ϕ2 называются противоречивыми. Число Qn парпротиворечивых подстановок n-множества X дается формулойQn = (n!)2 (1 -1 11+ −L+ ( −1) n )1! 2 !n!(7)♦ Зафиксируем подстановку ϕ1, которая выбирается n! способами, и найдемчисло Dn подстановок ϕ2, противоречивых с ϕ1. Покажем, что справедливоDn = n! (1 -1 11+ −L+ ( −1) n )1! 2 !n!(8)Действительно, введем свойства P1, … , Pn на множестве всех подстановок {ϕ} множества X, где свойство Pi, i ∈1, n означает, что выполнено ϕ(xi) = ϕ1(xi).

Характеристики

Список файлов книги