Материал: Дискретная математика теория и практика

2.5. Свойства биномиальных коэффициентов. Треугольник Паскаля

Биномиальное разложение служит основой для многих комбинаторных формул. Например:

n

1. Пусть a = b = 1. Тогда ∑Сnk = 2n . Так как Сnk – число k-элементных

k =0

подмножеств n-элементного множества, то сумма в левой части есть число всех подмножеств n-элементного множества. Таким образом, получили еще одно доказательства того, что мощность булеана n-элементного множества равна 2n.

n

2. Пусть a = –1, b = 1. Тогда ∑Сnk (−1)k = 0 . Следовательно, суммы бино-

k =0

миальных коэффициентов, стоящих на четных и на нечетных местах, равны между собой, и каждая равна 2n−1 .

вычислить Сnk при n = 0, затем при n = 1, при n = 2 и так далее. Вычисления удобно записывать в виде треугольной таблицы:

32

и Сnk−1 располагаются в этой таблице строкой выше, чем Сnk , и находятся в этой

строке слева и справа от него, то для получения Сnk надо сложить находящиеся

справа и слева от него числа предыдущей строки. Например, значение 10 в шестой строке мы получим, сложив числа 4 и 6 пятой строки.

Эту таблицу называют треугольником Паскаля, по имени французского математика Блеза Паскаля, в трудах которого она встречается. Это название так же, как и бином Ньютона, исторически неточно, поскольку такую таблицу уже знал упомянутый ранее Омар Хайям.

Задачи и упражнения к главе 2

1.Сколько существует способов избрания президента, вице-президента, секретаря и казначея среди членов клуба, включающего 8 студентов последнего курса, 10 студентов предпоследнего курса,15 второкурсников и 20 первокурсников, если:

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

в) студент последнего курса не может быть вице-президентом, г) первокурсники могут быть избраны только на должность секретаря.

2.Сколькими способами можно рассадить класс, если присутствует 26 человек, а мест 28?

3.Сколькими способами можно вытянуть 5 карт бубновой масти из колоды, содержащей 36 карт?

4.Сколько трехзначных чисел можно составить из цифр 1, 2, 3 так, чтобы цифры в записи числа не повторялись?

5.В кухне 5 лампочек с отдельными выключателями. Сколько существует способов освещения?

6.Сколькими способами можно расставить на полке 12 книг, включающих 4 одинаковых учебника по математике, 6 одинаковых учебников по информатике, 2 одинаковых учебника по химии?

7.В булочной продается 10 различных видов пончиков. Сколькими способами можно выбрать 12 пончиков?

8.Сколько прямых линий можно провести через 7 точек, из которых лишь 3 лежат на одной прямой?

33

9.На выпускном вечере 20 студентов группы попарно обменялись своими фотографиями. Сколько всего потребовалось сделать фотографий?

10.Сколькими способами в пассажирский поезд из 9 вагонов можно продать четырем пассажирам билеты в разные вагоны и без этого ограничения?

11.Сколькими способами можно обить 6 различных стульев, если имеется 12 сортов обивочного материала?

12.Сколько слов (включая лишенных смысла) можно составить из всех букв слова «миссисипи»?

13.Найти число возможных вариантов выхода в полуфинал первенства по шахматам трех из 20 участников.

14.Сколько существует способов вытащить из колоды, содержащей 52 карты,

13карт, из которых 9 карт одной масти?

15.Из колоды, содержащей 52 карты, вынули 10 карт. В скольких случаях среди этих карт окажется хотя бы один туз? В скольких случаях ровно один туз? Ровно два туза?

16.Автомобильные номера состоят из трех букв, за которыми идут 4 цифры, например МКМ-07-37.Сколько машин можно снабдить различными номерами, если используется 25 букв?

17.Сколько чисел больше 100 можно записать с помощью цифр 1, 2, 3, 4, если цифры в числе не повторяются?

18.Из 20 сотрудников лаборатории 5 человек должны выехать в командировку. Сколько может быть различных составов отъезжающей группы, если заведующий лабораторией и два ведущих инженера одновременно уезжать не должны?

19.Сколькими способами можно рассадить по жребию восемь рыцарей за круглым столом, чтобы первый и второй рыцари сидели рядом?

20.Двое друзей, А и В, стоят в очереди из 8 человек. Сколько существует вариантов очередей, в которых между А и В стоят два человека.

21.Сколькими способами можно сформировать железнодорожный состав из 9 вагонов так, чтобы второй и четвертый вагоны шли через один?

22.Сколькими способами можно рассадить вокруг круглого стола 6 мальчиков и 6 девочек, если каждая девочка должна сидеть между двумя мальчиками?

23.Сколькими способами можно рассадить случайным образом 12 студентов на

12первых местах одного партера, чтобы студенты А и В сидели рядом?

24.Сколькими способами 7 человек могут встать в очередь так, чтобы два определенных лица не стояли рядом?

25.Две команды, в каждой из которых по 5 спортсменов, строятся в одну шеренгу. Сколькими способами можно построить шеренгу, чтобы игроки одной команды не стояли рядом?

26.Сколькими способами могут быть размещены дни рождения 12 человек в году, считая, что в нем 365 дней. Во скольких случаях все дни рождения попадут на разные дни года, а во скольких на разные месяцы?

27.Найти разложение (a + b)8 , используя треугольник Паскаля.

28.Написать разложение бинома (x − 2 y)5 .

34

29.В разложении (x3 − 3y 2 )10 найдите коэффициент при x9 y14 .

30.Найти член, содержащий x4 в разложении бинома (3 x + x )9 .

31.Найти члены, не содержащие иррациональности в разложении бинома

(72 + 53)24 .

32. Решить уравнение (n + 2)! = 72 .

n!

4

33. Решить уравнение Ax+1 Px−4 = 15 .

Px−1

34. Решить уравнение Cxx+−11 = 21, x N .

35. Решить уравнение C2nn+1 : C2nn−+11 = 7 .

13

36. Решить уравнение Ax5 = 18Ax4−2 .

Глава 3. Отношения. Отображения

3.1. Понятие отношения

Определение 3.1. N-арным (n-местным) отношением P на множествах

A1, A2, …, An называется любое подмножество прямого произведения

A1 × A2 × …× An.

В случае n = 1 отношение P называется унарным (одноместным) и является подмножеством множества A1.

При n = 2 P называется бинарным (двуместным) отношением или соот-

ветствием. Если P A1 A 2 , то также говорят, что Р есть отношение между

множествами A1 и A2 (между элементами множеств A1 и A2 ) или что Р задано (определено) на паре множеств A1 и A2. Если A1 = A2 = A ( P A А ), то гово-

рят, что Р есть бинарное отношение на множестве А.

Пусть Р – бинарное отношение и (x, y) P, тогда говорят, что элемент x находится в отношении P к элементу y, или что x и y связаны отношением P. Вместо записи (x, y) P часто пишут xPy.

В дальнейшем речь будет идти о бинарных отношениях, так как они наиболее часто встречаются и хорошо изучены. Если не будет специально оговорено, то под «отношением» будем понимать бинарное отношение. Частично бинарные отношения (соответствия) уже были рассмотрены в параграфе 1.7. Введем еще несколько определений.

Определение 3.2. Пусть P A B, S A B. Отношения P и S называются равными (пишут Р = S), если для любых x A и y B пара (x, y) P тогда и только тогда, когда ( x , y ) S .

35

Другими словами, отношения Р и S равны, если Р и S равны как множе-

ства.

Определение 3.3. Для любого множества А отношение id A = {(x; x) | x A} называется тождественным отношением (диагональю), а

U A = A × A = {( x; y) | x, y A} – полным отношением (универсальным отношением).

Определение 3.4. Графиком бинарного отношения P R2 называется множество всех точек координатной плоскости Oxy с координатами (x, y) такими, что (x,y) P.

Определение 3.5. Пусть A = {a1 , a2 , ..., an }, B = {b1 , b2 , ..., bm } и P A × B .

Пример 3.1. Если A – конечное множество мощности n, то матрица тождественного отношения id A представляет собой единичную матрицу, а матрица

полного отношения UA представляет собой матрицу, все элементы которой равны 1:

Замечание 3.1. Матрица бинарного отношения P A × B содержит полную информацию о связях между элементами множеств А и В и позволяет представить эту информацию в графическом виде на компьютере. Любая мат-

рица, состоящая из нулей и единиц, является матрицей некоторого бинар- ного отношения.

3.2. Способы задания бинарных отношений

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

1.Списком входящих в отношение элементов (см. пример 1.12).

2.Характеристическим свойством.

Пример 3.2. P = {(x, y ) R 2 x 2 + y 2 = 4}.

3. Графиком (только для подмножеств R2).

Пример 3.3. График, изображенный на рис. 3.1, задает отношение P из примера 3.2.

2ответствия) между двумя различными множествами было введено в параграфе 1.7. Граф, изображенный на рис. 1.7, задает отношение R из примера 1.12. Если отношение P

36

-2

Рис. 3.1