Файл: Дискрет.матем_Ч.2_УП.pdf

31 

а) имеется только одно свойство р , тогда, очевидно, n( p ) = n – n(p); 
б)  имеется  конечное  число  свойств  р

1

,p

2

,...,p

N

,  не  совмести-

мых друг с другом, снова очевидно, что 

n(

N

p

p

1

) = n – 

∑

=

N

i 1

n(p

i

). 

Разумеется, что сущность метода на этих простых не выяв-

ляется  достаточно  полно.  Перейдем  к  более  общей  постановке 
вопроса, когда элементы множества могут обладать комбинация-
ми совместных свойств. В этом случае имеет место теорема: 

Если  даны n-множество  элементов  и N-множество  свойств 

p

i

, i= 1,2,..., N, совместных между собой,  

n(

N

p

p

1

) = n 

− 

∑

=

N

i 1

n(p

i

) + 

∑

j

i,

n(p

i

,p

j

) 

− 

∑

k

j

i ,

,

n(p

i

,p

j

,p

k

) +...  +... +  

+ (–1)

N

 n(p

1

,p

2

,...,p

N

).                                           (1.4.1) 

При  доказательстве  теоремы  ограничимся  чисто  логиче-

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

1

,  затем 

− свойством р

2

и т. д., т.е. 

∑

i

i

p

n

)

(

элементов

. 

Однако

при

этом

элементы

, 

имею

-

щие

два

свойства

, 

скажем

р

2

и

р

1

, 

оказались

исключенными

дваж

-

ды

 (

сначала

как

обладающие

свойством

р

2

, 

а

затем

как

обладаю

-

щие

свойством

р

1

). 

Значит

, 

надо

возвратить

все

множества

, 

эле

-

менты

которых

обладают

двумя

свойствами

, 

т

.

е

. 

прибавить

∑

j

i,

n(p

i

,p

j

) 

элементов

. 

Но

при

этом

элементы

, 

обладающие

тремя

свойствами

, 

скажем

р

1

,

р

2

,  

р

к

, 

оказались

включенными

дважды

 (

в

первом

слагаемом

 n 

и

как

обладающие

свойствами

р

1

и

р

2

), 

сле

-

довательно

, 

надо

вычесть

∑

k

j

i ,

,

n(p

i

,p

j

,p

k

). 

Рассуждая

далее

анало

-

гичным

образом

, 

получим

алгоритм

для

вычисления

 n(

N

p

p

1

), 

состоящий

в

попеременном

отбрасывании

и

возвращении

под

-

множеств

. 

Это

и

определило

появление

названия

: 

метод

включе

-

ния

и

исключения

. 

32 

Пусть

теорема

справедлива

для

 N=1:      n( p ) = n – n(p). 

В

соответствии

с

формулировкой

теоремы

мы

можем

напи

-

сать

также

: 

n(

N

p

p

p

,...,

,

2

1

) = n(

1

2

1

,...,

,

−

N

p

p

p

) – n(

N

N

p

p

p

p

,

,...,

,

1

2

1

−

). 

Пусть

теорема

верна

для

 N–1 

свойств

, 

т

.

е

.  

n(p

1

,p

2

,...,p

N–1

,p

N

) = n(p

N

) – 

∑

i

n(p

i

, p

N

) +... + (–1)

N–1

n(p

1

,p

2

,...,p

N

). 

Перейдем

к

случаю

, 

когда

имеется

 N 

свойств

. 

Применим

по

-

лученное

соотношение

для

числа

   n(p

1

,p

2

,...,p

N–-1

,p

N

): 

n(p

1

,p

2

,..., p

N–1

, p

N

) = n(p

N

) – 

∑

 n(p

i

,p

N

) +... + (–1)

N–1

n(p

1

,p

2

,...,p

N

). 

Вычитая

это

равенство

из

предыдущего

, 

получим

, 

очевидно

, 

утверждение

теоремы

. 

Характер

доказательства

таков

, 

что

его

можно

применить

для

любой

комбинации

свойств

как

выполняющихся

, 

так

и

не

имеющих

места

. 

Другими

словами

, 

в

левой

части

доказанного

ра

-

венства

может

стоять

не

только

 n(

N

p

p

p

,...,

,

2

1

) , 

но

и

, 

например

, 

n(

,

,

4

2

p

p

  p

1

,p

3

). 

Теорема

формулируется

при

относительной

со

-

вокупности

  p

2

и

  p

4 

с

обязательным

выполнением

  p

1

и

  p

3

сле

-

дующим

образом

: 

n(

,

,

4

2

p

p

  p

1

,p

3)

 = n(p

1

,p

3

) – n(p

1

,p

3

,p

2

) + n(p

1

,p

3

,p

2

,p

4

). 

Дальнейшее

усложнение

метода

связано

с

введением

весов

элементов

. 

Веса

−

это

числовые

характеристики

элементов

мно

-

жеств

, 

определяемые

условием

задачи

. 

Пусть

задано

 n-

множество

 S 

и

каждому

элементу

  s

i

∈

  S,        

i =1,2,...,n, 

приписан

вес

 V(s

i

). 

Из

 N-

множества

свойств

 p

1

,p

2

,...,p

N 

возьмем

 r-

выборку

  p

i1

,...,p

ir

и

обозначим

сумму

весов

элементов

, 

обладающих

всеми

 r 

выбранными

свойствами

, 

через

 V(p

i1

,...,p

ir

). 

А

сумму

, 

распространенную

на

все

возможные

 r-

выборки

свойств

, 

обозначим

через

∑

 (p

i1

,...,p

ir

) = V(r). 

Для

случая

 r = 0 

со

-

ответствующий

символ

 V(0) 

будет

обозначать

сумму

весов

всех

элементов

множества

 S. 

Предыдущая

теорема

при

этом

перефор

-

мулируется

так

: 

Если

даны

 n-

множество

 S, 

каждый

элемент

которого

имеет

вес

, 

и

 N-

множество

свойств

, 

то

сумма

  V

N

(0) 

весов

элементов

, 

не

33 

удовлетворяющих

ни

одному

из

выданных

свойств

, 

определяется

по

формуле

: 

V

N

 (0) = V(0) – V(1) + V(2) –... + (–1) V(N). 

Таким

образом

, 

чтобы

получить

искомую

сумму

весов

, 

надо

: 

а

) 

взять

сумму

весов

всех

элементов

множества

; 

б

) 

из

нее

вычесть

сумму

весов

элементов

, 

обладающих

хотя

бы

одним

свойством

; 

в

) 

возвратить

  (

прибавить

) 

сумму

всех

элементов

, 

имеющих

не

менее

двух

свойств

, 

и

т

.

д

. 

В

самом

деле

, 

всякий

элемент

  s

i

∈

 S, 

если

он

имеет

 t>0 

свойств

, 

вносит

свой

вес

 V(s

i

) 

в

первое

слагаемое

один

раз

, 

во

второе

 t 

раз

, 

в

третье

−

  (

t

2

) 

раз

и

т

. 

д

., 

а

всего

  (

t

0

) – (

t

1

) + (

t

2

)  –...        

+ (–1)(

t

N

)... = 

∑

(–1)(

n

k

) 

раз

, 

а

это

выражение

равно

нулю

. 

В

этом

легко

убедиться

, 

представив

, 

что

это

выражение

является

част

-

ным

значением

разложения

 (1+ t)

n

|

t=–1

 = 0. 

Если

все

элементы

 s

i

∈

 S 

имеют

единый

вес

, 

то

сумма

весов

равна

числу

слагаемых

в

сумме

. 

В

этом

случае

 V(c) = n, 

а

 V

N

 (0) 

равно

числу

элементов

множества

 S, 

не

удовлетворяющих

ни

од

-

ному

из

 N 

свойств

; 

формула

, 

получающаяся

при

этом

, 

−

это

фор

-

мула

 (1.4.1). 

Имеется

теорема

, 

которая

является

обобщением

предыду

-

щей

. 

Теорема.

Сумма

весов

элементов

 n-

множества

 S, 

удовлетво

-

ряющих

 r-

выборке

из

 N-

множества

свойств

 p

1

,p

2

,...,p

N

, 

находится

по

формуле

: 

V

N

(r) = V(r) – (

r–1

2

) V(r+2) –... + (–1)

N–r

 V(N). 

Доказательство

данной

теоремы

аналогично

предыдущей

. 

Область

применения

метода

включения

и

исключения

до

-

вольно

широка

. 

Всюду

, 

где

речь

идет

о

разделениях

дискретных

множеств

, 

производимых

в

зависимости

от

наличия

  (

или

отсут

-

ствия

) 

у

элементов

определенных

свойств

, 

этот

метод

появляется

, 

иногда

в

различных

модификациях

. 

К

числу

задач

, 

решаемых

с

помощью

данного

метода

, 

относятся

задачи

о

беспорядках

, 

ряд

задач

теории

чисел

, 

а

также

некоторых

задач

в

теории

вероятно

-

сти

. 

В

качестве

примера

рассмотрим

задачу

о

беспорядках

, 

иначе

называемой

задачей

о

встречах

. 

34 

Пусть

имеется

конечное

упорядоченное

множество

чисел

1,2,3,..., n. 

Для

них

могут

быть

образованы

перестановки

а

1

, 

а

2

,..., 

а

n

. 

Число

всех

перестановок

    S  =  n!. 

Среди

этих

перестановок

имеются

такие

, 

где

ни

один

элемент

не

сохранил

своего

первона

-

чального

места

: a

i

≠

 i, i = 1,2,..., n. 

Такие

перестановки

называют

беспорядками

. 

Сколько

существует

беспорядков

? 

Множество

 n 

элементов

рассматривается

по

отношению

к

множеству

свойств

элементов

оставаться

на

своем

месте

:                

p

i

 { a

i

 = i, i = 1,2,..., n}. 

N(S) 

соответствующих

перестановок

равно

 (n – s)!. 

Число

беспорядков

тогда

находится

с

помощью

метода

включения

и

ис

-

ключения

:  

N(0) = n! – (

n

1

)(n – 1)! + (

n

2

)(n – 2)! –... +(–1)

s

 (

n

s

)(n – s)! +... = 

                = n!(1 – 1 + 1/2! – 1/3! +... + (–1)

n

/n!), 

что

является

целым

числом

, 

ближайшим

к

 n!e

–1

. 

Если

речь

идет

не

о

беспорядках

, 

а

о

числе

перестановок

, 

в

которых

остаются

на

своих

местах

 S 

элементов

, 

то

: 

N(S) = – n!/s! (1 – 1 + 1/2! – 1/3! +... + (–1)

n–s

 1/(n–s)!). 

1.5 

Системы

различных

представителей

Здесь

мы

рассмотрим

один

из

комбинаторных

подходов

к

характеристике

структуры

конечных

множеств

. 

Уже

по

названию

можно

понять

, 

что

основной

идеей

является

замена

системы

множеств

собранием

их

представителей

. 

Пусть

имеются

 n-

множество

 S 

и

множество

 P(s) 

всех

его

подмножеств

. 

Пусть

 M(s) = (s

1

,s

2

,...,s

m

) 

есть

некоторая

 m-

выборка

из

 S. 

Если

выборке

 M(s) 

можно

сопоставить

  (

не

обязательно

од

-

нозначно

) 

выборку

, 

такую

, 

что

элементы

а

i

, i = 1,2,..., m 

попарно

различны

и

при

этом

 a

i

 = s

i

,    i = 1,..., m, 

то

говорят

, 

что

элемент

а

i

, 

представляет

множество

 S

i

, a 

вся

выборка

 (

а

1

, a

2

,..., a

m

) 

называ

-

ется

системой

различных

представителей

с

.

р

.

п

. 

для

 M(s). 

Заметим

сразу

же

, 

чтобы

избежать

неясностей

, 

что

в

с

.

р

.

п

. 

если

 i 

≠

 j, 

то

a

i

≠

 a

j

, 

даже

если

 s

i

 = s

j

. 

Если

множество

появляется

несколько

раз

, 

то

всякий

раз

оно

должно

иметь

представителя

, 

отличного

от

всех

других

. 

35 

Например

, 

выборка

из

пяти

подмножеств

 S

i

: 

                  S

1

 = {1,2,3}, 

                  S

2

 = {,2,4}, 

                  S

3

 = {,2,5}, 

                  S

4

 = {,3,4,5,6}, 

                  S

5

 = {,3,4,5,6} 

может

быть

представлена

следующей

с

.

р

.

п

.:  

а

1

 = 1, 

а

2

 = 2, 

а

3 

= 5,  

а

4

 = 3, 

а

5

 = 4. 

Но

если

взять

множества

 {1,2}, {1,2}, {1,2}, {3,4,5,6}, 

{3,4,5,6}, 

то

мы

не

сможем

получить

ни

одной

с

.

р

.

п

. 

На

вопрос

о

том

, 

существует

ли

с

.

п

.

р

. 

для

заданного

семей

-

ства

множеств

, 

отвечает

теорема

Ф

. 

Холла

 (1935 

г

.). 

Теорема  Ф.  Холла.

Подмножество

  S

1

, S

2

,..., S

m

имеет

с

.

п

.

р

. 

тогда

и

только

тогда

, 

когда

объединение

любой

к

-

выборки

этих

множеств

содержит

не

менее

к

элементов

. 

Иными

словами

, 

с

.

п

.

р

. 

для

 S

1

,S

2

,..., S

m

существует

тогда

и

только

тогда

, 

когда

 S

1

∪

S

2

∪

... 

∪

S

ik

состоит

не

менее

чем

из

к

элементов

, 

при

этом

к

 = 1,2,..., m, 

а

(i

1

,i

2

,...,i

k

) – 

любая

к

-

выборка

из

 1,2,..., m. 

Необходимость

почти

очевидна

, 

т

.

к

. 

существование

с

.

п

.

р

. 

обеспечивает

наличие

необходимого

числа

элементов

в

качестве

различных

представителей

. 

Что

касается

достаточности

, 

то

при

-

ведем

для

нее

усовершенствованную

формулировку

, 

которая

дает

нам

также

нижнюю

грань

для

числа

самих

с

.

п

.

р

. 

Теорема.

Пусть

семейство

 M(s) = (S

1

, S

2

,..., S

m

) 

удовлетворя

-

ет

необходимому

условию

существования

с

.

п

.

р

., 

и

пусть

наи

-

меньшее

каждое

из

множеств

 S

1

, S

2

,..., S

m 

состоит

не

менее

чем

из

t 

элементов

. 

Тогда

а

) 

если

 t 

≤

 m,  

то

 M(s) 

имеет

не

меньше

, 

чем

 t! 

с

.

п

.

р

.; 

б

) 

если

 t > m, 

то

 M(s) 

имеет

не

меньше

, 

чем

 t!/(t – m)! 

с

.

п

.

р

. 

Алгоритм

, 

позволяющий

подобрать

с

.

п

.

р

. 

для

конечного

числа

множеств

или

показать

, 

что

такой

системы

для

данного

на

-

бора

множеств

не

существует

, 

дал

Ф

. 

Холл

в

качестве

доказатель

-

ства

теоремы

Ф

. 

Холла

о

различных

представителях

. 

Пусть

задано

 n 

множеств

. 

Требуется

найти

для

них

с

.

п

.

р

. 

или

показать

, 

что

этой

системы

не

существует

. 

Пронумеруем

множе

-

ства

 S

1

, S

2

,..., S

n

и

зафиксируем

порядок

, 

в

котором

они

пронуме

-