Комбинаторика
<<  Сложение и умножение комбинаций Сочетания  >>
Sir Isaac Newton
Sir Isaac Newton
Треугольник Паскаля
Треугольник Паскаля
Бином Ньютона
Бином Ньютона
Картинки из презентации «Размещения и сочетания» к уроку алгебры на тему «Комбинаторика»

Автор: Joseph V Romanovsky. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока алгебры, скачайте бесплатно презентацию «Размещения и сочетания.ppt» со всеми картинками в zip-архиве размером 144 КБ.

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

содержание презентации «Размещения и сочетания.ppt»
Сл Текст Сл Текст
1Дискретный анализ. Лекция 4 8правого из нулей, которые еще можно
Комбинаторика. Размещения и сочетания. сдвигать, и «подтаскивание» к нему, всех
2Размещения и сочетания. Перестановки находящихся справа нулей. Полезен пример.
(permutations) были первым классическим 9Перебор сочетаний - 2. Пусть n=7 и
объектом комбинаторики. Сейчас мы m=5. 0011111 1010111 1101110 0101111
рассмотрим два остальных – размещения 1011011 1110011 0110111 1011101 1110101
(allocations) и сочетания (combinations). 0111011 1011110 1110110 0111101 1100111
Важность этих двух определений различна. 1111001 0111110 1101011 1111010 1001111
Сочетания используются повсеместно. 1101101 1111100 Красным выделены нули,
Размещения же нужны почти исключительно сдвигаемые на позицию вправо. Опишите этот
для того, чтобы сочетания было удобно алгоритм в терминах позиций, занятых
определять, они служат удобным переходом единицами, и в терминах позиций, занятых
от перестановок к сочетаниям. нулями.
3Размещения. Пусть задано множество из 10Сочетания и пути. Итак, каждое
n элементов. Упорядоченный набор m из этих сочетание из n по m – это набор из m
элементов называется размещением из n единиц и n-m нулей. А, как уже говорилось,
элементов по m. Обозначим множество каждый такой набор изображается путем на
размещений из n элементов через Anm , а прямоугольной решетки из точки (0,0) в
его мощность через Anm. И опять те же три точку (m,n-m). Так что число таких путей
вопроса: чему равно Anm, как перебрать равно Cnm. Вместе с тем, все пути,
элементы Anm , как их перенумеровать. приходящие в точку (m,n-m), идут через
Легко видеть, что Anm = n(n-1). . .(n-m+1) (m-1,n-m) или через (m,n-m -1). Отсюда
= n!/(n-m)! имеем n возможностей выбора следует, что Cnm = Cn-1m-1 +Cn-1m Эту
первого элемента, n-1 возможностей выбора формулу можно получить и непосредственным
второго и т.д. Получаем m сомножителей, вычислением. Попробуйте. Обычно формулу
начиная с n и уменьшая каждый раз на 1. для Cnm доопределяют для отрицательных m,
4Пример размещений. Перечислим полагая Cnm = 0.
размещения из 5 элементов по 3. Их число 11Нумерация сочетаний. Перенумеровать
должно быть равно 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 через точку (0,1), а затем пути, идущие
cda dca eca adc bdc cdb dcb ecb ade bde через точку (1,0). Пути из (0,1) в (m,n-m)
cde dce ecd aeb bea cea dea eda aec bec нумеруются как пути из (0,0) в (m,n-m-1).
ceb deb edb aed bed ced dec edc. Пути из (1,0) в (m,n-m) нумеруются как
5Пример размещений - 2. Если пути из (0,0) в (m-1,n-m) с добавлением
сгруппировать эти размещения в группы с смещения на Cn-1m уже использованных
одинаковым составом, мы получим 10 строк номеров. Пример.
по 6 элементов (это скоро понадобится) abc #(0,1,1,0,1,1,1)=#(1,1,0,1,1,1)=C54+#(1,0,
acb bac bca cab cba abd adb bad bda dab ,1,1)
dba abe aeb bae bea eab eba acd adc cad =C54+C43+#(0,1,1,1)=C54+C43+C33+C22+C11
cda dac dca ace aec cae cea eac eca ade =5+4+1+1+1=12.
aed dae dea ead eda bcd bdc cbd cdb dbc 12Теорема о биноме Ньютона. При любом n
dcb bce bec cbe ceb ebc ecb bde bed dbe справедлива формула (a+b)n=?k?0:n
deb ebd edb cde ced dce dec ecd edc. Cnkakbn-k. Доказательство. По индукции.
6Нумерация размещений. Чтобы нумеровать При n=1 формула очевидна. Предположим, что
перестановки, мы отобразим множество Anm она доказана для n-1 и докажем ее для n.
взаимнооднозначно в другое множество Tnm, Имеем (a+b)n=(a+b)(a+b)n-1=(a+b)(?k?0:n-1
на котором ввести нумерацию будет гораздо Cn-1kakbn-1-k)= = ?k?0:n-1
проще, а затем для любого элемента a? Anm Cn-1kak+1bn-k+?k?0:n-1Cn-1kakbn-k= =
в качестве его номера возьмем номер его ?k?0:n(Cn-1k-1+Cn-1k)akbn-k=
образа в Tnm. Множество Tnm– это прямое ?k?0:nCnk)akbn-k Эта формула так важна,
произведение нескольких числовых отрезков что часто числа называются биномиальными
Tn =(0:(n-1))?(0:(n-2)? … ?(0:n-m). Т.е. коэффициентами.
каждый элемент Tnm– это набор 13Sir Isaac Newton (1643-1727).
неотрицательных чисел i1, i2, …,, im, 14Треугольник Паскаля. Биномиальные
причем ik?n-k. Обратите внимание, коэффициенты очень красиво распола-гаются
насколько малы отклонения этого текста от треугольником, в котором каждое число
текста для перестановок. (кроме первого) является суммой двух
7Сочетания. Пусть задано множество из n предшествующих. Этот треугольник
элементов. Неупорядоченный набор m из этих называется треугольником Паскаля. 1 1 1 1
элементов называется сочетанием из n 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15
элементов по m. Определение отличается от 20 15 6 1 1 7 21 35 35 21 7 1. Blaise
определения для размещений всего одним Pascal (1623-1662).
словом: неупорядоченный. Обозначим 15Бином Ньютона и комбинаторные формулы.
множество сочетаний из n элементов через 1. При a=b=1 формула бинома превращается в
Cnm , а его мощность через Cnm. И еще раз формулу 2n=?k?0:n Cnk. 2. При a=1, b=?1
три вопроса: чему равно Cnm, как перебрать формула бинома превращается в формулу
элементы Cnm , как их перенумеровать. 0=Cn0?Cn1+Cn2?Cn3+. . . . Некоторые другие
Легко видеть связь между Anm и Cnm Cnm = замечательные формулы можно получить,
Anm/m!= n!/(m!(n-m)!) Вспомним вторую используя формулу де Муавра, французского
таблицу в примере: в каждой строке m! ученого, жившего в Лондоне и близко
элементов-размещений, и каждая строка – знавшего Ньютона. Abraham De Moivre
одно сочетание. (1667-1754).
8Перебор сочетаний. Для упрощения 16Экзаменационные вопросы. Размещения.
перебора сочетаний полезно их представить Их перебор и нумерация. Сочетания. Их
в другом виде. Каждое сочетание – это перебор и нумерация. Свойства сочетаний.
подмножество мощности m в множестве из n Бином Ньютона. Треугольник Паскаля.
элементов. Если вспомнить о представлении Комбинаторные формулы, получающиеся из
подмножества характеристическим вектором, формулы бинома Ньютона.
мы придем к тому, что сочетание задается 17Задание. 1. Найти число сочетаний из
набором, в котором ровно m единиц и n-m 10 элементов по 3 (входной замок). 2.
нулей. Значит нужно научиться перебирать Нарисовать треугольник Паскаля и
такие наборы. В лексикографическом убедиться, что числа в нем – биномиальные
порядке! Самый младший набор – тот, в коэффициенты. 3. Используя формулу бинома,
котором идут сначала все нули, а потом все доказать, что знакопеременная сумма
единицы. Самое выгодное увеличение набора биномиальных коэффициентов равна 0.
– это сдвиг на одну позицию вправо, самого
Размещения и сочетания.ppt
http://900igr.net/kartinka/algebra/razmeschenija-i-sochetanija-54589.html
cсылка на страницу

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

другие презентации на тему «Размещения и сочетания»

«Число вариантов» - Комбинаторные задачи. В коридоре висят три лампочки. Напитки. Выбор. Выбор напитка- испытание А. Физкультура. Сколькими способами можно разделить чашки между гостями? Ответ:15 чисел. 2 комбинации. Чай. Удобная формула!!! Перестановки. Правило умножения. Из чисел 1, 5, 9 составить трёхзначное число без повторяющихся цифр.

«Элементы комбинаторики» - Записать формулу для нахождения числа сочетаний? Определение: Подбор комбинаторных задач. Записать формулу для нахождения числа размещений? Пусть имеется n элементов и требуется выбрать один за другим некоторые k элементов. Число размещений из n элементов по k обозначаются (читается: «А из n по k»).

«Комбинаторные задачи и их решения» - Требования к уровню подготовки. Презентации. Углубление знаний учащихся. Появление стохастической линии. Содержание программы. Поурочное планирование. Школьнику о теории вероятностей. Комбинаторные задачи и их решения. Учебно-тематический план. Пояснительная записка.

«Формулы для перестановок, сочетаний, размещений» - Формулы для подсчёта количества перестановок. Лесник. Перестановки. Сочетания. Слово «факториал». Количество перестановок. Подарок. Количество сочетаний. Очередь. Количество размещений. Размещения.

«Остовное дерево» - Время работы шага. Эквивалентность. Алгоритм Прима. Оптимальное решение. Алгоритм Краскала находит оптимальное решение. Ориентированный лес и циклы. Как улучшить шаг. Эквивалентность трех задач. Как реализовать шаг. Максимальный взвешенный лес. Алгоритм Краскала. Остовные деревья. Корневое ориентированное дерево.

«Комбинаторные задачи» - Комбинаторные задачи. Из цифр 1, 5, 9 составить все трёхзначные числа без повторяющихся цифр. №2. Дерево возможных вариантов.

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

25 презентаций о комбинаторике
Урок

Алгебра

35 тем
Картинки
900igr.net > Презентации по алгебре > Комбинаторика > Размещения и сочетания