Среди различных задач, которые приходится решать математикам, встречаются такие, где нужно ответить на вопрос: каким числом различных способов можно осуществить требуемое? Такие задачи принято называть комбинаторными задачами. Для решения таких задач созданы общие методы и выведены готовые формулы. Однако для того чтобы лучше ознакомиться с методами их решения, мы начнем не с общих методов и готовых формул, а с рассмотрения конкретных примеров.
Пример 1. Каким числом способов можно обить 12 различных стульев, если есть 12 образцов обивочного материала, причем каждый материал имеется в любом количестве?
Решение. Поскольку имеется 12 различных образцов обивочного материала, то один стул можно обить двенадцатью различными способами. То же самое справедливо и для второго стула, так как каждый обивочный материал имеется в любом количестве. Но каждый способ обивки первого стула можно соединить с любым способом обивки второго, так что число различных способов обивки двух стульев равно 
.
При этом важно, что имеющиеся стулья различны. Если бы они были одинаковыми, то число различных способов обивки было бы меньшим, так как способы, при которых первый стул обит матералом 
, а второй — материалом b, или, наоборот, первый стул обит материалом b, а второй — материалом а, нельзя было бы считать различными способами.
Итак, для двух различных стульев мы получили 
различных способов их обивки. Очевидно, что для каждого следующего стула остается в силе приведенное выше рассуждение: для каждого стула существует двенадцать возможных способов обивки, и каждый способ обивки данного стула можно соединить с любым
способом обивки предыдущих. Отсюда следует, что для трех стульев число различных способов обивки составляет 123, для четырех 
и т. д. Для двенадцати стульев это число составляет 
.
Пример 2. Каким числом способов можно рассадить 12 гостей на имеющихся 12 различных стульях?
Решение. Представим себе, что гости входят в комнату по одному. Первому из входящих гостей предоставляется выбор из 12 различных стульев, т. е. 12 возможностей, как и в предыдущем примере. Однако уже для следующего гостя остаются не те же двенадцать возможностей, что и для первого, а всего лишь одиннадцать, поскольку один из стульев оказывается уже занятым. По-прежнему каждое место, занятое первым гостем, может комбинироваться с любым другим местом, занятым вторым; поэтому общее число различных способов, с помощью которых можно рассадить двух гостей, равно 
Дальнейший ход решения теперь уже ясен. Для гостя, входящего третьим, останется только 10 различных возможностей, так как из 12 мест два места окажутся уже занятыми. Поэтому для трех гостей число различных способов рассадить их составляет 
Продолжая аналогичные рассуждения, найдем, что общее число различных способов рассадить 12 гостей на 12 стульях составляет 
Пример 3. В отделении 12 солдат. Каким числом способов можно составить наряд из двух человек, если один из них должен быть назначен старшим?
Решение этой задачи очень похоже на решение предыдущей. Действительно, если назначить сначала старшего по наряду, то для его выбора у нас имеется 12 различных возможностей: каждый солдат отделения может быть назначен старшим наряда. После того как старший наряда назначен, вторым в наряд может быть назначен любой из оставшихся одиннадцати. Как и во всех предыдущих случаях, общее число различных нарядов составляет 
Пример 4. Какое число различных парных нарядов можно назначить из 12 солдат отделения, если не требуется назначать старшего по наряду?
Решение. Легко понять, что число таких нарядов должно быть меньше, чем в предыдущем примере. Действительно, наряды — Иванов (старший) и Петров или Петров (старший) и Иванов — различны, тогда как, если не требуется назначать старшего, эти два солдата в обоих случаях составляют один и тот же наряд. Каждый парный наряд без старшего можно превратить в два различных наряда
ряда со старшим. Поэтому число различных парных нарядов со старшим в два раза больше, чем нарядов без старших. Отсюда следует, что интересующее нас в данном примере число различных парных нарядов из 12 солдат отделения в два раза меньше, чем получено в предыдущем примере, т. е. равно 
Пример 5. Клавиатура пианино состоит из 88 клавиш. Сколько различных музыкальных фраз можно составить из 6 нот, допуская повторения одних и тех же нот в одной фразе?
Решение. Как и в примере 1, в качестве первой ноты для музыкальной фразы можно взять любую из 88 нот, т. е. для первой ноты мы имеем 88 возможностей. Так как повторения допускаются, то для второй ноты мы снова имеем те же 88 возможностей, и поэтому музыкальных фраз из двух нот существует 
. Продолжая рассуждения, как в примере 1, найдем, что число различных музыкальных фраз из 6 нот составляет 
Пример 6. Сколько различных музыкальных фраз можно составить из 6 нот, если не допускать в одной фразе повторений уже встречавшихся звуков?
Решение этой задачи так же отличается от решения предыдущей, как решение задачи примера 2 от примера 1. Действительно, при составлении произвольной музыкальной фразы для первой ноты мы имеем по-прежнему 88 возможностей. Для второй ноты число возможностей уменьшится уже до 87, так как нота, использованная первой, не должна больше употребляться. После того как выбрана вторая нота, для третьей остается уже только 86 возможностей. Теперь ясно, что общее число различных музыкальных фраз из 6 нот без повторений равно произведению 
.
Пример 7. Сколько существует различных аккордов из шести нот?
Решение. Аккорд отличается от музыкальной фразы тем, что все ноты, в него входящие, звучат одновременно. Отсюда следует, что все ноты аккорда должны быть различными. Кроме того, различные музыкальные фразы могут приводить к одному и тому же аккорду, если они состоят из одних и тех же нот, но расположенных в фразе в различном порядке. Поэтому, подобно примеру 4, так как число различных музыкальных фраз уже известно, нам остается определить, сколько различных музыкальных фраз могут «склеиваться» в один и тот же аккорд, или, наоборот, сколько различных фраз получается из одного и того же аккорда.
Мы приходим, таким образом, к задаче, аналогичной рассмотренной в примере 6: имеется аккорд из шести различных нот,
сколько различных музыкальных фраз можно из него составить? В качестве первой ноты для составляемой музыкальной фразы можно взять любую из входящих в аккорд нот, то есть мы имеем для нее шесть различных возможностей. Для второй ноты остается уже только пять возможностей, для третьей — четыре и т. д.
Теперь уже ясно, что число различных музыкальных фраз, которые можно получить из одного аккорда из шести нот, равно 
Это означает, что 6! различных музыкальных фраз склеиваются в один и тот же аккорд, так что число возможных аккордов будет в 61 раз меньше, чем число различных музыкальных фраз. Итак, мы получаем, что число различных возможных аккордов из 6 нот равно:
Пример 8. Из города А в город В ведет 
дорог, а в город 
дорог. В город 
из города В ведет 
дорог, а из города 
дорог. Города В и С дорогами не соединяются. Сколько различных автобусных маршрутов можно провести между городами А и 
Решение. Число автобусных маршрутов определяется числом различных дорог между городами. Всего из города А выходит 
дорог, а в город 
входит 
дорог. Мы не можем, однако, сказать, что общее число дорог равно произведению этих чисел, так как здесь невозможно комбинировать любую дорогу, выходящую из А, с любой дорогой, входящей в 
Если же рассматривать отдельно дороги, проходящие через В или через С, то такая комбинация возможна.
Рассмотрим всевозможные маршруты, идущие из А в D через В. Из А в В ведет 
дорог, а из В в 
дорог. Каждую из таких дорог, выходящих из А, можно комбинировать с любой дорогой, входящей в 
поэтому общее число различных маршрутов, как и во всех предыдущих задачах, получается перемножением числа возможностей и равно 
Следовательно, число различных маршрутов, идущих из А в 
через В, равно 
Аналогично подсчитывается число различных маршрутов, идущих из А в D через С; оно равно 
Далее, мы замечаем, что всякий автобусный маршрут, соединяющий города А и 
должен проходить или через В, или через С, и, значит, он должен входить либо в число 
маршрутов, идущих через В, либо в число 
маршрутов, идущих через С. Общее число различных маршрутов равна тогда сумме 
При решении конкретной комбинаторной задачи надо сначала выяснить, не решается ли она непосредственно применением правил суммы и произведения. Если такое решение окажется затруднительным, то следует составить математическую схему решаемой задачи, выяснив, идет ли в ней речь о составлении кортежей или подмножеств.
Приведем примеры решения комбинаторных задач.
З а д а ч а 1. Из города А в город В ведут 6 дорог, из города В в город С – 4 дороги и из города С в город D – 8 дорог. Сколько можно выбрать маршрутов, ведущих из города А в город D через города В и С?
Решение. Каждый путь искомого вида задается тройкой (а, b, с), где а – один из путей, соединяющих А и В, b – один из путей, соединяющих В и С, с – один из путей, соединяющих С и D. Так как по условию а можно выбрать шестью способами, b – четырьмя способами, с – восемью способами, то тройку (а, b, с) можно по правилу произведения выбрать 6 · 4 · 8 = 192 способами. Итак, можно выбрать 192 маршрута.
З а д а ч а 2. В отделении 12 солдат. Сколькими способами можно составить наряд из трех человек?
Решение. Так как порядок солдат не играет роли, то надо выбрать из множества, содержащего 12 элементов, подмножества, содержащие по 3 элемента. Число таких подмножеств равно 
.
. Составить наряд можно 220 способами.
З а д а ч а 3. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти различных цветов?
Решение. Обозначим пять имеющихся цветов буквами а, b, с, d, e. Тогда любой флаг «зашифровывается» кортежем из трех различных букв. Поэтому число флагов равно числу размещений без повторений из 5 по 3, т.е. 
= 5 · 4 · 3 = 60.
З а д а ч а 4. Чему равно число подмножеств m элементного множества А?
Решение. Обозначим 
, тогда каждое подмножество «зашифровывается» кортежем, состоящем из 0 и 1, по следующему правилу. Если элемент аi принадлежит подмножеству М, на i-ое место в кортеже пишем 1, если не принадлежит М, то на i-ое место пишем 0, в результате получим кортежи длиной m, состоящее из 1 и 0. Например, пустому множеству будет соответствовать кортеж, состоящий из одних нулей: (0, 0, …, 0). Множеству А соответствует кортеж, состоящий из одних единиц (1, 1, …, 1). Подмножеству М = <а3, а5> – кортеж (0, 0, 1, 0, 1, 0, …, 0). Итак, каждому подмножеству поставлен в соответствие единственный кортеж из 0 и 1, обратно, каждый такой кортеж определяет единственное подмножество множества А. Поэтому задача отыскания числа всех подмножеств множества А сводится к отысканию числа кортежей длиной m, составленных из 0 и 1, но каждый такой кортеж является размещением с повторениями из 2 по m. Следовательно, число всех таких кортежей равно 
, значит, число всех подмножеств множества А, состоящего из m элементов, равно 2 m .
Замечание. Число всех подмножеств А можно найти как сумму: 
. Поэтому
. Это еще одно из свойств числа сочетаний.
§ 5. Перестановки и сочетания с повторениями
Решим следующую з а д а ч у:
Найти число перестановок с повторениями из букв а, а, а, b, b, с, с.
Решение. Сначала перенумеруем все буквы так: а1, а2, а.3, b1, b2, с1, с2. Считая теперь все буквы различными, из них можно составить 7! перестановок. Заметим при этом, что 7 = 3 + 2 + 2.
Теперь уберем номера при буквах и тогда получим перестановки с повторениями из букв а, а, а, b, b, с, с. При этом одна и та же перестановка с повторениями получается несколько раз. Например, перестановка с повторениями (а, а, а, b, b, с, с) получается из всех перестановок букв (а1, а2, а3, b1, b2, с1, с2),в которых на первых трех местах стоят буквы а1, а2, а3 (в любом порядке), на четвертом и пятом – буквы b1, b2(влюбом порядке), а шестое и седьмое место занимают буквы с1и с2 (в любом порядке). Но буквы а1, а2, а3 можно переставлять 3!способами, буквы b1, b2 – 2!способами, буквы с1, с2 – 2!способами. Поскольку эти способы можно произвольно комбинировать друг с другом, то получаем, что перестановка (а, а, а, b, b, с, с)получается из 3! · 2! · 2! перестановок букв а1, а2, а3, b1, b2, с1, с2. Столькими же способами можно получить любую другую перестановку с повторениями из букв а, а, а, b, b, с, с. Значит, число различных перестановок с повторениями в 3! · 2! · 2! раз меньше общего числа перестановок семи букв а1, а2, а3, b1, b2, с1, с2, т.е. равно 
.
Рассуждая аналогично, как в приведенной выше задаче, можно найти число перестановок с повторениями, имеющих состав (п1, п2, п3, . пт). Их число обозначается Р(п1, п2, . пт) и выражается формулой:
.
Из этой формулы вытекает, что, если задано множество, состоящее из (т – k)букв а и k букв b, то число перестановок с повторениями будет равно: 
, но это число равно 
(см. формулу в § 2 этой главы).
Значит, получим: 
.
П р и м е р. Сколькими способами можно переставить буквы в слове «кишмиш»?
Решение. Слово «кишмиш» состоит из 6 букв и их можно переставить 6! =720 способами. Однако, заметим, что в этом слове дважды повторяются буквы «и» и «ш», а потому при перестановке, например, 2-й и 5-й букв, слово не меняется. Сосчитаем сначала число перестановок букв, не меняющих слово. Итак, можно оставить все буквы на месте; можно поменять местами буквы «и», можно поменять местами буквы «ш», можно поменять местами и две буквы «и» и две буквы «ш». Значит, число таких способов всего 4. Число различных перестановок букв слова «кишмиш» в 4 раза меньше, чем 720, т.е. равно 720 : 4 = 180.Или по формуле Р(1, 2, 2, 1)= 
.
Выше мы нашли число кортежей данного состава. Найдем теперь число различных составов, которые могут иметь кортежи длины п, состоящие из элементов множества X, содержащего т элементов. Каждый такой состав является кортежем, состоящим из т чисел п1, п2, . пт, таких, что п1 + п2 + . + пт = п. Его можно записать в виде кортежа из нулей и единиц, заменив каждое число соответствующим числом единиц и поставив 0после каждой группы единиц, кроме последней. Например, вместо кортежа (4, 2, 1) можно записать (1, 1, 1, 1, 0, 1, 1, 0, 1), а вместо кортежа (2, 0, 0, 3) – кортеж (1, 1, 0, 0, 0, 1, 1, 1). Число единиц, входящих в полученные кортежи, равно п1 + п2 + . + пт = п, а число нулей равно равно т – 1. Поэтому число различных кортежей такого вида равно числу перестановок с повторениями из п единиц и т – 1нулей, т.е. Р(п, т – 1).По формуле, выведенной выше, получим Р(п, т – 1) = 
.
Итак, мы доказали, что число составов кортежей длины п, компоненты которых принадлежат данному т элементному множеству, равно . Различные составы кортежей длины п, компоненты которых принадлежат данному т элементного множеству, называют также сочетаниями с повторениями из т элементов по п. Их число обозначают 
.Итак, = .
П р и м е р. Сколькими способами можно составить набор из 5 плиток шоколада, если их имеется 4 вида?
Решение. Поскольку в этой задаче порядок плиток шоколада не играет роли, то каждый набор задается кортежем длины 5 из 4 элементов, причем порядок компонентов не играет роли. Иными словами, надо найти число различных составов таких кортежей, т.е. число сочетаний с повторениями из 4 элементов по 5. По формуле получим: 
.
Существует 56 различных наборов.
§ 6. Первоначальные понятия теории вероятностей
При изучении математики, физики и других предметов решаются задачи, предусматривающие, как правило, однозначный результат действия. Например, если требуется определить площадь треугольника со сторонами а, b, с, то она однозначно может быть определена по формуле Герона.
Но есть большой круг задач в науке, в технических и художественных приложениях, в которых результат действия не определен однозначно. Рассмотрим простейший пример. Если подбросить монету, то нельзя точно сказать, какой стороной она ляжет вверх – гербом или цифрой. Однако при большом числе бросков примерно в половине случаев выпадает герб, а в половине – цифра. И это уже некоторая закономерность, именно такие закономерности и изучаются в теории вероятностей. При этом изменяется сама постановка задачи, в которой ставится цель определить не результат отдельного опыта, а результат, полученный после многократного повторения. В теории вероятностей изучаются закономерности массовых случайных событий.
Большое число вероятностных задач возникает при постановке экспериментов и планировании. Например, сколько опытов надо поставить, чтобы выводы из них были достоверны? Конечно, чем больше опытов, тем надежнее сделанные из них выводы. И все равно нужно знать, на каком большем числе опытов надо остановиться. В теории вероятностей имеются рекомендации о необходимом числе опытов для получения достаточно надежных выводов из эксперимента.
§ 7. Случайные события
В теории вероятностей опыт, эксперимент, наблюдение явления называют испытанием. Результат, исход испытания, называют случайным событием (или просто событием). События принято обозначать большими латинскими буквами: А, В, С, . .
П р и м е р. Рассмотрим такой опыт: игральную кость (кубик, на стороне которого указаны точки: 1, 2, 3, 4, 5, 6, соответствующие количеству очков) бросают на стол и смотрят, сколько очков выпало на верхней грани. При этом могут произойти следующие события:
Еще можно рассмотреть следующие события:
В –«число выпавших очков простое»,
С –«число выпавших очков четное»,
D –«число выпавших очков нечетное».
Ограничимся этими событиями, хотя их список можно было продолжить. Нетрудно заметить, что между отдельными событиями существует определенная связь.
Ясно, что события D и С немогут произойти одновременно, такие события называют несовместными, а события В и С совместные, они могут произойти одновременно.
Определение. Два события называют несовместными, если они в одном и том же испытании не могут произойти одновременно. События, которые в рассматриваемом опыте при одном и том же исходе испытания могут произойти одновременно, называют совместными.
Определение. Событие А благоприятствует событию В (пишут А Ì В), если из того, что произошло событие А следует, что произошло событие В. Если из того, что произошло событие А, еще не следует, что произошло событие В, то событие А не благоприятствует событию В (пишут: А Ë В). В приведенном выше примере:
Исходы испытания считаются равновозможными, если любой исход испытания не более возможен, чем другие. При решении конкретных задач о равновозможности исходов испытания обычно судят по тому, что выбор производится наудачу.
Например, если из набора экзаменационных билетов наудачу извлекается один билет, причем все билеты написаны на одинаковой по форме бумаге и не имеют пометок, то выбор любого билета равновозможен.
Определение. Два события А и В называют противоположными, если в данном испытании они несовместны и одно из них обязательно происходит. Событие, противоположное событию А, обозначают через 
.
Определение. Событие U называют достоверным, если в данном испытании оно является единственно возможным его исходом, и невозможным (V), если в данном испытании оно заведомо не может произойти.
Заметим, что достоверное и невозможное события в данном испытании являются противоположными.
П р и м е р. Из урны, в которой все шары белые, извлекается шар. Событие А – вынут белый шар – достоверное событие; событие В – вынут черный шар – невозможное событие.
§ 8. Формула для непосредственного подсчета вероятностей
Понятие вероятности является основным в теории вероятностей. Для введения этого понятия познакомимся с одной из важнейших схем теории вероятностей, так называемой классической схемой. Эта схема имеет место, когда все исходы испытания равновозможны и несовместны, а число всех исходов конечно.
Рассмотрим пример и попытаемся ответить на вопрос, какое из двух данных событий А или В является более возможным. Событие А, состоящее в том, что извлеченный экзаменационный билет имеет четный номер (из билетов, имеющих по порядку номера 1-25) или событие В, состоящее в том, что экзаменационный билет имеет нечетный номер (из числа тех же билетов). Можно сказать, что событие В более возможно, чем событие А, ведь среди номеров билетов от 1 до 25 включительно нечетных больше, чем четных.
Всякое испытание влечет за собой некоторую совокупность (группу) исходов, т.е. событий. Во многих случаях возможно перечислить все события, которые могут быть исходами данного испытания, т.е. всю группу.
Определение. Если группа событий такова, что в результате испытания обязательно должно произойти хотя бы одно из них, и любые два из них несовместны, то эту группу событий называют полной группой событий. События, образующие полную группу, называют элементарными событиями.
Приведем примеры полных групп событий: выпадение герба и выпадение цифры при одном бросании монеты; попадание в цель и промах при одном выстреле; выпадение одного, двух, трех, четырех, пяти и шести очков при одном бросании игральной кости.
Определение. (классическое определение вероятности).
Вероятностью Р(А) события А называют отношение 
числа элементарных событий, благоприятствующих событию А, к числу всех элементарных событий, т.е.
(1).
Эту формулу называют формулой для непосредственного подсчета вероятностей.
Из приведенного определения вытекают следующие ее свойства:
1º. Вероятность наступления достоверного события (U)равна 1.
В самом деле, достоверное событие (U) – это событие, происходящее при всех исходах испытания, следовательно, т = п и, значит, Р(U) = 1.
2º. Вероятность наступления невозможного события (V)равна 0.
В самом деле, невозможное событие (V)не происходит ни при одном исходе испытания, следовательно, т = 0и, значит Р(V) = 0.
3º. Вероятность наступления случайного события есть положительное число, меньшее единицы.
В самом деле, случайное событие А происходит не при всех исходах испытания, следовательно 0
Дата добавления: 2016-11-18 ; просмотров: 1854 | Нарушение авторских прав
Презентация была опубликована 2 года назад пользователемЕлена Лютикова
Похожие презентации
Презентация на тему: " «Число, положение и комбинаторика – три взаимно пересекающиеся, но различные сферы мысли, к которым можно отнести все математические идеи» Джозеф Сильвестр." — Транскрипт:
1 «Число, положение и комбинаторика – три взаимно пересекающиеся, но различные сферы мысли, к которым можно отнести все математические идеи» Джозеф Сильвестр (1844 г.) КОМБИНАТОРИКА
3 Комбинаторика – самостоятельная ветвь математической науки
4 КОМБИНАТОРИКА — это раздел математики, в котором изучаются простейшие «соединения»: перестановки, размещения, сочетания. (Большой Энциклопедический Словарь) — происходит от латинского слова «combina», что в переводе на русский означает – «сочетать», «соединять».
5 «Вперед поедешь – голову сложишь, направо поедешь – коня потеряешь, налево поедешь – меча лишишься.
6 n-факториал- это произведение всех натуральных чисел от до единицы до n. Обозначают n!=n·(n-1)·(n-2)·…·3·2·1. n-факториал- это произведение всех натуральных чисел от до единицы до n. Обозначают n!=n·(n-1)·(n-2)·…·3·2·1.
7 1! = 1, 2! = 2 · 1 = 2, 3! = 3 ·2·1 = 6, 4! = 4·3·2·1 = 24, 5! = 5·4·3·2·1 = 120. Необходимо знать, что 0!=1
8 Рассмотрим таблицу первых десяти значений n! n n!
9 Перестановки – Р n =1 ·2 ·3 ·… ·n Р n = n! Перестановки – соединения, которые можно составить из n предметов, меняя всеми возможными способами их порядок; Р n =1 ·2 ·3 ·… ·n Обозначают Р n =n! Число n называется порядком перестановки.
11 Задача 1 Сколькими способами 7 книг разных авторов можно расставить на полке в один ряд?
12 Решение: Р 7 = 7!= 1 · 2 · 3 · 4 · 5 · 6 · 7 =5040, Ответ: 5040 способов.
13 Задача 2 Квартет Проказница Мартышка Осёл, Козёл, Да косолапый Мишка Затеяли играть квартет … Стой, братцы стой! – Кричит Мартышка, — погодите! Как музыке идти? Ведь вы не так сидите… И так, и этак пересаживались – опять музыка на лад не идет. Вот пуще прежнего пошли у них разборы И споры, Кому и как сидеть… Сколькими способами можно рассадить четырех музыкантов?
14 Решение: P 4 = 4! = 1 · 2 · 3 · 4 = 24
15 Задача 3 Имеется 10 книг, среди которых есть трехтомник одного автора. Сколькими способами можно расставить эти книги на полке, если книги трехтомника должны находится вместе, но в любом порядке?
16 Решение: P 8 · Р 3 = 8! ·3! = Ответ:
17 Задача 4 Из цифр 0, 2, 4 и 5 образованы четырехзначные числа. Найдите количество всех таких чисел, если в них нет одинаковых цифр.
18 Решение: Из четырех цифр можно составить P 4 = 4! Р 3 =3! Р 4 – Р 3 =4!-3!=4·3!-3!=3·3!=18 Ответ: 18
19 Задача 5 Из цифр 1, 2, 3, 4, 5 составьте множество всех возможных пятизначных чисел без повторения цифр. Сколько среди этих пятизначных чисел таких, которые:
20 а) начинаются с цифры 5 Решение: Р 4 = 4! = 24 Ответ: 24
21 б) не начинаются с цифры 1; Решение: Р 5 = 5! 4! 5! — 4! = 5·4! -4!=44!=4-4·3·2·1 =96. Ответ: 96
22 в) начинаются с 23; Решение: Р 3 = 3! = 3 ·2 ·1=6 Ответ: 6
23 г) не начинаются с 452; Решение: Р 2 = 2 · 1 = 2 Р 5 = 5! = 5 · 4 ·3 ·2 ·1 = 120 5!-2!=118 Ответ: 118
24 д) четные. Решение: 4! 4!+4!=2 ·4!=2 ·4 ·3 ·2 ·1=48 Ответ: 48
25 Спасибо за внимание
27 Размещения и сочетания
28 В отделении 12 солдат. Каким числом способов можно составить наряд из двух человек, если один из них в наряде старший? Задача 2. В отделении 12 солдат. Каким числом способов можно составить наряд из двух человек, если один из них в наряде старший?
29 12 способов выбрать старшего 11 способов выбрать его помощника · 12 · 11=132
30 Задача 3. Для праздника в детском саду дети раскрашивали флажки в разные цвета. Верхнюю половину флажка красили в один цвет, а нижнюю в другой. Для раскраски у них имелись синяя, красная, желтая и зеленая краски. Сколько различных двухцветных флажков могли подготовить дети к празднику?
31 1 способ. 4 ·3=12 всего 12 различных флажков
33 3 способ. (с,к)(к,с)(ж,с)(з,ж) (с,ж)(к,ж)(ж,к)(з,с) (с,з)(к,з)(ж,з)(з,к) всего 12 различных флажков
34 Составим из элементов множества всевозможные пары, чтобы в каждой паре элементы не повторялись
36 Определение 1. Множество с заданным порядком расположения элементов называют упорядоченным множеством.
37 Определение 2. В комбинаторике конечные упорядоченные множества называются размещениями.
38 Размещением из n элементов по k, где k n, называют упорядоченное множество, содержащее k элементов. Вычисляется по формуле Размещением из n элементов по k, где k n, называют упорядоченное множество, содержащее k элементов. Вычисляется по формуле
39 Теорема. Число размещений из n элементов по k равно или, домножив числитель и знаменатель на (n-k)! получим, что
41 Вычислим число, где
46 Задача 4. Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны?
48 Задача 5. Сколькими способами четверо юношей могут пригласить четырех из шести девушек на танец?
50 Задача 6. В 9 классе обучается 24 ученика. Сколькими способами можно составить график дежурства по классу, если группа дежурных состоит из трех учеников?
51 Решение задачи: Ответ: число способов равно числу размещений из 24 по 3, т.е способа.
52 Задача 7. В магазине есть пять сортов печенья, шесть сортов конфет, четыре сорта шоколада. Сколько различных подарков может предложить магазин, если в подарок входит два различных вида угощения (печенья, конфет, шоколада) различных сортов (по одному).
53 5·6=30 различных подарков, состоящих только из конфет и печенья 5·4=20 различных подарков, состоящих только из шоколада и печенья 4·6=24 различных подарков, состоящих только из конфет и шоколада =74 – число различных подарков
54 Определение. Рассмотрим конечные множества A 1, А 2, А 3. Ак, количество различных элементов в каждом из которых соответственно равно n 1, n 2, n 3,…n k, причем у них нет общих элементов. Тогда общее число различных элементов в их объединении равно сумме чисел элементов в каждом из множеств:
55 Определение. В комбинаторике конечные множества называют сочетаниями
56 Определение. Число всех способов выбрать k элементов из n данных элементов без учета порядка называют числом сочетаний из n элементов по k и обозначают.
57 Теорема. Число сочетаний из n элементов по k равно
62 Рассмотрим таблицу значений при
73 012345Σ 01 1= = = = = =2 5 n k
76 Теорема. Число всех подмножеств, образованных из элементов множества, состоящего из n элементов, равно
77 Задача 7. Сколько трехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаются одновременно), если на нем всего 10 цифр?
78 Решение задачи: Ответ: число способов равно числу сочетаний из 10 по 3, т.е. 120 способов.
79 Задача Ученикам дали список из 10 учебников, которые рекомендуется использовать для подготовки к экзамену. Сколькими способами ученик может выбрать из них 4 книги? Сколькими способами ученик может выбрать из них 4 книги?
80 Решение задачи: Ответ: число способов равно числу сочетаний из 10 по 4, т.е. 30 способов.
81 Спасибо за внимание.
83 Размещениями из n элементов по k с повторениями называются всевозможные соединения по k элементов, взятых из данных n элементов и отличающихся либо самими элементами, либо их порядком
84 Задача 1. Сколько различных двузначных чисел можно образовать из цифр 1, 3 и 4?
85 Решение : На первое место мы можем поставить 3 числа, на второе тоже 3 и на третье – 3, значит
86 Перестановкой из n элементов называется упорядоченное множество, содержащее n заданных элементов, из которых некоторые повторяются раз
87 Задача 2. Сколько семизначных чисел можно составить из цифр 1, 2, 3, 4, 5, если число может содержать цифры 2, 3, 4 и 5 по одному разу, а цифру 1 -три раза?
88 Решение : 7!=5040 3!=6 Ответ: 840 двузначных чисел.
89 Сочетаниями с повторениями из n элементов по k элементов называются неупорядоченные множества по k элементов из n элементов, причем любой элемент может повторятся до k раз.
90 Задача 3. На спектакле в Михайловском театре по время антракта Катя зашла в буфет и увидела на витрине четыре вида пирожных: эклеры, буше, наполеон и миндальные. Она купила 10 пирожных. Сколькими способами она могла это сделать?
91 Решение : Ответ: 715 способами Катя может купить 10 пирожных.
92 Порядок важен? нет Повторения есть? нет Сочетания да Сочетания с повторениями да Нужно выбрать все n элементов? нет Повторения есть? нет Размещения да Размещения с повторениями Да Повторения есть? нет Перестановки да Перестановки с повторениями
93 Задача 1 Сколько шестизначных кодов для открывания замка можно составить из цифр 2, 3, 5 и трех букв А, В и С, если в коде не должны повторяться ни буквы, ни цифры.
94 Решение: 6! Р 6 =6!=720 Ответ: 720
95 Задача. Сколько разных слов можно образовать из слова « папа »?
96 Решение : 4!=24 2!=2 Ответ: 6 слов.
97 Задача. Сколько существует треугольников, длина сторон которых 5, 6, 7, 8, 9?
98 Порядок важен? нет Повторения есть? да Сочетания с повторениями
99 Ответ: 35 треугольников.
100 Задача. Сколько слов можно получить из слова « барабашка »?
101 Порядок важен? да Нужно выбрать все n элементов? Да Повторения есть? да Перестановки с повторениями
103 Библиографическая справка Термины «перестановки» и «размещения» впервые употребил Якоб Бернулли в книге «Искусство предположений». Термин «сочетания»впервые встречается у Блеза Паскаля в 1665 году.
104 Решение задач: Задача 1: В соревнованиях участвуют 12 команд. Сколько существует вариантов распределения призовых (I, II, III) мест? Задача 2: Студенты Женя, Сергей, Коля, Наташа и Ольга побежали на перемене к теннисному столу, за которым уже шла игра. Сколькими способами подбежавшие студенты могут занять очередь для игры в настольный теннис? Задача 3: В 9 классе учатся 7 учеников, в 10 – 9, а в 11 – 8 учеников. Для работы на пришкольном участке надо выделить двух учеников из 9 класса, трех – из 10 класса и одного – из 11 класса. Сколько существует способов выбора учеников для работы на пришкольном участке? Решение задач: Задача 1: В соревнованиях участвуют 12 команд. Сколько существует вариантов распределения призовых (I, II, III) мест? Задача 2: Студенты Женя, Сергей, Коля, Наташа и Ольга побежали на перемене к теннисному столу, за которым уже шла игра. Сколькими способами подбежавшие студенты могут занять очередь для игры в настольный теннис? Задача 3: В 9 классе учатся 7 учеников, в 10 – 9, а в 11 – 8 учеников. Для работы на пришкольном участке надо выделить двух учеников из 9 класса, трех – из 10 класса и одного – из 11 класса. Сколько существует способов выбора учеников для работы на пришкольном участке?
105 Особая примета комбинаторных задач — вопрос, который начинался словами «Сколькими способами…?» Особая примета комбинаторных задач — вопрос, который начинался словами «Сколькими способами…?»
106 Исторические сведения Комбинаторика как наука стала развиваться в XIII в. параллельно с возникновением теории вероятностей. Первые научные исследования по этой теме принадлежат итальянским ученым Дж. Кардано, Н. Чарталье ( ), Г. Галилею ( ) и французским ученым Б.Пискамо ( ) и П. Ферма. Комбинаторику, как самостоятельный раздел математики, первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666 г. Он также впервые ввел термин «Комбинаторика».
107 Исторические сведения Дата рождения: 1 июля 1646 г. Место рождения: Лейпциг, Германия Дата смерти:14 ноября 1716 г. Место смерти: Ганновер, Германия Школа/традиция: рационализм Направление: Европейская философия Основные интересы: Метафизика, эпистемология, наука, математика. Лейбниц Готфрид Вильгельм