Презентация, доклад Размещения и сочетания

Здесь Вы можете изучить и скачать урок презентацию на тему Размещения и сочетания бесплатно. Доклад-презентация для класса на заданную тему содержит 17 слайдов. Для просмотра воспользуйтесь проигрывателем, если презентация оказалась полезной для Вас - поделитесь ей с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций в закладки!
Презентации» Разное» Размещения и сочетания
500500500500500500500500500500500500500500500500500

Скачать

Слайды и текст этой презентации
Слайд 1
Описание слайда:
Дискретный анализ Лекция 4 Комбинаторика. Размещения и сочетания

Слайд 2
Описание слайда:
Размещения и сочетания Перестановки (permutations) были первым классическим объектом комбинаторики. Сейчас мы рассмотрим два остальных – размещения (allocations) и сочетания (combinations). Важность этих двух определений различна. Сочетания используются повсеместно. Размещения же нужны почти исключительно для того, чтобы сочетания было удобно определять, они служат удобным переходом от перестановок к сочетаниям.

Слайд 3
Описание слайда:
Размещения Пусть задано множество из 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.

Слайд 4
Описание слайда:
Пример размещений Перечислим размещения из 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

Слайд 5
Описание слайда:
Пример размещений - 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

Слайд 6
Описание слайда:
Нумерация размещений Чтобы нумеровать перестановки, мы отобразим множество Anm взаимнооднозначно в другое множество Tnm, на котором ввести нумерацию будет гораздо проще, а затем для любого элемента a Anm в качестве его номера возьмем номер его образа в Tnm. Множество Tnm– это прямое произведение нескольких числовых отрезков Tn =(0:(n-1))(0:(n-2) … (0:n-m). Т.е. каждый элемент Tnm– это набор неотрицательных чисел i1, i2, …,, im, причем ikn-k. Обратите внимание, насколько малы отклонения этого текста от текста для перестановок.

Слайд 7
Описание слайда:
Сочетания Пусть задано множество из n элементов. Неупорядоченный набор m из этих элементов называется сочетанием из n элементов по m. Определение отличается от определения для размещений всего одним словом: неупорядоченный. Обозначим множество сочетаний из n элементов через Cnm , а его мощность через Cnm. И еще раз три вопроса: чему равно Cnm, как перебрать элементы Cnm , как их перенумеровать. Легко видеть связь между Anm и Cnm Cnm = Anm/m!= n!/(m!(n-m)!) Вспомним вторую таблицу в примере: в каждой строке m! элементов-размещений, и каждая строка – одно сочетание.

Слайд 8
Описание слайда:
Перебор сочетаний Для упрощения перебора сочетаний полезно их представить в другом виде. Каждое сочетание – это подмножество мощности m в множестве из n элементов. Если вспомнить о представлении подмножества характеристическим вектором, мы придем к тому, что сочетание задается набором, в котором ровно m единиц и n-m нулей. Значит нужно научиться перебирать такие наборы. В лексикографическом порядке! Самый младший набор – тот, в котором идут сначала все нули, а потом все единицы. Самое выгодное увеличение набора – это сдвиг на одну позицию вправо, самого правого из нулей, которые еще можно сдвигать, и «подтаскивание» к нему, всех находящихся справа нулей. Полезен пример.

Слайд 9
Описание слайда:
Перебор сочетаний - 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 Красным выделены нули, сдвигаемые на позицию вправо. Опишите этот алгоритм в терминах позиций, занятых единицами, и в терминах позиций, занятых нулями.

Слайд 10
Описание слайда:
Сочетания и пути Итак, каждое сочетание из 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.

Слайд 11
Описание слайда:
Нумерация сочетаний Перенумеровать сочетания – это значит перенумеро-вать пути, о которых говорилось только что. Будем нумеровать сначала пути, идущие через точку (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.

Слайд 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 Эта формула так важна, что часто числа называются биномиальными коэффициентами.

Слайд 13
Описание слайда:
Sir Isaac Newton (1643-1727)

Слайд 14
Описание слайда:
Треугольник Паскаля Биномиальные коэффициенты очень красиво распола-гаются треугольником, в котором каждое число (кроме первого) является суммой двух предшествующих. Этот треугольник называется треугольником Паскаля. 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 Blaise Pascal (1623-1662)

Слайд 15
Описание слайда:
Бином Ньютона и комбинаторные формулы 1. При a=b=1 формула бинома превращается в формулу 2n=k0:n Cnk. 2. При a=1, b=1 формула бинома превращается в формулу 0=Cn0Cn1+Cn2Cn3+. . . . Некоторые другие замечательные формулы можно получить, используя формулу де Муавра, французского ученого, жившего в Лондоне и близко знавшего Ньютона. Abraham De Moivre (1667-1754)

Слайд 16
Описание слайда:
Экзаменационные вопросы Размещения. Их перебор и нумерация. Сочетания. Их перебор и нумерация. Свойства сочетаний. Бином Ньютона. Треугольник Паскаля. Комбинаторные формулы, получающиеся из формулы бинома Ньютона.

Слайд 17
Описание слайда:
Задание 1. Найти число сочетаний из 10 элементов по 3 (входной замок). 2. Нарисовать треугольник Паскаля и убедиться, что числа в нем – биномиальные коэффициенты. 3. Используя формулу бинома, доказать, что знакопеременная сумма биномиальных коэффициентов равна 0.


Скачать урок презентацию на тему Размещения и сочетания можно ниже:

Похожие презентации