Файл: Войтишек В.В. Курс лекций по математике для слушателей подготовительного отделения.pdf

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

Если

объект А можно выбрать тп.

способами,

а второй

объект

ß

(после

того, как

первый

выбран)

-

п

способами,

то

выбор пары

{ й,В

) в указанном

порядке

можно

осуществить ( т . п

)

способами.

Дадим

определение размещений,

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

(все

эти понятия в двух вариантах

-

с

повторением

и без

них),

широко

используя

понятие множества.^

Пусть дано некоторое

конечное

множество,

состоящее

из

эле­

ментов

( ап а& .......aJ -

Вместо

самих

элементов

-

a t

, а g ...

-

можно рассматривать

их индексы

^ 1,2,5

,

Сп-&), (п-і),

п} .

поскольку

природа

а^

с и

к 4 п )

нас

не

интересует. Важно

только,

что можно различать данные элементы.

Определение.

Сочетанием

из п

элементов

по к

(элементов)

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

элементов.

В двух различных сочетаниях из

п

элементов

по к

есть

хотя бы

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

сочетании

и не содержащийся в

другом.

ТЕОРЕМА

(без доказательства). Число

сочетаний

из

п.

элемен­

тов

по^іг (обозначение«?*

и ли (£)),

где

o d k i n . ,

равно

------- —-------- Здесь

принято

считать

0!=

I;

І!= І;

к != І .2 .3 ...СЗН)к.

кКп -к)!

,1

Итак,

С* =

к/Сп-к)!

п

ТЕОРЕМА

к

+ С

к-і

к

( без

доказательства).

С

гг

= С

^.

п

п+ і

Пусть дано конечное упорядоченное множество. (Единственное

требование

к такому множеству

-

приведение

его во

взаимно-одно­

значное

сосответствие

с множеством

{

f,â,3,

... , п } .

Это

соответствие

ся перестановкой элементов

этого

множества.

ТЕОРЕМА (без доказательства).

Число

всевозможных перестановок

из И элементов (обозначение

)

равно

кі/ Итак,

Определение. Операция взаимно-однозначного отображения

на

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

элементов

называется

подстановкой.

Для нее используют

символ

( і

2

3 ...

п

\

(

і

iz

i3 ...

іѣ / .

п.

, располо­

Во второй строке написаны те же самые числа от I до

женные в

другом порядке. Например, . / !

2

3

4 \ .

U

I

3

2 / ' -

Для двух подстановок определяют операцию (ее результат

- но­

вая

подстановка -

называется

произведением

исходных подстановок)

I 2 3. ..п

с,

h

' / 2 3 . . . я

1

К 1,■■■

{

b

f a h

•• ■к

/'

h

к

■■■к

I

г. J

п

Например,

1

2

3

4^/4

2

3

1

1 2

3

4

4

2

3

І/.(

3

2

4

1

3

2

4

1

Этот

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

так: пусть

{

/ , 2 , з , ч ]

-

множе­

остается неподвижной. Какое перемещение описывает

следующее

про­

изведение:

1 2 3 4VA 2 3 IN

/

I 2 3

4 \

?

4 2 3 іД .4 3 2 I /

( 4 3 2 I /

Интересно отметить, что переставлять сомножители

здесь

опас­

н о , т . е .

аб-4 § а

в общем случае.

Определение. Размещением из я

элементов

по к

называется

всякое

упорядоченное

подмножество,

содержащее

ровно к

элементов.

ТЕОРЕМА (без

доказательства).

Число

различных размещений из

п

элементов по£

(обозначение

Д*

) равно fn-yy

'

Следствия. I)

Д° = Рп ;

2)

^

= Pt -

.

Повторения. Допустим, что мы составляем конечное множество

из

п элементов а, , Од, в3 ,... ,а ѣ /причём

любой

эл ем ен ту можно

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

раз.

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

состояло

ровно из

я

элементов,

и каждый элемент встречался

во

множестве ровно один раз. Теперь

разрешается

брать

во

множество

несколько раз элемент

одного сорта.

Но если х = а , х& = а ,

, у = 6 , у^ -6,

у} =6

,

то

( a t b f = а 3+ З а 2Ь +

Появилась возможность привести подобные члены.

Итак, имеется і

ячеек и

я

сортов элементов

по к

штук

каждого сорта.

Определение. Размещением

с

повторениями

из я по К'(п-

число

типов элементов, в каждом типе

по к

одинаковых

элементов)

назы­

вается последовательность элементов длины к ,

причем

одно

разме­

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

равно другому

в том и только

в том случае,

друг от друга или видом входящих в них элементов,

или порядком >

этих элементов.

ТЕОРЕМА.(без доказательства). Число

всевозможных размещений

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

я

по к (обозначение

& )

равно я .

Пример. Всех

трехзначных чисел, составленных из четырех цифр

-[ 1 ,2 ,3 ,4 } ,будет 64

=43

(проверьте!).

элемент

повторяется

я)

раз,

второй элемент

- ,

я& раза и

так

далее,

последний к

-ый

элемент

повторяется

пі

раз “ где л,,...,по­

данные числа и

я, -t n& + n3

+... + n t

= я

,

называется

всякое

размещение с

повторениями из

п

по

к

с

заданным

выше

распределением

повторений.

ТЕОРЕМА (без доказательства). Число различных перестановок

с повторениями

из л

по к

(числа

nf , п&, . .

заданы;

обоз-

начение

Р ( п, , пг , п3>...,

пк ))

равно

п /

СП, +ТІ2 +... + пк)!

п /

nA( n p . . n t !

Ѵ ' Ѵ Ѵ - Ѵ

пз ■

Итак,

D /

п!

"

1

’ "s

"' ■’

'

n j пг !

'

Идея доказательства становится ясной из замечания, что если

бы все

элементы

были

разными,

то

P C U

J

■J X = п ! ,

т . е .

числу перестановок без повторений. А в слу^йіе

повторений п,

означает

число мест

из

п. ,

которые может

занимать первый

эле­

мент.

Неразличимых перестановок

поэтому

ц, /

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

должно уменьшиться в п,!

раз.

Эта теорема используется при подсчете коэффициентов после

раскрытия скобок

в выражении

с х + х а +х

*... +хк) ѣ

(полиномиальная теорема).

Замечание. Число

Р

Сп,,...,

пк ) часто подсчитывается в комбина­

торных задачах,

где

элементы располагаются цепочкой в ряд. Эту и

предыдущие формулы надо применять осторожно,

если

элементы

рас­

положены по кругу или

(как

в случае ожерелья)

этот

круг можно пере­

жается через предыдущие числа. Обозначим

это число так: С к

Тогда с к = РСк, п-i)

=C„+t-i ■

Пояснение. t Многочлен

Q

сх,у,...,

называется однородным

многочленом степени

п ,

ебли

его можно записать

в виде

суммы

одночленов, каждый из которых имеет одну

и ту

же

степень,

равную

п:

=

£

й5 х П,^ Пл ... иУПк,

П,*П2*..*Пк=П

— —

2

Тогда верно утверждение, что в этой сумме

С *

- Сп+к_1

различных слагаемых.

(Это утверждение мы

тоже

не доказываем здесь).

рениями. Сумма кратностей (число к

)

называется порядком соче­

тания.

Всякое

сочетание

с

повторениями

к

-

ого

порядка,

составлен­

ное из множества,

содержащего

п элементов,

называется сочетанием

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

п

элементов по к.

Мы заканчиваем перечисление фактов из комбинаторики еще од­

ним общим правилом, связанным с подсчетом элементов.

Формула включений и исключений. Пусть имеется

п. элементов,

некоторые

из

которых

обладают

свойствами

ы.і , ы.£ , .. ..о ^ .

При этой

каждый элемент

может либо не

обладать ни

одним из

этих

свойств, либо обладать одним или несколькими свойствами.

Пусть

М (ы. >0L

. . , ы і ) -

количество

элементов,

обладающих по

край­

ней мере

свойствами

ы.

ы .■

.. . , <*, .

Запись

ы,

означает,

что

1

' і

к

■ „

к

мы учитываем

элемент,

не

обладающий свойством

.

Тогда

М

(<*,

.,5S) = n-M(dLl)-M&Lj-...-M(dis)+

+ M (c l* J .£ fe+6M(ct.l ,otJ) + .. . + М (<*-, , oij) +■■■

+М

CcL^'CLj) -

- . . . - M C d ^ , d j . „ « V +...

Например, в первой сотне натуральных чисел есть числа, деля­

щиеся на

2 (свойство

оit

) ,

на 3 (с в о й с т в о ^ ) ,

на

5

(свойство

ас

) .

Тогда М (Ы'

,ök£ ,ökj)

- количество чисел,

не

делящихся ни

на 2 ,

ни

на 3 ,

ни на

5. По общей формуле

И

гЦ ,5 g

= 100 - M C М<Ы£ ) - М( ы3 -)+

М Ң , Ы Я) +М(<к,,сі} )+Мбсл ,Ыі ) - M U r ^£ ,<kj)

И <4,5g'äj) - 100-50-33-£0+16+10+6-5=£6.

Заключительное замечание. Приведем примеры задач, в которых

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

"работают" частично.

1. Сколько

существует

разных разверток куба на плоскости?

2 . Сколькими способами можно разложить число

один

миллион

на три разных сомножителя,

каждый их которых не равен

единице.