Комбинаторика.

Попов А.М.

Москва

ЛЕКЦИИ ПО ЛИНЕЙНОЙ АЛГЕБРЕ

 

 

Для студентов I курса бакалавриата, обучающихся по направлениям «Прикладная математика. Информатика», «Математика. Компьютерные науки», «Математика. Прикладная математика»

 

Издательство Российского университета дружбы народов

 

 

У т в е р ж д е н о

РИС Ученого совета

Российского университета

дружбы народов

Лекции по линейной алгебре. - М.: Изд-во РУДН, 2007. – 183 с.

 

Вошедшие в Лекции разделы изучаются в курсе алгебры на математических специальностях бакалавриата.

Для студентов I курса бакалавриата по направлениям «Прикладная мате­матика. Информатика», «Математика. Компьютерные науки», «Математика. Прикладная математика».

Подготовлено на кафедре дифференциальных уравнений и математической физики.

 

© А.М. Попов, 2007

© Издательство Российского университета дружбы народов, 2007

Лекция 1.

  1. КОМБИНАТОРИКА. БИНОМ НЬЮТОНА

Пусть Х = {х1 , х2 , …, хn } – множество из n элементов.

Определение.Размещением из n элементов по k называется упорядоченное подмножество, состоящее из k элементов, выбранных из множества Х. Подмножества, отличающиеся порядком, считаются различными.

Количество таких размещений обозначается и называется коротко количеством размещений из п по k.

Пример. {х3 , х2 , х5 }, {х3 , х2 , х4 }, {х2 , х3 , х4 } – различные размещения из п по 3.

Мы будем записывать также размещения в виде х3 х2 х5 ;

х3 х2 х4 ; х2 х3 х4 .

Определение.Сочетанием из n элементов по k называется (неупорядоченное) подмножество, состоящее из k элементов, выбранных из множества Х. Подмножества, отличающиеся порядком, считаются одинаковыми.

Количество таких сочетаний обозначается и называется коротко количеством сочетаний из п по k.

Пример. {х1 , х2}, {х1 , х3}, {х1 , х4}, {х2 , х3}, {х2 , х4},

{х3 , х4} – все сочетания из 4 по 2.

Мы будем записывать также сочетания в виде х1 х2 , х1 х3 , х1 х4 и т.д.

Определение.Перестановкой из n элементов называется размещение из п элементов по п.

Количество таких перестановок обозначается Pn.

Пример. {х1, х2, х3}, {х2, х3, х1}, {х3, х1, х2},{х2, х1, х3},

{х3, х2, х1}, {х1, х3, х2} – все перестановки из трёх элементов.

Утверждение 1.1.= п(п -1)(п – 2)…(п – k + 1).

Доказательствоиндукцией по k (для произвольного п,

k£ п).

k = 1. Очевидно, = п , так как размещениями из п по 1 являются подмножества в Х, состоящие из одного элемента, а количество таких подмножеств равно количеству элементов в Х, то есть п.

Пусть утверждение верно для k - 1. То есть " m ³ k-1

= m(m -1)(m – 2)…(m – k + 2).

Докажем его для k. Рассмотрим k мест:

1 2 … k - 1 k

. Произвольное размещение из п по

 

k получается размещением на 1-е место любого из п элементов множества Х (таких возможностей имеется п), а на оставшиеся k - 1 мест - произвольного размещения из оставшихся m = n – 1 элементов множества Х (таких размещений имеется ). Отсюда = п × и по предположению индукции = п ×= n×(n -1)(n –2)…(n – k + 1)= n! /(n – k)! .



Следствие.Pn= = n!

Утверждение 1.2.= n(n -1)(n – 2)…(n – k + 1) / k! .

Доказательство.Так как все размещения из п по k получаются выборками из множества Х различных сочетаний из k элементов, а затем их всевозможными перестановками, то

= × Pk Þ = / Pk = n(n -1)(n – 2)…(n – k + 1) / k! =

= n! /((n – k)!× k!) .

Утверждение 1.3.а) = = 1, б) = ,

в) = + .

 

Упражнение. Доказать утверждение с помощью формул.

Доказательствоутверждения 1.3 без формул (для умных, но ленивых).

а) Очевидно, из п элементов ничего не выбирать или выбрать все элементы можно только одним способом.

б) Очевидно, каждому выбранному сочетанию из п по k соответствует сочетание оставшихся в Х п – k элементов, и количество сочетаний выбранных элементов равно количеству сочетаний оставшихся элементов.

в) сочетания из п + 1 элементов по k + 1 можно выбирать двумя способами: или выбрать все k + 1 элементов из первых п элементов – это можно сделать способами, или обязательно включить в сочетание (п + 1)-й элемент, а остальные k элементов выбирать из первых п элементов – это можно сделать способами.