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

36

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

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

N

0

=

D

(

n

) =

n

!(1

−

1 +

1

2!

−

1

3!

+

. . .

+

(

−

1)

n

n

!

)

.

(1

.

26)

Ñóììà â ñêîáêàõ â (1.26) åñòü íà÷àëüíûé îòðåçîê ðÿäà

e

−

1

=

∞

P

i

=0

(

−

1)

i

1

i

!

.

Èç ôîðìóëû (1.26) âèäíî, ÷òî

n

!

e

 õîðîøåå ïðèáëèæåíèå ê

D

(

n

)

, è, â äåé-

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

D

(

n

)

 áëèæàéøåå öåëîå ê

n

!

e

. Ýòî

îçíà÷àåò, ÷òî áåñïîðÿäêè ñîñòàâëÿþò ôèêñèðîâàííóþ äîëþ

e

−

1

âñåõ ïåðå-

ñòàíîâîê è, ÷òî óäèâèòåëüíî, ýòà äîëÿ íå çàâèñèò îò

n

.

 çàäà÷å î áåñïîðÿäêàõ ôóíêöèÿ

b

(

i

)

(ñì. (1.23)) èìååò î÷åíü ñïåöè-

àëüíîå ñâîéñòâî

b

(

i

) =

i

!

 îíà çàâèñèò òîëüêî îò

i

, íî íå çàâèñèò îò

n

.

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

÷åê êîòîðûõ ëåæèò âî ìíîæåñòâå

T

, çàâèñèò òîëüêî îò

|

T

|

, íî íå îò

n

.

Ýòî îçíà÷àåò, ÷òî ôîðìóëó (1.26) ìîæíî ïåðåïèñàòü íà ÿçûêå êîíå÷íûõ

ðàçíîñòåé (ñì. óðàâíåíèå (1.6)) â âèäå

D

(

n

) = ∆

n

x

!

|

x

=0

(Ñîêðàùåííàÿ çàïèñü

D

(

n

) = ∆

n

0!)

.

Òàê êàê ÷èñëî

b

(

i

)

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

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

i

-ýëåìåíòíîì ìíîæåñòâå, çàâèñèò òîëüêî îò

i

, òî æå âåðíî è äëÿ ÷èñëà

a

(

i

)

ïåðåñòàíîâîê, èìåþùèõ â êà÷åñòâå ìíîæå-

ñòâà ïîäâèæíûõ òî÷åê íåêîòîðîå îïðåäåëåííîå

i

-ýëåìåíòíîå ìíîæåñòâî.

Èç êîìáèíàòîðíûõ ñîîáðàæåíèé ÿñíî, ÷òî

a

(

i

) =

D

(

i

)

.

Èç ôîðìóëû (1.26) òàêæå íåìåäëåííî ñëåäóåò, ÷òî ïðè

n

≥

1

D

(

n

) =

nD

(

n

−

1) + (

−

1)

n

,

(1

.

27)

D

(

n

) =

nD

(

n

−

1) +

D

(

n

−

2)

.

(1

.

28)

Çíà÷èòåëüíîãî

òðóäà

òðåáóåò

êîìáèíàòîðíîå

äîêàçàòåëüñòâî

ôîðìóëû (1.27), õîòÿ ïðÿìîå êîìáèíàòîðíîå äîêàçàòåëüñòâî (1.28) ñîâåð-

øåííî ïðîñòî. Ïðèâåäåì åãî.

Âûáåðåì è çàôèêñèðóåì íåêîòîðûé ýëåìåíò

i

>

1

ìíîæåñòâà

{

1

,

2

, . . . , n

}

. Âñå ïåðåñòàíîâêè áåç íåïîäâèæíûõ òî÷åê ðàçîáüåì íà

äâà òèïà ñëåäóþùèì îáðàçîì. Ê ïåðâîìó òèïó

K

1

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

êè, â êîòîðûõ

i

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

1

íå ñòîèò íà

i

-îì ìåñòå

(

K

1

=

{

π

∈

σ

n

|

π

(

i

) = 1

, π

(1)

6

=

i

}

)

. Êîëè÷åñòâî òàêèõ ïåðåñòàíîâîê ðàâíî

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

37

D

(

n

−

1)

. Êî âòîðîìó òèïó

K

2

îòíåñåì ïåðåñòàíîâêè, â êîòîðûõ

i

ñòîèò íà

ïåðâîì ìåñòå, à

1

íà

i

-îì ìåñòå

(

K

2

=

{

π

∈

σ

n

|

π

(

i

) = 1

, π

(1) =

i

}

)

.

Êîëè-

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

D

(

n

−

2)

.

Óêàçàííûå òèïû ïåðåñòàíîâîê

íå ïåðåñåêàþòñÿ, à èõ îáúåäèíåíèå ïî âñåì çíà÷åíèÿì

i

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

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

i

ìî-

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

n

−

1

ñïîñîáîì, ïîëó÷àåì ôîðìóëó (1.28).

Ðàññìîòðèì ïðèìåð, ê êîòîðîìó íåïîñðåäñòâåííî íåïðèëîæèìû ïðåä-

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

ïîðÿäêîâ. Ïóñòü

h

(

n

)

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

M

n

=

{

1

2

,

2

2

, . . . , n

2

}

, íèêàêèå äâà ïîñëåäîâàòåëüíûõ ÷ëåíà êîòîðûõ íå ðàâíû.

Òàêèì îáðàçîì,

h

(0) = 1

, h

(1) = 0

, h

(2) = 2

(ñîîòâåòñòâóþùèå ïåðåñòà-

íîâêè åñòü

1212

è

2121

). Ïóñòü

A

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

π

ìóëü-

òèìíîæåñòâà

M

n

è

P

i

äëÿ

1

≤

i

≤

n

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

π

èìåòü

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

i

. Òîãäà ìû èùåì

f

=

(

∅

) =

h

(

n

)

.

Èç ñîîáðàæåíèé ñèììåòðèè ÿñíî, ÷òî ïðè ôèêñèðîâàííîì

n f

≥

(

T

)

çàâèñèò

òîëüêî îò

i

=

|

T

|

, òàê ÷òî îáîçíà÷èì

g

(

i

) =

f

≥

(

T

)

. ßñíî, ÷òî

g

(

i

)

ðàâíî ÷èñ-

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

π

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

{

1

,

2

, . . . ,

(

i

+ 1)

2

,

(

i

+ 2)

2

, . . . , n

2

}

(çàìåíèòå êàæäîå ÷èñëî

j

≤

i

, âñòðå÷àþùååñÿ â

π

, äâóìÿ ïîñëåäîâàòåëü-

íûìè ÷ëåíàìè, ðàâíûìè

j

), òàê ÷òî

g

(

i

) = (2

n

−

i

)!2

−

(

n

−

i

)

Çàìåòèì, ÷òî

b

(

i

) =

g

(

n

−

i

) = (

n

+

i

)!2

−

i

íå ÿâëÿåòñÿ ôóíêöèåé ëèøü îò

i

,

òàê ÷òî ïðåäøåñòâóþùåå ðàññóæäåíèå â äåéñòâèòåëüíîñòè íåïðèìåíèìî.

Îäíàêî èç ôîðìóëû (1.25) ïîëó÷àåì, ÷òî

h

(

n

) =

n

X

k

=0

n
k

(

−

1)

n

−

k

(

n

+

k

)!2

−

k

= ∆

n

(

n

+

k

)!2

−

k

k

=0

1.5.2 Êîëè÷åñòâî ñþðúåêòèâíûõ îòîáðàæåíèé

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

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

X

èç

n

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

Y

èç

m

ýëåìåíòîâ.

Òåîðåìà 1.14. ×èñëî ñþðúåêòèâíûõ îòîáðàæåíèé êîíå÷íîãî ìíîæåñòâà

X,

|

X

|

=

n

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

Y,

|

Y

|

=

m

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

f

:

X

→

Y

, òàêèõ, ÷òî

f

(

X

) =

Y

, ðàâíî

f

(

n, m

) =

m

−

1

X

k

=0

(

−

1)

k

m

k

(

m

−

k

)

n

.

38

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

Äîêàçàòåëüñòâî. Ïóñòü

Y

=

{

y

1

, . . . , y

m

}

. Îáîçíà÷èì ÷åðåç

α

i

ñëåäó-

þùåå ñâîéñòâî ôóíêöèè

f

:

X

→

Y

: ôóíêöèÿ

f

:

X

→

Y

, òàêîâà, ÷òî

y

i

/

∈

f

(

x

)

. Ïóñòü

F

α

i

 ìíîæåñòâî ôóíêöèé, îáëàäàþùèõ ñâîéñòâîì

α

i

.

Òîãäà î÷åâèäíî, ÷òî

f

(

X

)

6

=

Y

⇔

m

[

i

=1

F

α

i

×èñëî âñåõ ôóíêöèé

f

:

X

→

Y

ðàâíî

m

n

.

Äëÿ ïðîèçâîëüíîé ïîñëåäîâàòåëüíîñòè

α

p

1

, α

p

2

, . . . , α

p

i

, òàêîé ÷òî

1

≤

p

1

< . . . < p

i

≤

m

,

N

(

α

p

1

, α

p

2

, . . . , α

p

i

) = (

m

−

i

)

n

. Èìåííî ñòîëüêî

èìååòñÿ ôóíêöèé

f

:

X

→

Y

\ {

y

p

1

, . . . , y

p

i

}

.

i

-ýëåìåíòíîå ïîäìíîæåñòâî

{

y

p

1

, . . . , y

p

i

}

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

m

i

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

ïî ôîðìóëå âêëþ÷åíèé-èñêëþ÷åíèé èìååì

f

(

n, m

) =

m

n

+

m

−

1

X

i

=1

(

−

1)

i

m

i

(

m

−

i

)

n

=

m

−

1

X

i

=0

(

−

1)

i

m

i

(

m

−

i

)

n

Ñëåäñòâèå. Íà îñíîâàíèè óòâåðæäåíèÿ 1.12 è äîêàçàííîé òåîðåìû

èìååì

S

(

n, k

) =

1

k

!

f

(

n, k

) =

1

k

!

k

−

1

X

i

=0

(

−

1)

i

C

i

k

(

k

−

i

)

n

Òàêèì îáðàçîì, ïîëó÷åíî åùå îäíî ÿâíîå âûðàæåíèå äëÿ ÷èñëà ðàçáèåíèé.

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

àíàëèòè÷åñêèõ èññëåäîâàíèÿõ ñâîéñòâ ðàçáèåíèé, õîòÿ åãî ýôôåêòèâíîñòü

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

íîãî èñïîëüçîâàíèÿ ðåêóððåíòíîãî ñîîòíîøåíèÿ (1.12).

1.5.3 Ïåðåñòàíîâêè ñ îãðàíè÷åíèÿìè íà ìåñòîïîëîæå-

íèå

 çàäà÷å î ÷èñëå áåñïîðÿäêîâ èùóò ÷èñëî ïåðåñòàíîâîê

π

∈

σ

n

, â êîòî-

ðûõ äëÿ êàæäîãî

i

íåêîòîðûå çíà÷åíèÿ

π

(

i

)

çàïðåùåíû (èìåííî,

π

(

i

)

6

=

i

)

.

Ðàññìîòðèì áîëåå îáùóþ òåîðèþ òàêèõ ïåðåñòàíîâîê. Òðàäèöèîííî åå îïè-

ñûâàþò, èñïîëüçóÿ øàõìàòíóþ òåðìèíîëîãèþ.

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

39

Ïóñòü

B

⊆

[

n

]

×

[

n

]

. Ìíîæåñòâî

B

íàçûâàþò äîñêîé. Äëÿ

π

∈

σ

n

îïðåäåëèì

ãðàôèê

G

(

π

)

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

π

óñëîâèåì

G

(

π

) =

{

(

i, π

(

i

))

, i

∈

[

n

]

}

.

Îïðåäåëèì òåïåðü

1.

N

j

=

|{

π

∈

σ

n

:

j

=

|

B

∩

G

(

π

)

|}|

,

2.

r

k

=

÷èñëî

k

-ïîäìíîæåñòâ ìíîæåñòâà B, òàêèõ, ÷òî íèêàêèå äâà ýëå-

ìåíòà íå èìåþò îáùåé êîîðäèíàòû

3.

r

k

=

÷èñëî ñïîñîáîâ ðàçìåñòèòü

k

íå àòàêóþùèõ äðóã äðóãà ëàäåé

íà

B

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

π

∈

σ

n

ñ ðàçìåùåíèåì

n

íå àòàêó-

þùèõ äðóã äðóãà ëàäåé â êâàäðàòàõ

(

i, π

(

i

))

äîñêè

[

n

]

×

[

n

]

. Òîãäà

N

j

åñòü

÷èñëî ñïîñîáîâ ðàçìåùåíèÿ

n

íå àòàêóþùèõ äðóã äðóãà ëàäåé íà äîñêå

[

n

]

×

[

n

]

, ïðè êîòîðûõ â òî÷íîñòè

j

èç ýòèõ ëàäåé íàõîäÿòñÿ â

B

. Íàïðèìåð,

åñëè

B

=

{

(1

,

1)

,

(2

,

2)

,

(3

,

3)

,

(3

,

4)

,

(4

,

4)

}

, òî

N

0

= 6

, N

1

= 9

, N

2

= 7

,

N

3

= 1

, N

4

= 1

, r

0

= 1

, r

1

= 5

, r

2

= 8

, r

3

= 5

, r

4

= 1

.

Íàøà öåëü 

îïèñàòü ÷èñëà

N

j

è, â îñîáåííîñòè

N

0

, â òåðìèíàõ ÷èñåë

r

k

. Îïðåäåëèì

ìíîãî÷ëåí

N

n

ôîðìóëîé

N

n

(

x

) =

X

j

N

j

x

j

Òåîðåìà 1.15. Èìååì

N

n

(

x

) =

n

X

k

=0

r

k

(

n

−

k

)!(

x

−

1)

k

(1

.

29)

 ÷àñòíîñòè,

N

0

=

N

n

(0) =

n

X

k

=0

(

−

1)

k

r

k

(

n

−

k

)!

(1

.

30)

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

Ïóñòü

C

k

åñòü ÷èñëî ïàð

(

π, C

)

, ãäå

π

∈

σ

n

è

C

k

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

æåñòâà

B

∩

G

(

π

)

. Äëÿ êàæäîãî

j

âûáåðåì

N

j

ñïîñîáàìè ïåðåñòàíîâêó

π

òàê,

÷òîáû

j

=

|

B

∩

G

(

π

)

|

, à çàòåì

C

âûáåðåì

j

k

ñïîñîáàìè. Ñëåäîâàòåëüíî,

C

k

=

P

j

j

k

N

j

.

40

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

Ñ äðóãîé ñòîðîíû, ìîæíî áûëî áû ñíà÷àëà âûáðàòü

r

k

ñïîñîáàìè ìíî-

æåñòâî

C

, à çàòåì ðàñøèðèòü åãî

(

n

−

k

)!

ñïîñîáàìè äî ïåðåñòàíîâêè

π

.

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

C

k

=

r

k

(

n

−

k

)!

. Ïîýòîìó

X

j

j

k

N

j

=

r

k

(

n

−

k

)!

,

èëè, ýêâèâàëåíòíî,

X

j

(

y

+ 1)

j

N

j

=

X

k

r

k

(

n

−

k

)!

y

k

.

Ïîëàãàÿ

y

=

x

−

1

, ïîëó÷àåì æåëàåìóþ ôîðìóëó (1.29).

2 Ñïîñîá.
Äîñòàòî÷íî äîêàçàòü ôîðìóëó (1.29) â ïðåäïîëîæåíèè, ÷òî

x

 ïîëî-

æèòåëüíîå öåëîå ÷èñëî. Ëåâàÿ ÷àñòü ôîðìóëû (1.29) ïîäñ÷èòûâàåò ÷èñëî

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

ìåòèòü êàæäóþ ëàäüþ íà B ýëåìåíòàìè ìíîæåñòâà

[

x

]

. Ñ äðóãîé ñòîðîíû,

òàêóþ êîíôèãóðàöèþ ìîæíî ïîëó÷èòü, ïîìåñòèâ

k

íå àòàêóþùèõ ëàäåé íà

ó÷àñòîê

B

, ïîìåòèâ êàæäóþ èç íèõ ýëåìåíòîì ìíîæåñòâà

{

2

,

3

, . . . , x

}

,

ïîìåñòèâ

n

−

k

äîáàâî÷íûõ ëàäåé íà äîñêó

[

n

]

×

[

n

](

n

−

k

)!

ñïîñîáàìè è ïî-

ìåòèâ íîâûå ëàäüè íà

B

åäèíèöàìè. Ýòî óñòàíàâëèâàåò æåëàåìîå âçàèìíî

îäíîçíà÷íîå ñîîòâåòñòâèå.

Äâà äîêàçàòåëüñòâà òåîðåìû 1.3 äàþò åùå îäíó èëëþñòðàöèþ äâóõ êîì-

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

íî, ìîæíî äîêàçàòü ôîðìóëó (1.30) ïðÿìûì ïðèìåíåíèåì ìåòîäà

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

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

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

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

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

âêëþ÷àþùèõ ïàðàìåòðû

x

è

y

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

ìóëó (1.30), ïîëàãàÿ

y

=

−

1

è

x

= 0

.

1.16. Ïðèìåð. (Ñíîâà çàäà÷à î áåñïîðÿäêàõ). Âîçüìåì

B

=

{

(1

,

1)

,

(2

,

2)

, . . . ,

(

n, n

)

}

. Ìû õîòèì âû÷èñëèòü

N

0

=

D

(

n

)

. ßñíî, ÷òî

r

k

=

n
k

,