Без темы
<<  «Я В железнодорожники пошел, пусть меня научат 10 наиболее распространенных ошибок в резюме  >>
Правило произведения: множество A
Правило произведения: множество A
0
0
Из любого набора,содержащего к элементов, можно с помощью перестановок
Из любого набора,содержащего к элементов, можно с помощью перестановок
Из любого набора,содержащего к элементов, можно с помощью перестановок
Из любого набора,содержащего к элементов, можно с помощью перестановок
1. Примеры комбинаторных задач и общие принципы комбинаторики
1. Примеры комбинаторных задач и общие принципы комбинаторики
Вратаря можно выбрать способами, защитников - способом, нападающих –
Вратаря можно выбрать способами, защитников - способом, нападающих –
Вратаря можно выбрать способами, защитников - способом, нападающих –
Вратаря можно выбрать способами, защитников - способом, нападающих –
Вратаря можно выбрать способами, защитников - способом, нападающих –
Вратаря можно выбрать способами, защитников - способом, нападающих –
Число точек пересечения прямых равно числу способов выбора
Число точек пересечения прямых равно числу способов выбора
Число точек пересечения прямых равно числу способов выбора
Число точек пересечения прямых равно числу способов выбора
Треугольник Паскаля:
Треугольник Паскаля:
Картинки из презентации «1. Примеры комбинаторных задач и общие принципы комбинаторики» к уроку обществознания на тему «Без темы»

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

1. Примеры комбинаторных задач и общие принципы комбинаторики

содержание презентации «1. Примеры комбинаторных задач и общие принципы комбинаторики.ppt»
Сл Текст Сл Текст
1§ 1. Примеры комбинаторных задач и 28§ 2. Размещения и перестановки.
общие принципы комбинаторики. 29k. Определение. Всякая упорядоченная
Преподаватель Монов Андрей Владимирович. выборка объема k из множества, состоящего
2Составление слова из восьми букв можно из n элементов, называется размещением из
представить как заполнение буквами клеток n элементов по k элементов и обозначается
следующей таблицы: 1 2 3 4 5 6 7 8 На через Аn .
первое место можно поставить любую из 30Определение. Размещение из n элементов
восьми букв, на второе - любую из семи по n называется перестановкой из n
оставшихся и т.д. вплоть до заполнения элементов и обозначается через Рn .
единственным способом клетки № 8 последней 31k. Справедлива формула Аn =n
оставшейся буквой. Число способов (n-1)...(n - к + 1). Где 1 ? к ? n.
заполнения таблицы будет равно 32k. На первое место в выборке можно
8·7·6·5·4·3·2·1=8! Напомним, что символом поместить любой из n элементов, на второе
п! (читается «эн факториал») обозначается - любой из (n - 1) оставшихся и т.д. После
произведение всех натуральных чисел от 1 выбора элементов на(k-1)-е место останется
до п: n!=1·2·...·(n-1)·n. Ответ: n!= 1 • 2 n-(к-1) = n-к+1 элемен- 1 2 k-1 k тов,
• ...• (n -1) • п. любой из которых можно поместить на к-е
3Пусть множество А ={a1,...,ат} состоит место. По правилу произведения получаем Аn
из т элементов, а множество В = = (n-1)...(n - к + 1) В частности, Рn=An
{b1,...,bn} - из n элементов. Рассмотрим =n(n-1)… ·2·1 = n! (2). … n.
множество, состоящее из всевозможных 33k. An = n(n - 1)...(N - k+1)·(n-k)!=
упорядоченных пар (а,b), где элемент а N! (N-к)! (N-к)!
принадлежит множеству А, а элемент b 34k. Pn=An Pn-k.
принадлежит множеству В (такое множество 35Пример 9. Сколько шестизначных чисел,
называется декартовым произведением кратных 5, можно составить из цифр 0, 1,2,
множеств А и В и обозначается A?В). Иными ..., 9 при условии, что цифры в записи
словами, рассматривается множество, числа не повторяются?
элементами которого являются «карточки» 365. 5. Последней цифрой искомого числа
вида Слово «упорядоченные» в определении может быть 0 или 5. В первом случае
А?В особенно важно, когда в А и В есть остальные пять цифр можно выбирать из
одинаковые элементы. Например, если А = В множества {1,2, ..., 9} 9! и число
= {a,б,...,я} — русский алфавит, то вариантов равно А9 = — = 15120. Если число
элементы А?В можно считать словами, а ax и 4! oканчивается цифрой 5, то в качестве
xa - разные слова! А. b. первой цифры можно взять любую из восьми
4Правило произведения: множество A?В цифр 1, 2, 3, 4, 6, 7, 8, 9 - нельзя
содержит тn элементов. Доказательство использовать 0, т.к. число должно быть
этого утверждения почти очевидно, т.к. все шестизначным. Цифры со второй по четвертую
элементы-карточки можно расположить в виде можно выбрать A8 = 1680 различными
прямоугольной таблицы, в которой т строк и способами. Следовательно, по правилу
n столбцов. произведения имеется 8·A8 чисел,
5Множество А?В?С, состоящее из оканчивающихся цифрой 5. По правилу суммы
упорядоченных троек, содержит тnр находим, сколько существует чисел,
элементов (р - число элементов в множестве удовлетворяющих условию задачи. А9 +8·A8 =
С). Действительно, карточек вида abc1 28560. Ответ: 28560. 4. 4. 4.
столько, сколько элементов в А?В, т.е. тn, 37Пример 10. Сколькими способами можно
столько же карточек вида abc2 и т.д. В расставить на книжной полке десятитомник
этом случае А? В?С можно представить в Пушкина так, чтобы том 2 стоял рядом с
виде прямоугольного параллелепипеда. томом 1 и справа от него? Ответ: 9!
6Множество А1?А2?...?Ар состоит 38§ 3. Сочетания.
элементов, где n1- число элементов в А1, 39Определение. Всякая неупорядоченная
n2 - в А2 и т.д. Доказывается это выборка объема к из множества, состоящего
утверждение индукцией по р аналогично из n элементов (к?n), называется
рассмотренному выше переходу от p=2 к p=3. сочетанием из n элементов по к элементов и
7Пусть объект а1 можно выбрать n1, обозначается через Сn . k.
различными способами, после каждого выбора 40Из любого набора,содержащего к
объекта а1 объект а2 можно выбрать n2 элементов, можно с помощью перестановок
различными способами,..., после каждого получить k! упорядоченных выборок объема
выбора объектов а1, а2,..., аp-1 объект аp k, поэтому Откуда (4).
можно выбрать nр различными способами. 41
Тогда количество способов, которыми можно 42Пример 11. Хоккейная команда состоит
выбрать а1, а2, ..., аp равно n1n2...np. из 2 вратарей, 7 защитников и 10
8Доказательство: если Ак - множество нападающих. Сколькими способами тренер
состояний, из которых выбирается объект может образовать стартовую шестерку,
ак, то nк - число элементов множества Ак состоящую из вратаря, двух защитников и
(k=1,2,...,р), и мы получаем известную нам трех нападающих?
формулировку правила умножения. 43Вратаря можно выбрать способами,
9Пусть а1 - первая буква слова, тогда защитников - способом, нападающих –
ее можно выбрать 8 способами, т.е. n1 = 8; способами. Всего, по правилу произведения,
вторую букву а2 можно выбрать 7 способами, существует 2 · 21 · 120 = 5040 способов
т.е. n2 = 7 и т.д. По правилу умножения выбора стартовой шестерки. Ответ: 5040.
число всех комбинаций равно 8·7·. .. ·2·1. 44Пример 12. На плоскости проведены n
10Пример 2. Сколько четырехбуквенных прямых, среди которых нет ни одной пары
«слов» можно составить из карточек «в», параллельных прямых и ни одной тройки
«е», «ч», «н», «о», «с», «т», «ь»? прямых, пересекающихся в одной точке.
11Пусть ак - к -я буква слова (к Найти число точек пересечения этих прямых
=1,2,3,4). Тогда n1 = 8,n2 = 7, n3=6, nА = и число треугольников, образованных этими
5 и по правилу произведения сразу получаем прямыми.
ответ: 8·7·6·5 = 1680. Ответ: 1680. 45Число точек пересечения прямых равно
12Пример 3. Сколькими способами можно числу способов выбора неупорядоченной пары
поставить на шахматную доску белую и прямых, т.е. . Аналогично, каждый
черную ладью так, чтобы они не били друг треугольник определяется тройкой прямых,
друга? поэтому общее число треугольников равно .
13Выбор объекта а1 - поля для белой Ответ: и .
ладьи - может быть сделан n1 = 64 46Пример 13. Для проведения письменного
способами. Независимо от выбора этого поля экзамена по комбинаторике надо составить 4
белая ладья бьет 15 полей, поэтому для варианта по 7 задач в каждом. Сколькими
черной ладьи остается 64-15 =49 полей: n2 способами можно разбить 28 задач на 4
= 49. Ответ: число расстановок ладей равно варианта?
64 · 49 = 3136. 47Задачи для первого варианта можно
14Пример 4. Сколькими способами можно выбрать способами. После этого останется
поставить на доску восемь ладей так, чтобы 21 задача, так что второй вариант можно
они не били друг друга? составить способами. Для третьего варианта
15Очевидно, что на каждой горизонтали и задачи можно выбрать способами, а для
на каждой вертикали должна стоять только четвертого - = 1 способом.
одна ладья. Будем расставлять ладьи 48По правилу произведения получаем число
последовательно, начиная с первой . Но так как варианты равноправны, то
горизонтали. На первой горизонтали 8 полученное число надо разделить на 4!
клеток, и первую ладью можно поставить на Ответ: =.
любую из них. Когда мы будем ставить 49Свойства чисел : 1°. , если 0?к?n; 2°.
вторую ладью, то на второй горизонтали ей , если 0?к?n+1; 3°.
будут доступны 7 клеток и т.д. По правилу 50Свойство 1°.
произведения получаем, что всего таких 51Свойство 2°.
позиций 8! 52
16Если же считать ладьи различными (как 53Треугольник Паскаля:
в примере 3), то число перестановок ладей 54Свойство 3° Положим Так как каждое
равно 64 · 49 · 36 · 25 · 16 · 9 · 4 · 1 = число строки с номером п входит в качестве
(8!)? Действительно, для первой ладьи слагаемого в два соседних числа следующей
можно выбрать любое поле доски размером строки, то Sn+1 = 2Sn . Следовательно,
8?8, вторая ладья фактически ставится на т.к. S0=1.
квадратную доску 7?7 (мы удалили одну 55§ 4. Бином Ньютона.
горизонталь и одну вертикаль и «сдвинули» 56(A + b) =a +2ab + b и (a + b) = а +3а
оставшиеся части доски) и т.д. Зафиксируем b + 3ab +b .
одну из таких расстановок различных ладей. 57
Число перестановок ладей на выделенных 58Доказательство. Если, не приводя
полях равно 8! (результат примера 1). Если подобные члены, перемножить n скобок (а +
мы считаем ладьи одинаковыми, то (8!)? b), то получится сумма, состоящая из
позиций разбиваются на классы по 8! слагаемых вида a b , k=0,1,…,n. Для
позиций в каждом, и все позиции данного данного k слагаемое a b получается только
класса будут одинаковыми. Поэтому число в том случае, если в каких-то к скобках мы
перестановок одинаковых ладей равно (8!)? возьмем b, a остальных (n - k) скобках -
/8!= 8!, что совпадает с ранее полученным a. Следовательно, число слагаемых вида a b
ответом. будет равно числу способов, которыми можно
17Пример 5. Сколь различных слов можно выбрать (без учета порядка выбора) k
получить, переставляя буквы слова скобок из n скобок, т.е. . Утверждение
«комбинаторика»? доказано.
18В слове «комбинаторика» 13 букв. Если 59Если в формуле (5) взять а =b = 1, то
бы все они были различны, то, переставляя получится известное нам свойство 3° чисел
их, можно было бы получить 13! слов. Но в , а если взять а=1, b = -1, то получим еще
нашем слове буквы к, о, и, а встречаются одно комбинаторное равенство:
по два раза. Обозначим их 60
к1,к2,о1,о2,и1,и2,а1,а2. Ясно, что слова, 61Формула (6) называется полиномиальной.
отличающиеся перестановкой букв к1ик2 - Например, (а + b + с) = а + b + с + 3(а b
одинаковые, так что 13! Слов разбиваются + а с + b а + b с + с а + c b ) + 6abc.
на пары одинаковых. Следовательно, если мы 62Пример 14. Найти n, если известно, что
не различаем к1 и к2, то число всех слов в разложении (1 + x) коэффициенты при х и
будет равно 13!/2!. Но эта совокупность х равны.
также разбивается на пары одинаковых с 63В n-й строке треугольника Паскаля два
точки зрения буквы “о„ слов и т.д. 13! 13! коэффициента равны в том и только том
Ответ: = = —. 2!2!2!2! 16. случае, когда они занимают клетки,
19Пример 6. Сколько существует равноудаленные от крайних. Действительно,
четырехзначных чисел, у которых все цифры треугольник Паскаля симметричен: , а при
нечетные? Сколько существует движении от края к середине строки
четырехзначных чисел, в записи которых коэффициенты возрастают: при и при.
есть хотя бы одна четная цифра? 64Следовательно, равно тогда и только
20Всего нечетных цифр — пять, поэтому тогда, когда 12 = n-5, т.е. n= 17. Ответ:
выбор к-й цифры числа может быть сделан nк n = 17.
=5 способами (к =1, 2, 3, 4) а количество 65Пример 15. Найти коэффициент при х в
четырехзначных чисел, у которых все цифры разложении (1 + х +х ) .
нечетные, равно 5·5·5·5 = 625. 66В силу формулы (6) = Так как уравнение
21Все четырехзначные числа, а их 5k2 + 9к3 =19 имеет только одно решение в
9999-999=9000, делятся на две группы: те, неотрицательных числах k2=2, k3 = 1, то
в записи которых все цифры нечетные, и те, коэффициент при х равен.
в записи которых есть хотя бы одна четная 672) Обозначим через . Тогда Рассмотрим
цифра. Следовательно, количество чисел k-е слагаемое (0?k?30): Такое слагаемое
второго типа равно 9000-625=8375. Ответ: будет содержать х , если для некоторого т
8375. выполняется равенство 5k + 4m = 19. Ясно,
221) Если множество А состоит из т что это возможно только при k=3 и т=1.
элементов, а множество В из n элементов, Следовательно, коэффициент при х равен
причем, эти множества не имеют общих =12180.
элементов (т.е. А ? В = 0), то их 68Литература 1. Кутасова А.Д., Пиголкина
объединение A U В, т.е. совокупность всех Т.С, Чехлов В.И., Яковлева Т.Х., Пособие
элементов из А и В, содержит т + n по математике для поступающих в вузы. /под
элементов. ред. Г.Н. Яковлева - M.: Наука, 1988. 2.
232) Если объект а можно выбрать т Виленкин Н.Я. Популярная комбинаторика. —
различными способами, а объект b можно М.: Наука, 1975. 3. Генкин С.А., Итенберг
выбрать n различными способами, причем И.В., Фомин Д.В. Ленинградские
результаты выбора объектов а и b никогда математические кружки. — Киров, 1994.
не совпадают, то выбор “либо а, либо b» 69Контрольные вопросы Сколько делителей
можно осуществить т + n различными у числа 2004 ? Сколько диагоналей в
способами. выпуклом 2004-угольнике? Сколько различных
24Пример 7. Сколько различных пар можно натуральных решений имеет неравенство
образовать из 28 костей домино так, чтобы n+m?2004? 4. Чему равен коэффициент при х
кости, входящие в пару, можно было y в выражении (х + у) после раскрытия
приложить друг к другу? скобок? 5. С помощью соответствующей
25Выбор пары костей — это выбор двух строки треугольника Паскаля выпишите
карточек вида a1b1, a2b2, где можно формулу для вычисления (а-b) .
считать, что а ? b. Выберем первую кость - 70Задачи 1(3). Сколько различных слов
это можно сделать 28 способами, из них в 7 можно получить, переставляя буквы в слове
случаях кость окажется дублем, т.е. кость «параллелограмм»? 2(4). Сколькими
вида aa, а в 21 случае — кость вида ab, а способами можно переставлять буквы слова
< b . В первом случае вторую кость «раз-­ мещение» так, чтобы три буквы «е»
можно выбрать 6 способами, а число не шли подряд? 3(3). Решите уравнение
способов выбора пары костей по правилу 4(3). Известно, что никакие три диагонали
произведения равно 7 · 6 = 42 . Во втором выпуклого восьмиуголь­ника не пересекаются
случае вторую кость можно выбрать 12 в одной точке. Найдите число точек
способами — 6 костей вида a|* и 6 костей пе­ресечения диагоналей. 5(4). Сколькими
вида *|а ,а число способов выбора пары способами можно поставить на шахматную
равно 21·12 = 252. Следовательно по доску белого и черного слонов так, чтобы
правилу суммы всего получается 42 + 252 = они не били друг друга? 6(5). Найдите
294 способа выбора упорядоченной пары. сумму всех трехзначных чисел, которые
Ответ: 147 пар. можно напи­сать с помощью цифр 1, 2, 3, 4,
26Пример 8. Найти число подмножеств 5 (любую из цифр можно ис­пользовать
множества А, состоящего из n элементов. несколько раз). 7(5). Докажите тождество
270. 1. 0. … 1. 1. Пусть А = 8(6).Сколькими способами можно
{а1,а2,...,аn}, тогда с каждым распределить 12 различных книг по четырем
подмножеством X множества A можно связать полкам так, чтобы на каждой полке
карточку-паспорт вида 1 2 3 n-1 n В этом ока­залась ровно три книги? 9(6).
паспорте в к-й клетке стоит 1, если ак Є Сколькими способами можно распределить 12
Х, 0 – если ак Є X. Ясно, что по каждому одинако­вых книг по четырем полкам так,
подмножеству X однозначно строится чтобы на каждой полке была хотя бы одна
паспорт, но верно и обратное: каждый книга? В задачах №8 и №9 все полки разные.
паспорт однозначно определяет множество X. 10(6). В выпуклом восьмиугольнике
В частности, паспорт из нулей проведены все диагона­ли, причем известно,
соответствует пустому множеству, а паспорт что никакие три диагонали не пере­секаются
из единиц - множеству А. Но число таких в одной точке. На сколько частей
паспортов по правилу произведения равно 2 разделится восьмиугольник? 11(6). Найдите
, т.к. каждая клетка может быть заполнена наибольший коэффициент многочлена (1 + 2х)
двумя способами независимо от того, как . 12(6). Найдите коэффициент при х в
заполняются другие клетки. Ответ: 2 . n. разложении по степе ням х 1+(1+x)+…+(1+x)
n. .
1. Примеры комбинаторных задач и общие принципы комбинаторики.ppt
http://900igr.net/kartinka/obschestvoznanie/1.-primery-kombinatornykh-zadach-i-obschie-printsipy-kombinatoriki-147922.html
cсылка на страницу

1. Примеры комбинаторных задач и общие принципы комбинаторики

другие презентации на тему «1. Примеры комбинаторных задач и общие принципы комбинаторики»

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

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

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

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

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

«Семья и детство» - Ребёнок в семье. Воспитание детей у разных народов. Сша. США. Общение ребёнка в семье. Германия. У каждого народа есть свой метод воспитания. Япония. Таким образом малыш самостоятельно познает мир. Дети отличаются от взрослых. В обычной американской семье традиционно минимум два ребенка. В разные эпохи, в разных странах детей воспитывали по разному.

Без темы

1473 презентации
Урок

Обществознание

85 тем
Картинки
900igr.net > Презентации по обществознанию > Без темы > 1. Примеры комбинаторных задач и общие принципы комбинаторики