Zabotin_Dulliev_Chernyaev_-_Mat_an

Элементы комбинаторики. Бином Ньютона.

Введем обозначение: 1 2 3 ... n = n! (читается «n-факториал»). Из определения ясно: n!= (n − 1)! n .

Например: 5!=1 2 3 4 5 = 4! 5 .

Очевидно, величина 0! не определена, однако во многих формулах общего вида эта величина встречается и значение ей удобно придавать равное единице, т.е. 0!=1. Мы также примем это соглашение, которое нас не будет приводить к неверным результатам.

Пусть даны два множества A ={a1 , a2 ,...,an } и B ={b1 , b2 ,..., bn }. Биекцию, отображающую A на B, назовем перестановкой, а число всех возмож-

ных перестановок обозначим pn .

Содержательный смысл: если a1 , a2 ,...,an – различные шары (занумерованные шары), а b1 , b2 ,..., bn – лунки, то pn – число способов, которыми шары можно расположить в лунках, помещая в каждую лунку лишь один шар.

Докажем, что pn = n!.

Сделаем это с помощью математической индукции. Очевидно, p1 =1 =1! Полагая pn = n! доказанным, добавим еще один шар и одну лун-

ку. Ясно, что an+1 имеет n + 1 вариант попадания в лунку и на каждый из этих вариантов приходится pn вариантов для остальных шаров, следовательно

pn+1 = pn (n +1) =(n +1)!,

что и требовалось.

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

Пусть теперь A ={a1 , a2 ,...,am }, B ={b1 , b2 ,..., bn } и m ≤n .

Инъекцию из A в B назовем размещением, а число всех возможных размещений обозначим A mn .

Содержательный смысл: если a1 , a2 ,...,am – занумерованные (различи-

мые) шары, а b1 , b2 ,..., bn – лунки, то A mn – это число способов, которыми эти

шары можно расположить в лунках, помещая в лунку лишь один шар. При этом, если поменять в каком-либо варианте местами любые два шара – получим новый вариант.

Докажем, что

Доказательство проведем с помощью индукции по переменной m. Очевидно An1 = n = n − (1 − 1) .

21

Пусть (1.2.2) доказано. Добавим еще один шар am+1 . Ясно, что на каждый из вариантов размещения шаров a1 , a2 ,...,am приходится (n − m) вариан-

тов расположения шара в оставшихся свободными (n − m) лунках. Таким об-

разом Anm+1 = Anm (n − m) = n(n − 1)(n − 2)...(n − (m − 1))(n − m) . Что и требова-

лось.

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

Замечание. Для Anm можно получить еще одну удобную формулу:

Эта формула получается из равенства (1.2.2) делением и умножением его правой части на (n − m)!.

Пусть вновь даны A = {a1 , a2 ,...,am }, B = {b1 , b2 ,..., bn } и m<n. Все множество инъекций из A в B разобьем на группы по следующему принципу: две инъекции f1 и f 2 отнесем к одной и той же группе, если

f 1 (A) = f 2 (A). Каждую такую группу отображений назовем сочетаниями, а

число всех возможных сочетаний обозначим Cnm .

Содержательный смысл здесь тот же, что и у размещений с той разницей, что если в фиксированном варианте расположения шаров в лунках поменяем местами два шара, то не получим нового варианта.

Из сказанного очевидна формула:

мул мы считали m<n. Однако из содержательного смысла числа C nn следует,

что C nn = 1. Действительно, существует лишь одна группа инъекций из {a1 , a2 ,...,an } в {b1 , b2 ,..., bn } указанного выше вида или, то же самое, лишь

одним способом можно разместить n неразличимых шаров в n лунках. Из сделанного замечания, кстати, следует, что соглашение о равенстве 0!=1 необходимо было принять, поскольку из формулы (1.2.5) следует:

22

Свойства числа Cnm .

1°. Симметричность: Cnm = Cnn−m . Доказательство очевидно из (1.2.5). 2°. Для всех n,m (m≤n) имеет место:

Доказательство. Воспользуемся формулой (1.2.5):

C30C31C32C33

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

Cn0Cn1 ...Cnm−1Cnm ...Cnn

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

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

учесть это правило и то, что Cn0 = Cnn =1 для всех значений n, то легко построить этот треугольник уже «в числовом виде»:

11

12 1

1 3 3 1

………………………..

Кстати, теперь получена и иллюстрация свойства 1° – симметричности. Треугольник Паскаля удобен для вычислений Cnm с достаточно

малым n.

Числа сочетаний C mn часто называется биномиальными коэффициен-

тами.

23

Бином Ньютона.

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

(a +b)2 = a2 +2ab +b2 , (a +b)3 = a3 +3a2b +3ab2 +b3

(формула (a +b)1 = a +b очевидна).

Если внимательно посмотреть на правые части этих формул, то можно увидеть две интересных особенности: во-первых,– коэффициенты, стоящие перед степенями величин a и b, являются элементами соответствующей строки треугольника Паскаля; во-вторых – степени переменной a убывают, соответственно степени b – возрастают.

Если вычислить (a +b)4 = ((a +b)2 )2 , то получим такой результат: (a +b)4 = a4 +4a3b +6a2b2 +4ab3 +b4 .

Ну вот,– мы набрали достаточно материала (сделали достаточно много наблюдений) для того, чтобы выдвинуть индукционную гипотезу: для любых

a, b R и любых n N имеет место формула:

(a +b)n = Cn0 an +Cn1 +an−1b +Cn2 an−2b2 +... +Cn2 an−2b2 +... +Cnk an−k bk +... +Cnnbn

или, если использовать сокращенную запись:

Сейчас мы докажем с помощью математической индукции справедливость формулы (1.2.7), которая носит название: формула бинома Ньютона.

Итак, как мы уже видели, формула (1.2.7) справедлива для n=1;2;3. Пусть она справедлива для n, докажем ее справедливость для n+1:

До сих пор все ясно без комментариев. Теперь поставим себе цель – в двух последних суммах заменить n на n+1, для этого от первой суммы отде-

лим слагаемое, содержащее an+1 , а второй – слагаемое с bn+1 , тогда

24

Пример: Запишем с помощью формулы (1.2.7) (a + b)6 .

Для этого заметим, что из треугольника Паскаля мы можем легко найти

строку биномиальных коэффициентов: 1, 6, 15, 20, 15, 6, 1, следовательно: (a+b)6=a6+6a5b+15a4b2+20a3b3+15a2b4+6ab5+b6.

6

Или в компактной форме: (a + b)6 = ∑C6k ak b6−k .

k =0

Упражнение 1.2.

1. Используя метод математической индукции, доказать тождества:

ж) 1 1!+ 2 2!+ 3 3!+ ... + n n!= (n + 1)!− 1.

2.Из двух математиков и десяти экономистов надо составить комиссию из восьми человек. Сколькими способами можно составить комиссию, если в неё должен входить хотя бы один математик?

3.Сколькими способами можно выбрать четырёх человек на четыре различные должности, если имеется девять кандидатов на эти должности?

4.Сколько четырёхзначных чисел можно составить, используя цифры

1, 2, 3, 4 и 5, если:

а) никакая цифра не повторяется более одного раза; б) повторения цифр допустимы;

в) числа должны быть нечётными и повторений цифр быть не должно.

5.В компании из 10 человек произошло 14 попарных ссор. Доказать, что всё равно можно составить компанию из трёх друзей.

6.Вычислить суммы:

25

а) C50 + 2C51 + 22 C52 + ... + 25 C55 ;

б) Cn0 − Cn1 + ... + (−1)n Cnn ;

в) Cn0 + Cn1 + ... + Cnn .

7. Доказать тождества:

а) C2nn = (Cn0 )2 + (Cn1 )2 + ... + (Cnn )2 ;

б) Cnk+m = Cn0Cmk + Cn1Cmk−1 + ... + Cnk Cm0 ; в) Cnk = Cnk−−11 + Cnk−−21 + ... + Ckk−−11 .

8*. Найти m и n зная, что Cnm++11 : Cnm+1 : Cnm+−11 = 5 : 5 : 3 .

9*. Доказать равенство (свойство шестиугольника):

Cnk−−11 Cnk+1 Cnk+1 = Cnk−1 Cnk++11 Cnk−1 .

Ответы. 2. 2 C107 + 1 C106 . 3. C94 . 4. а) 5!; б) 54 ; в) 2 4!. 6. а) 35 ; б) 0; в) 2n . 8*. m=3, n=2.

26

1°. Для всех a,b A имеет место: a ϕ b = bϕ a (коммутативное свойство ϕ или коммутативность ϕ ).

2°. Для всех a,b, c A имеет место (a ϕ b)ϕ c = aϕ (bϕ c) (ассоциативность ϕ ).

3°. Существует e A такой, что для всех a A имеет место a ϕ e = a (существование нейтрального элемента).

4°. Для любого a A существует a −1 A такой, что aϕ a−1 =a . ( a −1 называют обратным к а).

В этом случае множество A называют абелевой (по имени великого датского математика Нильса Абеля) или коммутативной группой, а опера-

цию ϕ называют групповой операцией.

Мы видим, что операция сложения «+», введенная в школьном курсе математики, обладает на R свойствами групповой операции, при этом нейтральным элементом является число 0.

Легко также видеть, что операция умножения × делает множество

R0 = R \{0} коммутативной группой с нейтральным элементом e = 1. Эти

две операции взаимодействуют друг с другом через дистрибутивный закон:

x, y, z R : x( y + z) = xy + xz.

Но складывать и умножать,– это не все, чтό мы умеем делать с действительными числами. Очень важно то, что мы умеем их сравнивать, т.е. на R введена еще операция – операция сравнения. Она уже не относится к классу бинарных операций, т.к. не ставит паре чисел a и b в соответствие третьего числа. Эта операция относится к так называемым бинарным отношениям. Познакомимся вкратце с понятием бинарного отношения.

Пусть дано множество X произвольной природы. Из элементов множества X построим всевозможные пары (a,b); a, b X. При этом будем считать, что если a ≠ b , то пары (a, b) и (b, a) – различны (такие пары называют упорядоченными). Из этого множества (всех упорядоченных пар) в свою очередь выделим подмножество T, которое называется бинарным отношением на X. Если (a,b) T, то говорят, что a находится с b в отношении T и пишут aT b .

В зависимости от «конфигурации» множества T, бинарное отношение может обладать различными интересными свойствами. Мы здесь будем считать, что T удовлетворяет следующим требованиям:

1°. a x : aTa;((a, a) T ) – рефлексивность T. 2°. aTb bTc aTc – транзитивность T.

3°. aTb bTa a = b – антисимметричность T или закон тождества. 4°. a,b X : aTb bTa – линейность (связность) T.

Бинарное отношение, обладающее этими свойствами, называется ли-

нейным отношением порядка. И называется отношением частичного поряд-

ка, если удовлетворяет условиям 1°-3°.

28

Обычно отношение порядка обозначается так: a ≤ b , т.е. абстрактный символ T заменяют на “ ≤”.

Отношение порядка связывается на R с операциями сложения и умножения следующими аксиомами:

1°. a,b, c R : (a ≤ b) (a + c ≤ b + c) ;

2°. a, b R c > 0 : (a ≤ b) (a × c ≤ b × c) .

Определение 1.3.3. Множество R, на котором введены операции сложения и умножения, операция линейного сравнения и все они связаны между собой так, как это сделано выше, называется линейным упорядоченным полем, а его элементы действительными или вещественными числами.

Теперь можно доказать, что R допускает все известные нам арифметические операции: вычитание, деление, действие над дробями и т.д. Мы не станем здесь делать всех необходимых выкладок, ограничимся только примерами.

Теорема 1.3.1 (о единственности нуля). Свойством нуля обладает единственный элемент.

Доказательство. Пусть существует два нуля: 01 и 02 .Тогда

01 +02 = 01 и 01 +02 = 02 , отсюда 01 = 02 .

Теорема 1.3.2 (о единственности элемента обратного данному относительно операции сложения). Для любого a R

единственен.

Доказательство. Предположим обратное: у числа а существует два

обратных элемента b и c. Тогда и a +c = 0 . Отсюда a = (a +b)+c = a +b +c = (a +c)+b = b +0 = b .

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

Элемент, обратный к a относительно сложения, обозначается –a. Операция вычитания вводится естественным образом: a −b = a +(−b).

Эту операцию можно было бы определить и так: разностью элементов a и b называется элемент c, обозначаемый a −b , такой, что a = b +c .

Спрашивается: равносильны ли эти определения? Разумеется, да и это

c = a −b .

Аналогично можно было бы доказать теоремы о единственности единицы и единственности элемента, обратного по умножению,– мы вынесем эти вопросы в задания к разделу.

Операция деления: пусть b ≠ 0 , тогда у b существует обратный элемент b −1 . Положим по определению ba = a × b −1 .

29

И вновь, как и для операции сложения, можно показать, что c = ba a =b ×c (сделайте это!).

Элемент c называется частным от деления a на b. Элементы R будем называть числами.

Натуральное число n вводится как результат сложения 1. А именно: 2=1+1, 3=1+2 и т.д.

Введя натуральные числа, мы легко введем целые числа: 0;1; –1;2; –2;… Множество всех целых чисел обозначают символом Z.

Число, которое получается делением одного целого числа на другое, называется рациональным числом:

p = mn , n, m Z , m ≠ 0 .

Часто знак × заменяют знаком “ ”, например 2 ×3 = 2 3 , а при буквенной записи и вовсе не пишут никакого знака: a ×b = ab .

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

Например:

1) 1n m1 = n 1m , иными словами n−1m−1 = (nm)−1 .

лось.

Эти примеры показывают принципы, с помощью которых мы извлекаем из системы аксиом правила работы с рациональными числами.

30