org/BreadcrumbList»>
• Предметы
• Алгебра
• 11 класс

1. Правило суммы

2. Правило произведения

3. Перестановки.

   Перестановки без повторений

4. Размещения. Размещения с повторениями

5. Сочетания и их свойства

6. Треугольник Паскаля. Бином Ньютона

Пракикум «решение задач по комбинаторике».

Комбинаторика — это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиальновозможное количество различных вариантов развития событий.

Основная формула комбинаторики

Пусть имеется k групп элементов, причем i-я группа состоит из n i элементов. Выберем по одному элементу из каждой группы. Тогда общее число N способов, которыми можно произвести такой выбор, определяется соотношением N=n 1 *n 2 *n 3 *…*n k .

Пример 1. Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из n 1 элементов, а вторая — из n 2 элементов. Сколько различных пар элементов можно составить из этих двух групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить n 2 . Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет n 2 . Так как в первой группе всего n 1 элемент, всего возможных вариантов будет n 1 *n 2 .

Пример 2. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?
Решение: n 1 =6 (т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6), n 2 =7 (т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5, 6), n 3 =4 (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4, 6).
Итак, N=n 1 *n 2 *n 3 =6*7*4=168.

В том случае, когда все группы состоят из одинакового числа элементов, т.е. n 1 =n 2 =…n k =n можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно n k . Такой способ выбора в комбинаторики носит название выборки с возвращением.

Пример 3. Сколько всех четырехзначных чисел можно составить из цифр 1, 5, 6, 7, 8?
Решение. Для каждого разряда четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=5 4 =625.

Рассмотрим множество, состоящие из n элементов. Это множество в комбинаторике называется генеральной совокупностью .

Число размещений из n элементов по m

Определение 1. Размещением из n элементов по m в комбинаторике называется любой упорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.

Пример 4. Различными размещениями из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком.

Число размещений в комбинаторике обозначается A n m и вычисляется по формуле:

Замечание: n!=1*2*3*…*n (читается: «эн факториал»), кроме того полагают, что 0!=1.

Пример 5 . Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различные и нечетные?
Решение: т.к. нечетных цифр пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:

Определение 2. Сочетанием из n элементов по m в комбинаторике называется любой неупорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.

Пример 6 . Для множества {1, 2, 3}сочетаниями являются {1, 2}, {1, 3}, {2, 3}.

Число сочетаний из n элементов по m

Число сочетаний обозначается C n m и вычисляется по формуле:

Пример 7. Сколькими способами читатель может выбрать две книжки из шести имеющихся?

Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:

Перестановки из n элементов

Определение 3. Перестановкой из n элементов называется любой упорядоченный набор этих элементов.

Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов {1, 2, 3} являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).

Число различных перестановок из n элементов обозначается P n и вычисляется по формуле P n =n!.

Пример 8. Сколькими способами семь книг разных авторов можно расставить на полке в один ряд?

Решение: эта задача о числе перестановок семи разных книг. Имеется P 7 =7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.

Обсуждение. Мы видим, что число возможных комбинаций можно посчитать по разным правилам (перестановки, сочетания, размещения) причем результат получится различный, т.к. принцип подсчета и сами формулы отличаются. Внимательно посмотрев на определения, можно заметить, что результат зависит от нескольких факторов одновременно.

Во-первых, от того, из какого количества элементов мы можем комбинировать их наборы (насколько велика генеральная совокупность элементов).

Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны.

И последнее, важно знать, является ли для нас существенным порядок элементов в наборе. Поясним последний фактор на следующем примере.

Пример 9. На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек?
Решение: В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5.

Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантов перестановок , которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5.

Задачи для самопроверки
1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?

2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

3. В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день?

4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек?

5. Сколькими способами можно разложить восемь различных писем по восьми различным конвертам, если в каждый конверт кладется только одно письмо?

6. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?

Задача 1. Восемь студентов обменялись рукопожатиями. Сколько было рукопожатий?

Решение. В рукопожатии участвует «подмножество», состоящее из двух студентов (m=2), тогда как всё множество» студентов составляет 8 человек (n=8). Так как в процессе рукопожатия порядок не важен, выбираем формулу для числа сочетаний:

Задача. Сколькими способами можно составить трехцветный полосатый флаг из пяти различных по цвету отрезков материи?

Решение . Порядок важен, так как перестановка материи внутри трехцветного флга обозначает разные страны. Поэтому выбираем формулу числа размещений без повторений, где множество отрезков материи n = 5, а подмножество цветов m=3:

Задача 2. Сколько словарей надо издать, чтобы можно было выполнять переводы с любого из шести языков на любой из них?

Решение . Множество включает 6 языков n=6. Поскольку перевод есть отношение между двумя языками, то m=2, причем порядок важен, так как, например, словари русско-английский и англо-русский имеют различное применение. Поэтому выбираем размещения без повторений:

Задача 3. Сколько имеется вариантов составления расписания на понедельник, если предметов у студентов 9, а в понедельник 4 пары занятий, и предметы не повторяются?

Решение . а) Для студентов порядок не важен, поэтому выбираем формулу числа сочетаний:

б) Для преподавателей порядок важен, поэтому выбираем формулу размещений без повторений:

Задача 4. Сколькими способами можно расставить на книжной полке девять книг, среди которых есть трехтомник А.С. Пушкина?

Решение .

Так как три тома, входящие в трехтомник, должны стоять рядом, причем по возрастанию номера славе направо, то рассматриваем их как один элемент данного множества, в котором имеется еще 6 элементов. Поэтому выбираем перестановки без повторений во множестве, содержащем семь элементов:

Р 7 = 7! = 5040

Задача 5. Сколькими способами можно назначить в группе из 30 человек трех дежурных?

Решение .

а) Если их роль в процессе дежурства одинакова, то порядок не важен, поэтому выбираем сочетания без повторений:

С 3 30 = 30! / 3!27! = 4060

б) Если порядок важен, т.е. во время дежурства их функциональные обязанности различны, то по формуле размещения без повторений имеем:

А 3 30 = 30! / 27! = 24360

Задача 6. Сколько существует шестизначных телефонных номеров, у которых: а) возможны любые цифры; б) все цифры различные?

Решение.

а) 1. Так как в шестизначном наборе телефонного номера возможны любые цифры, то на каждом из шести мест может встретиться любая из 10-ти цифр от 0 до 9. Необходимо из всех возможных десяти цифр выбрать лишь те шесть, которые будут испльзованы для для шастизначных телефонных номеров. Поскольку в записи телефонных номеров порядок расположения цифр важен, по формуле размещений с повторениями имеем:

А 10 6 = 10 6 = 1000000

2. Как известно, не бывает шестизначных номеров, начинающихся с нуля, поэтому надо подсчитать их количество и вычесть его из общего числа комбинаций. Число номеров, первая цифра у которых 0, найдем по формуле размещений с повторениями, «зафиксировав» ноль т.е. на каждом из пяти остальных возможных мест может встретиться любая из десяти цифр от
0 до 9. Тогда число таких комбинаций:

А 10 5 = 10 5 = 100000

3. Общее число шестизначных телефонных номеров, у которых могут быть любые, в том числе и повторяющиеся, цифры, равно разности:

А 10 6 – А 10 5 = 10 6 – 10 5 = 1000000 – 100000 = 900000

б) 1. Пусть теперь в шестизначном наборе все цифры различные. Необходимо из всех возможных десяти цифр выбрать лишь те шесть, которые используются для шестизначных телефонных номеров, причем никакая цифра не повторяется. Тогда по формуле размещений без повторений имеем:

А 10 6 = 10! / (10 – 6)! = 5х6х7х8х9х10 = 151200

2. Поскольку шестизначных номеров, начинающихся с нуля, не бывает, надо посчитать их количество и вычесть его из общего числа комбинаций. Число номеров, первая цифра у которых 0, найдем по формуле размещений без повторений, «зафиксировав ноль», т.е. на каждом из пяти оставшихся возможных мест могут встретиться цифры от 0 до 9. Тогда число таких комбинаций найдем по формуле размещений без повторений. Имеем:

А 10 5 = 10! / (10-5)! = 6х7х8х9х10 = 30240

3. Общее число шестизначных телефонных номеров, у которых не может быть повторяющихся цифр, равно разности:

А 10 6 – А 10 5 = 10 6 – 10 5 = 151200 – 30240 = 120960

Задача 7. Сколькими способами можно выделить делегацию в составе трех человек, выбирая их среди четырех супружеских пар, если:

а) в состав делегации входят любые трое из данных восьми человек;

б) делегация должна состоять из двух женщин и одного мужчины;

в делегацию не входят члены одной семьи?

Решение.

а) Порядок не важен:

С 8 3 = 8! / 3! 5! = 56

б) Выберем двух женщин из имеющихся 4-х С 4 2 способами и одного мужчину из 4-х С 4 1 способами. По правилу произведения (и мужчина, и две женщины) имеем С 4 2 х С 4 1 = 24.

в) Из четырех семей выбираем 3-х членов делегации четырьмя способами (т.к. С 4 3 = 4! / 3!1! = 4). Но в каждой семье имеется по два способа выбора члена делегации. По правилу произведения С 4 3 х2х2х2 = 4х8 =32.

Задача 8. В колледже учится 2000 студентов. Можно ли утверждать, что хотя бы двое из них имеют одинаковые инициалы и имени, и фамилии?

Решение.

В русском алфавите 33 буквы, из них ъ, ь, ы, й не могут быть использованы, поэтому n = 33-4 = 29. Каждая из 29 букв может быть инициалом и имени,и фамилии. По правилу произведения 29х29 = 841

В последние годы все больше внимания уделяется проблемам развивающего обучения. Небывалый рост объема информации требует от современного человека таких качеств, как инициативность, изобретательность, предприимчивость, способность быстро и безошибочно принимать решения. А это невозможно без умения работать творчески, самостоятельно. Если в недавнем прошлом основной задачей, стоящей перед учителем, была передача ученикам определенной суммы знаний, то в настоящее время на первый план выдвигается задача развития учащихся в процессе обучения. Обучение математике должно быть ориентировано не столько на собственно математическое образование, в узком смысле этого слова, сколько на образование с помощью математики.

Развитие математического мышления и творческих способностей осуществляется в ходе размышлений учащихся над задачами. Самостоятельная деятельность учащихся по решению задач занимает главное место в обучении математике. Умение решать задачи – критерий успешности в учебе. Очень важно показать, как обычную жизненную ситуацию можно описать математической моделью.

Материалы разработки могут быть использованы как в рамках урока (5 – 7 класс), так и на занятиях математического кружка или факультатива.

Целью разработки является повышение математической культуры учащихся, пробуждение и развитие устойчивого интереса к математике, расширение и углубление знаний.

Основные задачи, решаемые внедрением разработки – это знакомство на популярном уровне с комбинаторикой – разделом дискретной математики, который приобрел сегодня серьезное значение в связи с развитием теории вероятностей, математической логики, информационных технологий . Учащиеся должны получить представление о том, что такое комбинаторная задача, познакомиться с методами и правилами ее решения.

На этом богатом материале повышается уровень математического и логического мышления учащихся, развиваются навыки исследовательской деятельности .

Пояснительная записка

Занятия по программе «Развивающее обучение на уроках математики» проводятся мною систематически в рамках учебного времени. Такие уроки я провожу в начале и в конце четверти, чтобы активизировать деятельность учащихся, пробудить и развить интерес к математике. Кроме этого, одну – две нестандартные задачи стараюсь рассмотреть на каждом уроке, наряду с программным материалом, развивая тем самым в учениках «вкус» к познанию. При подготовке к подобным занятиям использую материалы пособия «Математика: дополнительные главы – 5 класс», а также задания из УМК и.

План урока

· Организационный момент

· Актуализация знаний учащихся

· Исторический экскурс (сообщение ученика)

· Теоретический материал

· Решение задач (с элементами самопроверки)

· Постановка домашнего задания, повторение теории

· Самостоятельная работа (взаимопроверка)

· Подведение итогов урока

(раздаточный материал ) ПРИЛОЖЕНИЕ 1

К а р т а у р о к а

«Считай несчастным тот день или тот час, в который ты не усвоил ничего нового и ничего не прибавил к своему образованию»,

«Учиться нелегко, но интересно». Ян Амос Коменский (),

чешский педагог, писатель

тема урока ________________________________

Комбинаторика – это раздел математики, посвященный решению задач выбора и расположения заданных элементов по заданным правилам.

Правило суммы

(выбор одного элемента)

А – m способов

В – n способов

А В – (m+n) способов

Например: 5 яблок, 4 груши.

Выбор яблока или груши:

5 + 4 = 9 способов

https://pandia.ru/text/78/021/images/image003_105.jpg»>

Правило произведения

(выбор пары,

нескольких элементов)

А – m способов

В – n способов

А В – (m·n) способов

Например: 2 конверта, 3 открытки.

Выбор конверта с открыткой:

2 · 3 = 6 способов

https://pandia.ru/text/78/021/images/image006_71.jpg»>

0 «>

__________________

__________________________________

№ 5. 1, 2, 3, 4, 5

__________________

__________________________________

№ 6. 0, 1, 2, 3

__________________

__________________________________

__________________

___________________________________

№ 7. 1, 3, 5, 7, 9; меньше 400

__________________

__________________________________

№ 8. _______________________________________________________________________________________________________________

______________________________________

№ 9. ____________________________________________________________________________________________________________________________________________________________________

_________________________________________

_________________________________________

_____________________________________________________________________________________________________________________________________________________________________________________________________________

_________________________________________

(раздаточный материал )

Задачи к уроку «Знакомьтесь, комбинаторика!»

1.

2. У одного знаменитого мушкетера в гардеробе имеются 3 элегантных шляпы, 4 чудных плаща и 2 пары отличных сапог. Сколько вариантов костюма ему можно составить?

3.

4.

5.

6. Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3, если цифры: а) могут повторяться; б) не могут повторяться?

7.

ПРИЛОЖЕНИЕ 2

9. Сколькими способами можно разместить 6 человек за столом, на котором поставлено 6 приборов?

10.

11.

12. Сколько различных чисел, меньших миллиона, можно записать с помощью цифр 8 и 9?

«Переменка»

Найдите закономерность построения

последовательности 111, 213, 141,

516, 171, 819, 202, 122…

Домашнее задание

1) В 5 «б» классе 26 учеников. Сколькими способами можно выбрать старосту класса и его заместителя? старосту, заместителя и ответственного за дежурство?

2) В магазине купили 9 красных, 10 зеленых и 7 желтых воздушных шаров . Сколькими способами можно взять один любой шар? зеленый и желтый шар? красный или желтый?

3 шара разного цвета?

2 шара разного цвета? (рассмотреть

все возможные варианты)

Актуализация знаний.

Повторение пройденного (решение задач методом перебора).

«Счет и внимание – основы порядка в голове»

· Сколько различных двузначных чисел можно составить из цифр 5 и 0

(без повтора)? 1 число (50)

· Сколько различных двузначных чисел можно составить из цифр 3 и 5

(повтор допускается)? 4 числа (33, 55, 53, 35)

· Сколько различных трехзначных чисел можно составить из цифр 3 и 5

(повтор допускается)? 8 чисел (333, 555, 355, 533, 335, 553, 353, 535)

· Сколько различных трехзначных чисел можно составить из цифр 3, 8, 7

(без повтора)? 6 чисел (387, 378, 837, 873, 738, 783)

Используя количество полученных в каждом задании чисел, составить название темы сегодняшнего урока и вписать ее в карту урока: «Знакомьтесь, ___________________ !»

1 число – «комби»

2 числа – «вичи»

3 числа – «рум»

4 числа – «нато»

5 чисел – «тема»

6 чисел – «ка»

7 чисел – «аза»

8 чисел – «ри»

9 чисел – «немо»

10 чисел – «хор»

Ответ: «комбинаторика»

В математике существует немало задач, в которых требуется из имеющихся элементов составить различные наборы, подсчитать количество всевозможных комбинаций элементов, образованных по определенному правилу. Решая подобные задачи, приходится перебирать различные варианты, переставлять заданные элементы, комбинировать их. Такие задачи называются комбинаторными, а раздел математики, занимающийся решением этих задач, называется комбинаторикой.

Исторический экскурс (сообщение учащегося)

С комбинаторными задачами люди имели дело еще в глубокой древности, когда, например, выбирали наилучшее расположение воинов во время охоты, придумывали узоры на одежде или посуде. В дальнейшем появились игры, требовавшие умения планировать, рассчитывать свои действия, продумывать возможные комбинации. Приспособления для таких игр археологи находили в древних захоронениях, например, в пирамиде египетского фараона Тутанхамона (II век до н. э.). А позже появились нарды, шашки, шахматы.

Долгие века комбинаторика развивалась внутри арифметики, алгебры и геометрии. Так, древнегреческие ученые большое внимание уделяли и комбинаторике чисел – составление и изучение магических квадратов, и геометрической комбинаторике – разрезанию фигур.

Как ветвь математики комбинаторика возникла только в XVII веке. Гражданин Франции Шевалье Де Марэ любил изобретать различные игры, играя в которые, получал очень интересные результаты. Например, однажды он придумал такую игру: бросает 4 кости, выигрывает тот, у кого на одной есть шестерка. Но с ним очень быстро перестали играть, так как он слишком часто выигрывал. В другой раз Шевалье придумал такую игру: бросает две кости несколько раз, выигрывает, если хотя бы раз выпало две шестерки. Однако вскоре он сам бросил играть, так как стал часто проигрывать. Такой исход дела очень удивил Шевалье де Марэ, и он обратился к двум крупнейшим математикам Франции того времени – Блезу Паскалю и Пьеру Ферма с вопросом, как можно объяснить эти удачи и проигрыши в игре, а также, как правильно делать ставки в таких и в аналогичных играх.

Решая эту задачу, Блез Паскаль и Пьер Ферма разработали начало двух ветвей математики: комбинаторики и теории вероятности. Впоследствии этими науками занимались многие великие математики тех времен: , Якоб Бернулли, Леонард Эйлер и др.

Использование комбинаторики в настоящее время очень разнообразно. Одно из них – кодирование и расшифровка текстов (шифр появился еще в средние века). В биологии комбинаторика служит для подсчета клеточных структур ДНК и РНК, в физике – для описания свойств кристаллов. Также комбинаторика широко используется и в химии.

Теоретический материал.

Комбинаторика – это раздел математики, посвященный решению задач выбора и расположения заданных элементов по заданным правилам (см. карту урока).

Обычный вопрос в комбинаторных задачах – это «Сколькими способами …?» или

«Сколько вариантов …?»

Комбинаторные задачи можно решать несколькими способами: методом перебора, перестановок (с ним мы уже знакомы), использование определенных правил комбинаторики (с ними мы познакомимся сегодня на уроке) и с помощью построения так называемого «дерева вариантов» (о нем мы поговорим позже).

Итак, начнем знакомиться с правилами комбинаторики – это правила суммы и произведения.

Правило суммы:

если некоторый элемент А можно выбрать m способами, а элемент В можно выбрать n способами, то выбор «либо А, либо В» можно сделать (m + n) способами. Например, если вам предлагают 5 яблок и 4 груши, то выбрать один плод можно 5 + 4 = 9 способами (см. карту урока).

а) В вазе 6 яблок, 5 груш и 4 сливы. Сколько вариантов выбора одного плода?

(15 вариантов)

б) В магазине продаются 3 алые, 2 белые и 4 желтые розы. Сколькими способами можно купить один цветок? (9 способов)

Еще раз обращаем внимание на то, что мы выбираем лишь один из предложенных элементов.

Правило произведения:

если некоторый элемент А можно выбрать m способами, а элемент В можно выбрать n способами, то выбор «А и В» можно сделать (m · n) способами. Например, если вам предлагают 2 конверта и 3 открытки, то составить пару (конверт и открытка) можно 3 · 2 = 6 способами (см. карту урока).

Устно решите следующие задачи:

а) Сколько танцевальных пар можно составить из 8 юношей и 6 девушек? (48 пар)

б) В столовой имеются в продаже 4 первых блюда и 7 вторых. Сколько различных вариантов обеда из двух блюд можно заказать? (28 вариантов)

Обращаем внимание на то, что мы выбираем пару элементов из предложенных множеств.

Решение задач

Учащиеся работают на бланках карты урока в соответствующем разделе, тексты задач на отдельных листах у каждого ученика. Список задач можно изменять, добавляя или убирая некоторые вопросы в зависимости от уровня подготовки класса. Можно разбить задачи по уровню сложности, некоторые оставить для самостоятельного решения. В некоторых задачах полезно подчеркнуть, что они уже ранее решались методом перебора, а сегодня – второй способ их решения. Осуществить на этом этапе дифференцированный подход. Ввести элементы самостоятельной работы с последующей самопроверкой.

1. Сколькими способами можно выбрать гласную и согласную буквы в слове «платок»? (Согласных букв в слове – 4, гласных букв – 2, значит, по правилу умножения, вариантов выбора пары — 4 · 2 = 8. )

2. У одного довольно знаменитого мушкетера в гардеробе имеются 3 элегантных шляпы,

4 чудных плаща и 2 пары отличных сапог. Сколько вариантов костюма ему можно со —

ставить? (Выбираем по одному элементу из трех множеств, то есть, составляем

«тройку», значит, по правилу умножения получаем 3 · 4 · 2 = 24 варианта костюма.)

3. В футбольной команде 11 человек. Необходимо выбрать капитана и его заместителя. Сколькими способами можно это сделать? (Всего 11 человек, значит, капитана можно выбрать 11-ю способами, осталось 10 футболистов, из которых можно выбрать заместителя капитана. Итак, пару, капитана и его заместителя, можно выбрать 11 · 10 = 110 способами.)

4. Сколько различных двузначных чисел можно составить, используя цифры 1, 4, 7, если допустить повторение цифр? (Должно получиться двузначное число – всего две позиции. На первую позицию можно поставить любую из предложенных цифр – 3 варианта выбора, на вторую позицию, с учетом возможности повтора цифры, тоже 3 варианта выбора. Значит, пару цифр мы составляем 3 · 3 = 9 способами, т. е. получится 9 чисел.

Запись решения:

3 ∙ 3 = 9 чисел.

Такая запись решения используется во всех подобных задачах при работе на бланках карты урока.)

5. Сколько различных трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5 при условии, что ни одна цифра не повторяется? (Трехзначное число: первая позиция – 5 вариантов цифр, вторая позиция, с учетом исключения повторов цифр, — 4 варианта, третья позиция – 3 варианта. Получаем 5 · 4 · 3 = 60 чисел.)

6. Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3, если цифры:

а) могут повторяться; б) не могут повторяться? (а) Двузначное число, как и любое мно-

гозначное, не может начинаться с 0, поэтому на первую позицию можно поставить

лишь 3 из имеющихся 4-х цифр, 3 варианта выбора, на вторую позицию, с учетом по-

втора, можно поставить любую из цифр – 4 варианта выбора. Поэтому получается

3 · 4 = 12 чисел; б) Первая позиция – 3 варианта, вторая позиция – 3 варианта, т. к.

повтор исключается. Получаем 3 · 3 = 9 чисел.)

7. Сколько различных трехзначных чисел, меньших 400, можно составить из цифр 1, 3, 5, 7, 9, если любая цифра может быть использована только один раз? (Трехзначное число

8. Шифр для сейфа состоит из пяти различных цифр. Сколько различных вариантов составления шифра? (5 · 4 · 3 · 2 · 1 = 120 вариантов.)

9. Сколькими способами можно разместить 6 человек за столом, на котором поставлено

6 приборов? (6 · 5 · 4 · 3 · 2 · 1 = 720 способов.)

10. В пятом классе изучаются 8 предметов. Сколько различных вариантов расписания можно составить на понедельник, если в этот день должно быть 5 уроков и все уроки – разные? (8 · 7 · 6 · 5 · 4 = 6720 вариантов.)

11. Сколько вариантов семизначных телефонных номеров можно составить, если исключить из них номера, начинающиеся с 0 и 9? (Используются цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 – всего 10 цифр, исключая по условию 0 и 9 в начале номера, с учетом возможности повтора, получаем 8 · 10 · 10 · 10 · 10 · 10 · 10 = 8 номеров. )

12. Сколько различных чисел, меньших миллиона, можно записать с помощью цифр

8 и 9? (Однозначных чисел – 2, двузначных чисел — 2 · 2 = 4, трехзначных чисел –

2 · 2 · 2 = 8, четырехзначных чисел – 16, пятизначных чисел – 32, шестизначных

чисел – 64. А всего — 2 + 4 + 8 + 16 + 32 + 64 = 126 чисел.)

«Переменка»

Найдите закономерность построения последовательности 111, 213, 141, 516, 171, 819, 202, 122… (В данной последовательности надо иначе расставить запятые, и получим 11, 12, 13, 14, 15…)

Постановка домашнего задания (см. приложение 2) , повторение теоретического материала (правила сложения и умножения, условия выбора элементов).

Самостоятельная работа (с последующей взаимопроверкой в парах)

· Выбор одного любого элемента из предложенных множеств выполняется по правилу ______________________. Выбор пары и более элементов из множеств происходит по правилу ______________________.

· В вазе стоят 5 красных, 3 белых и 3 желтых тюльпана. Один цветок из вазы можно выбрать _______ способами, три цветка разного цвета ________ способами.

· Сколько различных трехзначных чисел можно составить, используя цифры 3 и 5, если их повтор допускается? ____________________________________________________________

· В четверг в первом классе должно быть 4 урока: письмо, чтение, математика, физкультура. Сколько различных вариантов расписания на этот день можно предложить?

_________________________________________________________________________________

Ответы: сложения, умножения, 11, 45, 2 · 2 · 2 =8, 4 · 3 · 2 · 1 = 24.

Взаимопроверка, выставление оценок, обсуждение результатов.

Подведение итогов урока

На этом этапе урока, помимо традиционной беседы о том, какие задачи ставились, насколько успешно с ними справились, следует вернуться к эпиграфу урока (см. бланк карты урока) и поразмышлять о словах.

Кроме того, ученикам предлагается ответить на 3 блиц — вопроса:

· На сегодняшнем уроке мне было … (легко, обычно, трудно)

· Новый материал я … (усвоил и могу применить, усвоил и затрудняюсь применить, не усвоил)

· Моя самооценка за урок …

Ответы на приведенные вопросы можно не подписывать, т. к. их основная функция помочь учителю проанализировать урок и его результаты.

П о с л е с л о в и е

На следующем уроке предполагается отработка пройденного материала на этапе устной работы, введения понятия «дерево возможных вариантов» как еще одного способа решения комбинаторных задач, систематизация изученных методов решения задач, практикум по решению задач различными способами, решение задач повышенного уровня, контроль знаний.

Комбинаторика – это раздел математики, посвящённый решению задач выбора и расположения элементов некоторого множества в соответствии с заданными правилами. Комбинаторика изучает комбинации и перестановки предметов, расположение элементов, обладающее заданными свойствами. Обычный вопрос в комбинаторных задачах: сколькими способами….

К комбинаторным задачам относятся также задачи построения магических квадратов, задачи расшифровки и кодирования.

Рождение комбинаторики как раздела математики связано с трудами великих французских математиков 17 века Блеза Паскаля (1623–1662) и Пьера Ферма (1601–1665) по теории азартных игр. Эти труды содержали принципы определения числа комбинаций элементов конечного множества. С 50-х годов 20 века интерес к комбинаторике возрождается в связи с бурным развитием кибернетики.

Основные правила комбинаторики – это правило суммы и правило произведения .

• Правило суммы

Если некоторый элемент А можно выбрать n способами, а элемент В можно выбрать m способами, то выбор «либо А, либо В» можно сделать n + m способами.

Например, Если на тарелке лежат 5 яблок и 6 груш, то один плод можно выбрать 5 + 6 = 11 способами.

• Правило произведения

Если элемент А можно выбрать n способами, а элемент В можно выбрать m способами, то пару А и В можно выбрать n m способами.

Например, если есть 2 разных конверта и 3 разные марки, то выбрать конверт и марку можно 6 способами (2 3 = 6).

Правило произведения верно и в том случае, когда рассматривают элементы нескольких множеств.

Например, если есть 2 разных конверта, 3 разные марки и 4 разные открытки, то выбрать конверт, марку и открытку можно 24 способами (2 3 4 = 24).

Произведение всех натуральных чисел от 1 до n включительно называется n – факториалом и обозначается символом n!

n! = 1 2 3 4 … n.

Например, 5! = 1 2 3 4 5 = 120.

Например, если есть 3 шарика – красный, синий и зелёный, то выложить их в ряд можно 6 способами (3 2 1 = 3! = 6).

Иногда комбинаторная задача решается с помощью построения дерева возможных вариантов .

Например, решим предыдущую задачу о 3-х шарах построением дерева.

Практикум по решению задач по комбинаторике.

ЗАДАЧИ и решения

1. В вазе 6 яблок, 5 груш и 4 сливы. Сколько вариантов выбора одного плода?

Ответ: 15 вариантов.

2. Сколько существует вариантов покупки одной розы, если продают 3 алые, 2 алые и 4 жёлтые розы?

Ответ: 9 вариантов.

3. Из города А в город В ведут пять дорог, а из города В в город С ведут три дороги. Сколько путей, проходящих через В, ведут из А в С?

Ответ: 15 путей.

4. Сколькими способами можно составить пару из одной гласной и одной согласной букв слова «платок»?

гласные: а, о – 2 шт.
согласные: п, л, т, к – 4 шт.

Ответ: 8 способами.

5. Сколько танцевальных пар можно составить из 8 юношей и 6 девушек?

Ответ: 48 пар.

6. В столовой есть 4 первых блюда и 7 вторых. Сколько различных вариантов обеда из двух блюд можно заказать?

Ответ: 28 вариантов.

7. Сколько различных двузначных чисел можно составить, используя цифры 1, 4 и 7, если цифры могут повторяться?

1 цифра – 3 способа
2 цифра – 3 способа
3 цифра – 3 способа

Ответ: 9 различных двузначных чисел.

8. Сколько различных трёхзначных чисел можно составить, используя цифры 3 и 5, если цифры могут повторяться?

1 цифра – 2 способа
2 цифра – 2 способа
3 цифра – 2 способа

Ответ: 8 различных чисел.

9. Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3, если цифры могут повторяться?

1 цифра – 3 способа
2 цифра – 4 способа

Ответ: 12 различных чисел.

10. Сколько существует трёхзначных чисел, у которых все цифры чётные?

Чётные цифры – 0, 2, 4, 6, 8.

1 цифра – 4 способа
2 цифра – 5 способов
3 цифра – 5 способов

Ответ: существует 100 чисел.

11. Сколько существует четных трёхзначных чисел?

1 цифра – 9 способов (1, 2, 3, 4, 5, 6, 7, 8, 9)
2 цифра – 10 способов (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
3 цифра – 5 способов (0, 2, 4, 6, 8)

9 10 5 = 450

Ответ: существует 450 чисел.

12.Сколько различных трёхзначных чисел можно составить из трёх различных цифр 4, 5, 6?

1 цифра – 3 способа
2 цифра – 2 способа
3 цифра – 1 способ

Ответ: 6 различных чисел.

13. Сколькими способами можно обозначить вершины треугольника, используя буквы А, В, С, D?

1 вершина – 4 способа
2 вершина – 3 способа
3 вершина – 2 способа

Ответ: 24 способа.

14. Сколько различных трёхзначных чисел можно составить из цифр 1, 2, 3, 4, 5,при условии, что ни одна цифра не повторяется?

1 цифра – 5 способов
2 цифра – 4 способа
3 цифра – 3 способа

Ответ: 60 различных чисел.

15. Сколько различных трёхзначных чисел, меньших 400, можно составить из цифр 1, 3, 5, 7, 9, если любая из этих цифр может быть использована только один раз?

1 цифра – 2 способа
2 цифра – 4 способа
3 цифра – 3 способа

Ответ: 24 различных числа.

16. Сколькими способами можно составить флаг, состоящий из трёх горизонтальных полос различных цветов, если имеется материал шести цветов?

1 полоса – 6 способов
2 полоса – 5 способов
3 полоса – 4 способа

Ответ: 120 способов.

17. Из класса выбирают 8 человек, имеющих лучшие результаты по бегу. Сколькими способами можно составить из них команду из трёх человек для участия в эстафете?

1 человек – 8 способов
2 человек – 7 способов
3 человек – 6 способов

Ответ: 336 способов.

18. В четверг в первом классе должно быть четыре урока: письмо, чтение, математика и физкультура. Сколько различных вариантов расписания можно составить на этот день?

1 урок – 4 способа
2 урок – 3 способа
3 урок – 2 способа
4 урок – 1 способ

4 3 2 1 = 24

Ответ: 24 варианта.

19. В пятом классе изучаются 8 предметов. Сколько различных вариантов расписания можно составить на понедельник, если в этот день должно быть 5 уроков и все уроки разные?

1 урок – 8 вариантов
2 урок – 7 вариантов
3 урок – 6 вариантов
4 урок – 5 вариантов
5 урок – 4 варианта

8 7 6 5 4 = 6720

Ответ: 6720 вариантов.

20. Шифр для сейфа составляется из пяти различных цифр. Сколько различных вариантов составления шифра?

1 цифра – 5 способов
2 цифра – 4 способа
3 цифра – 3 способа
4 цифра – 2 способа
5 цифра – 1 способ

5 4 3 2 1 = 120

Ответ: 120 вариантов.

21. Сколькими способами можно разместить 6 человек за столом, на котором поставлено 6 приборов?

6 5 4 3 2 1 = 720

Ответ: 720 способов.

22. Сколько вариантов семизначных телефонных номеров можно составить, если исключить из них номера, начинающиеся с нуля и 9?

1 цифра – 8 способов
2 цифра – 10 способов
3 цифра – 10 способов
4 цифра – 10 способов
5 цифра – 10 способов
6 цифра – 10 способов
7 цифра – 10 способов

8 10 10 10 10 10 10 = 8.000.000

Ответ: 8.000.000 вариантов.

23. Телефонная станция обслуживает абонентов, у которых номера телефонов состоят из 7 цифр и начинаются с 394. На сколько абонентов рассчитана эта станция?

№ телефона 394

10 10 10 10 = 10.000

Ответ: 10.000 абонентов.

24. Имеется 6 пар перчаток различных размеров. Сколькими способами можно выбрать из них одну перчатку на левую руку и одну перчатку на правую руку так, чтобы эти перчатки были различных размеров?

Левые перчатки – 6 способов
Правые перчатки – 5 способов (6 перчатка того же размера, что и левая)

Ответ: 30 способов.

25 . Из цифр 1, 2, 3, 4, 5 составляют пятизначные числа, в которых все цифры разные. Сколько таких чётных чисел?

5 цифра – 2 способа (две чётные цифры)
4 цифра – 4 способа
3 цифра – 3 способа
2 цифра – 2 способа
1 цифра – 1 способ

2 4 3 2 1 = 48

Ответ: 48 чётных чисел.

26. Сколько существует четырёхзначных чисел, составленных из нечётных цифр и делящихся на 5?

Нечётные цифр – 1, 3, 5, 7, 9.
Из них делятся на 5 – 5.

4 цифра – 1 способ (цифра 5)
3 цифра – 4 способа
2 цифра – 3 способа
1 цифра – 2 способа

1 4 3 2 = 24

Ответ: 24 числа.

27. Сколько существует пятизначных чисел, у которых третья цифра – 7, последняя цифра – чётная?

1 цифра – 9 способов (все, кроме 0)
2 цифра – 10 способов
3 цифра – 1 способ (цифра 7)
4 цифра – 10 способов
5 цифра – 5 способов (0, 2, 4, 6, 8)

9 10 1 10 5 = 4500

Ответ: 4500 чисел.

28. Сколько существует шестизначных чисел, у которых вторая цифра – 2, четвёртая – 4, шестая – 6, а все остальные – нечётные?

1 цифра – 5 вариантов (из 1, 3, 5, 7, 9)
2 цифра – 1 вариант (цифра 2)
3 цифра – 5 вариантов
4 цифра – 1 вариант (цифра 4)
5 цифра – 5 вариантов
6 цифра – 1 вариант (цифра 6)

5 1 5 1 5 1 = 125

Ответ: 125 чисел.

29.Сколько различных чисел, меньших миллиона, можно записать с помощью цифр 8 и 9?

Однозначных – 2
Двузначных – 2 2 = 4
Трёхзначных – 2 2 2 = 8
Четырёхзначных – 2 2 2 2 =16
Пятизначных – 2 2 2 2 2 = 32
Шестизначных – 2 2 2 2 2 2 = 64

Всего: 2 + 4 + 8 + 16 + 32 + 64 = 126

Ответ: 126 чисел.

30. В футбольной команде 11 человек. Нужно выбрать капитана и его заместителя. Сколькими способами это можно сделать?

Капитан – 11 способов
Заместитель – 10 способов

Ответ: 110 способов.

31.В классе учатся 30 человек. Сколькими способами из них можно выбрать старосту и ответственного за проездные билеты?

Староста – 30 способов
Ответ. за билеты – 29 способов

Ответ: 870 способов.

32. В походе участвуют 12 мальчиков, 10 девочек и 2 учителя. Сколько вариантов групп дежурных из трёх человек (1 мальчик, 1 девочка, 1 учитель) можно составить?

12 10 2 = 240

Ответ: 240 способов.

33. Сколько комбинаций из четырёх букв русского алфавита (в алфавите всего 33 буквы) можно составить при условии, что 2 соседние буквы будут разными?

При решении многих практических задач приходится использовать комбинации элементов, выбирать из данной совокупности те, которые имеют определенные свойства, и размещать их в определенном порядке. Такие задачи называются комбинаторными . Раздел математики, посвящённый решению задач выбора и расположения элементов в соответствии с данными условиями, называется комбинаторикой. Термин «комбинаторика» происходит от латинского слова «combina» , что в переводе на русский язык означает – «сочетать», «соединять».

Выбранные группы элементов называют соединениями. Если все элементы соединения разные, то получаем соединения без повторений, которые и рассмотрим ниже.

Большинство комбинаторных задач решается с помощью двух основных правил – правила суммы и правила произведения .

Задача 1.

В магазине «Все для чая» есть 6 разных чашек и 4 разных блюдца. Сколько вариантов чашки и блюдца можно купить?

Решение .

Чашку мы можем выбрать 6-ю способами, а блюдце 4-я способами. Так как нам надо купить пару чашку и блюдце, то это можно сделать 6 · 4 = 24 способами (по правилу произведения).

Ответ: 24.

Для успешного решения комбинаторных задач надо еще и правильно выбрать формулу, по которой искать количество нужных соединений. В этом поможет следующая схема.

Рассмотрим решение нескольких задач на разные виды соединений без повторений.

Задача 2.

Найдите количество трехзначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, 7, если цифры в числе повторяться не могут.

Решение.

Для выбора формулы выясняем, что для чисел, которые мы будем составлять, порядок учитывается и не все элементы одновременно выбираются. Значит, это соединение – размещение из 7 элементов по 3. Воспользуемся формулой для числа размещений: A 7 3 = 7(7 – 1)(7 – 2) = 7 · 6 · 5 = 210 чисел.

Ответ: 210.

Задача 3.

Сколько существует семизначных телефонных номеров, в которых все цифры разные, а номер не может начинаться с нуля?

Решение.

На первый взгляд эта задача такая же, как и предыдущая, но сложность в том, что надо не учитывать те соединения, которые начинаются с нуля. Значит необходимо из существующих 10-ти цифр составить все семизначные номера телефонов, а потом от полученного числа отнять количество номеров, начинающихся с нуля. Формула будет иметь вид:

A 10 7 – A 9 6 = 10 · 9 · 8 · 7 · 6 · 5 · 4 – 9 · 8 · 7 · 6 · 5 · 4 = 544 320.

Ответ: 544 320.

Задача 4.

Сколькими способами можно расставить на полке 12 книг, из которых 5 книг – это сборники стихотворений, так, чтобы сборники стояли рядом?

Решение.

Сначала примем 5 сборников условно за одну книгу, потому что они должны стоять рядом. Так как в соединении существенным есть порядок, и все элементы используются, значит это перестановки из 8 элементов (7 книг + условная 1 книга). Их количество Р 8 . Далее будем переставлять между собой только сборники стихотворений. Это можно сделать Р 5 способами. Поскольку нам нужно расставить и сборники, и другие книги, то воспользуемся правилом произведения. Следовательно, Р 8 · Р 5 = 8! · 5!. Число способов будет большим, поэтому ответ можно оставить в виде произведения факториалов.

Ответ: 8! · 5!

Задача 5 .

В классе 16 мальчиков и 12 девочек. Для уборки территории возле школы нужно 4 мальчика и 3 девочки. Сколькими способами можно их выбрать со всех учеников класса?

Решение.

Сначала отдельно выберем 4 мальчика из 16 и 3 девочки из 12. Так как порядок размещения не учитывается, то соответственные соединения – сочетания без повторений. Учитывая необходимость одновременного выбора и мальчиков, и девочек, используем правило произведения. В результате число способов будет вычисляться таким образом:

С 16 4 · С 12 3 = (16!/(4! · 12!)) · (12!/(3! · 9!)) = ((13 · 14 · 15 · 16) / (2 · 3 · 4)) ·((10 · 11 · 12) / (2 · 3)) = 400 400.

Ответ: 400 400.

Таким образом, успешное решение комбинаторной задачи зависит от правильного анализа ее условия, определения типа соединений, которые будут составляться, и выбора подходящей формулы для вычисления их количества.

Остались вопросы? Не знаете, как решать комбинаторные задачи?
Чтобы получить помощь репетитора – зарегистрируйтесь .
Первый урок – бесплатно!

сайт, при полном или частичном копировании материала ссылка на первоисточник обязательна.

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

Этот раздел включает в себя основные примеры и задачи, которые помогут вам подготовиться к следующему разделу решения задач.

Кэлвин хочет поехать в Милуоки. Он может выбрать из 333 автобусных маршрутов или 222 поездов, чтобы отправиться из дома в центр Чикаго. Оттуда он может выбрать один из двух автобусов или трех поездов, чтобы отправиться в Милуоки.

На этот раз он должен купить проездной билет на автобус (что позволит ему ездить только на автобусах) или билет на поезд (что позволит ему ездить только на поезде).Если у него есть деньги только на 111 таких концессий, сколько у него есть способов добраться до Милуоки?

---

Если Кальвин покупает автобус, у него есть 3×2=6 3 х 2=63×2=6 способов добраться до Милуоки. (Правило произведения)
Если Кальвин покупает концессию на поезд, у него есть 2×3=6 2\×3=62×3=6 способов добраться до Милуоки. (Правило произведения)
Следовательно, всего у него есть 6+6=12 6+6=126+6=12 способов добраться до Милуоки. (Правило суммы) □_\квадрат□​

Шестеро друзей Энди, Бэнди, Кэнди, Денди, Энди и Фэнди хотят сесть в ряд в кинотеатре.Если доступно только шесть мест, сколькими способами мы можем посадить этих друзей?

---

На первое место у нас есть выбор любого из 6 друзей. После посадки первого человека на второе место у нас есть выбор любого из оставшихся 5 друзей. После посадки второго человека на третье место у нас есть выбор любого из оставшихся 4 друзей. После посадки третьего человека на четвертое место у нас есть выбор любого из оставшихся 3 друзей. После посадки четвертого человека на пятое место у нас есть выбор любого из оставшихся 2 друзей.После посадки пятого человека, на шестое место у нас есть выбор только из 1 оставшегося друга. b2a5b, где a aa и b bb — целые числа, удовлетворяющие условию 0≤a≤4,0≤b≤3 0 \leq a \leq 4, 0 \leq б \leq 30≤a≤4,0≤b≤3.Существует 5 возможностей для a aa и 4 возможности для b bb, следовательно, всего имеется 5×4=20 5 х 4 = 205×4=20 (правило произведения) положительных делителей числа 2000. □_\квадрат□​

Следующие задачи познакомят вас с двумя правилами, описанными выше.

Сколько параллелограммов образуется при пересечении набора из 5 параллельных прямых с набором из 4 параллельных прямых?

Детали и предположения

• Все параллельные линии бесконечно удлиняются.

Отправьте свой ответ

Если вы подсчитаете способы подъема на 3 ступени, вы обнаружите, что существует 4 способа подъема на 3 ступени. Представьте себе, что ноги человека такие длинные, что они могут подняться на 11 ступенек за раз. Также человеку разрешено подниматься только вверх.

Тогда найдите количество способов, которыми вы можете подняться на 11 ступенек?

Бонус : Обобщите это для nnn шагов.

Отправьте свой ответ

Трое детей, каждый в сопровождении опекуна, хотят поступить в школу.Princi хочет опросить всех 6 человек одного за другим при одном условии, что ни один ребенок не будет опрошен в присутствии его опекуна. Сколькими способами это можно сделать?

Правило суммы, Правило произведения

[Этот пост предназначен для учащегося 1-го уровня. ]

Правило суммы (принцип сложения) и правило произведения (принцип умножения) — это два основных принципа подсчета, которые используются для построения теории перечислительной комбинаторики.Эти правила очень просты, и мы неосознанно пользуемся ими каждый день. Рассмотрим следующие примеры:

1. В одном городе кинотеатр CAL показывает 4 летних блокбастера. Через дорогу в другом кинотеатре показывают 3 (совершенно разных) независимых фильма. Сколько шоу доступно?

2. В кинотеатрах CAL идет показ 4 летних блокбастеров. Каждое шоу показывается 5 раз в день. Сколько сеансов проходит в кинотеатрах CAL в день?

Прежде чем обсуждать ответы, сформулируем правило суммы и правило произведения.

Правило суммы/принцип сложения Если есть способы сделать что-то и способы сделать что-то другое, оба из которых не могут быть выполнены одновременно, то есть способы выбрать одно из этих действий.

Правило произведения / принцип умножения Если есть способы сделать что-то, а после этого — еще что-то, то есть способы выполнить оба этих действия.

На первый вопрос отвечает правило суммы, так как в одном месте 4 шоу, а в другом 3 (разных) шоу.Таким образом, есть общее количество шоу, которые доступны. На второй вопрос отвечает правило продукта, так как есть 4 показа, каждый из которых показан 5 раз. Таким образом, в день проводится общее количество просмотров. Ниже мы рассмотрим несколько более сложных примеров.

Примеры работы

1. Кальвин хочет поехать в Милуоки. Он может выбрать один из трех автобусных маршрутов или двух поездов, чтобы отправиться из дома в центр Чикаго. Оттуда он может выбрать один из двух автобусов или трех поездов, чтобы отправиться в Милуоки.Сколько у него есть способов попасть в Милуоки?

Этот вопрос показывает, что мы не всегда просто складываем (или умножаем) все заданные числа. Порядок рассмотрения также важен, как продемонстрирует следующий вопрос.

2. Кальвин хочет поехать в Милуоки (см. предыдущий вопрос). На этот раз он должен купить концессию на автобус (что позволит ему ездить только на автобусах) или концессию на поезд (что позволит ему ездить только на поездах). Если у него есть деньги только на одну из этих концессий, сколько у него есть способов добраться до Милуоки?

3.6 друзей Энди, Бэнди, Кэнди, Денди, Энди и Фэнди хотят сесть в ряд в кинотеатре. Если доступно только 6 мест, сколькими способами мы можем посадить этих друзей?

В более общем смысле эта проблема известна как перестановка. Есть способы рассадить людей в ряд.

4. Сколько положительных делителей имеет?

Для обобщения рабочего примера 4 учащиеся должны прочитать Делители целого числа.

Проверь себя

1. Сколько существует четных трехзначных положительных целых чисел?

2.Шестеро друзей Энди, Бэнди, Кэнди, Денди, Энди и Фэнди хотят создать клуб. Они решают, что будет 1 президент, 1 казначей, 1 секретарь и 3 обычных члена. Сколькими способами они могут организовать этот клуб?

3. В классе из 15 учащихся сколькими способами учитель может распределить следующие призовые места: Первое по математике, Второе по математике, Третье по математике, Первое по физике, Первое по химии, Первое по биологии, Первое по английскому языку, Второе на английском? Студент не может выиграть 2 приза по предмету, но может выиграть призы по разным предметам.

4. (Live Challenge Combinatorics 1) Кальвин хочет поехать из Чикаго в Австралию на каникулы. Он заходит в интернет и обнаруживает, что есть рейсы из Чикаго в Гонконг, рейсы из Гонконга в Сингапур, рейсы из Сингапура в Австралию, рейсы из Чикаго в Сингапур и рейсы из Гонконга в Австралию. Сколькими способами Келвин может долететь из Чикаго в Австралию?

Примечание. Все рейсы выполняются в одном направлении в указанном направлении. В частности, нет доступных рейсов из Сингапура в Гонконг.

5. (*) Сколько существует упорядоченных наборов неотрицательных целых чисел, таких что ? Подсказка: решение задачи по комбинаторике

Нравится:

Нравится Загрузка…

Принципы счета

Раздел 2.6 Принципы подсчета

Как в чистой, так и в прикладной математике часто полезно подсчитывать размеры конечных множеств. В этом разделе мы докажем некоторые основные теоремы такого рода. n \abs{ A_j }. \end{уравнение*}

Очевидно, но мы опускаем техническое доказательство до тех пор, пока у нас не будет надлежащего обсуждения определения числа элементов в наборе, что произойдет только в главе 5.

Теорема 2.6.2

Для конечных множеств \(A, B\text{,}\), которые не обязательно не пересекаются,

Очевидно, если посмотреть на диаграмму Венна, но мы опускаем техническое доказательство по тем же причинам.j A_{n_k} } \right). \end{уравнение*}

В приведенной выше формуле сумма берется по всем поднаборам \(j\) различных множеств из числа \(A_1, \ldots, A_n\text{.}\) В частности, когда \(n = 3\text{, }\) вышеприведенное становится

По индукции и с помощью теоремы 2. n \abs{ A_j }. \end{уравнение*}

Использование индукции и правила сумм.

Определение 2.6.5 Перестановка (комбинаторика)

перестановка конечного множества — это расположение элементов в определенном порядке.

Для следующей теоремы напомним, что факториал натурального числа \(n\) определяется индуктивно как

Эквивалентно \(n! = n(n-1)(n-2)\cdots 1\text{.}\)

Теорема2.6,6

Число перестановок множества из \(n\) элементов равно \(n!\)

Индукцией по количеству элементов в множестве.

Теорема 2.6.7

Если \(n \in \mathbb{N}\) и \(r \in \mathbb{Z}\) с \(0 \le r \le n\text{,}\), то количество перестановок любые \(r\) отдельные объекты из набора \(n\) объектов равны

По индукции по \(r\) и теореме 2.6.6.

Определение 2.6.8 Комбинация

Для \(n \in \mathbb{N}\) и \(r \in \mathbb{Z}\) с \(0 \le r \le n\text{,}\) комбинация из \ (r\) элементов из набора размера \(n\) является просто подмножеством размера \(r\text{. }\)

Количество комбинаций называется биномиальным коэффициентом и обозначается \(\binom{n}{r}\text{.}\) Мы читаем этот символ как «\(n\) Choose \(r\text{ .}\)”

Теорема 2.6.9 Комбинированное правило

У нас есть следующая формула для биномиальных коэффициентов:

Обратите внимание, что количество перестановок любых \(r\) различных объектов из набора \(n\) объектов обязательно равно количеству подмножеств размера \(r\) (т.е. количеству комбинаций, биномиальный коэффициент ), умноженное на количество способов упорядочить эти \(r\) элементы (т. е. перестановки множества размера \(r\)). Следовательно, по теореме 2.6.6 и теореме 2.6.7 имеем

тем самым подтверждая результат.

Примечание: приведенная выше теорема гарантирует \(\binom{n}{r} = \binom{n}{n-r}\text{.{н-р}. \end{уравнение*}

По индукции и с учетом того, что при \(r \ge 1\text{,}\)

, что вы должны доказать. Это отображаемое уравнение по существу говорит о том, что треугольник Паскаля генерирует биномиальные коэффициенты.

2.4: Подведение итогов — Mathematics LibreTexts

Скорее всего, вы использовали правило сумм или правило произведения при подсчете простых вещей, даже не задумываясь о том, что вы делаете.Причина, по которой мы рассматриваем каждую из них очень медленно и тщательно, заключается в том, что когда мы начинаем рассматривать более сложные задачи, наше использование правил суммы и произведения становится более тонким. Если в очень простых ситуациях у нас нет очень четкого понимания того, что мы делаем и почему, мы полностью потеряемся, когда дойдем до более сложных примеров.

Опасно пытаться придумать простое руководство, когда следует использовать правило произведения, а когда — правило сумм, потому что такое руководство часто будет ошибочным в сложных ситуациях.Тем не менее, хороший вопрос, который следует задать себе, когда вы пытаетесь решить, какое правило использовать: «Как бы я описал это словом «и» или словом «или»?» Слово «и» обычно используется в ситуациях, когда уместно использовать правило произведения, в то время как «или» имеет тенденцию соответствовать правилу сумм.

Давайте посмотрим, как это применимо к каждому из примеров, которые мы рассмотрели в этой главе.

В примере 2.1.1 вам нужно было выбрать размер и сорт кофе. В примере 2.1.2, Кайл хотел выбрать пончик и кофе. В примере 2.1.3 Chlöe нужно было определить размер, цвет, изображение и слоган для каждой футболки. В примере 2.1.4 мы хотели узнать пол третьего и четвертого детей Питера и Мэри. Итак, в каждом из этих примеров мы использовали правило произведения.

В примере 2.2.1 вам нужно было выбрать рогалик или пончик. В примере 2.2.2 у Мэри и Питера может быть ноль, один, два или три ребенка. Итак, в каждом из этих примеров мы использовали правило сумм.

Вы определенно должны быть осторожны при применении этого руководства, так как проблемы могут быть сформулированы вводящим в заблуждение образом. Мы могли бы сказать, что в примере 2.2.1 мы хотим знать, сколько всего существует различных видов пончиков и рогаликов. Однако важно то, что вы не выбираете обе эти вещи; вы выбираете что-то одно, и это будет либо пончик, либо рогалик.

В примере 2.3.1 Грейс выбирала основное блюдо, гарнир и напиток, поэтому мы использовали правило продукта, чтобы объединить эти аспекты.Наличие дополнительных вариантов основного блюда зависело от того, выбирала ли она блины, вафли, овсянку, омлет или ничего, поэтому здесь применялось правило сумм. (Обратите внимание, что на самом деле мы не рассматривали каждую из этих четырех вещей по отдельности, поскольку они, естественно, подпадали под две категории. Однако мы пришли бы к тому же ответу, если бы рассмотрели каждую из них по отдельности.) дополнительные варианты, доступные для ее гарнира, зависели от того, выбрала она тост или нет, поэтому снова применялось правило сумм.

В примере 2.3.2 номера могут быть обычными (любым из двух способов), ветеранскими или мотоциклетными, поэтому использовалось правило сумм. В каждой из этих категорий мы должны были рассмотреть варианты для первого символа и второго символа (и так далее), поэтому применялось правило произведения.

Наконец, в примере 2.3.3 рубашка, которую выбирает Кэти, может быть как с короткими, так и с длинными рукавами, поэтому к этому различию применяется правило сумм. Поскольку она хочет выбрать рубашку и подарочную упаковку, к этой комбинации применяется правило продукта.

Упражнение \(\PageIndex{1}\)

Для каждой из следующих задач нужно использовать правило сумм, правило произведения или и то, и другое?

1. Подсчитайте все числа, имеющие ровно две цифры, и числа, имеющие ровно четыре цифры.
2. Сколько возможных исходов может быть при броске красного и желтого кубиков?
3. Сколько возможных исходов может быть при броске трех кубиков, если вы считаете только исходы, при которых не более чем один из кубиков выпадает как единица?

День 22 — Комбинаторика: искусство счета —

Давайте учиться считать! Вы, наверное, некоторое время считали, но мы хотим познакомить вас с различными математическими инструментами для тщательно думая о счете: счет предметов, счет способов делать вещи и многое другое.

Наше первое правило подсчета — это правило сумм : используйте сложение для представления самостоятельный выбор. Вот несколько примеров.

Пример 1: Побег из Клермонта

Предположим, вы пытаетесь спланировать свой маршрут в Лос-Анджелес на вечер современный танец в REDCAT.

Вы можете ехать, взяв 210/605/10, просто взяв 10 или взяв 10, а затем переключиться на 60. То есть есть три способа идти.

Но можно и на поезде! Вы можете взять CalTrain в Союз Станция, или вы можете доехать до Азузы на велосипеде и сесть на Золотую линию.Это, Есть два способа добраться на поезде.

Всего есть пять разных способов попасть в REDCAT.

Пример 2. Начало движения

Вы беспокойны и вам нужно немного потренироваться. Ты мог бы бежать, покататься на велосипеде или попробовать упражнения с собственным весом.

Если вы бегаете, вы можете бежать по обычному маршруту или бежать дольше.

Если вы ездите на велосипеде, вы можете ездить по улицам или использовать свой горный велосипед на каком-то синглтреке.

Если вы выполняете упражнения с собственным весом, вы можете выполнять упражнения для верхней части тела, кора или ноги.Или вы могли бы просто делать берпи в своей гостиной, чтобы мучить себя.

Есть два способа бегать, два способа ездить и четыре способа делать упражнения с собственным весом. В общем, у вас есть восемь возможных виды деятельности. (Не позволяйте нерешительности держать вас на диване! больше энергии, если вы немного подвигаете своим телом.)

Полное правило сумм

Принцип, который мы только что применили, называется правилом сумм :

Предположим, что есть $n$ способов что-то сделать, и есть еще $m$ способов сделать это по-другому, то есть $n + m$ способов сделать это.

Ключом к применению правила сумм является то, что параметры должны быть независимый : вы можете либо ехать, либо поездом, но вы не будете делать оба. (По крайней мере, не в нашем примере.) Вы будете делать только одну форму. упражнений.

Если вы собираетесь комбинировать вещи из разных категории, вам понадобится другое правило.

Наше второе правило подсчета — это правило произведения : используйте умножение для представлять комбинации. Вот несколько примеров.

Пример 1: О, пастообразные!

Допустим, вы открываете итальянский ресторан: «О, Pastabilities!», ориентированный на блюда из макарон: посетители выбирают форму пасты, начинка и соус.

Вы предлагаете пять форм макарон:

• спагетти («кусочки шпагата»)
• тальятелле («ассорти»)
• феттучини («маленькие ломтики»)
• фузилли («веретено»)
• пенне («ручки»).

(А там целый мир форм с восхитительные имена!)

В то время как в итальянской пасте часто нет ничего, кроме соуса, ваш ресторан для американского рынка и будет включать начинки, ориентированные на белок:

• ничего
• овощи
• фрикадельки
• морепродукты.

Наконец, вы предлагаете всего три соуса:

• aglio e olio (оливковое масло и чеснок — просто, но вкусно!)
• маринара (томатный соус с зеленью, чесноком и луком)
• альфредо (традиционно просто масло и пармаджано реджано, но часто с оттенком сливок).

Учитывая наше меню пасты, начинки и соусов, мы могли бы захотеть знать сколько разных блюд можно приготовить.

Сколько существует различных комбинаций начинки/соуса? Кому перечислите их вручную, это помогает быть методичным.Для каждого возможного начинка, подумайте, с какими соусами она может сочетаться:

• без топпинга с аглио и олио
• без топпинга с маринарой
• без топпинга с альфредо

Итак, есть три варианта. Далее считаем овощи:

• овощи с аглио и олио
• овощи с маринарой
• овощей с Альфредо

Аналогично можно составить списки для фрикаделек:

• фрикадельки с альо и олио
• фрикадельки с маринарой
• фрикадельки с Альфредо

И для морепродуктов:

• Морепродукты с альо и олио
• морепродукты с маринарой
• морепродукты с альфредо (не рекомендуется)

В сумме получается двенадцать вариантов. Вы могли заметить что есть 4 начинки и 3 соуса, а 12 долларов = 4 \cdot 3$. Это не случайно!

С нашими пятью формами макаронных изделий, сколько различных «пастостей» может быть там? Ну, есть 12 комбинаций соуса/начинки и пять макарон. фигуры, так что… $60 = 5\cdot 12$.

Пример 2. Отвезите меня в Tuple Town

Имея пару множеств $A$ и $B$, мы можем говорить о декартовых произведение этих множеств как $A \times B$. (В Coq мы написали A * B .) Используя нотацию построителя наборов (полностью мы познакомимся с ней в день 24), можно сказать, что $A \times B = \{ (x, y) \mid x \in A, y \in B \}$, т. е. множество $A \times B$ есть множество пар значений $(x,y)$, где $x$ происходит от $A$, а $y$ происходит от $B$. Мы хотим рассмотреть все возможные пары.

Итак: сколько таких кортежей? Если $n$ элементов $A$ и $m$ элементов из $B$, то $n \cdot m$ элементов из $A \раз В$. (Что, возможно, поможет вам понять выбор $\times$ и название «продукт»!)

Конкретно, сколько кортежей типа $\texttt{bool} \times \texttt{base}$ есть? Ну, есть два логических значения ( true и false ) и четыре основания ( A , C , G и T ). Итак: 8.

Полное правило продукта

Мы можем применить то, что называется правилом продукта :

Предположим, вы выполняете задачу, состоящую из двух частей. Если есть $n$ способов сделать первую часть и $m$ способов сделать вторую часть, есть $n \cdot m$ способов выполнить всю задачу.

Большая часть проблем в комбинаторике связана с решением, какие правила применять в каком порядке. Идиомы естественного языка для указания вещи—«не менее трех», «не более 1», «ровно 2»—перевести различными способами.Вот пример, где мы используем пятизначный номер телефона extensions, чтобы увидеть некоторые из этих идиом.

Каждый телефон в колледже Помоны имеет пятизначный добавочный номер база 909-60х. Например, мой полный рабочий номер телефона 909-607-4554, но мое расширение обычно записывается как x7-4554. (По состоянию на Осень 2020 года, это не принесет вам много пользы — я не был на моем офис в месяцах!)

Давайте проигнорируем x и дефис и просто сократим мое расширение на 74554. 2 = 10 \cdot 81 = 810$$

Сколько существует расширений, в которых ровно четыре шестерки их? Теперь наши перечисления стали проще.1 &+& 1 \\ &=& 59049 &+& 32805 &+& 7290 &+& 810 &+& 45 &+& 1 \\ &=& 100 000 \\ \конец{массив}\]

Все подтвердилось! Это не только хороший способ проверить наши рассуждения/перечисления, уравнение здесь является удобным способом ответить на ряд других вопросов.

Неточный подсчет

До сих пор мы насчитали ровно . Но нас часто интересуют неточные вопросы. Например, , сколько существует расширений, которые имеют хотя бы одна шестерка в них?

Вероятно, мы могли бы сделать что-то необычное с перечислениями, как показано выше, но это привередливо и подвержено ошибкам.5$ означает мы насчитываем 5 различных вещей, где каждая вещь имеет десять возможности) в дополнение к окончательному ответу ($100,000$). Оба это важно, но вы можете быть удивлены, узнав, что формула важнее, чем окончательный ответ . Формула говорит Читатель, как ты туда попал. Если вы просто их число, ну … почему они должны тебе верить?

Соответственно: пожалуйста всегда дайте формулу. Если это удобно (или мы вас просим), дайте и окончательный ответ.Но это гораздо больше важно, чтобы ваша формула была в форме, отражающей то, как ты посчитал!

В автосалоне продается пятнадцать автомобилей. Десять из них имеют солнечная крыша. Шесть из них — гибридные автомобили. Четыре и то, и другое. Сколько автомобили без люка и не гибриды?

Счет здесь сложный — даже формулировка сложная. Десять автомобилей иметь солнечную крышу; шесть — гибриды… но только у четырех есть и то, и другое. Быстрый счет может вас смутить: 10$ + 6 + 4 = 20$, но их всего пятнадцать машины? Как это возможно?

Что ж, английский язык усложняет тебе жизнь.Если есть десять автомобилей с солнечными крышами и шесть гибридов, и четыре, которые оба, что означает, что мы действительно смотрим на автомобили за 10 долларов + 6 — 4 = 12 долларов. Почему? Двойной подсчет!

1. СР
2. СР
3. СР
4. СР
5. СР
6. СР
7. СР, ГИБРИД
8. СР, ГИБРИД
9. СР, ГИБРИД
10. СР, ГИБРИД
11. ГИБРИД
12. ГИБРИД
13. ни
14. ни
15. ни

Если мы просто посчитаем солнечные крыши, то найдем десять.Если считать гибриды, мы получим шесть. Но у четырех из этих автомобилей есть и то, и другое, т. е. они были посчитал дважды ! Чтобы получить точный результат, необходимо учитывать этот дополнительный подсчет.

Итак, есть 12 автомобилей с люками на крыше и/или гибридными двигателями, поэтому это означает, что 3 должны жить в темные века, буквально и образно.

В более общем смысле правило включения/исключения (иногда называемое правило вычитания):

Предположим, вы одновременно выполняете две задачи.Если есть $n$ способов выполнить первую задачу и $m$ способов выполнить вторую вторую задачу и $k$ способов выполнить обе, то существует $n + m — k$ способов выполнить всю задачу.

Предположим, у вас есть книги для чтения:

• Волшебник Земноморья (AWE)
• Над морем, под камнем (OSUS)
• Ведьма Аката (AW)
• Шикаста (S)

В скольких различных порядках вы могли бы прочитать эти книги? Ну ты есть четыре варианта для первой книги, затем три для второй, затем два, затем определяется последний.Итак: $4 \cdot 3 \cdot 2 \cdot 1 = 24$.

Что, если бы вы также собирались прочитать пятую книгу, Одиннадцатая станция ? Тогда будет $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5 \cdot 24 = 120$ возможные заказы.

Мы только что подсчитали количество перестановок пяти элементов. Наш формула — это просто прямое применение правила произведения с некоторыми рассуждения о том, «что осталось сделать».

Общее правило определяется следующей функцией:

\[ \mathit{factorial}(n) = \begin{cases} 1 & n \le 1 \\ n \cdot \mathit{factorial}(n’) & n = S(n’) \\ \end{ случаи} \]

Обычно используется обозначение $n!$, где:

\[ п! = \mathit{factorial}(n) = \prod_{i=1}^n i = n \cdot (n-1) \cdot \dots \cdot 2 \cdot 1 \]

Мы произносим $n!$ как «$n$ факториал». n f(i)$, обозначающее произведение $f(b) \cdot f(b+1) \cdot \dots f(n-1) \cdot f(n)$. Символ – столица Греции. буква пи.)

Полное правило перестановки

Теперь мы можем дать правило перестановки в его абстрактной форме:

Если вы собираетесь делать $n$ разных вещей в произвольном порядке, существует $n!$ возможных порядков.

Вы планируете факультативные занятия по подводному плаванию плетение корзин, и у вас есть несколько вариантов:

• Ткачество в морской воде (SW)
• Рид Жесткость (RR)
• Расширенное вымачивание (AR)
• Сравнительный анализ переплетения (CWA)
• Смешанные ткани (MMW)

Сейчас, в связи с перебором в Департаменте подводного Плетение корзин, вы можете сдавать только одно в семестр из трех ваших оставшиеся семестры. Сколькими способами можно выбрать три из эти факультативы? Вы можете взять каждый только один раз, и вы берете только один в семестр.

Ну, мы можем использовать правило продукта, как указано выше: $5 \cdot 4 \cdot 3 = 60$. У вас есть пять вариантов на первый семестр, четыре на следующий, и только три последних.

Через мгновение у нас будет другой способ подсчета.

Иногда то, что вы делаете, имеет некоторое понятие «симметрии», которое вам хотелось бы игнорировать — например, порядок может не иметь значения.

Пример 1. Заключите сделку, повернитесь лицом к рулю

Предположим, вы собираетесь сделать прялку, чтобы раздавать призы от дверей. на хакатоне 5С. Дверь варианты приза:

• Футболка (T)
• Книга (Б)
• Ремешок (L)
• Подарочная карта (G)

Идея в том, что приходящие люди будут крутить колесо и брать что угодно стрелка указывает на. Сколько существует различных колесных формул?

Вы могли бы сказать, что есть четыре элемента, поэтому мы должны просто использовать правило перестановки — есть 24 колеса.Но это было бы не совсем правильно. .. вы бы пересчитали в 4 раза! Почему?

Вот одно колесо:

\[ \begin{массив}{ccc} &Т&\\ Б&\bigcirc&L\\ & Г & \\ \конец{массив} \]

Вот еще одно колесо:

\[ \begin{массив}{ccc} & Б & \\ G&\bigcirc&T\\ & л & \\ \конец{массив} \]

Ха. Это те же колеса ! Второй просто повернут на 90° по часовой стрелке. Для любого заданного расположения колеса существует четыре возможные повороты.Чтобы избежать 4-кратного пересчета, мы должны разделить число перестановок на четыре для учета симметричных случаев.

Итак: возможных колес действительно всего 6. Вот они с каждым их оборотов:

• ТЛГБ / ЛГБТ / ГБТЛ / БТЛГ
• ТЛБГ / ЛБГТ / БГТЛ / ГТЛБ
• ТБГЛ/БГЛТ/ГЛТБ/ЛТБГ
• ТБЛГ/БЛГТ/ЛГТБ/ГТБЛ
• ТГЛБ/ГЛБТ/ЛБТГ/БТГЛ
• ТГБЛ/ГБЛТ/БЛТГ/ЛТГБ

Мы записали их с фиксированной буквой «Т» в качестве первого элемента.Делает поэтому выделяет еще один способ подсчета возможных колес: рассмотрим одно фиксированный элемент, а затем расположите остальные. Итак, если их четыре элементы, исправьте букву «Т», а затем найдите 3 доллара! = 3 \cdot 2 \cdot 1 = 6$ возможные договоренности.

Пример 2: В сумке

Предположим, мы хотим выбрать два числа из списка [1; 2; 3; 4] . Это частичная перестановка, поэтому мы можем просто остановиться раньше. Там $4 \cdot 3 = 12$ возможностей

• [1;2]

• [1;3]

• [1;4]

• [2;1]

• [2;3]

• [2;4]

• [3;1]

• [3;2]

• [3;4]

• [4;1]

• [4;2]

• [4;3]

Однако, если мы не заботимся о порядке, то их действительно меньше: в чем разница между [1;2] и [2;1] ? За каждый «путь» выбирая два числа [n] и [m], есть два эквивалентных способа: [н;м] и [м;н] .Итак, если бы мы выбрали два таких числа, не заботясь о заказе , тогда возможно $\frac{12}{2} = 6$ заказов:

• [1;2]

• [1;3]

• [1;4]

• [2;3]

• [2;4]

• [3;4]

Как мы можем сказать, что мы не удалили ненадлежащим образом параметр или случайно пересчитал? Мы можем использовать порядок наших перечислений чтобы убедиться, что мы покрываем все наши базы — если каждый набор опций отсортированы, мы можем быть уверены, что появятся только нужные вещи.Это, мы используем отсортированные списки как каноническую форму .

Полное правило деления

Мы можем дать правило деления во всей его общности:

Если есть $n$ способов сделать что-то и для каждого способа сделать это существует $m$ эквивалентных способов, то существует $\frac{n}{m}$ способов сделай это.

Общие применения правила деления для игнорирования порядка (как мы делал выше) или другие «симметрии».

Зная, когда применять правило деления, и применяя его правильно, можно быть сложным.Трудно точно знать, на что делить! Это как правило, разумно иметь другой способ проверить свою работу, например перечисление вариантов в некоторой канонической форме.

Частичные перестановки

Мы сделали частичные перестановки, «остановившись раньше», но вы можете дать другую учетную запись, используя правило деления.

Выбрать три из пяти факультативы, мы можем подсчитайте, написав $5 \cdot 4 \cdot 3$. Но мы также можем думать о задачу по-другому: устроить все пять курсов, но потом отбросить последний два (которые вы не возьмете).То есть мы бы рассмотрели SW-CWA-RR-AR-MMW такие же, как SW-CWA-RR-MMW-AR такие же, потому что они отличаются только последние два курса… которые в любом случае не посещаются. То есть мы смог вычислить:

\[ \фракция{5!}{(5-3)!} = \фракция{5!}{2!} = \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1} = 5 \cdot 4 \cdot 3 = 60 \]

Это описание частичных перестановок достаточно распространено, чтобы имя, функция $P : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$, где $P(n, k)$ — $k$-перестановка из $n$ элементов, т.е.е., выбор $k$ вещей из $n$ вещей:

\[ P(n,k) = \frac{n!}{(n-k)!} \]

Менее формально $P(n,k) = n \cdot (n-1) \cdot \dots \cdot (n — k + 2) \cdot (n — k + 1)$. Люди иногда произносят $P(n, k)$ как «$n$ переставить $k$». По соглашению $P(n, k) = 0$, когда $k > n$; соответственно, $P(n, n) = \frac{n!}{(n-n)!} = \frac{n!}{1!} = n!$.

Чтобы выбрать два элемента из четырех, мы можно просто вычислить $P(4,2) = \frac{4!}{(4-2)!} = \frac{4!}{2!} = \frac{24}{2} = 12$.Уф: мы получили тот же ответ.

Подожди, ОТДЕЛЕНИЕ?!

Я знаю, я знаю: у нас не будет формального определения для разделение. Это не должно всплывать ни в одной работе, которую мы делаем, но если вам нужно использовать факт о делении в доказательстве, это должно быть хорошо—просто спроси сначала.

Предположим, вы просто хотите выбрать три из пяти подводных факультативы по плетению корзин, независимо от порядка. Сколько способов выбрать три из пяти факультативов есть, без оглядки на приказ?

Мы должны использовать как правила произведения, так и правила деления.Есть $P(5,3) = 5 \cdot 4 \cdot 3$ способов выбрать три курса. Есть 3 доллара! знак равно 3 \cdot 2 \cdot 1$ ​​способов заказать эти курсы, но нам все равно о порядке. Итак, мы имеем $\frac{P(5,3)}{3!} = \frac{5 \cdot 4 \cdot 3}{3 \cdot 2 \cdot 1} = \frac{60}{6} = 10$ способов выбрать множество три факультатива.

Рассуждения, которые мы только что привели, достаточно распространены, чтобы иметь свою собственную определение, называемое «выбор» или «выбор». Есть много обозначений в общего пользования: $\newcommand{\C}[2]{\left(\begin{array}{@{}c@{}} {#1} \\ {#2} \\ \end{массив} \right)}$ \[ n C k \equiv C(n, k) \equiv \C{n}{k} = \frac{P(n,k)}{k!} = \frac{n!}{(n-k)! \cdot k!} \]

Люди произносят это обозначение «$n$ выбирают $k$», и это то, как вы вычислить, выбрав наборов из $k$ вещей из $n$ вещей, т.е.д., выбирая $k$ вещей из $n$, не заботясь о порядке.

Несколько соглашений: мы используем только натуральные числа для $n$ и $k$. Если $k n$, мы говорим $\C{n}{k} = 0$: невозможно выбрать 5 вещей из 3 вещи.

Мне не нравится первое обозначение (хотя оно и совпадает с произношением Что ж). Вторая запись хороша, когда вы пишете программу, но третья запись лучше подходит для математики на бумаге. Я использую оба. На самом деле я дать вам макрос в домашнем задании на 22 день, который упрощает использование последнее обозначение:

  \newcommand{\C}[2]{\ensuremath{\left(\begin{array}{@{}c@{}} {#1} \\ {#2} \end{массив} \right)} }

\[ \C{n}{k} = \frac{n!}{(n-k)! \cdot k!} \]
  

Большую часть 23-го дня мы посвятим разговорам о выборе.

Copyright © 2020 Майкл Гринберг

Дискретная математика

В этом разделе используются три основных правила счета, по одному для каждой из арифметических операций умножения, сложения и вычитания.

8.1. Правило продукта (

Чтобы найти общее количество исходов для двух или более последовательных событий, в которых должны произойти оба события, умножьте количество исходов для каждого события вместе.Например, если вы хотите найти количество возможных исходов, когда вы бросаете кубик и подбрасываете монету, вы можете использовать правило произведения. Важно отметить, что события должны быть независимыми, то есть одно не влияет на другое.

Это называется правилом произведения для подсчета, потому что оно включает умножение, чтобы найти произведение. Правило произведения может быть расширено до более чем двух вариантов.

8.2. Правило суммы (

Подумайте о том, чтобы найти общее количество способов, которыми конкретное событие происходит, из множества различных вариантов. Например, если вы хотите найти количество способов выбрать специальность ITEC, чтобы выиграть приз, зная, что есть студенты из разных концентраций, вы можете использовать правило сумм. Важно отметить, что события должны быть взаимоисключающими, то есть не иметь ничего общего.

Это называется правилом суммы для подсчета, потому что оно включает в себя сложение, чтобы найти итог. Правило сумм также может быть расширено до более чем двух вариантов.

8.3. Правило вычитания (

Если ваши события не являются взаимоисключающими, чтобы найти общее количество возможностей, используйте правило вычитания.

Правило вычитания также называют принципом включения-исключения.

8.4. Принцип сортировки

Удивительное количество проблем со счетом может быть решено с помощью так называемого принципа ячейки.

Десять голубей в девяти ячейках

8.5. Перестановки и комбинации

Рассмотрим первые четыре буквы алфавита \(A, B, C, D\). А перестановка из этих букв будет расположение их в разном порядке.

• \(ABCD, BACD, ABDC\) — это перестановки букв, взятых по четыре за раз.

• \(BDA, ABC, ABD\) — это перестановки букв, взятых по три за раз.

• \(AB, AC, DB\) — это перестановки букв, взятых по две за раз

В общем, для набора \(n\) объектов упорядоченное расположение из \(r \le n\) из них называется \(r\)-перестановка или перестановка \(n\) объектов, взятых \(r\) одновременно .Мы будем обозначать это через \(P(n,r)\). (Обратите внимание, что \(_nP_r\) — обычно используемая запись, особенно в калькуляторах.)

Теперь рассмотрите буквы \(A, B, C, D\) и выберите по три за раз, где порядок не имеет значения. То есть выбор \(ABC\) совпадает с выбором \(BCA\). Этот выбор, в котором порядок не имеет значения, называется комбинация .Есть только четыре возможных способа выбрать три буквы без учета порядка:

*\(ABC, ABD, ACD,\) и \(BCD\).

В общем, для набора \(n\) объектов и неупорядоченный выбор из \(r\le n\) из них является \(r\)-сочетание или комбинация \(n\) объектов, взятых \(r\) одновременно .Мы будем обозначать это через \(C(n,r)\), читая как «\(n\) выбирают \(r\)». (Обратите внимание, что \(_nC_r\) обычно используется калькуляторами.)

8.6. Упражнения

В колледже 67 специальностей по математике и 124 специальности ITEC.

1. Сколькими способами можно выбрать двух представителей, чтобы один был специалистом по математике, а другой — ITEC?

2. Сколькими способами можно выбрать одного представителя, специализирующегося либо на математике, либо на ITEC?

   1. Тест с несколькими вариантами ответов содержит 20 вопросов, и каждый вопрос имеет четыре варианта ответа.

3. Сколькими способами студент может ответить на все вопросы теста?

4. Сколькими способами учащийся может ответить на все вопросы, если ему разрешено пропустить некоторые из них?

   1. Сколько разных трехбуквенных инициалов может быть у человека?

   2. Сколько различных трехбуквенных инициалов оканчивается на «Р»?

   3. Сколько существует битовых строк длины пять?

   4. Сколько существует битовых строк длины пять, начинающихся и заканчивающихся на 1?

   5. Сколько существует битовых строк длины меньше \(n\), где \(n\) — натуральное число, начинающихся и заканчивающихся на 1?

   6. Сколько номерных знаков можно составить, используя три цифры, за которыми следуют четыре заглавные английские буквы, если:

5. Цифры и буквы могут повторяться?

6. Цифры и буквы не могут повторяться?

   1. Если каждый студент, изучающий дискретную математику, имеет специализацию по математике, специализацию ITEC или двойную специализацию, а в классе 5 математических специальностей (включая двойную специализацию), 23 ITEC специальностей (включая двойные специальности) и 7 двойных специальностей, сколько студентов в классе?

   2. Предположим, компьютерная система требует пароль длиной не менее 7 и не более 10 символов, и каждый символ должен быть строчной английской буквой. буква, заглавная английская буква, цифра или один из шести специальных символов (*, >, <, !, +, =).{-9}\) секунд). Сколько времени потребуется хакеру проверять каждый потенциальный пароль?

      1. Докажите, что если в классе 29 учеников, по крайней мере у двоих фамилии начинаются на одну и ту же букву.

      2. Сколько учеников должно быть в классе, чтобы по крайней мере два ученика получили одинаковую оценку на экзамене, оцениваемом по шкале от 0 до 100 баллов?

      3. Докажите, что в любом наборе из 5 целых чисел есть по крайней мере два, которые дают одинаковый остаток при делении на 4.

      4. В мешке 8 красных и 7 синих шаров.

   3. Сколько шаров нужно выбрать, чтобы быть уверенным, что вы выберете 3 одного цвета?

   4. Сколько нужно выбрать, чтобы быть уверенным, что вы выберете 3 красных шара?

      1. Кто-то убирает на чердаке и находит коробку с 12 компакт-дисками в стиле рок и 12 компакт-дисками в стиле кантри.Какое минимальное количество компакт-дисков они могут взять, чтобы гарантировать не менее по одному каждого вида?

      2. Приведите аргумент, что в Атланте есть по крайней мере два человека с одинаковым количеством волос на голове.

      3. В колледже 67 специальностей по математике и 124 специальности ITEC.

   5. Сколькими способами можно выбрать двух представителей, чтобы один был специалистом по математике, а другой — ITEC?

   6. Сколькими способами можно выбрать одного представителя, специализирующегося либо на математике, либо на ITEC?

      1. Тест с несколькими вариантами ответов содержит 20 вопросов, и каждый вопрос имеет четыре варианта ответа.

   7. Сколькими способами студент может ответить на все вопросы теста?

   8. Сколькими способами учащийся может ответить на все вопросы, если ему разрешено пропустить некоторые из них?

      1. Сколько разных трехбуквенных инициалов может быть у человека?

      2. Сколько различных трехбуквенных инициалов оканчивается на «Р»?

      3. Сколько существует битовых строк длины пять?

      4. Сколько существует битовых строк длины семь, начинающихся и заканчивающихся на 0?

      5. Сколько существует битовых строк длины меньше \(n\), где \(n\) — натуральное число, начинающихся и заканчивающихся на 1?

      6. Сколько номерных знаков можно составить, используя четыре цифры, за которыми следуют три заглавные английские буквы, если:

   9. Цифры и буквы могут повторяться?

   10. Цифры и буквы не могут повторяться?

       1. Если каждый студент, изучающий дискретную математику, изучает математику, ITEC или двойную специальность, а в классе 18 математических специальностей (включая двойные специальности), 25 ITEC специальностей (включая двойные специальности) и 8 двойных специальностей, сколько студентов в классе?

       2. Предположим, компьютерная система требует пароль длиной не менее 8 и не более 11 символов, и каждый символ должен быть строчной английской буквой буква, заглавная английская буква, цифра или один из шести специальных символов (*, >, <, !, +, =).{-9}\) секунд). Сколько времени потребуется хакеру проверять каждый потенциальный пароль?

          1. Докажите, что если в классе 29 учеников, по крайней мере у двоих фамилии начинаются на одну и ту же букву.

          2. Сколько учеников должно быть в классе, чтобы было хотя бы два ученика получить одинаковую оценку за экзамен, оцениваемый по шкале от 0 до 50 баллов?

          3. Докажите, что в любом наборе из 8 целых чисел найдутся хотя бы два с одинаковыми остаток при делении на 7.

          4. В мешке 12 красных и 7 синих шаров.

       3. Сколько шаров нужно выбрать, чтобы быть уверенным, что вы выберете 4 одного цвета?

       4. Сколько нужно выбрать, чтобы быть уверенным, что вы выберете 4 красных шара?

          1. Кто-то убирает на чердаке и находит коробку с 12 компакт-дисками в стиле рок, 12 компакт-дисками в стиле хип-хоп и 12 компакт-дисками в стиле кантри.Какое минимальное количество компакт-дисков они могут взять, чтобы гарантировать не менее по одному каждого вида?

          2. Приведите аргумент, что в Атланте есть по крайней мере два человека с одинаковым количеством волос на голове.

          3. Перечислите все перестановки \(\{1, 2, 3\}\).

          4. Сколько существует перестановок множества \(\{1, a, 2, b, 3, c, 5\}\)?

          5. Пусть \(A=\{a, b, c, d\}\)

       5. Перечислите все 3-перестановки \(A\).

       6. Перечислите все 3-комбинации \(A\).

          1. Пусть \(A=\{a, b, c, d, e\}\)

       7. Перечислите все 2-перестановки \(A\).

       8. Перечислите все 2-комбинации \(A\).

          1. Найдите значение следующего

       9. \(Р(5,2)\)

       10. \(Р(10,8)\)

       11. \(Р(14,10)\)

       12. \(Р(12,8)\)

       13. \(С(5,2)\)

       14. \(С(10,8)\)

       15. \(С(14,10)\)

       16. \(С(12,8)\)

           1. Сколько битовых строк длины 10 содержат:

       17. Ровно пять единиц?

       18. Максимум пять единиц?

       19. Хотя бы четыре единицы?

       20. Одинаковое количество нулей и единиц?

           1. Сколько перестановок цифр \(12345678\) содержит:

       21. Строка 284?

       22. Строка 3581?

       23. Строка 21 и 57?

           1. Сколькими способами можно выбрать 9 карт из стандартной колоды из 52 карт?

           2. Сколькими способами можно получить пару в 5-карточной руке (2 карты одного достоинства и 3 карты разного достоинства)?

           3. Сколькими способами вы можете получить фулл-хаус в 5-карточной руке (2 карты одного достоинства и 3 карты одного достоинства)?

           4. Сколько номерных знаков состоят из 4 букв, за которыми следуют 3 цифры, если:

       24. Повторение разрешено?

       25. Повтор не допускается?

           1. Используя \(C(n,r) = \displaystyle \frac{n!}{r!(n-r)!}\), оцените члены этой треугольной таблицы.Вам понадобится формула, чтобы расширить таблицу до большего количества строк?

       \begin{массив}{ccccccccccccc} &&&&&&&C(0,0)&&&&&&\\ &&&&&& С(1,0) && С(1,1) &&&&&\\ &&&&& С(2,0) && С(2,1) && С(2,2) &&&&\\ &&&& С(3,0) && С(3,1) && С(3,2) && С(3,3) &&&\\ &&& С(4,0) && С(4,1) && С(4,2) && С(4,3) && С(4,4) &&\\ \конец{массив}

       01:640:454 Комбинаторика Осень 2011

       Неделя	Даты лекций	Секции	темы
       1	1 сентября (Чт)	1, 2.1-2.3	Введение, правила произведения и суммы, перестановки
       2	9/6 (только вторник)	2,5 –2,7	r — перестановки и r — комбинации; Подмножества
       3	9/13, 15 (TTh)	2,8–2,11, 2,13, 2,14	Вероятность, различимая и неразличимая выборка
       4	9/20, 22 (ТТх)	2.16–2.19	Алгоритмы и комбинации; Принципы сортировки
       5	9/27, 29 (TTh)	3.1, 3.2, 3.3	Графы, связность, BFS, раскраски, планарные графы
       6	10/4, 6 (TTh)	3,4, 3,5	Хроматические многочлены, Деревья и циклы
       7	11/10, 13 (TTh)	Главы 2–3	Обзор, Промежуточный экзамен
       8	10/18, 21 (ТТх)	5.1–5,4	Генерация функций и подсчет
       9	10/25, 27 (TTh)	5,5–5,7, 2,15	Производящие функции, перестановки, индексы мощности
       10	11/1, 11/3 (TTh)	6,1–6,3	Рекуррентные отношения
       11	11/8, 10 (TTh)	9.1, 9.2, 9.3	Латинские квадраты, Блочные конструкции, ортогональные блочные конструкции
       12	11/15, 17 (ТТх)	9. Добавить комментарий Отменить ответ Ваш адрес email не будет опубликован. Обязательные поля помечены * Комментарий * Имя * Email * Сайт