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

6

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

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

ïîäñ÷åò ÷èñëà ýëåìåíòîâ â êîíå÷íîì ìíîæåñòâå. Â ýòîé øèðîêîé ïðîáëåìå

ìîæíî óñëîâíî âûäåëèòü ñëåäóþùèå îñíîâíûå íàïðàâëåíèÿ èññëåäîâàíèé:

•

èçó÷åíèå èçâåñòíûõ êîíôèãóðàöèé;

•

èññëåäîâàíèå íåèçâåñòíûõ êîíôèãóðàöèé;

•

ïîäñ÷åò ÷èñëà êîíôèãóðàöèé;

•

ïðèáëèæåííûé ïîäñ÷åò ÷èñëà êîíôèãóðàöèé;

•

ïåðå÷èñëåíèå êîíôèãóðàöèé;

•

îïòèìèçàöèÿ.

1.2 Äâà ïðèíöèïà êîìáèíàòîðèêè

Ïðè ïîäñ÷åòå ÷èñëà ðàçëè÷íûõ êîìáèíàöèé â êîìáèíàòîðèêå èñïîëüçóþò-

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

Ïðàâèëî ïðîèçâåäåíèÿ: åñëè îáúåêò A ìîæåò áûòü âûáðàí

m

ðàç-

ëè÷íûìè ñïîñîáàìè è ïîñëå êàæäîãî èç òàêèõ âûáîðîâ îáúåêò B â ñâîþ

î÷åðåäü ìîæåò áûòü âûáðàí

n

ðàçëè÷íûìè ñïîñîáàìè, òî âûáîð äâóõ îáú-

åêòîâ ¾A è B¿ â óêàçàííîì ïîðÿäêå ìîæåò áûòü îñóùåñòâëåí

mn

ñïîñîáà-

ìè.

Ïðàâèëî ñóììû: åñëè îáúåêò A ìîæåò áûòü âûáðàí

m

ðàçëè÷íûìè

ñïîñîáàìè, à îáúåêò B ìîæåò áûòü âûáðàí äðóãèìè

n

ðàçëè÷íûìè ñïîñî-

áàìè ïðè óñëîâèè, ÷òî îäíîâðåìåííûé âûáîð A è B íåâîçìîæåí, òî âûáîð

¾A èëè B¿ ìîæåò áûòü îñóùåñòâëåí

m

+

n

ñïîñîáàìè.

1.3 Ôóíêöèè è ðàçìåùåíèÿ

Êëàññè÷åñêîé çàäà÷åé êîìáèíàòîðèêè ÿâëÿåòñÿ çàäà÷à îïðåäåëåíèÿ ÷èñëà

ñïîñîáîâ ðàçìåùåíèÿ íåêîòîðûõ îáúåêòîâ â êàêîì-òî êîëè÷åñòâå ÿùèêîâ

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

ñôîðìóëèðîâàòü íåñêîëüêî áîëåå ôîðìàëüíî ñëåäóþùèì îáðàçîì.

Òåðìèíû ¾ôóíêöèÿ¿, ¾îòîáðàæåíèå¿, ¾ïðåîáðàçîâàíèå¿ è ¾ñîîòâåòñòâèå¿

áóäóò â äàëüíåéøåì èñïîëüçîâàòüñÿ êàê ñèíîíèìû.

Ïðè ýòîì çàïèñü

f

:

X

→

Y

îçíà÷àåò, ÷òî

f

åñòü ôóíêöèÿ ñ îáëàñòüþ

îïðåäåëåíèÿ

X

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

Y

,

1.3. ÔÓÍÊÖÈÈ È ÐÀÇÌÅÙÅÍÈß

7

òî åñòü äëÿ êàæäîãî

x

∈

X

ôóíêöèÿ

f

îïðåäåëÿåò åäèíñòâåííûé ýëåìåíò

y

=

f

(

x

)

∈

Y

.

Ïóñòü äàíû ìíîæåñòâà

X

è

Y

, ïðè÷åì ìíîæåñòâî

X

ñîäåðæèò

n

ýëå-

ìåíòîâ (

|

X

|

=

n

), à ìíîæåñòâî

Y

ñîäåðæèò

m

ýëåìåíòîâ (

|

Y

|

=

m

). Â

ýòèõ òåðìèíàõ çàäà÷à ìîæåò áûòü ñôîðìóëèðîâàíà ñëåäóþùèì îáðàçîì:

ñêîëüêî ñóùåñòâóåò ôóíêöèé (îòîáðàæåíèé), óäîâëåòâîðÿþùèõ çàäàííûì

îãðàíè÷åíèÿì. Ýëåìåíòû ìíîæåñòâà

X

ñîîòâåòñòâóþò îáúåêòàì, ýëåìåí-

òû ìíîæåñòâà

Y

 ÿùèêàì, à êàæäàÿ ôóíêöèÿ

f

:

X

→

Y

îïðåäåëÿåò

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

x

∈

X

ÿùèê

y

=

f

(

x

)

∈

Y

, â êîòîðîì äàííûé îáúåêò íàõîäèòñÿ.

Äðóãóþ òðàäèöèîííóþ èíòåðïðåòàöèþ ìîæíî ïîëó÷èòü, òðàêòóÿ

Y

êàê

ìíîæåñòâî öâåòîâ, à

f

(

x

)

êàê ¾öâåò îáúåêòà x¿. Íàøà çàäà÷à ýêâèâàëåíòíà,

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

òàê, ÷òîáû áûëè ñîáëþäåíû íåêîòîðûå îãðàíè÷åíèÿ.

Íàêîíåö, êàæäîìó îòîáðàæåíèþ

f

:

X

→

Y,

|

X

|

=

n,

|

Y

|

=

m

, ìîæíî

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

<

f

(

x

1

)

,

. . . ,

f

(

x

n

)

>

=

=

< y

1

, y

2

, . . . , y

n

>

=

y

1

y

2

. . . y

n

â àëôàâèòå èç

m

ñèìâîëîâ. Ïîëó÷àåì

òðåòüþ ýêâèâàëåíòíóþ ôîðìóëèðîâêó çàäà÷è: ïîäñ÷åò ÷èñëà ñëîâ â àëôà-

âèòå, óäîâëåòâîðÿþùèõ çàäàííûì îãðàíè÷åíèÿì.

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

öèè íå íàêëàäûâàåòñÿ íèêàêèõ îãðàíè÷åíèé.
Óòâåðæäåíèå 1.1. Åñëè

|

X

|

=

n,

|

Y

|

=

m

, òî êîëè÷åñòâî âñåõ ôóíêöèé

f

:

X

→

Y

ðàâíî

mn

.

Ýêâèâàëåíòíîå óòâåðæäåíèå 1.1': ÷èñëî ñëîâ äëèíû

n

â àëôàâèòå èç

m

ñèìâîëîâ ðàâíî

mn

.

Äîêàçàòåëüñòâî. Áåç ïîòåðè îáùíîñòè ìîæíî âñåãäà ñ÷èòàòü, ÷òî

X

= 1

, . . . , n, Y

= 1

, . . . , m

. Êàæäóþ ôóíêöèþ ìîæíî òîãäà îòîæäå-

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

< f

(1)

, . . . , f

(

n

)

>

=

< y

1

, . . . , y

n

>

. Êàæ-

äûé ÷ëåí

y

i

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

m

ñïîñîáàìè, ÷òî äàåò

mn

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

< y

1

, . . . , y

n

>

.

Îïðåäåëåíèå. Îòîáðàæåíèå

f

:

X

→

Y

ñþðúåêòèâíî, åñëè äëÿ êàæ-

äîãî ýëåìåíòà

y

∈

Y

ñóùåñòâóåò õîòÿ áû îäèí ýëåìåíò

x

∈

X

, òàêîé ÷òî

ϕ

(

x

) =

y

(â êàæäîì ÿùèêå ïðè ðàçìåùåíèè íàõîäèòñÿ õîòÿ áû îäèí îáú-

åêò, âñå áóêâû àëôàâèòà èñïîëüçóþòñÿ â ñëîâå, âñå öâåòà èñïîëüçóþòñÿ ïðè

îêðàñêå).

Îïðåäåëåíèå. Îòîáðàæåíèå

ϕ

:

X

→

Y

èíúåêòèâíî, åñëè

x

1

6

=

x

2

⇒

ϕ

(

x

1

)

6

=

ϕ

(

x

2

)

.

8

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

 ïåðå÷èñëåííûõ èíòåðïðåòàöèÿõ îñíîâíîé çàäà÷è ñþðúåêòèâíîìó îòîá-

ðàæåíèþ ñîîòâåòñòâóþò òàêèå ðàçìåùåíèÿ îáúåêòîâ ïî ÿùèêàì, ÷òî êàæ-

äûé ÿùèê íå ïóñò; ðàñêðàñêè îáúåêòîâ òàêèå, ÷òî âñå öâåòà èñïîëüçîâà-

íû ïðè ðàñêðàñêå; ñëîâà â çàäàííîì àëôàâèòå, òàêèå ÷òî â êàæäîì ñëîâå

èñïîëüçîâàíû âñå áóêâû àëôàâèòà. Èíúåêòèâíîìó îòîáðàæåíèþ ñîîòâåò-

ñòâóþò òàêèå ðàçìåùåíèÿ îáúåêòîâ ïî ÿùèêàì, â êîòîðûõ êàæäûé ÿùèê

ñîäåðæèò íå áîëåå îäíîãî îáúåêòà; òàêèå ðàñêðàñêè îáúåêòîâ, ïðè êîòîðûõ

öâåòà âñåõ îáúåêòîâ ðàçëè÷íû è, íàêîíåö, ñëîâà â àëôàâèòå, âñå áóêâû êî-

òîðûõ ðàçëè÷íû.

Åñëè

x

 äåéñòâèòåëüíîå ÷èñëî, ïîëîæèì ïî îïðåäåëåíèþ

[

x

]

n

=

x

(

x

−

1)(

x

−

2)

. . .

(

x

−

n

+ 1)

.

Îáîçíà÷åíèå

[

x

]

n

÷èòàåòñÿ êàê ¾

n

ôàêòîðèàë îò

x

âíèç¿ èëè ¾íèæíÿÿ

n

-àÿ

ñòåïåíü

x

¿.

Óòâåðæäåíèå 1.2. ×èñëî èíúåêòèâíûõ îòîáðàæåíèé (èíúåêöèé)

ìíîæåñòâà

X

èç

n

ýëåìåíòîâ,

|

X

|

=

n

, âî ìíîæåñòâî

Y

èç

m

ýëåìåíòîâ,

|

Y

|

=

m

, åñòü

[

m

]

n

.

Ýêâèâàëåíòíîå óòâåðæäåíèå 1.2'. ×èñëî ñëîâ äëèíû

n

áåç ïîâòîðåíèé

áóêâ â àëôàâèòå èç

m

áóêâ åñòü

[

m

]

n

.

Äîêàçàòåëüñòâî. Áóäåì îïðåäåëÿòü íà ýòîò ðàç ÷èñëî èíúåêòèâíûõ, (òî

åñòü èìåþùèõ âñå ðàçëè÷íûå ÷ëåíû) ïîñëåäîâàòåëüíîñòåé

< y

1

, . . . , y

n

>

.

Ýëåìåíò

y

1

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

m

ñïîñîáàìè, ýëåìåíò

y

2

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

m

−

1

ñïîñîáîì èç îñòàâøèõñÿ ýëåìåíòîâ. Â îáùåì ñëó÷àå, åñëè óæå âû-

áðàíû ýëåìåíòû

y

1

, . . . , y

i

−

1

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

y

i

ìîæåò áûòü âûáðàí ëþ-

áîé èç

m

−

i

+ 1

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

Y y

1

, . . . , y

i

−

1

. (Ïðèíèìàåì, ÷òî

m

≥

n

, åñëè

n > m

, òî è

[

m

]

n

è èñêîìîå ÷èñëî ôóíêöèé ðàâíî 0). Ýòî äàåò

m

(

m

−

1)

. . .

(

m

−

n

+ 1)

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

íîñòåé

< y

1

, . . . , y

n

>

.

Îòìåòèì, ÷òî

[

m

]

n

=

m

(

m

−

1)

. . .

(

m

−

n

+1) =

m

(

m

−

1)

. . .

1

(

m

−

n

)(

m

−

n

−

1)

. . .

1

=

m

!

(

m

−

n

)!

.

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

f

:

X

→

X

íàçûâàåòñÿ ïåðåñòàíîâêîé ìíîæåñòâà

X

.

 ñîîòâåòñòâèè ñ óòâåðæäåíèåì 2 ÷èñëî ïåðåñòàíîâîê

n

-ýëåìåíòíîãî

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

n

!

.

1.3. ÔÓÍÊÖÈÈ È ÐÀÇÌÅÙÅÍÈß

9

1.3.1 ×èñëà Ñòèðëèíãà ïåðâîãî ðîäà

Âûðàæåíèå

[

x

]

n

ÿâëÿåòñÿ ïîëèíîìîì ñòåïåíè

n

îò ïåðåìåííîé

x

, ñëåäîâà-

òåëüíî åãî ìîæíî ïðåäñòàâèòü â âèäå ñëåäóþùåãî ðàçëîæåíèÿ ïî ñòåïå-

íÿì

x

:

[

x

]

n

=

s

(

n,

0) +

s

(

n,

1)

x

+

. . .

+

s

(

n, n

)

x

n

Ïî îïðåäåëåíèþ, êîýôôèöèåíòû

s

(

n, k

)

òàêîãî ðàçëîæåíèÿ íàçûâàþòñÿ

÷èñëàìè Ñòèðëèíãà ïåðâîãî ðîäà.
Óòâåðæäåíèå 1.3. ×èñëà Ñòèðëèíãà ïåðâîãî ðîäà óäîâëåòâîðÿþò ñëå-

äóþùèì ðåêóððåíòíûì ñîîòíîøåíèÿì:

s

(

n

+ 1

, k

) =

s

(

n, k

−

1)

−

ns

(

n, k

)

, k

= 1

, . . . , n

;

s

(

n,

0) = 0;

s

(

n, n

) = 1

.

Äîêàçàòåëüñòâî. Ïî îïðåäåëåíèþ

[

x

]

n

+1

= [

x

]

n

(

x

−

n

)

. Ïðåäñòàâëÿÿ ïîëè-

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

x

,

ïîëó÷èì:

s

(

n

+1

, n

+1)

x

n

+1

+

. . .

+

s

(

n

+1

, k

)

x

k

+

. . .

+

s

(

n

+1

,

0) = (

s

(

n, n

)+

. . .

+

s

(

n, k

−

1)

x

k

−

1

+

s

(

n, k

)

x

k

+

. . .

+

s

(

n,

0))(

x

−

n

)

.

Âû÷èñëÿÿ è ïðèðàâíèâàÿ

êîýôôèöèåíòû ïðè

x

k

ñëåâà è ñïðàâà, ïîëó÷àåì ïåðâóþ ôîðìóëó óòâåð-

æäåíèÿ. Äðóãèå äâå ôîðìóëû î÷åâèäíû.

Óòâåðæäåíèå 1.3 äàåò ýôôåêòèâíûé ñïîñîá ðåêóððåíòíîãî âû÷èñëåíèÿ

÷èñåë Ñòèðëèíãà ïåðâîãî ðîäà.

Ïðèâåäåì ÷àñòü çíà÷åíèé òàáëèöû

s

(

n, k

)

äëÿ íà÷àëüíûõ çíà÷åíèé

n

è

k

.

s

(

n, k

)

k

= 0

k

= 1

k

= 2

k

= 3

k

= 4

k

= 5

n

= 1

0

1

0

0

0

0

n

= 2

0

-1

1

0

0

0

n

= 3

0

2

-3

1

0

0

n

= 4

0

-6

11

-6

1

0

n

= 5

0

24

-50

75

-10

1

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

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

íîâîê.

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

Ïåðåñòàíîâêè ìíîæåñòâ è ìóëüòèìíîæåñòâ  îäèí èç ñàìûõ áîãàòûõ îáú-

åêòîâ ïåðå÷èñëèòåëüíîé êîìáèíàòîðèêè. Îñíîâíàÿ ïðè÷èíà ýòîãî  áîëü-

øîå ðàçíîîáðàçèå ñïîñîáîâ êîìáèíàòîðíîãî ïðåäñòàâëåíèÿ ïåðåñòàíîâêè.

10

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

Ïåðåñòàíîâêó ìîæíî ïðåäñòàâëÿòü êàê ñëîâî èëè êàê ôóíêöèþ. Â ÷àñòíî-

ñòè, ôóíêöèÿ

π

: [

n

]

→

[

n

]

, çàäàâàåìàÿ ðàâåíñòâîì

π

(

i

) =

a

i

, ñîîòâåòñòâóåò

ñëîâó

a

1

a

2

. . . a

n

.

Åñëè ðàññìàòðèâàòü ïåðåñòàíîâêó

π

êîíå÷íîãî ìíîæåñòâà

S

êàê âçà-

èìíî îäíîçíà÷íîå îòîáðàæåíèå

π

:

S

→

S

, òî åñòåñòâåííî äëÿ êàæäî-

ãî

x

∈

S

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

x, π

(

x

)

, π

2

(

x

)

, . . .

. Â êîí-

öå êîíöîâ (òàê êàê

π

 âçàèìíî îäíîçíà÷íîå ñîîòâåòñòâèå, è ìíîæåñòâî

S

ïðåäïîëàãàåòñÿ êîíå÷íûì) ìû âíîâü ïîëó÷èì

x

. Òàêèì îáðàçîì, äëÿ

íåêîòîðîãî åäèíñòâåííîãî íàèìåíüøåãî

k

≥

1

èìååì, ÷òî

π

k

(

x

) =

x

è

ýëåìåíòû

x, π

(

x

)

, . . . , π

k

−

1

(

x

)

âñå ðàçëè÷íû. Íàçîâåì ïîñëåäîâàòåëü-

íîñòü

(

x, π

(

x

)

, . . . , π

k

−

1

(

x

))

öèêëîì ïåðåñòàíîâêè

π

äëèíû

k

. Öèêëû

(

x, π

(

x

)

, . . . , π

k

−

1

(

x

))

è

(

π

i

(

x

)

, π

i

+1

(

x

)

, . . . , π

k

−

1

(

x

)

, x, . . . , π

i

−

1

(

x

))

ñ÷èòàþòñÿ ýêâèâàëåíòíûìè. Êàæäûé ýëåìåíò

S

âñòðå÷àåòñÿ òîãäà â åäèí-

ñòâåííîì öèêëå ïåðåñòàíîâêè

π

, è ìû ìîæåì ðàññìàòðèâàòü

π

êàê îáúåäè-

íåíèå íåïåðåñåêàþùèõñÿ öèêëîâ èëè, ïî-äðóãîìó, êàê ïðîèçâåäåíèå ðàç-

ëè÷íûõ öèêëîâ

C

1

, . . . , C

n

.

Íàïðèìåð, åñëè ïåðåñòàíîâêà

π

: [7]

→

[7]

îïðåäåëåíà êàê

1

2

3

4

5

6

7

4

2

7

1

3

6

5

,

òî åñòü

π

(1) = 4

, π

(2) = 2

, π

(3) = 7

, π

(4) = 1

, π

(5) = 3

, π

(6) = 6

, π

(7) = 5

,

òî

π

= (14)(2)(375)(6)

. Êîíå÷íî, âîçìîæíû ðàçëè÷íûå îáîçíà÷åíèÿ òàêîãî

ïðåäñòàâëåíèÿ ïåðåñòàíîâêè; íàïðèìåð, èìååì:

π

= (753)(14)(6)(2)

.

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

•

â êàæäîì öèêëå ïèøåòñÿ ïåðâûì åãî íàèáîëüøèé ýëåìåíò;

•

öèêëû çàïèñûâàþòñÿ â ïîðÿäêå âîçðàñòàíèÿ èõ ìàêñèìàëüíûõ ýëå-

ìåíòîâ.

Ïóñòü

c

(

n, k

)

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

n

ýëåìåíòîâ,

êîòîðûå èìåþò

k

öèêëîâ. Áóäåì îáîçíà÷àòü ìíîæåñòâî âñåõ ïåðåñòàíîâîê

n

-ýëåìåíòíîãî ìíîæåñòâà ñèìâîëîì

σ

n

.

Óòâåðæäåíèå 1.4. ×èñëà

c

(

n, k

)

óäîâëåòâîðÿþò ñëåäóþùåìó ðåêóð-

ðåíòíîìó ñîîòíîøåíèþ:

c

(

n, k

) = (

n

−

1)

c

(

n

−

1

, k

) +

c

(

n

−

1

, k

−

1)

, n, k

≥

1

ñ íà÷àëüíûìè óñëîâèÿìè

c

(

n, k

) = 0

, ïðè

n

≤

0

èëè

k

≤

0

, çà èñêëþ÷åíèåì

c

(0

,

0) = 1

.