Комбинаторика. Подготовка к контрольной работе

Сентябрь 12, 2022

Главная
Математика
Комбинаторика. Подготовка к контрольной работе

Содержание

2. Формулы сложения и произведения Сложение -Когда использовать?? -Когда задача разбивается на несколько непересекающихся случаев! Произведение -Когда
3. Примеры использования сложения и произведения Сложение и произведение Пусть имеется 3 синих, 4 красных, и 5
4. Перестановки Формула P(n)=n! Когда использовать?? Имеется n отличающихся между собой объектов, и n позиций для них.
5. Размещение без повторений Формула A(n,m)=n!/(n-m)! Когда использовать?? Когда нужно выбрать из n различных объектов m, и
6. Примеры Каким количеством способов можно выбрать в группе из 30 старосту и его помощника? A(30,2)=30!/(30-2)!=30*29=870 Каким
7. Размещения с повтореними Формула: А(n,m)=m^n Когда использовать?? Когда имеется n объектов, и требуется разбить их на
8. Примеры Каким количеством способов 17 человек могут выйти на 15 остановках? Первый может выйти на любой
9. Сочетания Формула: С(n,k)=n!/(k!*(n-k)!) Когда использовать?? Из n различных объектов нужно выбрать группу (в которой порядок не
10. Примеры Сколькими способами можно выбрать 10 карт из 36? С(36,10) Сколькими способами можно выбрать 4 позиций
11. Задача Муавра Формула F(n,k)=C(n+k-1,k-1) Когда использовать?? Либо когда у нас n ОДИНАКОВЫХ объектов, раскладывается по k
12. Примеры Сколькими способами можно купить 9 ручек, если в продаже имеется 4? Пусть xi – количество
13. Пример задач с ограничениями (было у нас в прошлом году на кр) Каким количеством способом могут
14. Пример задач с ограничениями (было у нас в прошлом году на кр) Каким количеством способом могут
15. Формула включений исключений Когда использовать? Когда нужно найти объединение некоторых множеств, при этом легко находятся их
16. Примеры Сколько последовательностей из букв английского алфавита (их 26!) длины 5 содержащих хотя бы одну букв
17. Задачи для решения (они из учебника Шварца ничего нового, но в конце презентации есть решения к
18. Решение задачи 111 Введем систему координат, сейчас мы находимся в клетке (1,1,1) надо попасть в (10,10,10).
19. Решение задачи 115 Выберем позиции на которых будут стоять четные числа, это можно сделать С(10,5) способами.
20. Решение задачи 121 Выберем k позиций из n С(n,k) способами, это позиции на которых будут стоять
21. Решение задачи 158 Всего способов 4^15 (так как каждый из 15 может попасть в любую из
22. Решение задачи 171 А) У ней есть 28 промежуточных полей, на каждое поле можно как вступать
23. Решение задачи 194 Всего решений этого уравнений в неотрицательных целых числах С(n+3-1,3-1) способов. Вычтем те случаи
24. Решение задачи 199 Если бы цветов каждого вида было бы бесконечно много, или хотя бы больше
26. Скачать презентацию

Слайд 2

Формулы сложения и произведения
Сложение
-Когда использовать??
-Когда задача разбивается на несколько непересекающихся случаев!
Произведение
-Когда

использовать??
-Когда задача разбивается на несколько независимых подзадач. Пусть количество решений первой подзадачи X, для ЛЮБОГО решения первой подзадачи имеется Y решений второй, тогда общее количество X*Y

Слайд 3

Примеры использования сложения и произведения
Сложение и произведение
Пусть имеется 3 синих, 4

красных, и 5 белых шаров, каким количество способом можно вытащить 2 разноцветных шара?
Решение: Разбиваем задачу на непересекающиеся случаи
-Синий и красный 3*4=12 (так как для каждого из 3 синих, можем вытянуть 4 красных)
-Синий и белый 3*5=15 (аналогично)
-Красный и белый 4*5=20
Ответ: 12+15+20=47

Слайд 4

Перестановки
Формула P(n)=n!
Когда использовать?? Имеется n отличающихся между собой объектов, и n

позиций для них. Нужно расставить их на эти позиции. НИКАКОЙ ВЫБОРКИ ОБЪЕКТОВ НЕТ!
Объяснение формулы: На первое можно поставить любой из n объектов, на следующее любой из оставшихся n-1, на следующее n-2 и.т.д.
Пример: Каким количеством способов можно расставить 10 людей в линию? 10! Пример: Каким количеством способов можно перемешать колоду из 52 карт? 52!

Слайд 5

Размещение без повторений
Формула A(n,m)=n!/(n-m)!
Когда использовать?? Когда нужно выбрать из n различных

объектов m, и выставить их в определенном порядке, при этом каждый объект может использоваться только 1 раз
Объяснение формулы: На первую позицию можем поставить n объектов, на вторую n-1, на третью n-2, на последнюю n-m+1,
n*(n-1)*(n-2)*…*(n-m+1)=n!/(n-m)!

Слайд 6

Примеры
Каким количеством способов можно выбрать в группе из 30 старосту и

его помощника? A(30,2)=30!/(30-2)!=30*29=870
Каким количеством способов 10 человек из 30 могут выстроится в очередь к врачу? А(30,10)=30!/20!

Слайд 7

Размещения с повтореними
Формула: А(n,m)=m^n
Когда использовать?? Когда имеется n объектов, и требуется

разбить их на n групп, при этом в каждой группе может быть более одного объекта
Объяснение формулы: Первый объект может попасть в любую из m групп, второй тоже независимо от того куда попал первый может попасть в m групп -> m*m*…*m=m^n

Слайд 8

Примеры
Каким количеством способов 17 человек могут выйти на 15 остановках? Первый

может выйти на любой 15, второй на любой из 15 -> Ответ 15^17. (Очень важно понимать почему не подходит обратные соображения с ответов 17^15)
Сколько подмножеств у множества из 100 элементов? Объекты – элементы, и есть 2 группы (группа элементов, входящих в подмножество и не входящих в ней), первый элемент можно отнести в любую из 2 групп, второй тоже в любую независимо от первого -> Ответ 2^100

Слайд 9

Сочетания
Формула: С(n,k)=n!/(k!*(n-k)!)
Когда использовать?? Из n различных объектов нужно выбрать группу (в

которой порядок не важен) из k объектов.
Объяснение формулы: С(n,k)=A(n,k)/P(k) Если мы сначала решим задачу, где нам важен порядок внутри группы, ответ будет А(n,k). Однако все порядки отличающиеся лишь порядком элементов, будут давать одну группу, а таких групп будет k! Для каждой выборки

Слайд 10

Примеры
Сколькими способами можно выбрать 10 карт из 36? С(36,10)
Сколькими способами можно

выбрать 4 позиций из 10? С(10,4)
Сколькими способами можно выбрать 8 карт из 36, чтобы там были 2 короля и 2 туза? С(4,2)*С(4,2)*С(28,4) - Количество способов выбрать 2 короля из 4, 2 туза из 4, и 4 любые карты из оставшихся 28
В турнире по шахматам, каждый игрок должен сыграть с каждым ровно один раз, сколько партий будет сыграно в турнире из 14 человек? С(14,2) – Количество неупорядоченных пар шахматистов и есть количество партий в турнире

Слайд 11

Задача Муавра
Формула F(n,k)=C(n+k-1,k-1)
Когда использовать?? Либо когда у нас n ОДИНАКОВЫХ объектов,

раскладывается по k кучам, либо когда задача сводится к нахождению решений уравнений x1+x2+…xk=n в целых числах, когда каждый xi>=0
Объяснение: Расположим между n шарами k-1 перегородок, однозначно разбивающую группу на k групп. Всего позиций у нас получается n+k-1, надо выбрать те, где будут стоять перегородки, это количество C(n+k-1, k-1). Во втором случае мы как бы раскидываем n единиц по иксам.

Слайд 12

Примеры
Сколькими способами можно купить 9 ручек, если в продаже имеется 4?

Пусть xi – количество ручек i x1+x2+x3+x4=9 ->Ответ С(9+4-1,4-1)=С(12,3)
Сколькими способами можно разделить 7 яблок и 4 груши на 3 человека? Будем по отдельности делить яблоки и груши, поделит яблоки С(7+3-1,3-1) способов, а груш С(4+3-1,3-1) способов (Стандартная задача Муавра, объекты – фрукты, люди - ящики). -> Ответ С(9,2)*С(6,2)

Слайд 13

Пример задач с ограничениями (было у нас в прошлом году на

кр)

Каким количеством способом могут распределиться голоса на выборах, если избирающих 450 человек, кандидатов 4, и известно что победитель набрал более 2/3 голосов.
Решение: Так как победитель набрал более 2/3, значит как минимум 301 голос, отдадим их одну из 4 кандидатов, и оставшиеся 149 голосов распределим по Муавру.
Ответ: 4*С(149+4-1,4-1)=4*С(152,3)

Слайд 14

Пример задач с ограничениями (было у нас в прошлом году на

кр)

Каким количеством способом могут распределиться голоса на выборах, если избирающих 450 человек, кандидатов 4, и известно что кандидат А набрал ровно половину голосов.
Решение: Так как А набрал 225 голосов, отдадим их ему, а оставшиеся распределим между 3 кандидатами по Муавру
Ответ: С(225+3-1,3-1)=С(227,2)

Слайд 15

Формула включений исключений
Когда использовать?
Когда нужно найти объединение некоторых множеств, при этом

легко находятся их пересечения
Когда в задаче легко найти обратное событие (очень часто тут используется ключевое слово ХОТЯ БЫ)

Слайд 16

Примеры
Сколько последовательностей из букв английского алфавита (их 26!) длины 5 содержащих

хотя бы одну букв X, хотя бы одну Y и хотя Z?
Решение: 26^5-3*25^5+3*24^5-23^5 (От общего числа вычитаем те, где нет X, те где нет Y, те где нет Z, прибавляем те где нет пар, и вычитаем те, где нет всей тройки)

Слайд 17

Задачи для решения (они из учебника Шварца ничего нового, но в

конце презентации есть решения к ним)

Слайд 18

Решение задачи 111
Введем систему координат, сейчас мы находимся в клетке (1,1,1)

надо попасть в (10,10,10). Мы сделаем это за 27 ходов, среди которых 9 ходов это +1 по первой координате, 9 - +1 по второй и 9 - +1 по третьей. То есть наш путь описывается последовательностью из символов i, j,k, где каждого символа должно быть 9 штук. Выберем позиции на которых будет i С(27,9) способами, из оставшихся 18 выберем позиции, на которых будет j, на оставшиеся автоматически попадут k.
Ответ С(27,9)*С(18,9)=27!/(9!*9!*9!)

Слайд 19

Решение задачи 115
Выберем позиции на которых будут стоять четные числа, это

можно сделать С(10,5) способами. Выбрав позиции для четных, мы однозначно их расставляем в порядке возрастания, позиции для нечетных тоже выбираются однозначно и числа в них расставляются однозначно в порядке убывания
Ответ: С(10,5)

Слайд 20

Решение задачи 121
Выберем k позиций из n С(n,k) способами, это позиции

на которых будут стоять единицы. На оставшихся n-k позициях могут стоять как 0 так и 2. Количество способов их расставить 2^(n-k) так как по 2 способа на каждую позицию.
Ответ: С(n,k)*2^(n-k)

Слайд 21

Решение задачи 158
Всего способов 4^15 (так как каждый из 15 может

попасть в любую из 4 комнат). Вычтем те, где какая-то пустая C(4,1)*3^15 (первый множитель это выбор пустых комнат, второй это разбиение людей по комнатам). Прибавим те, где какая-то пара комнат пуста С(4,2)*2^15, и вычтем те, где тройка комнат пуста С(4,3)*1^15. Надо бы еще прибавить те способы, где все пусты, но таких нет.
Ответ: 4^15-C(4,1)*3^15+C(4,2)*2^15-C(4,3)*1^15

Слайд 22

Решение задачи 171
А) У ней есть 28 промежуточных полей, на каждое

поле можно как вступать так и не вступать, поэтому ответ 2^28
Б) Она должна сделать 7 шагов, каждый шаг положительной длины, сумма шагов равна 29. x1+x2+x3+x4+x5+x6+x7=29, но все х положительные, значит задача с ограничениями, положим по единице в каждый x получим x1+x2+x3+x4+x5+x6+x7=22. По Муавру ответ C(22+7-1, 7-1)=C(28,6)

Слайд 23

Решение задачи 194
Всего решений этого уравнений в неотрицательных целых числах С(n+3-1,3-1)

способов. Вычтем те случаи в которых какая пара совпала. То есть найдем количество решений уравнения 2*x+z=n. Их n/2+1 штук ( округление вниз, не имеет никакого отношения к комбинаторике, но не трудно убедиться). То есть мы вычитаем от нашего решения 3*(n/2+1). Но возможен случай что все 3 переменные равны, его мы вычли 3 раза, надо 2 раза сложить. Такой случай возможен только если n кратно трем.
Ответ: При n кратном 3: С(n+2,2)-3*(n/2+1)+2
При n не кратном 3: С(n+2,2)-3*(n/2+1)

Слайд 24

Решение задачи 199
Если бы цветов каждого вида было бы бесконечно много,

или хотя бы больше 9, ответом была формула Муавра С(9+3-1,3-1). Однако нам нужно вычесть лишние случаи, когда мы превысили лимит на какой-то вид роз. Если мы превысили лимит на первый тип, то значит положили взяли его как минимум 4 раза, и того количество способов это сделать С(5+3-1,3-1), второй цветок чтобы превысить надо взять его минимум 5 раз, и того останется всего выбор для 4 цветов С(4+3-1,3-1), а для третьего останется 3 С(3+3-1,3-1). Но возможен случай когда мы превысили лимит на первые цветка одновременно (для остальных в данной задаче это невозможно), такой способ 1.
Ответ: С(11,2)-С(7,2)-С(6,2)-С(5,2)+1

Комбинаторика. Подготовка к контрольной работе

Содержание

Формулы сложения и произведенияСложение-Когда использовать??-Когда задача разбивается на несколько непересекающихся случаев!Произведение-Когда

Примеры использования сложения и произведенияСложение и произведениеПусть имеется 3 синих, 4

ПерестановкиФормула P(n)=n!Когда использовать?? Имеется n отличающихся между собой объектов, и n

Размещение без повторенийФормула A(n,m)=n!/(n-m)!Когда использовать?? Когда нужно выбрать из n различных

ПримерыКаким количеством способов можно выбрать в группе из 30 старосту и

Размещения с повторенимиФормула: А(n,m)=m^nКогда использовать?? Когда имеется n объектов, и требуется

ПримерыКаким количеством способов 17 человек могут выйти на 15 остановках? Первый

СочетанияФормула: С(n,k)=n!/(k!*(n-k)!)Когда использовать?? Из n различных объектов нужно выбрать группу (в

ПримерыСколькими способами можно выбрать 10 карт из 36? С(36,10)Сколькими способами можно

Задача МуавраФормула F(n,k)=C(n+k-1,k-1)Когда использовать?? Либо когда у нас n ОДИНАКОВЫХ объектов,

ПримерыСколькими способами можно купить 9 ручек, если в продаже имеется 4?

Пример задач с ограничениями (было у нас в прошлом году на

Пример задач с ограничениями (было у нас в прошлом году на

Формула включений исключенийКогда использовать?Когда нужно найти объединение некоторых множеств, при этом

ПримерыСколько последовательностей из букв английского алфавита (их 26!) длины 5 содержащих

Задачи для решения (они из учебника Шварца ничего нового, но в

Решение задачи 111Введем систему координат, сейчас мы находимся в клетке (1,1,1)

Решение задачи 115Выберем позиции на которых будут стоять четные числа, это

Решение задачи 121Выберем k позиций из n С(n,k) способами, это позиции

Решение задачи 158Всего способов 4^15 (так как каждый из 15 может

Решение задачи 171А) У ней есть 28 промежуточных полей, на каждое

Решение задачи 194Всего решений этого уравнений в неотрицательных целых числах С(n+3-1,3-1)

Решение задачи 199Если бы цветов каждого вида было бы бесконечно много,

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

Формулы сложения и произведения
Сложение
-Когда использовать??
-Когда задача разбивается на несколько непересекающихся случаев!
Произведение
-Когда

Примеры использования сложения и произведения
Сложение и произведение
Пусть имеется 3 синих, 4

Перестановки
Формула P(n)=n!
Когда использовать?? Имеется n отличающихся между собой объектов, и n

Размещение без повторений
Формула A(n,m)=n!/(n-m)!
Когда использовать?? Когда нужно выбрать из n различных

Примеры
Каким количеством способов можно выбрать в группе из 30 старосту и

Размещения с повтореними
Формула: А(n,m)=m^n
Когда использовать?? Когда имеется n объектов, и требуется

Примеры
Каким количеством способов 17 человек могут выйти на 15 остановках? Первый

Сочетания
Формула: С(n,k)=n!/(k!*(n-k)!)
Когда использовать?? Из n различных объектов нужно выбрать группу (в

Примеры
Сколькими способами можно выбрать 10 карт из 36? С(36,10)
Сколькими способами можно

Задача Муавра
Формула F(n,k)=C(n+k-1,k-1)
Когда использовать?? Либо когда у нас n ОДИНАКОВЫХ объектов,

Примеры
Сколькими способами можно купить 9 ручек, если в продаже имеется 4?

Формула включений исключений
Когда использовать?
Когда нужно найти объединение некоторых множеств, при этом

Примеры
Сколько последовательностей из букв английского алфавита (их 26!) длины 5 содержащих

Решение задачи 111
Введем систему координат, сейчас мы находимся в клетке (1,1,1)

Решение задачи 115
Выберем позиции на которых будут стоять четные числа, это

Решение задачи 121
Выберем k позиций из n С(n,k) способами, это позиции

Решение задачи 158
Всего способов 4^15 (так как каждый из 15 может

Решение задачи 171
А) У ней есть 28 промежуточных полей, на каждое

Решение задачи 194
Всего решений этого уравнений в неотрицательных целых числах С(n+3-1,3-1)

Решение задачи 199
Если бы цветов каждого вида было бы бесконечно много,