Файл: Журавлев Флеров Дискретный анализ МФТИ 1991.pdf

1.5. ÏÐÈÍÖÈÏ ÂÊËÞ×ÅÍÈÉ-ÈÑÊËÞ×ÅÍÈÉ

41

òàê ÷òî

N

n

(

x

) =

n

X

k

=0

n
k

(

n

−

k

)!(

x

−

1)

k

=

n

X

k

=0

n

!

k

!

(

x

−

1)

k

⇒

⇒

N

0

=

N

n

(0) =

n

X

k

=0

(

−

1)

k

n

!

k

!

1.17. Ïðèìåð. (Çàäà÷à î ñóïðóæåñêèõ ïàðàõ (î ãîñòÿõ).) Ýòà èçâåñòíàÿ

çàäà÷à ôîðìóëèðóåòñÿ ñëåäóþùèì îáðàçîì: ñêîëüêèìè ñïîñîáàìè ìîæíî

ðàññàäèòü çà êðóãëûì ñòîëîì n ñóïðóæåñêèõ ïàð òàê, ÷òîáû íèêàêàÿ ïà-

ðà íå ñèäåëà ðÿäîì è æåíùèíû ÷åðåäîâàëèñü ñ ìóæ÷èíàìè. Çàäà÷à ýê-

âèâàëåíòíà ïîèñêó ÷èñëà ïåðåñòàíîâîê

π

∈

σ

n

, äëÿ êîòîðûõ

π

(

i

)

6

=

i,

i

+ 1(mod

n

)

äëÿ âñåõ

i

∈

[

n

]

. Äðóãèìè ñëîâàìè, ìû èùåì ÷èñëî

N

0

äëÿ

äîñêè

B

=

{

(1

,

1)

,

(2

,

2)

, . . . ,

(

n, n

)

,

(1

,

2)

,

(2

,

3)

, . . . ,

(

n

−

1

, n

)

,

(

n,

1)

}

.

Âçãëÿíóâ íà ðèñóíîê äîñêè

B

, ìû âèäèì, ÷òî

r

k

ðàâíî ÷èñëó ñïîñîáîâ, êî-

òîðûìè ìîæíî âûáðàòü

k

èç

2

n

ðàñïîëîæåííûõ íà îêðóæíîñòè òî÷åê òàê,

÷òîáû ñðåäè íèõ íå áûëî äâóõ ïîñëåäîâàòåëüíûõ (ñîñåäíèõ).
Ëåììà 1.18. ×èñëî ñïîñîáîâ, êîòîðûìè ìîæíî âûáðàòü

k

òî÷åê èç

m

òî÷åê íà îêðóæíîñòè òàê, ÷òîáû ñðåäè íèõ íå áûëî äâóõ ïîñëåäîâàòåëü-

íûõ (ñîñåäíèõ) òî÷åê, ðàâíî

m

m

−

k

m

−

k

k

.

Äîêàçàòåëüñòâî. 1 ñïîñîá

Ïóñòü

f

(

m, k

)

 èñêîìîå ÷èñëî, è ïóñòü

g

(

m, k

)

 ÷èñëî ñïîñîáîâ âû-

áðàòü k íå ïîñëåäîâàòåëüíûõ òî÷åê èç

m

òî÷åê, ðàñïîëîæåííûõ ïî îêðóæ-

íîñòè, à çàòåì ïîêðàñèòü

k

âûáðàííûõ òî÷åê â êðàñíûé öâåò è îäíó èç

íåîêðàøåííûõ òî÷åê ïîêðàñèòü â ñèíèé öâåò. ßñíî, ÷òî

g

(

m, k

) = (

m

−

k

)

f

(

m, k

)

.

Íî ìîæíî âû÷èñëèòü

g

(

m, k

)

òàêæå ñëåäóþùèì îáðàçîì. Ñíà÷àëà ïî-

êðàñèì îäíó òî÷êó â ñèíèé öâåò

m

ñïîñîáàìè. Òåïåðü íàì íóæíî ïîêðà-

ñèòü â êðàñíûé öâåò

k

òî÷åê, âûáðàííûõ èç ëèíåéíîãî ìàññèâà

m

−

1

òî÷åê òàê, ÷òîáû ñðåäè íèõ íå áûëî äâóõ ïîñëåäîâàòåëüíûõ. Îäíèì èç

ñïîñîáîâ äàëüíåéøèõ ðàññóæäåíèé ìîæåò áûòü ñëåäóþùèé. Ðàñïîëîæèì

m

−

1

−

k

íåîêðàøåííûõ òî÷åê â ëèíèþ è âñòàâèì

k

êðàñíûõ òî÷åê â

m

−

k

ïðîìåæóòêîâ ìåæäó íåîêðàøåííûìè òî÷êàìè (ñ÷èòàÿ íà÷àëî è êîíåö).

42

ÃËÀÂÀ 1. ÝËÅÌÅÍÒÛ ÊÎÌÁÈÍÀÒÎÐÈÊÈ

Ýòî

ìîæíî

ñäåëàòü

m

−

k

k

ñïîñîáàìè.

Ñëåäîâàòåëüíî,

g

(

m, k

) =

m

m

−

k

k

. Îòêóäà

f

(

m, k

) =

m

m

−

k

m

−

k

k

.

Ïðåäëîæåííîå äîêàçàòåëüñòâî îñíîâàíî íà íåêîòîðîì îáùåì ïðèíöèïå ïå-

ðåõîäà îò êðóãîâîãî ê ëèíåéíîìó ìàññèâó. Ýòîò ïðèíöèï øèðîêî èñïîëü-

çóåòñÿ ïðè ðåøåíèè êîìáèíàòîðíûõ çàäà÷.

2 ñïîñîá

Ïîìåòèì òî÷êè ÷èñëàìè

1

,

2

, . . . , m

â âîçðàñòàþùåì ïî ÷àñîâîé ñòðåë-

êå ïîðÿäêå. Ìû õîòèì ïîêðàñèòü

k

èç íèõ â êðàñíûé öâåò, òàê ÷òîáû íå

áûëî äâóõ ïîñëåäîâàòåëüíûõ êðàñíûõ òî÷åê. Ñíà÷àëà ïîäñ÷èòàåì ÷èñëî

âîçìîæíîñòåé, ïðè êîòîðûõ òî÷êà

1

íå îêðàøåíà â êðàñíûé öâåò. Ðàñïîëî-

æèì

m

−

k

íåîêðàøåííûõ òî÷åê ïî êðóãó, ïîìåòèâ îäíó èç íèõ åäèíèöåé

è âñòàâèì

k

êðàñíûõ òî÷åê â

m

−

k

ïðîìåæóòêîâ ìåæäó íåîêðàøåííû-

ìè òî÷êàìè

m

−

k

k

ñïîñîáàìè. Ñ äðóãîé ñòîðîíû, åñëè òî÷êà

1

áóäåò

ïîêðàøåíà â êðàñíûé öâåò, òî ðàñïîëîæèì

m

−

k

+ 1

òî÷åê ïî êðóãó, ïî-

êðàñèì îäíó èç ýòèõ òî÷åê â êðàñíûé öâåò è ïîìåòèì åå

1

, à çàòåì âñòàâèì

m

−

k

−

1

k

−

1

ñïîñîáàìè

k

−

1

êðàñíóþ òî÷êó íà

m

−

k

−

1

ðàçðåøåííûõ

ìåñò.

Ñëåäîâàòåëüíî,

f

(

m, k

) =

m

−

k

k

+

m

−

k

−

1

k

−

1

=

m

m

−

k

m

−

k

k

Íà îñíîâàíèè äîêàçàííîé ëåììû èìååì

Óòâåðæäåíèå 1.19. Ìíîãî÷ëåí

N

n

(

x

)

äëÿ äîñêè

B

=

{

(

i, i

)

,

(

i, i

+ 1(mod

n

)) : 1

≤

i

≤

n

}

äàåòñÿ ôîðìóëîé

N

n

(

x

) =

n

X

k

=0

2

n

2

n

−

k

2

n

−

k

k

(

n

−

k

)!(

x

−

1)

k

.

1.6. ÑÈÑÒÅÌÛ ÏÐÅÄÑÒÀÂÈÒÅËÅÉ ÌÍÎÆÅÑÒÂ

43

 ÷àñòíîñòè, ÷èñëî

N

0

ïåðåñòàíîâîê

π

∈

σ

n

, äëÿ êîòîðûõ

π

(

i

)

6

=

i

,

i

+ 1 (mod

n

)

ïðè

1

≤

i

≤

n

, äàåòñÿ ôîðìóëîé

N

0

=

n

X

k

=0

2

n

2

n

−

k

2

n

−

k

k

(

n

−

k

)!(

−

1)

k

1.6 Ñèñòåìû ïðåäñòàâèòåëåé ìíîæåñòâ

Ðàññìîòðèì îäèí èç êîìáèíàòîðíûõ ïîäõîäîâ ê õàðàêòåðèñòèêå ñòðóêòó-

ðû êîíå÷íûõ ìíîæåñòâ. Óæå ïî íàçâàíèþ ìîæíî ïîíÿòü, ÷òî îñíîâíîé

èäååé ÿâëÿåòñÿ çàìåíà ñèñòåìû ìíîæåñòâ ñîáðàíèåì èõ ïðåäñòàâèòåëåé.

Ìû ðàññìîòðèì çäåñü íåñêîëüêî òåîðåì, êîòîðûå ãàðàíòèðóþò ñóùåñòâî-

âàíèå îïðåäåëåííûõ âûáîðîâ ïðè ñîîòâåòñòâóþùèõ ïðåäïîëîæåíèÿõ. Îíè

èíòåðåñíû ñàìè ïî ñåáå è ìîãóò áûòü èñïîëüçîâàíû â êà÷åñòâå òåîðåì ñó-

ùåñòâîâàíèÿ â ðàçëè÷íûõ êîìáèíàòîðíûõ çàäà÷àõ.

1.6.1 Ñèñòåìû ðàçëè÷íûõ ïðåäñòàâèòåëåé

Ïóñòü

S

 êîíå÷íîå ìíîæåñòâî èç

m

ýëåìåíòîâ,

|

S

|

=

m

.

P

(

S

)

 ìíîæåñòâî

âñåõ åãî ïîäìíîæåñòâ.

Îïðåäåëåíèå. Ïóñòü

M

(

S

) = (

S

1

, S

2

, . . . , S

n

)

íåêîòîðàÿ ñîâîêóï-

íîñòü ïîäìíîæåñòâ èç

P

(

S

)

, íåîáÿçàòåëüíî ðàçëè÷íûõ,

a

= (

a

1

, . . . , a

n

)

 ïîñëåäîâàòåëüíîñòü ýëåìåíòîâ èç

S

, òàêàÿ, ÷òî âñå ýëåìåíòû

a

i

,

i

=

1

,

2

, . . . , n

ðàçëè÷íû:

a

i

6

=

a

j

,

i

6

=

j

. Åñëè ïðè ýòîì

a

i

∈

S

i

, òî ãîâîðÿò, ÷òî

ýëåìåíò

a

i

ïðåäñòàâëÿåò ìíîæåñòâî

S

i

, à âñÿ ñîâîêóïíîñòü

(

a

1

, . . . , a

n

)

íàçûâàåòñÿ ñèñòåìîé ðàçëè÷íûõ ïðåäñòàâèòåëåé (ñ.ð.ï.) äëÿ

M

(

S

)

.

Çàìåòèì åùå ðàç, ÷òî â ñ.ð.ï. åñëè

i

6

=

j

, òî

a

i

6

=

a

j

, åñëè äàæå

S

i

=

S

j

.

Åñëè ìíîæåñòâî ïîÿâëÿåòñÿ íåñêîëüêî ðàç, òî âñÿêèé ðàç îíî äîëæíî èìåòü

ïðåäñòàâèòåëÿ, îòëè÷íîãî îò âñåõ äðóãèõ.

Ñðàçó æå îêàçûâàåòñÿ, ÷òî ñ.ð.ï. ìîæåò ñóùåñòâîâàòü íå äëÿ âñåõ ñîâî-

êóïíîñòåé ìíîæåñòâ. Åñëè â êîíå÷íîé ñèñòåìå ìíîæåñòâà íåïóñòû è ðàç-

ëè÷íû, òî ñ.ð.ï., î÷åâèäíî, ñóùåñòâóåò. Âîçüìåì áîëåå ñëîæíûé ñëó÷àé:

S

=

{

a, b, c, d, f

}

M

(

S

) :

S

1

=

{

a, b, c, d

}

, S

2

=

{

a, b, f

}

, S

3

=

S

4

=

{

b, f

}

.

 ýòîì ñëó÷àå ñóùåñòâóåò äâå ñ.ð.ï.:

(

c, a, b, f

)

,

(

d, a, f, b

)

. Íî ñòîèò èç-

ìåíèòü ëèøü îäíî èç ïîäìíîæåñòâ, íàïðèìåð, âìåñòî

S

2

âçÿòü

S

2

= (

d, f

)

è ìû óæå íå ñìîæåì ïîëó÷èòü íè îäíîé ñ.ð.ï.

44

ÃËÀÂÀ 1. ÝËÅÌÅÍÒÛ ÊÎÌÁÈÍÀÒÎÐÈÊÈ

Òåîðåìà 1.20 (Òåîðåìà î ðàçëè÷íûõ ïðåäñòàâèòåëÿõ). Ïîäìíîæåñòâà

S

1

, S

2

, . . . , S

n

èìåþò ñ.ð.ï. òîãäà è òîëüêî òîãäà, êîãäà óäîâëåòâî-

ðÿåòñÿ ñëåäóþùåå óñëîâèå Ñ: ñðåäè ýëåìåíòîâ ëþáîãî êîíå÷íîãî ÷èñëà

k

ìíîæåñòâ

S

i

èìååòñÿ ïî ìåíüøåé ìåðå

k

ðàçëè÷íûõ ýëåìåíòîâ; èíû-

ìè ñëîâàìè ìíîæåñòâî

S

i

1

∪

S

i

2

∪

. . .

∪

S

i

k

ñîñòîèò íå ìåíåå ÷åì èç

k

ýëåìåíòîâ äëÿ âñåõ

k

= 1

,

2

, . . . , n

.

Çàìå÷àíèå. Åñëè îáùåå ÷èñëî ìíîæåñòâ êîíå÷íî, à ñàìè ìíîæåñòâà áåñ-

êîíå÷íû, òî òåîðåìà îñòàåòñÿ â ñèëå, òàê êàê ìîæíî, î÷åâèäíî, îòáðîñèòü

âñå ýëåìåíòû, êðîìå

n

, â êàæäîì

S

i

, íå íàðóøàÿ óñëîâèÿ Ñ.

Äîêàçàòåëüñòâî. Ïðàêòè÷åñêè î÷åíü òðóäíî ïðîâåðèòü, âûïîëíÿåòñÿ ëè

â äàííîì êîíêðåòíîì ñëó÷àå óñëîâèå Ñ. Äîêàçàòåëüñòâî, îñíîâàííîå íà

ïîëíîé ìàòåìàòè÷åñêîé èíäóêöèè, íå äàåò íè÷åãî, ÷òî ïîìîãëî áû íàéòè

ñ.ð.ï. Ýòî íå óäèâèòåëüíî, òåîðåìû ñóùåñòâîâàíèÿ ÷àùå âñåãî ïîÿâëÿþòñÿ

òàì, ãäå áûâàåò òðóäíî èëè íåâîçìîæíî íàéòè àëãîðèòì, ïðèâîäÿùèé ê

íàõîæäåíèþ ðåøåíèÿ.

Î÷åâèäíî, ÷òî óñëîâèå Ñ åñòü íåîáõîäèìîå óñëîâèå, ïîòîìó ÷òî åñëè

ðàçëè÷íûå ïðåäñòàâèòåëè ñóùåñòâóþò, òî äëÿ ëþáûõ

k

ìíîæåñòâ ïðåäñòà-

âèòåëÿìè áóäóò

k

ðàçëè÷íûõ ýëåìåíòîâ, ñîäåðæàùèõñÿ â ýòèõ ìíîæåñòâàõ.

 êà÷åñòâå äîêàçàòåëüñòâà äîñòàòî÷íîñòè ïðèâåäåì àëãîðèòì, êîòî-

ðûé ïîçâîëÿåò ïîñòðîèòü ñ.ð.ï. èëè ïîêàçàòü, ÷òî òàêîé ñèñòåìû äëÿ äàí-

íîãî íàáîðà ìíîæåñòâ íå ñóùåñòâóåò.

Ïóñòü çàäàíî

n

ìíîæåñòâ è âûïîëíåíî óñëîâèå Ñ. Òðåáóåòñÿ íàéòè äëÿ

íèõ ñ.ð.ï. èëè ïîêàçàòü, ÷òî ýòîé ñèñòåìû íå ñóùåñòâóåò, åñëè óñëîâèå Ñ

íå âûïîëíÿåòñÿ.

Ïðîíóìåðóåì ìíîæåñòâà

S

1

, . . . , S

n

è çàôèêñèðóåì ïîðÿäîê, â êîòîðîì

îíè çàíóìåðîâàíû. Âûáåðåì ïðîèçâîëüíûé ýëåìåíò

a

1

èç

S

1

â êà÷åñòâå åãî

ïðåäñòàâèòåëÿ. Ïîî÷åðåäíî áóäåì âûáèðàòü ïðåäñòàâèòåëåé äðóãèõ ìíî-

æåñòâ:

a

2

∈

S

2

, a

3

∈

S

3

, . . .

, çàáîòÿñü ëèøü î òîì, ÷òîáû êàæäûé èç íèõ

áûë îòëè÷åí îò ëþáîãî äðóãîãî, âûáðàííîãî â êà÷åñòâå ïðåäñòàâèòåëÿ, ýëå-

ìåíòà. Åñëè ýòîò ïðîöåññ óäàñòñÿ äîâåñòè äî

S

n

, òî ìû ïîëó÷èì ñ.ð.ï.

Ìû ìîæåì, îäíàêî, äîñòè÷ü ìíîæåñòâà

S

r

, âñå ýëåìåíòû êîòîðîãî

b

1

, b

2

, . . . , b

t

áûëè óæå èñïîëüçîâàíû êàê ïðåäñòàâèòåëè ìíîæåñòâ

S

1

, S

2

, . . . , S

r

−

1

. Ýòî, îäíàêî, åùå íå îçíà÷àåò, ÷òî ñ.ð.ï. íå ñóùåñòâóåò.

Òîãäà ïîñòðîèì ïîñëåäîâàòåëüíîñòü âñïîìîãàòåëüíûõ ìíîæåñòâ

T

0

, T

1

, . . . .

Çàôèêñèðóåì ïîðÿäîê íóìåðàöèè ýëåìåíòîâ ìíîæåñòâà

S

r

:

S

r

=

{

b

1

, b

2

, . . . , b

t

} ⊂ {

a

1

, a

2

, . . . , a

r

−

1

}

.

1.6. ÑÈÑÒÅÌÛ ÏÐÅÄÑÒÀÂÈÒÅËÅÉ ÌÍÎÆÅÑÒÂ

45

Îïðåäåëèì ìíîæåñòâî

T

0

ñîñòîÿùèì èç ýëåìåíòîâ ìíîæåñòâà

S

r

ñ ôèêñè-

ðîâàííûì âûøå ïîðÿäêîì íóìåðàöèè ýëåìåíòîâ:

T

0

=

{

b

1

, b

2

, . . . , b

t

}

.

Áóäåì äâèãàòüñÿ ïî ñïèñêó ýëåìåíòîâ ìíîæåñòâà

T

0

è ïîñëåäîâàòåëüíî

ñòðîèòü âñïîìîãàòåëüíûå ìíîæåñòâà

T

1

, T

2

, . . .

, äî òåõ ïîð, ïîêà íå îáíà-

ðóæèì ýëåìåíò, íå èñïîëüçîâàííûé â êà÷åñòâå ïðåäñòàâèòåëÿ èëè íå èñ-

÷åðïàåì âñå ìíîæåñòâà. Îáîçíà÷èì ñèìâîëîì

S

(

b

i

)

ìíîæåñòâî, ïðåäñòàâè-

òåëåì êîòîðîãî ÿâëÿåòñÿ ýëåìåíò

b

i

.

Ïóñòü òåïåðü ìíîæåñòâî

T

1

ñîñòîèò èç ýëåìåíòîâ ìíîæåñòâà, ïðåäñòà-

âèòåëåì êîòîðîãî ÿâëÿåòñÿ

b

1

, çà èñêëþ÷åíèåì ñàìîãî ýëåìåíòà

b

1

è âñåõ

îñòàëüíûõ èñïîëüçîâàííûõ â êà÷åñòâå ïðåäñòàâèòåëåé ýëåìåíòîâ:

T

1

=

S

(

b

1

)

\

T

0

.

Ìíîæåñòâî

T

1

ìîæåò áûòü è ïóñòûì, íî åñëè îíî íå ïóñòî, òî ìîäèôèöè-

ðóåì ìíîæåñòâî

T

0

, ïðèïècàâ ê ñïèñêó åãî ýëåìåíòîâ íåïîñðåäñòâåííî çà

b

1

, . . . , b

t

ýëåìåíòû ìíîæåñòâà

T

1

, îáîçíà÷åííûå êàê

b

t

+1

, . . . , b

s

:

T

0

=

T

0

×

T

1

=

{

b

1

, . . . , b

t

|

{z

}

T

0

, b

t

+1

, . . . , b

s

|

{z

}

T

1

}

Äàëåå, åñëè

i

-ûé ýëåìåíò

b

i

åñòü ïðåäñòàâèòåëü ìíîæåñòâà

S

j

=

S

(

b

i

)

,

òî ìû ïîñòðîèì ìíîæåñòâî

T

i

, ñîñòîÿùåå èç òåõ ýëåìåíòîâ

S

j

, êîòîðûå åùå

íå èñïîëüçîâàíû, è çàïèøåì ýòè ýëåìåíòû ïîñëå ýëåìåíòîâ, óæå èñïîëüçî-

âàííûõ:

T

i

=

S

(

b

i

)

\

T

0

;

T

0

=

T

0

·

T

i

.

Òàê ìû ñìîæåì ïîñòóïàòü äî òåõ ïîð, ïîêà ëèáî:

1. ìû äîñòèãëè íåêîòîðîãî ýëåìåíòà

b

i

∈

S

j

(

i > t, j < r

)

, ëèáî

2. ïîñëåäîâàòåëüíîñòü

T

0

èñ÷åðïûâàåòñÿ ýëåìåíòàìè

b

1

, . . . , b

s

êàê ïðåä-

ñòàâèòåëÿìè ìíîæåñòâ.

Âî âòîðîì ñëó÷àå ìû äîëæíû áûòü óáåæäåíû, ÷òî ñ.ð.ï. íå ñóùåñòâóåò. Â

ñàìîì äåëå, ïîëó÷åíà íåêîòîðàÿ ïîñëåäîâàòåëüíîñòü ýëåìåíòîâ

b

1

, . . . , b

v

,

èñ÷åðïûâàþùàÿ ìíîæåñòâî âñåõ ðàçëè÷íûõ ïðåäñòàâèòåëåé. Ýòè ýëåìåí-

òû ÿâëÿþòñÿ ïðåäñòàâèòåëÿìè

v

ìíîæåñòâ

(

v < n

)

. Ïî ïîñòðîåíèþ êàæäûé

ýëåìåíò ýòèõ

v

ìíîæåñòâ ñîäåðæèòñÿ â ïîñëåäîâàòåëüíîñòè. Íî òîãäà ýòè