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

Date: 2015-10-07; view: 424.

Лекция 1.

Попов А.М.

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

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

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

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

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

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

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

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

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

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

Пример. {х₃ , х₂ , х₅ }, {х₃ , х₂ , х₄ }, {х₂ , х₃ , х₄ } – различные размещения из п по 3.

Мы будем записывать также размещения в виде х₃ х₂ х₅ ;

х₃ х₂ х₄ ; х₂ х₃ х₄ .

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

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

Пример. {х₁ , х₂}, {х₁ , х₃}, {х₁ , х₄}, {х₂ , х₃}, {х₂ , х₄},

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

Мы будем записывать также сочетания в виде х₁ х₂ , х₁ х₃ , х₁ х₄ и т.д.

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

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

Пример. {х₁, х₂, х₃}, {х₂, х₃, х₁}, {х₃, х₁, х₂},{х₂, х₁, х₃},

{х₃, х₂, х₁}, {х₁, х₃, х₂} – все перестановки из трёх элементов.

Утверждение 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 мест:

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

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



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

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

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

= × P_k Þ = / P_k = 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 элементов выбирать из первых п элементов – это можно сделать способами.