Лекция 4 Комбинаторика




НазваниеЛекция 4 Комбинаторика
Дата конвертации11.03.2013
Размер445 b.
ТипЛекция


Дискретный анализ

  • Лекция 4

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

  • Размещения и сочетания


Размещения и сочетания

  • Перестановки (permutations) были первым классическим объектом комбинаторики. Сейчас мы рассмотрим два остальных – размещения (allocations) и сочетания (combinations).

  • Важность этих двух определений различна. Сочетания используются повсеместно. Размещения же нужны почти исключительно для того, чтобы сочетания было удобно определять, они служат удобным переходом от перестановок к сочетаниям.



Размещения

  • Пусть задано множество из n элементов. Упорядоченный набор m из этих элементов называется размещением из n элементов по m.

  • Обозначим множество размещений из n элементов через Anm , а его мощность через Anm.

  • И опять те же три вопроса: чему равно Anm, как перебрать элементы Anm , как их перенумеровать.

  • Легко видеть, что

  • Anm = n(n-1). . .(n-m+1) = n!/(n-m)!

  • имеем n возможностей выбора первого элемента, n-1 возможностей выбора второго и т.д. Получаем m сомножителей, начиная с n и уменьшая каждый раз на 1.



Пример размещений

  • Перечислим размещения из 5 элементов по 3. Их число должно быть равно 543=60. Имеем

  • abc bac cab dab eab

  • abd bad cad dac eac

  • abe bae cae dae ead

  • acb bca cba dba eba

  • acd bcd cbd dbc ebc

  • ace bce cbe dbe ebd

  • adb bda cda dca eca

  • adc bdc cdb dcb ecb

  • ade bde cde dce ecd

  • aeb bea cea dea eda

  • aec bec ceb deb edb

  • aed bed ced dec edc



Пример размещений - 2

  • Если сгруппировать эти размещения в группы с одинаковым составом, мы получим 10 строк по 6 элементов (это скоро понадобится)

  • abc acb bac bca cab cba

  • abd adb bad bda dab dba

  • abe aeb bae bea eab eba

  • acd adc cad cda dac dca

  • ace aec cae cea eac eca

  • ade aed dae dea ead eda

  • bcd bdc cbd cdb dbc dcb

  • bce bec cbe ceb ebc ecb

  • bde bed dbe deb ebd edb

  • cde ced dce dec ecd edc



Нумерация размещений

  • Чтобы нумеровать перестановки, мы отобразим множество Anm взаимнооднозначно в другое множество Tnm, на котором ввести нумерацию будет гораздо проще, а затем для любого элемента a Anm в качестве его номера возьмем номер его образа в Tnm.

  • Множество Tnm– это прямое произведение нескольких числовых отрезков

  • Tn =(0:(n-1))(0:(n-2) … (0:n-m).

  • Т.е. каждый элемент Tnm– это набор неотрицательных чисел i1, i2, …,, im, причем ikn-k.

  • Обратите внимание, насколько малы отклонения этого текста от текста для перестановок.



Сочетания

  • Пусть задано множество из n элементов. Неупорядоченный набор m из этих элементов называется сочетанием из n элементов по m.

  • Определение отличается от определения для размещений всего одним словом: неупорядоченный.

  • Обозначим множество сочетаний из n элементов через Cnm , а его мощность через Cnm.

  • И еще раз три вопроса: чему равно Cnm, как перебрать элементы Cnm , как их перенумеровать.

  • Легко видеть связь между Anm и Cnm

  • Cnm = Anm/m!= n!/(m!(n-m)!)

  • Вспомним вторую таблицу в примере: в каждой строке m! элементов-размещений, и каждая строка – одно сочетание.



Перебор сочетаний

  • Для упрощения перебора сочетаний полезно их представить в другом виде. Каждое сочетание – это подмножество мощности m в множестве из n элементов. Если вспомнить о представлении подмножества характеристическим вектором, мы придем к тому, что сочетание задается набором, в котором ровно m единиц и n-m нулей.

  • Значит нужно научиться перебирать такие наборы. В лексикографическом порядке!

  • Самый младший набор – тот, в котором идут сначала все нули, а потом все единицы. Самое выгодное увеличение набора – это сдвиг на одну позицию вправо, самого правого из нулей, которые еще можно сдвигать, и «подтаскивание» к нему, всех находящихся справа нулей. Полезен пример.



Перебор сочетаний - 2

  • Пусть n=7 и m=5.

  • 0011111 1010111 1101110

  • 0101111 1011011 1110011

  • 0110111 1011101 1110101

  • 0111011 1011110 1110110

  • 0111101 1100111 1111001

  • 0111110 1101011 1111010

  • 1001111 1101101 1111100

  • Красным выделены нули, сдвигаемые на позицию вправо.

  • Опишите этот алгоритм в терминах позиций, занятых единицами, и в терминах позиций, занятых нулями.



Сочетания и пути

  • Итак, каждое сочетание из n по m – это набор из m единиц и n-m нулей. А, как уже говорилось, каждый такой набор изображается путем на прямоугольной решетки из точки (0,0) в точку (m,n-m). Так что число таких путей равно Cnm.

  • Вместе с тем, все пути, приходящие в точку (m,n-m), идут через (m-1,n-m) или через (m,n-m -1). Отсюда следует, что

  • Cnm = Cn-1m-1 +Cn-1m

  • Эту формулу можно получить и непосредственным вычислением. Попробуйте.

  • Обычно формулу для Cnm доопределяют для отрицательных m, полагая Cnm = 0.



Нумерация сочетаний

  • Перенумеровать сочетания – это значит перенумеро-вать пути, о которых говорилось только что. Будем нумеровать сначала пути, идущие через точку (0,1), а затем пути, идущие через точку (1,0).

  • Пути из (0,1) в (m,n-m) нумеруются как пути из (0,0) в (m,n-m-1). Пути из (1,0) в (m,n-m) нумеруются как пути из (0,0) в (m-1,n-m) с добавлением смещения на Cn-1m уже использованных номеров.

  • Пример.

  • #(0,1,1,0,1,1,1)=#(1,1,0,1,1,1)=C54+#(1,0,1,1,1)

  • =C54+C43+#(0,1,1,1)=C54+C43+C33+C22+C11

  • =5+4+1+1+1=12.



Теорема о биноме Ньютона

  • При любом n справедлива формула

  • (a+b)n=k0:n Cnkakbn-k.

  • Доказательство. По индукции. При n=1 формула очевидна. Предположим, что она доказана для n-1 и докажем ее для n. Имеем

  • (a+b)n=(a+b)(a+b)n-1=(a+b)(k0:n-1 Cn-1kakbn-1-k)=

  • = k0:n-1 Cn-1kak+1bn-k+k0:n-1Cn-1kakbn-k=

  • = k0:n(Cn-1k-1+Cn-1k)akbn-k= k0:nCnk)akbn-k

  • Эта формула так важна, что часто числа называются биномиальными коэффициентами.



Sir Isaac Newton (1643-1727)



Треугольник Паскаля

  • Биномиальные коэффициенты очень красиво распола-гаются треугольником, в котором каждое число (кроме первого) является суммой двух предшествующих. Этот треугольник называется треугольником Паскаля.

  • 1

  • 1 1

  • 1 2 1

  • 1 3 3 1

  • 1 4 6 4 1

  • 1 5 10 10 5 1

  • 1 6 15 20 15 6 1

  • 1 7 21 35 35 21 7 1



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

  • 1. При a=b=1 формула бинома превращается в формулу 2n=k0:n Cnk.

  • 2. При a=1, b=1 формула бинома превращается в формулу 0=Cn0Cn1+Cn2Cn3+. . . .

  • Некоторые другие замечательные формулы можно получить, используя формулу де Муавра, французского ученого, жившего в Лондоне и близко знавшего Ньютона.



Экзаменационные вопросы

  • Размещения. Их перебор и нумерация.

  • Сочетания. Их перебор и нумерация.

  • Свойства сочетаний. Бином Ньютона. Треугольник Паскаля.

  • Комбинаторные формулы, получающиеся из формулы бинома Ньютона.



Задание

  • 1. Найти число сочетаний из 10 элементов по 3 (входной замок).

  • 2. Нарисовать треугольник Паскаля и убедиться, что числа в нем – биномиальные коэффициенты.

  • 3. Используя формулу бинома, доказать, что знакопеременная сумма биномиальных коэффициентов равна 0.



Похожие:

Лекция 4 Комбинаторика iconУрок проект: Комбинаторика и ее применение Проблемный вопрос: Может ли нам комбинаторика помочь в реальной жизни?
Решение комбинаторных задач развивает творческие способности, помогает при решении олимпиадных задач, задач из егэ
Лекция 4 Комбинаторика iconУрока: «Решение комбинаторных задач с помощью графов» Вопросы к уроку. Чем занимается комбинаторика? Что такое граф? Какие задачи относятся к комбинаторным?
Комбинаторика-раздел математики,рассматривающий вопросы(задачи), связанные с подсчётом числа всевозможных комбинаций из элементов...
Лекция 4 Комбинаторика iconЛекция 1 Основные понятия и определения теоретической механики Лекция 2 Виды связей и реакции связей Лекция 3 Момент силы относительно точки Лекция 4 Кинематика точки
Теоретическая механика это наука о наиболее общих законах механиче­ского движения и равновесия материальных объектов
Лекция 4 Комбинаторика iconУрока: Введение в комбинаторику. Цель урока: 1 дать понятие комбинаторной задачи; 2 показать, что изучает и чем занимается комбинаторика
«Число, место и комбинация три взаимно перекрещивающиеся, но отличные сферы мышления, к которым можно отнести все математические...
Лекция 4 Комбинаторика iconПрезентация Голубевой Аллы Дмитриевны ргпу им. А. И. Герцена Тема: «Структура лексического значения слова и ее части». Использованная литература
Никитин М. В. Лексическое значение слова (структура и комбинаторика) Никитин М. В. Курс лингвистической семантики Смирницкий А. И.,...
Лекция 4 Комбинаторика iconЛекция Лекция 1
Мир, окружающий нас материален: он состоит из вечно существующей и непрерывно движущейся материи
Лекция 4 Комбинаторика iconЛекция Лекция Семинар Психологическая консультация Научная конференция Деловая игра Тренинг личностного роста

Лекция 4 Комбинаторика iconЛекция 9 Пять механизмов нарушения
Гештальт терапия Перлза «Человек находится в равновесии с самим собой и окружающим его миром» Лекция 9
Лекция 4 Комбинаторика iconЛекция №7 Основные формы психокоррекции и психотерапии
Кафедра философии и психологии имост кандидат медицинских наук, доцент кафедры философии и психологии Е. В. Алексеева Тема Лекция...
Лекция 4 Комбинаторика iconЛекция №15. Смазка механизмов и смазочные устройства
Занятие 5/1 Тема корпусные детали, смазочные и уплотняющие устройства. Лекция №15
Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница