к‡Б‰ВО III. щгЦеЦзнх нЦйкаа ЗЦкйьнзйлнЦв

§ 1. Некоторые формулы комбинаторики

Комбинаторика — раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами (Ма-

тематическая энциклопедия. Т. 2. С. 974).

Задача 1. Имеется три одинаковых по размерам кубика разных цветов: красного (К), синего (С) и белого (Б). Сколько существует различных вариантов расположения этих кубиков в ряд?

Таких вариантов 6: КСБ, СКБ, СБК, КБС, БКС, БСК.

При решении этой задачи было упорядочено множество трех элементов К, С, Б шестью способами. Упорядочение состояло в закреплении за каждым кубиком (элементом) определенного места (номера).

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

Число перестановок из n элементов обозначается Pn . Мы уже показали, что P3 =6 . Если множество состоит из одного элемента, то, очевидно, существует лишь один способ упорядочения, т. е. P1 =1. Для двухэлементного множества {a,b} можно составить две перестановки: ab и ba, таким образом, P2 =2 или P2 =1 2 . Как мы видели, P3 =6 =1 2 3 . Теперь составим все возможные перестановки из четырех элементов {a,b,c,d}. Для этого к каждой пере-

становке из элементов a, b и c присоединим элемент d, закрепляя за ним поочередно номера один, два, три и четыре. Поскольку P3 =6 ,

а для каждой перестановки из трех элементов можно составить 4 перестановки из четырех элементов (например, для перестановки abc можно составить перестановки dabc, adbc, abdc и abcd), то получится, что

P4 =P3 4 =1 2 3 4 =24 .

— 184 —

Можно было бы доказать, что

Pn =1 2 3 ... (n−1) n .

Произведение 1 2 3 ... (n−1) n обозначается символом n!

(эн факториал). Итак,

Pn =n!

(1)

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

Решение. Искомое количество пятизначных чисел равно числу перестановок из пяти элементов:

P5 =5!=1 2 3 4 5=120 .

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

Решение. Из данных цифр можно составить 120 чисел, причем нас интересуют только те из них, которые оканчиваются на 2 или на 4. Зафиксируем цифру 2 на последней позиции, тогда первые 4 позиции могут занимать цифры 1, 3, 4 и 5. Поскольку P4 =4!=24 ,

то чисел, оканчивающихся на 2, из данных пяти цифр можно составить 24. Легко видеть, что столько же чисел будет оканчиваться цифрой 4. Значит, из цифр 1, 2, 3, 4 и 5 можно составить (без повторений цифр) 48 четных чисел.

Задача 2. Группа студентов из 25 человек выбирает трех делегатов на конференцию. Сколькими способами могут быть проведены эти выборы?

Прежде чем решать задачу, дадим определение.

Пусть имеется множество, состоящее из n элементов. Все его подмножества, содержащие m элементов (m n), называются сочетаниями из n элементов по m элементов.

Обозначим число всех таких сочетаний Cnm . Примем по опре-

делению 0! = 1. Известно, что число перестановок из n элементов равно n!. Предположим, что из данного множества составлены все

— 185 —

подмножества по m элементов, число которых равно Cnm . Возьмем

одно такое подмножество, тогда оставшиеся n – m элементов также образуют подмножество. Сделаем все возможные перестановки в обоих подмножествах; их количества соответственно равны m! и (n – m)!. С помощью этих перестановок образуем перестановки из n элементов, причем так, чтобы первые m мест занимали перестановки первого типа, а последние n – m мест — перестановки второго типа. Число таких n-элементных перестановок равно m!(n – m)!, а всего таких перестановок можно составить

m!(n−m)!Cnm .

Ясно, что таким образом получаются все перестановки из n элементов, т. е.

m!(n−m)!Cnm =n!.

Из этого равенства получается формула для числа сочетаний из n по m:

				Cnm =	n!			.		(2)
					m!(n−m)!
Используя формулу, можно решить задачу 2. Имеем
C253 =	25!	=	1 2 ... 22 23 24 25			=			23 24 25	=2300 .
	3!22!			1 2 3 1 2 ... 22					1 2 3

Отметим без доказательства некоторые свойства сочетаний. Справедливы следующие равенства:

Cnm =Cnn−m ;

Cnm−1 +Cnm−−11 =Cnm .

Замечание. Определим смысл символа Cn0 . По формуле (2) получается

Cn0 =0!nn!!=1.

— 186 —

С другой стороны Cn0 означает число пустых подмножеств

n-элементного множества. Как отмечалось ранее (раздел I, глава 1, § 1), пустое множество является подмножеством любого множества, поэтому равенство

Cn0 =1

можно истолковать так: число пустых подмножеств n-элементного множества равно 1.

Задача 3. Группа студентов из 25 человек выбирает старосту, профорга и культорга. Сколькими способами могут быть проведены эти выборы?

Эта задача похожа на задачу 2, но отличается от нее тем, что нужно не просто выбрать троих из 25, а и распределить их по должностям. Другими словами, на каждое выбранное подмножество (сочетание) из 25 по 3 приходится еще 3! = 6 перестановок. По-

этому результат решения задачи в P3 =6 раз больше, чем C253 , т. е.

равен 2300 6 =13800 .

Определение. Пусть из множества, содержащего n элементов, составлены все сочетания из m элементов (m n). Если в каждом сочетании произвести все перестановки, то все множество образовавшихся комбинаций называется размещениями из n

элементов по m и обозначается Anm .

Из определения следует, что число размещений из n по m больше соответствующего числа сочетаний в m! раз, поэтому

Am =m!Cm =		m!n!		=	n!	.	(3)
n	n	m!(n−m)!			(n−m)!

§ 2. Биномиальная формула Ньютона

Из школьного курса математики известны формулы:

(x +a)1 =x+a ,

(x +a)2 =x2 +2xa +a2 ,

— 187 —

(x +a)3 =x3 +3x2a +3xa2 +a3 .

Заметим, что C11 =C10 =1; C22 =C20 =1 ; C21 =1; C33 =C30 =1;

C32 =C31 =3 . Поэтому формулы можно переписать в виде

(x +a)1 =C10 x +C11a ,

(x +a)2 =C20 x2 +C21 xa +C22a2 ,

(x +a)3 =C30 x3 +C31x2a +C32 xa2 +C33a3 .

Методом математической индукции можно доказать, что для любого натурального числа n, верна формула

(x +a)n =Cn0 xn +Cn1 xn−1a + ... +Cnn-1xan−1 +Cnnan . (*)

Числа Cn0 , Cn1 , ... , Cnn называются биномиальными коэффициен-

тами, а правая частьформулы (*) — разложениембинома(двучлена). Отметим некоторые свойства биномиального разложения.

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

Cn0 =Cnn , Cn1 =Cnn−1,

............

Cnk =Cnn−k .

2) Заменяя в формуле (*) a на –a, получим

(x−a)n =Cn0 xn −Cn1 xn−1a + ... +(-1)n-1Cnn−1xan−1 +(−1)n Cnnan ,

т. е. члены, содержащие a в нечетной степени, имеют отрицательный знак.

3)Разложение бинома (x +a)n содержит n + 1 член.

4)Сумма всех биномиальныхкоэффициентов (x +a)n равна 2n .

—188 —