Комбинаторика
<<  Введение в комбинаторику Краткое введение в теорию графов  >>
1 минута на размышление
1 минута на размышление		 Вторая строка этой схемы не что иное, как бланк длины 15, заполненный
Вторая строка этой схемы не что иное, как бланк длины 15, заполненный		 Блуждания, фигурные числа
Блуждания, фигурные числа		 Блуждания, фигурные числа
Блуждания, фигурные числа		 Блуждания, фигурные числа
Блуждания, фигурные числа
Кролики Фибоначчи
Кролики Фибоначчи
Картинки из презентации «Более сложные задачи по комбинаторике» к уроку алгебры на тему «Комбинаторика»

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

Более сложные задачи по комбинаторике

содержание презентации «Более сложные задачи по комбинаторике.ppt»
Сл Текст Сл Текст
1Более сложные задачи по комбинаторике. 51способами можно расположить в 9 лузах 7
Выполнила: учитель математики Дмитровской белых шаров и 2 черных шара? Часть луз
сош №1 им В.И. Кузнецова Кизьякова Елена может быть пустой, а лузы считаются
Борисовна. различными.
2Цели занятия: рассмотреть более 52Раскладки. 7 белых шаров можно
сложные задачи по комбинаторике на разместить в 9 лузах способами 2 черных
Раскладки; Разбиения; Смещения и шара - способами. Всего имеем способов.
субфакториалы; дать понятие о блужданиях и 53Раскладки. Задача 5. Двое ребят
фигурных числах, рекуррентных отношениях. собрали 10 ромашек, 15 васильков и 14
3Вспомним и повторим… Задача 1. На незабудок. Сколькими способами они могут
блюде лежат 3 яблока и 2 груши. Сколькими разделить эти цветы?
способами можно взять один фрукт? 54Раскладки. Решение: Так как цветы
41 минута на размышление... Время каждого вида можно делить независимо от
истекло. цветов другого вида, то по правилу
5Вспомним и повторим… Задача 1. На произведения получаем 11*16*15 = 2640
блюде лежат 3 яблока и 2 груши. Сколькими способов раздела цветов.
способами можно взять один фрукт? Ответ: 5 55Раскладки. Введем ограничение, что
способами. каждый из ребят должен получить не менее 3
6Какое правило использовали? Правило цветков каждого вида. Общее число способов
суммы: Если некоторый объект А можно деления равно 5*10*9 = 450.
выбрать m способами, а другой объект B 56Раскладки. В общем случае, если
можно выбрать n способами, то выбор «либо имеется n1 одинаковых предметов одного
А, либо В» можно осуществить m + n вида, n2 одинаковых предметов другого
способами. вида, … nk одинаковых предметов k-того
7Вспомним и повторим… Задача 2. Имеется вида, то их можно разделить между двумя
5 видов конвертов и 4 вида марок. людьми (n1+1)(n2+1)…(nk+1) способами.
Сколькими способами можно выбрать конверт 57Раскладки. Задача 6. Сколькими
с маркой для посылки письма? способами можно разделить 10 белых грибов,
81 минута на размышление... Время 15 подберезовиков и 8 подосиновиков между
истекло. 4 ребятами (грибы одного вида считаются
9Вспомним и повторим… Задача 2. Имеется одинаковыми)?
5 видов конвертов и 4 вида марок. 58Раскладки. Решение: Применяя формулу
Сколькими способами можно выбрать конверт Число способов размещения n одинаковых
с маркой для посылки письма? Ответ: предметов по m различным ящикам равно
10Какое правило использовали? правило Получаем 38 507 040 Если же каждый должен
произведения: Если объект А можно выбрать получить хотя бы по одному грибу каждого
m способами и если после каждого такого вида, то ответом будет 1 070 160.
выбора объект В можно выбрать n способами, 59Подобная формула верна и в общем
то выбор пары (А; В) в указанном порядке случае. Если имеется n1 предметов одного
можно осуществить mn способами. вида, n2 предметов другого вида, …, nk
11Вспомним и повторим… Задача 3. У предметов k-того вида, причем предметы
англичан принято давать ребенку несколько одного и того же вида неотличимы друг от
имен. Сколькими способами в Англии можно друга, то число способов распределения
назвать ребенка, если общее число имен этих предметов по m различным ящикам
равно 300, а ему дают не более трех имен? равно.
121 минута на размышление... Время 60Разбиения. Рассмотрим задачи о
истекло. разбиении числа на слагаемые. К этой
13Вспомним и повторим… Задача 3. У задаче сводятся многие другие, причем
англичан принято давать ребенку несколько возникают разные особенности в зависимости
имен. Сколькими способами в Англии можно от ограничений, накладываемых на величину
назвать ребенка, если общее число имен или число слагаемых.
равно 300, а ему дают не более трех имен? 61Разбиения. Имеются марки достоинством
Ответ: 300 + 300*299 + 300*299*298 = 26 в n1, n2, …, nk рублей (все числа ni
820 600. различны, а запас марок неограничен).
14Вспомним и повторим… Задача 4. Сколькими способами, наклеивая марки в
Сколькими способами можно разложить в два ряд, можно оплатить с их помощью сумму в N
кармана девять монет различного рублей, если два способа, отличающиеся
достоинства? порядком следования различных марок,
151 минута на размышление... Время считаются разными?
истекло. F(N)=F(N-n1)+F(N-n2)+…+F(N-nk) (1) При
16Вспомним и повторим… Задача 4. этом F(N)=0, если N<0 и F(0)=1.
Сколькими способами можно разложить в два 62Разбиения. Задача 1. (о наклейке
кармана девять монет различного марок) За пересылку бандероли надо
достоинства? Ответ: Каждая монета может уплатить 18 рублей, наклеивая на нее
попасть в один из двух карманов. Поэтому марки. На почте есть по одному виду марок
имеем 29 способов. достоинством в 4, 6 и 10 рублей (зато в
17Использовали формулу: Размещения с неограниченном количестве). Сколькими
повторениями из n элементов по k. (k мест способами можно оплатить пересылку
нужно заполнить элементами одного из n бандероли, если два способа, отличающиеся
видов, элементы могут повторяться). номиналом или порядком наклеивания марок,
18Задача 5. В 2004 году в России давали считаются различными (марки наклеиваются в
автомобильные номера типа 77х451хо, в один ряд)?
которых употреблялись цифры и 63Разбиения. Решение: Обозначим через
кириллические буквы, имеющие аналог в F(N) число способов, которыми можно
латинском алфавите (таких 12). Первые два наклеить марки достоинством в 4, 6 и 10
элемента – цифры(код региона), затем идет рублей, так чтобы общая стоимость этих
буква, затем трехзначное число и под конец марок равнялась N. По формуле (1) получаем
еще две буквы. А) сколько таких F(18) = F(14) + F(12) + F(8). F(14) =
автомобильных номеров могли выдать в F(10) + F(8) + F(4) F(12) = F(8) + F(6) +
России? Б) На Москву были выделены коды F(2) F(8) = F(4) + F(2) + F(-2).
региона 77, 97 и 99. Сколько номеров могли 64Разбиения. F(14) = 3 + 1 + 1 = 5 F(12)
выдать в Москве? = 1 + 1 + 0 = 2 F(8) = 1 Итак, сумму 18
193 минуты на размышление... Время можно получить 8 способами.
истекло. 65Такой способ задач, при котором сразу
20Задача 5. В 2004 году в России давали не дается окончательной формулы ответа, а
автомобильные номера типа 77х451хо, в указывается лишь процесс, позволяющий
которых употреблялись цифры и сводить задачу ко все меньшим и меньшим
кириллические буквы, имеющие аналог в числовым данным, встречается в
латинском алфавите (таких 12). Первые два комбинаторике очень часто. Равенства вида
элемента – цифры(код региона), затем идет (1) называют рекуррентными формулами.
буква, затем трехзначное число и под конец 66Разбиения. Задача 2. Сколькими
еще две буквы. А) сколько таких способами можно наклеить на конверт в одну
автомобильных номеров могли выдать в линию марки на 40 рублей, используя марки
России? Б) На Москву были выделены коды достоинством в 5, 10, 15 и 20 рублей
региона 77, 97 и 99. Сколько номеров могли (расположения, отличающиеся порядком
выдать в Москве? марок, считаются как различные; число
21Ответы: а) 102*12*103*122 = 172 800 марок не ограничено)?
000 номеров. б) 3*12*103*122 = 5 184 000. 67Разбиения. F(40) = F(35) + F(30) +
22Размещения без повторений: Размещение F(25) + F(20) F(40) = 108.
на k местах некоторые из n элементов, 68Смещения, субфакториалы. «Девушка
причем элементы не могут повторяться. спешит на свидание» Сформулируем задачу в
23Вспомним и повторим… Задача 6. В общем виде: найти число перестановок n
правление избрано 9 человек. Из них надо элементов, при которых ни один из
выбрать председателя, заместителя элементов не стоит на своем месте. Такие
председателя и секретаря. Сколькими перестановки называют смещениями, а их
способами это можно сделать? число обозначают .
241 минута на размышление... Время 69Смещения, субфакториалы. Решение
истекло. проводится с помощью формулы включений и
25Вспомним и повторим… Задача 6. В исключений. <p> свойство
правление избрано 9 человек. Из них надо перестановки, заключающееся в том, что
выбрать председателя, заместителя число p стоит на своем месте N(p) –
председателя и секретаря. Сколькими количество перестановок, обладающих этим
способами это можно сделать? Ответ: свойством N(pq) обозначим количество
26Вспомним и повторим… Задача 7. перестановок, одновременно обладающих
Сколькими способами можно выбрать из свойствами <p> и <q>, т.е.
полной колоды карт, содержащей 52 карты, таких что и p, и q стоят на своих местах,
по одной карте каждой масти? А если среди и т.д. Через обозначим N( , т.е. число
вынутых карт нет ни одной пары одинаковых, перестановок, в которых ни одно число не
т.е. двух королей, двух десяток и т.д.? стоит на своем месте.
271 минута на размышление... Время 70Смещения, субфакториалы. В данном
истекло. случае задача облегчается тем, что
28Вспомним и повторим… Задача 7. свойства совершенно равноправны Ответ:
Сколькими способами можно выбрать из 71Общая задача о смещении. Найти число
полной колоды карт, содержащей 52 карты, перестановок из n элементов, при которых
по одной карте каждой масти? А если среди ни один элемент не остается в
вынутых карт нет ни одной пары одинаковых, первоначальном положении.
т.е. двух королей, двух десяток и т.д.? 72Обобщая формулу (2) на случай n=0,
Ответ: 134 способов. Если среди карт не получаем, что естественно принять Число
должно быть пар, то имеем размещения без перестановок, при которых ровно r
повторений. элементов остаются на первоначальных
29Перестановки. Размещения, которые местах, а остальные n-r элементов меняют
отличаются друг от друга лишь порядком свое положение, выражается формулой.
входящих в них элементов, называются 73Смещения, субфакториалы. Найдем, во
перестановками из n элементов. скольких случаях ровно один адресат
30Вспомним и повторим… Задача 8. На получит свой паспорт. общее число
званый вечер приглашены 5 мужчин и 5 способов, при которых в точности один
женщин. Напротив каждого места на круглый человек получит свой паспорт, равно
стол необходимо поставить табличку с 5*9=45. (т.к. ).
именем того, кто будет на этом месте 74Смещения, субфакториалы. Найдем, во
сидеть, но никакие два лица одного пола не скольких случаях в точности двое получат
должны сидеть рядом. Сколькими способами свои паспорта. 2*10=20.
можно расставить таблички? 75Смещения, субфакториалы. Числа
311 минута на размышление... Время называют субфакториалами.
истекло. 76Блуждания, фигурные числа. Задача 1.
32Вспомним и повторим… Ответ: Разделение Путник хочет попасть из пункта А в пункт В
мест на мужские и женские можно сделать кратчайшим путем, т.е. двигаясь все время
двумя способами. После этого мужчин можно или «слева направо», или «снизу вверх».
посадить на выбранные места способами. Сколькими путями он может добраться из А в
Столько же способов рассадить женщин. В? (На рисунке изображен план города
Всего получаем 2*(5!)2= 28 800 способов. (примерно такой вид имеет план Канберры –
33Перестановки с повторениями. Где . столицы Австралии).
34Вспомним и повторим… Задача 9. 77Блуждания, фигурные числа. Сопоставим
Сколькими способами можно расставить белые каждому пути из А в В последовательность
фигуры (короля, ферзя, две ладьи, двух из нулей и единиц – если на очередном
слонов и двух коней) на первой линии перекрестке выбран путь вправо, ставим
шахматной доски (не соблюдая шахматные цифру 0, а если выбран путь вверх, ставим
правила)? цифру 1. Число перестановок из k нулей и n
351 минута на размышление... Время единиц равно.
истекло. 78Блуждания, фигурные числа.
36Вспомним и повторим… Ответ: Арифметический квадрат Напишем на каждом
37Сочетания без повторений. Сочетания из поле доски число путей, ведущие из
n элементов по k - любой выбор k элементов углового поля в данное поле доски. Ясно,
из имеющихся n элементов. (когда не что на пересечении k-й вертикали и n-й
интересует порядок элементов, а интересует горизонтали стоит число.
только состав). 79Блуждания, фигурные числа. Мы получим
38Сочетания с повторениями. таблицу. Эту таблицу называют
39Вспомним и повторим… Задача 10. арифметическим квадратом.
Сколько существует треугольников, у 80Блуждания, фигурные числа. Достаточно
которых длина каждой стороны принимает было использовать элементы предыдущей
одно из значений 4, 5, 6, 7? строки. Существует формула сочетаний:
401 минута на размышление... Время Такой метод вычисления арифметического
истекло. квадрата связан с восходящим к
41Вспомним и повторим… Задача 10. древнегреческим математикам Пифагору и
Сколько существует треугольников, у Никомаху учением о фигурных числах.
которых длина каждой стороны принимает 81Блуждания, фигурные числа. K-е
одно из значений 4, 5, 6, 7? Ответ: по треугольное число равно . Дело в том, что
формуле. числа 1, 2, 3, … можно изображать строками
42Раскладки. В задачах на раскладки из одной, двух, трех и т.д. точек, а эти
элементы раскладываются в несколько строки объединить в треугольники (рис 46).
«ящиков» и надо найти число способов это Тогда число точек в каждом треугольнике
сделать. будет равно соответствующему числу во
43Раскладки. Задача 1. Шары и лузы. второй строке арифметического квадрата.
Скольким способами могут распределиться 15 Поэтому числа 1, 3, 6, 10, 15, 21 и т.д.
перенумерованных бильярдных шаров в 6 называют треугольными числами,
лузах? 82Блуждания, фигурные числа.
44Вторая строка этой схемы не что иное, Треугольники, изображенные на рис 46,
как бланк длины 15, заполненный цифрами 1, можно объединять в пирамиды (рис. 47).
2, 3, 4, 5 и 6. Поэтому число таких Число точек в каждой пирамиде равно
распределений шаров равно числу размещений соответствующему числу в третьей строке
с повторениями из 6 элементов по 15, т. е. арифметического квадрата. Поэтому числа 1,
-. 4, 10, 20, 35 и т.д. называют
45Раскладки. Вывод: Число способов пирамидальными. Их общий вид такой:
размещения n различных предметов по m 83Рекуррентные соотношения. При решении
различным «ящикам» равно. многих комбинаторных задач часто
46Раскладки. Задача 2. Сбор яблок. Трое пользуются методом сведения данной задачи
ребят собрали с яблони 40 яблок. Сколькими к задаче, касающейся меньшего числа
способами они могут их разделить, если все предметов. Метод сведения к аналогичной
яблоки считаются одинаковыми? задаче для меньшего числа предметов
47Раскладки. Мы имеем дело с сочетаниями называется методом рекуррентных
с повторениями - есть 3 типа предметов соотношений (от латинского recurrere –
(мальчики) и надо делать из них комбинации возвращаться).
из 40 элементов (по числу яблок, какое - 84Кролики Фибоначчи. Пара кроликов
кому), порядок элементов не учитывается, приносит раз в месяц приплод из двух
разные комбинации отличаются количеством крольчат (самки и самца), причем
предметов хотя бы одного типа (т.е. как новорожденные крольчата через два месяца
раз числом яблок, достающимся хотя бы после рождения уже приносят приплод.
одному мальчику). Сколько пар кроликов появится через год,
48Раскладки. Вывод: Число способов если в начале года была одна пара кроликов
размещения n одинаковых предметов по m и ни одна пара кроликов не погибла.
различным ящикам равно. 85Кролики Фибоначчи. Обозначим через un
49Раскладки. Задача 3. Тайным число пар кроликов в начале n-го месяца.
голосованием 30 человек голосуют по 5 Тогда U1 = 1 U2 = 1 U3 = 2 (появится
предложениям. Сколькими способами могут приплод) U4 = 3 (к началу 4 – го месяца
распределиться голоса, если каждый первая пара даст приплод , а новорожденные
голосует только за одно предложение и кролики приплода еще не дадут) U5 = 5
учитывается лишь количество голосов, (т.к. приплод даст и первоначальная пара и
поданных за каждое предложение? новорожденная).
50Раскладки. Ответ: Так как не 86Кролики Фибоначчи. Uk=Uk-1+Uk-2 U13 =
учитывается порядок голосов, а учитывается 233 Числа U1, U2, …, Un,… называют числами
только их количество, то надо распределить Фибоначчи (обычно полагают еще U0 = 0,
30 неразличимых бюллетеней по 5 «ящикам». чтобы выполнялось равенство U2 = U1 + U0).
То это сочетание с повторением. 87Спасибо за внимание!
51Раскладки. Задача 4. Сколькими
Более сложные задачи по комбинаторике.ppt
http://900igr.net/kartinka/algebra/bolee-slozhnye-zadachi-po-kombinatorike-174256.html
cсылка на страницу

Более сложные задачи по комбинаторике

другие презентации на тему «Более сложные задачи по комбинаторике»

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

«Задачи по комбинаторике» - Сколькими способами можно сформировать экипаж корабля, состоящий из командира и инженера? Задача № 3. Задача №1. Комбинаторика. Правило сложения Правило умножения. Решение: 3 * 2 = 6 (способ). Правило умножения. Решение: 30 + 40 = 70 (способами). Пусть существует три кандидата на пост командира и 2 на пост инженера.

«Комбинаторика 9 класс» - 3. Сколько перестановок можно получить из букв, составляющих слово «апельсин». Ответ: Сочетаниями из n объектов по k называют любой выбор k объектов, взятых из n объектов. I. Фронтальный опрос. Статистика. Литература для учителя. Решение задач в группах с последующим обсуждением. Ответы: На тренировке занимаются 12 баскетболистов.

«Перестановки элементов» - Нумерация множества. Комбинаторика. Дискретный анализ. Нумерация перестановок. Задача о наибольшей возрастающей подпоследовательности. Формальное описание алгоритма. Задача о минимуме скалярного произведения. Экзаменационные вопросы. Перебор перестановок элементарными транспозициями. Перебор перестановок.

«Комбинаторика и её применение» - Комбинаторика и ее применение. Трехзначное число. Сколько четырехзначных чисел можно составить из 4 цифр. Расписание на вторник. Ученик. Устный счет. Сколько различных трехзначных чисел можно составить из цифр. Комбинаторика. Костюм. Четырехзначное число. Истоки комбинаторики. Области применения комбинаторики.

«Понятие комбинаторики» - Комбинаторика. Правило произведения. Цифры. Дерево возможных вариантов. Область математики. Правило перестановки. Варианты решения задачи. Капля в море. Сочетание с повторением. Комбинаторная задача. Правило размещения. Тонкости. Сочетание без повторения. Сигналы. Решение элементарных задач. Решение.

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

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

Алгебра

35 тем

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

Картинки
900igr.net > Презентации по алгебре > Комбинаторика > Более сложные задачи по комбинаторике