Комбинаторика
<<  Правила комбинаторики Комбинаторика  >>
Комбинаторика
Комбинаторика
Определение
Определение
Определение
Определение
Картинки из презентации «Комбинаторика» к уроку алгебры на тему «Комбинаторика»

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

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

содержание презентации «Комбинаторика.pps»
Сл Текст Сл Текст
1Комбинаторика. { Определение – правила 11как в первой задаче. На первом, втором,
равенства, суммы и произведения – принцип третьем и четвертом месте может находиться
включений – исключений – обобщение правила любая из четырех цифр. Значит всего таких
произведения – общее правило произведения чисел может быть 4 · 4 · 4 · 4 = 256.
– выборки – перестановки и сочетания – Количество четырехзначных чисел, все цифры
перестановки и сочетания с повторениями – которых нечетны, равно 625; количество
бином ньютона – примеры }. четырехзначных чисел, которые состоят из
2Определение. Комбинаторика - раздел цифр 1, 3, 7, 9 равно 256; тогда
дискретной математики, в котором изучаются количество четырехзначных чисел, все цифры
объекты, составленные из элементов которых нечетны, причем хотя бы одна из
конечных множеств. В комбинаторике них 5, равно 625 ? 256 = 369.
решается перечислительная задача о числе 12Пример. @. Сколько может быть
выборок, получаемых из элементов заданного четырехзначных чисел, делящихся на 5, если
конечного множества по некоторым правилам у них все цифры различные ? Решение. Если
и при некоторых условиях. Комбинаторный ?4 = 0 тогда цифра ?1 может быть выбрана 9
смысл биномиальных коэффициентов состоит в способами, цифра ?2 может быть выбрана 8
том, что они представляют собой число способами, а ?3 – 7 способами. По правилу
различных k - членных комбинаций из n - произведения получаем, что число ? может
элементного множества без повторений. быть получено 9 ? 8 ? 7 = 504 способами.
Треугольник Паскаля. Бином Ньютона. Таким образом, используя правило суммы,
3Определения из теории множеств. |A| – получаем, что существует 504 + 448 = 952
число элементов (мощность) конечного четырехзначных числа, делящихся на 5, у
множества A. A1 x A2 x . . . x an – прямое которых все цифры различные.
декартово произведение множеств A1 , A2 , 13Выборки. В простейших комбинаторных
. ., an . 2 A – множество всех подмножеств задачах требуется подсчитать число
множества A. Буквой E обозначают способов выбрать k элементов из n –
двухэлементное множество {0,1} . элементного множества. То, что получается
4Правила равенства, суммы и в результате выбора, называется выборкой
произведения. F называется биекцией или из n по k или (n,k) – выборкой. Понятие
взаимно однозначным отображением, если выборки отличается от понятия
выполняются условия: каждому одному подмножества. Отличие состоит в том, что в
элементу из A соответствует один элемент выборках может допускаться повторение
множества B (функция, удовлетворяющая элементов. Это означает, что в выборку
этому условию, называется инъекцией); для может входить несколько экземпляров одного
любого y ? B существует такой x ? A ,что f и того же элемента. Говорят, что
( x) = y (такая функция называется рассматриваются выборки с повторениями.
сюръекцией). Пусть A и B - конечные Выборки могут быть упорядоченными или
множества, f - функция, определенная на A неупорядоченными. Упорядоченность
со значениями в B . Если существует означает, что выборки, состоящие из одних
биекция из A в B , то говорят также, что и тех же элементов, но расположенных в
между A и B имеется взаимно однозначное разном порядке, считаются различными. Если
соответствие. же такие выборки считаются одинаковыми, то
5Правила равенства, суммы и говорят, что рассматриваются
произведения. Правило равенства Если между неупорядоченные выборки. Упорядоченные
конечными множествами A и B есть взаимно выборки называют перестановками (или
однозначное соответствие, то |A | = |B | . размещениями), неупорядоченные –
B. A. Правила суммы и произведения сочетаниями.
обобщаются на случай любого числа 14Перестановки и сочетания. Число (n,k)
слагаемых или сомножителей. Для правила – перестановок с повторениями равно n k.
суммы обобщение очевидно: мощность Таким образом, имеется четыре основных
объединения любого числа попарно типа выборок: Перестановки (без
непересекающихся множеств равна сумме их повторений), Перестановки с повторениями,
мощностей. Сочетания (без повторений). Сочетания с
6Принцип включений - исключений. повторениями. Подсчитаем число выборок
Принцип включений - исключений. Общее каждого типа. Множеством, из которого
правило произведения. делается выбор, будем считать множество
7Обобщение правила произведения. Д о к чисел In = { 1, 2, …. , n } . Перестановки
а з а т е л ь с т в о. Теорема. При k = 2 с повторениями. Перестановки с
это справедливо. Для большего числа повторениями из n по k – это
сомножителей равенство доказываем последовательности длины k, состоящие из
индукцией по k . элементов множества In , то есть элементы
8Обобщение правило произведения. По множества Ink . По правилу произведения
правилу равенства: . По правилу следует:
произведения для двух сомножителей: По 15Перестановки. Перестановки из n по k
предположению индукции: c. обозначим. Размещения. Доказательство. В
9Пример. @. Есть m различных шаров и n качестве первого элемента перестановки
различных урн. Найти число способов может быть выбран любой из n элементов
раскладки шаров по урнам . Решение. Каждый множества In . Поскольку повторения
шар может занимать одно из n мест, то есть недопустимы, второй элемент можно выбрать
n – число способов размещения одного шара n ? 1 способами, третий n ? 2 способами и
по n урнам. Воспользуемся правилом т.д. Применяя обобщенное правило
произведения. Получим, что число способов произведения, получаем. При k = n получим
раскладки шаров по урнам будет равно nm . формулу для числа перестановок всех n
10Пример. @. Сколько существует элементов. c.
различных четырехзначных чисел, в записи 16Пример. @. Сколько может
которых используются только нечетные цифры 2-перестановок из четырех объектов,
? Решение. Представим, что мы начали пронумерованных как 1, 2, 3, 4 ? Решение.
выписывать все такие четырехзначные числа. 17Сочетания. Сочетания (без повторений)
Для начала напишем первую цифру. Поскольку из n по k. Сочетания из n по k, то есть
нечетных цифр всего пять (1, 3, 5, 7, 9), неупорядоченные выборки без повторений,
то она может быть любой из пяти. Если мы это просто k – элементные подмножества n –
написали первой цифрой 1, то к ней можно элементного множества. Доказательство. c.
приписать любую из тех же пяти цифр и 18Перестановки и сочетания с
получить числа 11, 13, 15, 17, 19.. повторениями. Число перестановок с
Аналогично рассматриваем ситуации с повторениями, которые получаются из n
числами, которые начинаются с цифры 3 и элементов находится по формуле. Число (nk
другие случаи. Затем анализируем случаи ) - сочетаний с повторениями находится по
записи, в которых учтены первые комбинации формуле.
первых двух нечетных цифр в сочетании с 19Пример. @. Каким числом способов можно
третьей (нечетной) цифрой, .. и так застроить улицу из 10 домов, если 3 дома
доходим до четырехзначных цифр. Поскольку пятиэтажные, 5 – двухэтажные и 2 -
на каждом из четырех мест может стоять четырехэтажные ? Решение.
любая из пяти цифр, то всего существует 5 20Пример. @. Найти число сочетаний с
· 5 · 5 · 5 = 5 4 = 625 таких повторениями по 2 из четырех элементов,
четырехзначных чисел. пронумерованных как 1, 2, 3, 4 ? Решение.
11Пример. @. Сколько существует 21Бином Ньютона. Бином Ньютона.
четырехзначных чисел, все цифры которых 22Свойства сочетаний.
нечетные, причем хотя бы одна из них равна 23Треугольник Паскаля.
5 ? Решение. Основная сложность задачи 24Пример. @. Из колоды (52 карты) вынули
состоит в том, что не ясно, какая из цифр 10 карт. Найти вероятность того, что
по счету является 5, условию задачи выбран ровно один туз. Решение. 1 туз
удовлетворяют и те числа, в которых цифр 5 можно выбрать 4 способами (число мастей -
несколько. Выяснено, что число 4).
четырехзначных чисел, все цифры которых 25Пример. @. Из колоды (52 карты) вынули
нечетны, равно 625. Найдем теперь 10 карт. Найти вероятность того, что
количество четырехзначных чисел, в которых выбрано не менее двух тузов. Решение. Для
все цифры нечетны, но нет ни одной цифры выборки не менее двух тузов отнимем от
5. Это четырехзначные числа, в записи общего числа способов число способов
которых встречаются только четыре цифры: выборки без тузов и с одним тузом.
1, 3, 7, 9. Начнем проводить рассуждения
Комбинаторика.pps
http://900igr.net/kartinka/algebra/kombinatorika-248876.html
cсылка на страницу

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

другие презентации на тему «Комбинаторика»

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

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

«Комбинаторика 9 класс» - Ответ: Сочетаниями из n объектов по k называют любой выбор k объектов, взятых из n объектов. Сколькими способами можно присудить первую, вторую и третью премии? Обобщающий урок по теме «Элементы комбинаторики». Сколькими способами можно образовать набор из 12 фруктов? Число размещений из n объектов по k обозначают и вычисляют по формуле:

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

«Соединения в комбинаторике» - Встретились пятеро. Букет. Бином Ньютона. Возникновение комбинаторики. Правило произведения. Размещения. Раздел математики. Виды соединений. Основные задачи комбинаторики. Лишних знаний не бывает. Виды соединений в комбинаторике. Метод решения комбинаторных задач. 8 участниц финального забега. Полный перебор.

«Перестановки элементов» - Дискретный анализ. Задача о минимуме скалярного произведения. Экзаменационные вопросы. Пример отображения. Комбинаторика. Теорема о лексикографическом переборе перестановок. Отображение. Прямой алгоритм лексикографического перебора перестановок. Перебор перестановок элементарными транспозициями. Перебор перестановок.

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

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

Алгебра

35 тем
Картинки