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

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

11

Äîêàçàòåëüñòâî. Âîçüìåì ïåðåñòàíîâêó

π

∈

σ

n

−

1

ñ

k

öèêëàìè. Ìû ìîæåì

âñòàâèòü ñèìâîë

n

ïîñëå ëþáîãî èç ñèìâîëîâ

1

,

2

, . . . , n

−

1

â ðàçëîæåíèè

ïåðåñòàíîâêè íà íåïåðåñåêàþùèåñÿ öèêëû

n

−

1

ñïîñîáîì, ïîëó÷èâ òàêèì

îáðàçîì ðàçëîæåíèå íà íåïåðåñåêàþùèåñÿ öèêëû ïåðåñòàíîâêè

π

0

∈

σ

n

ñ

k

öèêëàìè, ãäå

n

âñòðå÷àåòñÿ â öèêëå äëèíû, íå ìåíüøåé 2. Ñëåäîâàòåëüíî,

ñóùåñòâóåò

(

n

−

1)

c

(

n

−

1

, k

)

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

π

0

∈

σ

n

ñ

k

öèêëàìè, äëÿ êîòîðûõ

π

0

(

n

)

6

=

n

.

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

π

0

∈

σ

n

−

1

ñ

k

−

1

öèêëîì,

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

π

0

∈

σ

n

ñ

k

öèêëàìè, óäîâëåòâîðÿþ-

ùåé óñëîâèþ

π

0

(

n

) =

n

. Ïîëîæèì

π

0

(

i

) =

(

π

(

i

)

,

åñëè

i

∈

[

n

−

1];

n,

åñëè

i

=

n.

Ñëåäîâàòåëüíî, èìååòñÿ

c

(

n

−

1

, k

−

1)

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

π

0

∈

σ

n

ñ

k

öèêëàìè,

äëÿ êîòîðûõ

π

0

(

n

) =

n

, è äîêàçàòåëüñòâî çàêîí÷åíî.

×èñëà

c

(

n, k

) = (

−

1)

n

−

k

s

(

n, k

)

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

ëèíãà ïåðâîãî ðîäà áåç çíàêà.

Óêàæåì íà åùå îäíó âàæíóþ ðîëü ÷èñåë

c

(

n, k

)

.

Ïóñòü

x

 ïåðåìåííàÿ. Ôèêñèðóåì

n

≥

0

. Òîãäà èìååò ìåñòî

Óòâåðæäåíèå 1.5.

n

P

k

=0

c

(

n, k

)

x

k

=

x

(

x

+ 1)(

x

+ 2)

. . .

(

x

+

n

−

1)

.

Äîêàçàòåëüñòâî. Ïîëîæèì

F

n

(

x

) = (

x

+

n

−

1)

F

n

−

1

(

x

) =

n

X

k

=1

b

(

n

−

1

, k

−

1)

x

k

+ (

n

−

1)

n

−

1

X

k

=0

b

(

n

−

1

, k

)

x

k

.

Îòñþäà ñëåäóåò, ÷òî

b

(

n, k

) = (

n

−

1)

b

(

n

−

1

, k

) +

b

(

n

−

1

, k

−

1)

.

Ïîýòîìó

b

(

n, k

)

óäîâëåòâîðÿþò òåì æå ðåêóððåíòíûì ñîîòíîøåíèÿì è íà÷àëüíûì

óñëîâèÿì, ÷òî è

c

(

n, k

)

, à çíà÷èò, îíè ñîâïàäàþò.

1.3.3 Óïîðÿäî÷åííûå ðàçìåùåíèÿ

Ïóñòü

x

 ïåðåìåííàÿ èëè äåéñòâèòåëüíîå ÷èñëî.

Ïîëîæèì, ïî îïðåäåëåíèþ

[

x

]

n

=

x

(

x

+ 1)(

x

+ 2)

. . .

(

x

+

n

−

1)

.

12

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

Îáîçíà÷åíèå

[

x

]

n

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

n

ôàêòîðèàë îò

x

ââåðõ¿ èëè ¾âåðõíÿÿ

n

-àÿ ñòåïåíü

x

¿.

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

X

 ìíîæåñòâî èç

n

îáúåêòîâ

1

,

2

, . . . , n

, êî-

òîðûå äîëæíû áûòü ðàçìåùåíû ïî

m

ÿùèêàì òàê, ÷òîáû êàæäûé ÿùèê

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

íûõ â íåì îáúåêòîâ. Äâà ðàçìåùåíèÿ ñîâïàäàþò (ðàâíû), åñëè â êàæäîì

ÿùèêå ñîäåðæèòñÿ îäíà è òà æå ïîñëåäîâàòåëüíîñòü îáúåêòîâ. Ðàçìåùåíèÿ

òàêîãî òèïà íàçûâàþòñÿ óïîðÿäî÷åííûìè ðàçìåùåíèÿìè

n

îáúåêòîâ ïî

m

ÿùèêàì.

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

îáúåêòîâ 1 è 2 â äâóõ ÿùèêàõ.

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

òî÷åê

|

, ïðåäñòàâëÿþùèõ ðàçäåëÿþùèå ÿùèêè ïåðåãîðîäêè. Òàêèì îáðà-

çîì 2

|

1 ïðåäñòàâëÿåò ðàçìåùåíèå, ïðè êîòîðîì â ïåðâîì ÿùèêå íàõîäèòñÿ

ýëåìåíò 2, à âî âòîðîì ÿùèêå  ýëåìåíò 1.

Òàáëèöà âñåâîçìîæíûõ ðàçìåùåíèé äâóõ îáúåêòîâ â äâóõ ÿùèêàõ èìååò

ñëåäóþùèé âèä:

∅

|

1 2;

1

|

2;

1 2

|

∅

∅

|

2 1;

2

|

1;

2 1

|

∅

Óòâåðæäåíèå 1.6. ×èñëî óïîðÿäî÷åííûõ ðàçìåùåíèé

n

îáúåêòîâ ïî

m

ÿùèêàì ðàâíî:

[

m

]

n

=

m

(

m

+ 1)

. . .

(

m

+

n

−

1)

(ïîëàãàåì

[

m

]

0

= 1

)

Äîêàçàòåëüñòâî. Ïîñòðîèì ñíà÷àëà òàáëèöó

T

n

−

1

âñåõ óïîðÿäî÷åííûõ ðàç-

ìåùåíèé îáúåêòîâ

1

,

2

, . . . , n

−

1

ïî

m

ÿùèêàì. Êàæäîå ðàçìåùåíèå

i

1

i

2

. . .

|

i

k

i

k

+1

. . .

|

. . .

|

. . .

|

. . . i

n

−

1

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

(

n

−

1) + (

m

−

1)

ñèìâîëîâ,

ÿâëÿþùèõñÿ ëèáî áóêâîé

i

j

, ëèáî âåðòèêàëüíîé ÷åðòîé

|

. ×òîáû èç ýòîé

ïîñëåäîâàòåëüíîñòè ïîëó÷èòü ïîñëåäîâàòåëüíîñòü, ïðåäñòàâëÿþùóþ óïî-

ðÿäî÷åííîå ðàçìåùåíèå

n

îáúåêòîâ â íåå äîñòàòî÷íî âñåìè âîçìîæíûìè

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

n

. Ñèìâîë

n

ìîæíî äîáàâèòü ê ýòîé ïîñëåäîâà-

òåëüíîñòè

(

n

−

1) + (

m

−

1) + 1

ñïîñîáàìè, ïîìåùàÿ åãî ïåðåä ñàìûì ïåðâûì

ñèìâîëîì, ìåæäó äâóìÿ ëþáûìè ñèìâîëàìè è ïîñëå ïîñëåäíåãî ñèìâîëà.

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

|

T

n

|

= (

m

+

n

−

1)

|

T

n

−

1

|

= (

m

+

n

−

1)(

m

+

n

−

2)

. . .

(

m

+ 1)

|

T

1

|

= [

m

]

n

.

Î÷åâèäíî, ÷òî

|

T

1

|

=

m.

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

13

Îòìåòèì ïðîñòûå, ÷àñòî èñïîëüçóåìûå ñîîòíîøåíèÿ:

[

m

]

n

= (

m

−

n

+ 1)[

m

]

n

−

1

;

[

m

]

n

= (

m

+

n

−

1)[

m

]

n

−

1

[

m

]

n

=

m

!

(

m

−

n

)!

;

[

m

]

n

=

(

m

+

n

−

1)!

(

m

−

1)!

[

m

]

n

= [

m

+

n

−

1]

n

;

[

m

]

n

= [

m

]

n

−

1

(

m

+

n

−

1)

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

A

 àëôàâèò (òî åñòü êîíå÷íîå ìíîæåñòâî ñèì-

âîëîâ) ñî ìíîæåñòâîì áóêâ

a

1

, . . . , a

m

, óïîðÿäî÷åííûõ òàê, ÷òî

a

1

< a

2

< . . . < a

m

.

Ñëîâî

x

1

x

2

. . . x

n

äëèíû

n

 ìîíîòîííîå, åñëè

x

1

< x

2

< . . . x

n

.

Ïðèìåð

Ïóñòü

A

=

{

a, b, c, d

}

, a < b < c < d

.

Òîãäà ìîíîòîííûìè áóäóò, íàïðèìåð, ñëåäóþùèå ñëîâà:

aaa, aab, abc, aad, bcd, ddd.

(Ïî íåñêîëüêî óñòàðåâøåé òåðìèíîëîãèè, ýòî êîìáèíàöèè ñ ïîâòîðåíèÿìè

èç m îáúåêòîâ, âçÿòûå ïî n øòóê).
Óòâåðæäåíèå 1.7. ×èñëî ìîíîòîííûõ ñëîâ äëèíû

n

â àëôàâèòå èç

m

áóêâ ðàâíî

[

m

]

n

n

!

.

Äîêàçàòåëüñòâî. Ðàññìîòðèì óïîðÿäî÷åííîå ðàçìåùåíèå

n

îáúåêòîâ

1

,

2

, . . . , n

ïî

m

ÿùèêàì

a

1

, . . . , a

m

è ïóñòü åìó ñîîòâåòñòâóåò ìîíî-

òîííîå ñëîâî ñëåäóþùèì îáðàçîì:

3

|{z}

a

1

|

251

|{z}

a

2

|

87

|{z}

a

3

|

. . .

|

64

n

|{z}

a

m

⇒

a

1

a

2

a

2

a

2

a

3

. . . a

m

a

m

a

m

.

 ñîîòâåòñòâóþùåì ñëîâå áóêâà

a

1

íàïèñàíà ñòîëüêî ðàç, ñêîëüêî îáúåê-

òîâ â ÿùèêå

a

1

, çàòåì áóêâà

a

2

ñòîëüêî ðàç, ñêîëüêî îáúåêòîâ â ÿùèêå

a

2

, . . .

. Êàæäîìó óïîðÿäî÷åííîìó ðàçìåùåíèþ

n

îáúåêòîâ ñîîòâåòñòâóåò

åäèíñòâåííîå ìîíîòîííîå ñëîâî. Âñå ìîíîòîííûå ñëîâà òàêèì îáðàçîì ìî-

ãóò áûòü ïîëó÷åíû. Ìîíîòîííîìó ñëîâó, ñ äðóãîé ñòîðîíû, ñîîòâåòñòâóåò

ðîâíî

n

!

ðàçëè÷íûõ óïîðÿäî÷åííûõ ðàçìåùåíèé. Ïîýòîìó ÷èñëî ìîíîòîí-

íûõ ñëîâ åñòü

[

m

]

n

n

!

.

14

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

Ïðèëîæåíèå. (Çàäà÷à Ìóàâðà). Íàéäåì ÷èñëî ñïîñîáîâ ïðåäñòàâëå-

íèÿ öåëîãî ïîëîæèòåëüíîãî ÷èñëà

m

êàê óïîðÿäî÷åííîé ñóììû

n

íåîòðè-

öàòåëüíûõ öåëûõ ÷èñåë:

m

=

u

1

+

u

2

+

. . .

+

u

n

.

Äâà òàêèõ ïðåäñòàâëåíèÿ

m

=

u

1

+

u

2

+

. . .

+

u

n

è

m

=

u

0

1

+

u

0

2

+

. . .

+

u

0

n

áóäåì ñ÷èòàòü ñîâïàäàþùèìè òîãäà è òîëüêî òîãäà, êîãäà

u

1

=

u

0

1

, u

2

=

u

0

2

, . . . , u

n

=

u

0

n

,

òî åñòü êîãäà ñîâïàäàþò ñëàãàåìûå è ïîðÿäîê èõ ñëåäîâàíèÿ.

Ïîëîæèì çíà÷åíèå

σ

k

ðàâíûì ÷àñòè÷íîé ñóììå ïåðâûõ

k

÷ëåíîâ ïîñëå-

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

u

1

, . . . , u

k

:

σ

k

=

u

1

+

u

2

+

. . .

+

n

k

. Êàæäîìó ïðåäñòàâëåíèþ

m

â âèäå ñóììû

n

ñëàãàåìûõ âçàèìíî îäíîçíà÷íî ñîîòâåòñòâóåò ñëîâî

σ

1

σ

2

. . . σ

n

−

1

,

ãäå

0

≤

σ

1

≤

σ

2

≤

. . .

≤

σ

n

−

1

≤

m.

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

m

â âèäå óïîðÿäî÷åííîé ñóì-

ìû íåîòðèöàòåëüíûõ öåëûõ ñëàãàåìûõ ðàâíî êîëè÷åñòâó ìîíîòîííûõ ñëîâ

σ

1

σ

2

. . . σ

n

−

1

äëèíû

n

−

1

â àëôàâèòå èç

m

+ 1

ñèìâîëà

(

σ

i

∈ {

0

,

1

, . . . , m

}

,

i

= 1

, . . . , n

−

1)

.

×èñëî ïðåäñòàâëåíèé ðàâíî

[

m

+ 1]

n

−

1

(

n

−

1)!

=

(

m

+

n

−

1)!

m

!(

n

−

1!)

.

1.3.4 Ñî÷åòàíèÿ è áèíîìèàëüíûå êîýôôèöèåíòû

Ïðîñòåéøèìè êîìáèíàòîðíûìè îáúåêòàìè ÿâëÿþòñÿ ñî÷åòàíèÿ è áèíîìè-

àëüíûå êîýôôèöèåíòû.

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

X

, ñîäåðæàùåå

n

ðàçëè÷íûõ ýëåìåí-

òîâ. Íàñ èíòåðåñóåò êîëè÷åñòâî ðàçëè÷íûõ

k

-ýëåìåíòíûõ ïîäìíîæåñòâ, êî-

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

X

. Äâà ïîäìíîæåñòâà

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

íèõ ýëåìåíòîì.

Òàêèå ïîäìíîæåñòâà íàçûâàþòñÿ ñî÷åòàíèÿìè èç

m

ýëåìåíòîâ ïî

k

ýëå-

ìåíòîâ è îáîçíà÷àþòñÿ

X

k

, à èõ êîëè÷åñòâî îáîçíà÷àåòñÿ

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

15

C

k

m

èëè

m

k

. Îáîçíà÷åíèå ÷èòàåòñÿ êàê ¾÷èñëî ñî÷åòàíèé èç

m

ïî

k

¿

èëè ïðîñòî ¾èç

m

ïî

k

¿.

Óòâåðæäåíèå 1.8. ×èñëî ðàçëè÷íûõ ïîäìíîæåñòâ èç

k

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

æåñòâà

A,

|

A

|

=

m

åñòü

C

k

m

=

m

k

=

[

m

]

k

k

!

=

m

(

m

−

1)

. . .

(

m

−

k

+ 1)

1

·

2

·

. . .

·

k

=

m

!

k

!(

m

−

k

)!

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

Ïîñòðîèì òàáëèöó

T

âñåõ ñòðîãî âîçðàñòàþùèõ (ìîíîòîííûõ, áåç ïîâòîðå-

íèé áóêâ) ñëîâ äëèíû

k

â àëôàâèòå

A

èç

m

áóêâ.

Ïðèìåð.

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

A

ñîñòîèò èç ïÿòè ðàçëè÷íûõ

ýëåìåíòîâ:

A

=

{

a, b, c, d, e

}

.

Ïîëîæèì

k

= 3

.

Òîãäà òàáëèöà

T

âñåõ ñòðîãî âîçðàñòàþùèõ ñëîâ äëèíû 3 â àëôàâèòå

A

èìååò ñëåäóþùèé âèä:

abc

acd

ade

abd

ace

abe
bcd

bde

bce
cde

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

çíà÷èì ïîëó÷èâøóþñÿ òàáëèöó

T

0

.

T

0

 ìíîæåñòâî ñëîâ áåç ïîâòîðåíèÿ

áóêâ äëèíû

k

â àëôàâèòå

A

.

 òàáëèöå

T

0

íåò ïðîïóñêîâ: êàæäîå ñëîâî äëèíû

k

ïîÿâèòñÿ â òàáëè-

öå

T

0

.

 òàáëèöå

T

0

íåò ïîâòîðåíèé: äâà ñëîâà èç

T

0

ëèáî ïîëó÷åíû èç îäíîãî

ñëîâà

T

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

T

è òîãäà

ðàçëè÷àþòñÿ áóêâàìè.

Ïî óòâåðæäåíèþ 1.2:

|

T

0

|

= [

m

]

k

.

Ïîýòîìó:

|

T

|

=

[

m

]

k

k

!

.