Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/s43/math/uroki/2013_2014/8mat_1314/spec/01_combinatorics.pdf Дата изменения: Sun Jan 12 19:04:39 2014 Дата индексирования: Sun Mar 2 02:05:59 2014 Кодировка: Windows-1251 Поисковые слова: нлу

Комбинаторикажестве Количество элементов в мно
Количество элементов в множестве
Пример.

A

обозначается

| A|

или

#A

. Достаточно часто,

вместо количество элементов мы будем говорить слово мощность.

(формула включенийисключений)
|A B | = |A B C | = - + | | | | A A A A

| + |B | - | A B | | + |B | + |C | - B | - | B C | - | C A| + B C|

Доказательство. Докажем только второе равенство, используя первое.

|A B C | = |A (B C )| = |A| + |B C | - |A (B C )| = = |A| + |B | + |C | - |B C | - |A (B C )| =
откуда, учитывая что

X (Y Z ) = (X Y ) (X Z ),

получаем

= |A| + |B | + |C | - |B C | - (|A B | + |B C | - |(A B ) (B C )|) = = |A| + |B | + |C | - |A B | - |B C | - |C A| + |A B C |.
Сейчас мы рассмотрим следующую идею:

если между двумя множествами можно установить взаимно однозначное соответствие, то в них одинаковое количество элементов.
Утверждение. Количество

k

-элементных подмножеств

n

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

ства совпадает с количеством последовательностей длины

n

из 0 и 1, в которых ровно

k

единиц.
Доказательство. Занумеруем элементы нашего множества:

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

{a1 , a2 , . . . , an }. длины n из 0 и 1: k

Кажесли

ai

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

i

-ом месте ставим 1, иначе 0.

1

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

-элементные

k

единицами.

Утверждение. Количество подмножеств

n

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

2

n

.

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

что количество подмножеств совпадает с количеством последовательностей длины из 0 и 1. Легко посчитать, что их ровно
Определение.

n

2

n

.

Числом сочетаний из

n

элементов по
n k,

k

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

k

-элементных подмножеств

n

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

k Обозначение. Cn (читается как цэ из эн по ка) или
собов выбрать из пятерых равно


Замечание. Число сочетаний имеет комбинаторный смысл: это количество спо-

n
.

предметов

k

без учета порядка.

Пример. 1. Количество способов выгнать из класса, в котором сидит 23 человека,

5 C23

При таком сопоставлении последовательности называют

характеристическими.


3 C5 равно {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5} {1, 2, 3, 4, 5}.
2. Легко проверить, что

10: и

{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {3, 4, 5} все трехэлементные подмножества

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

(a + b)n

.

(a + b) = (a + b)(a + b) . . . (a + b) ab
i n-i n
, где
раз

n

и, после раскрытия

скобок, все одночлены будут иметь вид до

i

может принимать значения от 0

n

. Стало быть,

(a + b)n = c0 an + c1 a
для некоторых коэффициентов

n-1

b + . . . + ci a

n-i i

b + . . . + cn b

n

ci . n n n-1 Заметим также, что тогда (b + a) = c0 b + c1 b a + . . . + cn an , но (a + b)n = (b + a)n , откуда, сравнивая коэффициенты при ai bn-i в обоих выражениях, можно сразу получить, что ci = cn-i .
Утверждение.

(бином Ньютона)
n-1 i n b + . . . + Cn an-i bi + . . . + Cn bn .

0 1 (a + b)n = Cn an + Cn a

Доказательство. Раскроем скобки в выражении

(a + b)n = (a + b)(a + b) . . . (a + b),
i
. Для этого, в выражении

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

an-i b

(a + b)(a + b) . . . (a + b) мы из остальных n - i скобок

должны выбрать

i

скобок, из которых мы возьмем

b

(тогда

i мы возьмем a). Сделать это можно Cn способами. i Заметим, что из бинома и наблюдения выше (ci = cn-i ) следует, что Cn =
Воспользуемся теперь биномом Ньютона для доказательства следующего
Утверждение.

n Cn

-i

.

i Cn

+1

i i = Cn + Cn-1

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

(a + b)n (a + b)n

+1 +1

0 = Cn+1 an

+1

i + . . . + Cn+1 a(

n+1)-i i

n+1 b + . . . + Cn+1 b n-i i

n+1

0 i = (a + b)n (a + b) = (Cn an + . . . + Cn a 0 = Cn an +1 i + . . . + Cn a( n+1)-i i i+1 0 i + Cn an b + . . . + Cn an-i b 0 = Cn an +1 i + . . . + Cn a( 0 i + Cn an b + . . . + Cn-1 a( 0 = Cn an +1

n b + . . . + Cn bn )(a + b) =

n b + . . . + Cn abn + n+1

n + . . . + Cn b

=
n+1

n+1)-i i

n b + . . . + Cn abn + n b + . . . + Cn b n+1)-i i

n+1)-i i

=
n+1

i i + . . . + (Cn + Cn-1 )a(

n b + . . . + Cn b

Откуда, сравнивая коэффициенты при

a(n

+1)-i i

b

, получаем требуемое.

Замечание. Учитывая бином Ньютона, числа сочетаний достаточно часто назы-

вают

биномиальными коэффициентами.


Треугольник Паскаля
Рассмотрим несколько способов заполнения треугольной решетки. 1. В

k

-ое место

n

-ой строки (и строки, и места в

них нумеруются с нуля) стоит число

k Cn

(см. рис).

0 1 2
0 C2 0 C1

0 C0 1 C1 1 C2 2 C2

2. На 0м и последнем местах каждой строки стоят единицы, а любое другое число равняется сумме двух, стоящих в предыдущей строке левее и правее выбранного. 3. Каждое число равняется количеству способов добраться из вершины, двигаясь только вправо-вниз и влево-вниз. Мы хотим доказать, что на самом деле эти три способа дают одинаковый результат.

0 n Cn

1 Cn

k Cn

n Cn

Для начала заметим, что совпадают 1ый и 2ой способы. Действительно, заметим, что

0 n Cn = Cn = 1

и

k k k Cn+1 = Cn + Cn

-1

, поэтому в 1ом способе на 0м и последнем местах

каждой строки стоят единицы, а любое другое число равняется сумме двух, стоящих в предыдущей строке левее и правее выбранного. Теперь докажем, что совпадают 1ый и 3ий способы. Для этого докажем, что количество способов добраться до такой путь содержит ровно остальные

k -ого места n-ой n ходов (так как

строки ровно

k Cn

. Заметим, что любой

за 1 ход мы увеличиваем номер стро-

ки, в которой находимся, на 1), притом из них ровно

k

раз мы ходили вправо-вниз, а

k мы будем ходить вправо-вниз как раз и равно Cn .
Из 2ого способа легко видеть, что треугольник Паскаля симметричен относительно вертикальной прямой, проходящей через его вершину, и мы еще раз получаем, что

n-k

влево вниз. Количество способов выбрать из

n

ходов те

k

, когда

k n Cn = Cn

-k

.

Упражнение. Выпишите треугольник Паскаля до 6ой строки.

Выделение элемента
Сейчас мы рассмотрим еще одну идею устанавливать соответствие между подмножествами некоего множества.

Зафиксируем какой-то элемент

x

множества разбиваются на пары
-1

A \ { x}

из нашего множества. Тогда все поди

A {x }

(то есть подмноже-

ства отличаются только наличием-отсутствием элемента
Утверждение.

x

).

k k k Cn+1 = Cn + Cn

.

Доказательство. Зафиксируем некий элемент

x

. Все

k

-элементные подмноже-

n + 1-элементного множества делятся на 2 типа: в них либо есть x (таких, как k -1 несложно понять, Cn (поскольку оставшиеся элементы каждого такого подмножества суть k - 1-элементные подмножества n-элементного множества) ), либо его нет k (их Cn ).
ства