Diskretka

Diskretka.doc20.02.2014

51

σ

M

приσ

i

= 1

i

i = 1,2, …n,

Mi i =

M i приσ

i

= 0

М, * = <

, I = 1, 2,п..., ,

первичнымтермо.

вдальбудемнейшемазывать

Множествови

да

n

Miσi

= M1σ1

M 2σ2 ...

M nσn σI

= 0,1 назовем конституентой.

i=1

I

I

I

2n.Каждойконституентеможно

Общеечислоразличныхконституентнепревышает

сопостдвоичныйадлинывитьбор

I

п, числоэтихнаборовравно

2n.Еслинекоторые

конституентыравны

,то

бщееколичествоконституентменьше

2n,приэтомсреди

подмноженайдутхотябыдватакие,скоттвямовыразирыежноодночерездругое,т..ь

зависимые.Например,если

п= 2

и

M 2

=

M1

, тосуществуюттолькодвеотличные

конституенты

= M 0

M

0 = M 1

I

M 2

. C = M 0

I

M 1 ,

C = M 1

I

M 0 .

1

2

1

2

1

1

2

2

1

2

различныхко иеституентпусто.

Лемма1.1.

Пересечедвух

I

C

n

M σi

C =

n

*

≠ σ *

Действ,еслконституентытельно

a

=

и

M σi различны,то

σ

k

i=1

i

b

i=1

i

k

σk*

покрайнмердляодногоей

k, k ≤ n.Нот

σk

=

следовательно.

=

MIk

I M k

I

Лемма1.2.

Объединенвсехконстравноитуент

гда

1. ,

I

Ca

Cb

.

Представим 1 ввиде

n

(Mi0

Mi1 )

1 =

i=1

правойчастиравенстполучимобъединениевсеха

и,раск,рывобки

U

конституент. I

Контрольныевоп

росы

1Ч.т:акоедекартомножеспроизв;декартоваедениестепенькоторого

множества А;бинарноеотношение,задма ноеожестве

А?

2Ч.тунаракотношениео,приведитепримеры.

3Ч.тбинарноеактношение,приведитепримеры.

4Назовите. ос

новныесвойсбинарныхотношенийва.

5Какое. отношазываетр ниефлексивным,симметричным,я

антисимметр,транзит? ивчным

6Какое. отнотношениемазываетсяэквивалентности?

7Дайте. определениеотобрамножествания

А множество

В.

Поясните

терминмощ« но»жества.сть

8Ч.тсюръекцияакое,инъекция,биекция?

9Дайте. определенфункции. е

10Чемув.математикеслужатотношения?

11Какклассифицируютсвязей. отношениявзависч сламомеждусти

элементаминожества?

12Дайте.определение

бинаротношения. го

13Чтопредставляет. собойдекартомножествпроиз ?едение

Аа,=Вb},{=

{1,

3};

14Выпиши. декарпроизтмножествведенияы

декартовогоквадрата

А=а}{1, .

A

=

{1,

2,...,i,

15Скольэлементов. ключдекквадратретмножестваовый

...,n}?

n-арногоотнвтерминахшения

16Дайте.определбинар,тернарногоииеого

множеств.

Diskretka.doc20.02.2014

52

17Чтопонимают. подрефлексантирефлексивнымиотношениями?

18Какхарактеризуются. асимметричные,

иантисимметротношен? иячные

19Да. йтеопределениетранзитивногоотношения.

20Дайте.определенотношенияэквивалентностиприведитепримеры.

21Какое.отношениеазываетсяот ошениемстпорядка?Явогоголяется

отношение ≤ намножестве А= {1, 2, 3}

отнестошениемпорядка?огого

22.Какоеотнотношениемазываетсястрпорядка?гого

23Какое.множествоназываетсяупорядоченным,полностьюупорядоченным?

24Чт. линакоепорядок?йный

25Дайте.определенфункции. е

R а>,= {<1а>},b>, <2,

26Яв. лотношениеяется

,определенно енадекартовом

произведениимножеств

А= {1,2},а b}

B = {

,функцией?

27Яв. лфункцияяется

f(х)х=

2 инъективной?

Лекция№

5

Извнимательногоисследованияча тнлучаяжетго

возникнутьобщее

понимание.

А.ПойаМатематикаправдоподобные

рассуждения.М.Наука: , 1975.

ЭЛЕМЕНТЫКОМБИНАТОРИКИ

(лек.час2+пр.зачас2нятк+лаб.час4.самос+. ча12)

Комбинаторика – эторазделматематики,изучающийсвобъек,стваосаовленных

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

изкон ечногомножества.

Комбинматематикучастоназываютторную

анализом иликомбинаторикой.

Типичнызадачакомбинмиявляютсяараздкиеторикикакперестановкилы,

разбиениямножествчисел,биномиальныекоэффици,производящиефункциитнты

.д.а,

такжеалгоритмыгенерирупомянутыхк ваниямбинаторныхобъектов.Классической

задачейкомбинаторикиявляетсязадача

определениячисласпособовразмещениякаком

-то

количестящико« » ве

так,чтобыбыливыполненынекоторыеусл.Комбинавияимееторика

Diskretka.doc20.02.2014

53

делосконечнымимнож,поэтомустваминазываютиногда

теориейконечных

множеств.

Основныеправилакомбинаторики

Правилопроизведения

.Пустьимдеемкартовопроизведениедвухмножеств

{a,b,c}×{1,2,3,4}.Числоэлементов,которог

оравнопроизведчислаэлементоврвогонию

×4 = 12. В

множестваначислоэлемевтормнтов,даногожесслучаеэтобудетва3

общемслучаеможносформулпроизведенияатьправи:ло

k независимых операций,каждая

Еслитребуетсявыполнитьследовательно

можетбытьвыполнена

ni (i

=1,2,

,k)спос,тобщеечбамиисходовлоравноих

произведению n = n1 n2 ... nk.

n

Числоэлементовдекартовапроизведениямощность( )

сомножителейравно

произведениючислаэлемощности( ентов)каждого

изэтихсомножителей.

Правилосумм.

x можетбытьвыбран

m способами,элемент

y - n спос,тобами

Есэлементи

выбор,либо

x, либо y можетосуществляться

m + n способами.

Перечислкомбинаторикательная

Кперечислкомбиоттельнойзаосятсядачторике

поискачисласпособов

построениякортежейизэлементконечногомн,какжестваразными,такодинаковыми.

Простейшикортежаявляютсями

перестановки,размещениясочетания

.

Пусть A – конечноемножество,состоящееиз

n эле,т.емощность. енэтовго

множества│

A│= card A = n.

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

Дамножество

A. Пусть A – конечноемножество,состоящееиз

n

элементов A =

{a1, a2, …, an},т.е.мощностьэтогомн│жества

A│= card A = n.

Перестановкой элементовмножества

A называелюбойкортсяеж

<a1, a2, …, an>

состоящийиз

n различэлементовыхожества

A.

Посткоизрэтоготежиоиммн жества

A длиной n.Кортежибудутотличатьсядруг

отдругатолькопорядкаждом,таккав изнихвстречаютсяпоодномуразувсе

элементымножества

A. Этикортежиназыв

аются перестановками иобозначаются Pn (от

англ.

permutation).

Числоперестановокпределимисходяизследующегорассуждения.Наперместевом

кортежеможнопоставитьлюбойиз

n элемент,навторместоев

- любойиз

n-1 оставшихся

и т.д.Дляпослмеостаднегоединствеетсяэлемент.Общеечислокортежейный

n (n-1)

(n-2) …2 1,т.е.

Pn = n!

Пример.

{1,2,3}.

Сколькотрехзначчиселможсоснизтыхорехавитьцифр

Решение

Кортежибудутсоо равныветственно:

<1, 2, 3>;

<1, 3, 2>;иихчисло<2,равно1, 3>;

<2, 3, 1>; <3, 1, 2>;

<3, 2, 1>,

P3 = 3! = 1 2 3 6=

A

Подчеркнемещераз,чтоприведеннформуласправедлива,еслимножествоя

состоитиз

разных элементов.

Перестановкиповторениями

Пустьвмножестве

A имеютсяодинаковыеповторяющиеся( )элементы.

Перестановкойповторениями

состава(

n1, n2, … ,nk)изэлементов(

a1, a2, … ,ak)называется

кортеждлиной

n = n1 + n2 + …+ nk, вкоторый a1 входит n1 раз, a2

входит n2 разит.д.Число

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

Diskretka.doc20.02.2014

54

P (n , n ..., n ) =

n!

(n1 + n2 +... + nk )!

=

1

2

k

n1

!n2 !...nk !

n1 !n2 !...nk !

Пример.

Сколькословможнополучить,переставляябуквысловеМАТЕМАТИКА« »

Решение

СловоМАТЕМАТИКА« »являекордлтсяежем10,инымеющимсостав(2, 3, 2, 1,

1,т.е.буква1)М«»входитдвар,буквазаА«»входитраза3,букваТ«

»входитдвар, за

остальныепоодномуразу.ЧислословприперебуквстановкеловаМАТЕМАТИКА« »

будетравно

10!

P (2,3, 2,1,1,1) =

=151200

2!3!1!1!1!

Дадимдругоеопределениепереста.Наязыкемноэтоможножестввкипредставить

следующимобразом.

f: X —> Y называется перестановкой

Каждоевзаимноодноз

начноеотображение

множества X.

Если тп,=

токаждаявзаимнооднозфуначнаякция

f: X —> Y являетсявзаимно

однотображениемзначныммножества

X намножество

Y. Втакомслучае

[п] п =пп(

-1)п (

-

2) . . . 1 обозначаем п! (п факториал).

Теорема.

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

n-элемножестваентногоравно

п! .

Доказательствоследуетизпредыдрасс. ущегождения

Спрзавочныеисимости.

|т|

п =т( - п+1)т| |

п-1

|т|

п =т!

/п!

|т| п =т+п|

-1|п

Размещения

k (1≤ k≤n), состоящие из различных элементов n-элементного

Кортежидлины

множества A (кортличаютсяежиодинотдругогокаксамиэле,мтакихентами

порядком),называются

размещениями из n

элементовмножества

A

по k. Числотаких

размещеобычобозначаетсяоий

Ak

(бу ква

A отфранцузскогослова

arrangement

-

размещение)или

|n|k.

n

k

n-элемножестваентногобез

Схемавыборасостоитвыборе

элементовиз

возвращения.Дляэтогонеобходимосовершить

k действий:первоедействиеможно

совершить n способами,второеуже

n -1 способами,

k-едействие n – (k – 1) способами.

Согласновышеуказаннправилупроизведенияполумунечнперестановокаемисло

Ak = n (n −1) ...(n − k +1).Умножимразделимна

(n − k )!,получим:

n

Ak =

n!

n

(n − k )!

Отличиеразмещения

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

.Еслиразмещенияотличаютсядругдруга

толькопорядкаждом,таккавкизнихвстречаютсяпоодномуразувсеэлементы

P = An .

множества A, то

акиеразмещенияявляюперестановками,..

Пример.

Дано A = {1, 2, 3}.Найтивсеразмещенизтрехэлементовподваиихя

n

n

число.

Решение.

<1, 2>; <1, 3>;

<2, 3>; <2, 1>;

<3, 1>;

<3, 2>. Числоразмещений,как

видноравно6.

3!

1 2 3

A2

=

=

= 6

3

(3 − 2)!

1

Diskretka.doc20.02.2014

55

Подчеркнемещераз,чтоприведеннформуласправедлива,еслимножествоя

A

состоитиз

разных элементов.

Размещениясповторениями

A

Пустьвомножестве

имеютсяодинаковыеповторяющиеся( )элементы.

Размещениямисповторен ями

из n элементовпо

k называютсякортежидлиной

k,

составленныеиз

n-элемножестваентного

A. Числоэтих

кортежейобозначают

Ak

.Черта

n

Ak

= nk

Пример.

n

Сколькопятизначныхтелефонныхноможносоставитьеровизэлементов

множества{0,1,2,3,4,5,6,7,8,9}.

Решение.

k =составленные5,из

Телефонныеном

ераявляюкортежамидлинойся

десятиэлементногомножествавозвращени,..дляк изждогопятиеместьентов

девятьспособоввыбора.

A5

= 105

= 100000

10

Рассмотримразмещениянаязыкемножеств.

Дамныожества

X, Y, причем \X\ = n, |Y| = m. Сколькосуществуетфункций:

X —>

Y, удовлетворяющихзаданнымограничениям?

X соответствуютобъектам,элементымножества

Y — ящикам,

Элементымножества

акаждаяфункция

f:. X —> Y определяетнекотороеразмещение,указываядлякаждого

объекта x X ящик

y Y , вкоторомданобъектныйаходится.Другуютрадиционную

интерпполучим, ретациюактуя

Y какмножцв«»,аетоство

f(х)

какцвет«объекта

х».

Нашазад,такимобразомча,эквивалентнавопр,скосу

лькиспосможнопокраситьбами

объектытак,чтобыбылисоблюденынекоторыеограничения.

Х=п}{1, ...,

и Y = {1,

Заметим,чтобезпотериобщностиможемвсегдасчи, тоать

...т}, . Каждуюфункцию

f

можнотогдаот ждествитьпоследовательностью

< f(1)

, ,.., f

(п)> .

Нашазадимеетсамыйчапростойвид,еслиненакладываетсяникакихограничений

наразмещ.И следующаястниятеорема.

f: X —> Y равно тn.

Теорема1.1.

Если |X| = n, |Y| = m, точивсфункцийлоех

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

Считая,что

Х =

{1, ..

.п,} ,сводимнашузадачуквопросучи леех

последовательности < y1 ..., yn > с членамииз

m-элемножестваентного

Y.Каждыйчлен

последовательности yi

мыможемвыбрать

т способами,чтодает

тn возможностейвыбора

последовательности < y1 ..., yn >.

Легтанайтикчисложеразмещений,длякоторыхкаждыйящиксоднеболеержит

одногообъекта

— такжеразмещенсоответстввзаоднозиямнофункция.ютачным

Обозначимчерез

|т|

п чивсвзаимнолоехднозфуизначныхкций

n-элементного

множества m-элементноемножество.

Упоразмещениеядоченное

Разместим п объектовпо

m ящикамтак,чтобыаждыйящиксодержалбы

последовательность,немножество,какпрежде,помещенныхбъектов.Два

размещенияназовем

равными,есливкаждомящикесододнаритжится

е

последовобъек.Размещениятельностьакогоовтипаназываются

упорядоченными

размещениями п объектовпо

m ящикам.Обознчислотупорядоченийак черезхм

|т| п .

Теорема1.4.

Числоупоразмещенийядоченных

n объектовпо

т ящикамравно

|т| п =тт(+1

) т.+. . (

n-1)