Рассмотрим множество А = {а1, а2,..., аn},
содержащее n различных элементов, которое будем называть n-множеством
или генеральной совокупностью объема n. Из n-множества можно образовать его части (подмножества).
Определение. Подмножество, состоящее из m элементов n-множества, называют m-подмножеством n-множества или со-
единением из n элементов по m, или выборкой объема m из генеральной совокупности объема n.
Возможны два способа выбора:
1. Выбор без возвращения,
при котором однажды выбранный элемент удаляется из генеральной совокупности. Выборка
(соединение) в этом случае не содержит повторяющихся элементов.
2. Выбор с возвращением,
при котором выбор производится каждый раз из всей генеральной совокупности, то есть перед
следующим выбором предыдущий выбранный элемент возвращается в генеральную совокупность. В выборке (соединении) в
этом случае встречаются повторения.
Какие выборки одного и того же объема считать различными и какие одинаковыми, зависит от правил выбора соедине-
ния (подмножества, выборки).
Два соединения могут отличаться либо 1) составом, если они содержат хотя бы по одному различному элементу, либо
2) порядком входящих элементов.
В зависимости от правил выбора соединения делят на три типа: размещения, перестановки, сочетания. В зависимости от
способа выбора (без возвращения или с возвращением) каждый тип соединения может быть без повторений или с повторениями.
2. Размещения без и с повторениями.
Классической задачей комбинаторики является задача о числе размещений без повторений,
содержание которой можно
выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?
Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой
можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов,
среди которых есть одинаковые?
Определение. Размещениями из n элементов по m называются соединения из n элементов по m, которые отличаются
друг от друга либо своими элементами (составом), либо порядком их расположения.
На языке теории множеств это звучит следующим образом: размещения из n элементов по m – это упорядоченное
m-подмножество n-множества (упорядоченная m-выборка из генеральной совокупности объема n). Термин «упорядоченная»
означает, что порядок следования элементов в выборке существенен: выборки с одними и теми же элементами, но с разным
порядком их следования различны.
Задача
. Пусть имеется множество, содержащее 4 буквы:
{А, B, C, D}. Записать все возможные размещения из 4 указанных букв по две:
а) без повторений;
б) с повторениями.
Решение.
а) Таких размещений 12: (АВ), (AC), (АD), (ВС),(ВD), (BA), (CA), (CB), (СD), (DА), (DВ), (DС). Заметим, что
размещения отличаются порядком входящих в них элементов и их составом. Размещения АВ и ВА содержат одинаковые буквы,
но порядок их расположения различен.
б) Таких размещений 16. К приведенным для случая (а)
размещениям добавляются размещения из одинаковых элементов (АА), (BB), (CC), (DD).
Задача
. Пусть имеется множество, содержащее 2 буквы:{A, B}. Записать все возможные размещения с повторениями из
4-х букв.
Решение. Таких размещений 16: (AAAA), (BBBB), (AAAB),(AABA), (ABAA), (BAAA), (AABB), (ABAB), (BABA), (BBAA), (ABBA),
(BAAB), (BBBA), (BBAB), (BABB), (ABBB).
Теорема 3. 3.1 Число различных размещений без повторений из n элементов по m равно
для выборки без возвращения.
3.2 Число размещений с повторениями из n элементов по m равноm (2) для выборки с возвращением.
Доказательство. Для доказательства воспользуемся пра- вилом умножения.
Рассмотрим выборки без возвращения. Для выбора первого элемента имеется n возможностей, второго – (n – 1)
(перед вторым выбором в генеральной совокупности ос- талось (n –1) элементов),..., при m-ом выборе (n – m + 1) воз- можностей.
Таким образом, по правилу умножения
Запишем выражение в более удобном виде, умножив и разделив его на (m – n)!
Считается, что 0! = 1, что позволяет использовать эту формулу для случая m = n.
Рассмотрим выборки с возвращением
. Для выбора первого элемента имеется n возможностей, второго – тоже n (перед выбо-
ром очередного элемента предыдущий выбранный элемент зафиксирован и возвращен в генеральную совокупность), при m-м вы-
боре тоже n возможностей. Таким образом .
Задача . В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии.
Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?
Решение
. В данной задаче генеральной совокупностью являются 12 страниц газеты, и выборкой без возвращения 4 выбранные из них страницы для фотографий. В данной задаче важно не только то, какие выбраны страницы, но и в каком порядке (для расположения фотографий). Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:
Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.
Задача
. У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих
штампов нанести на все книги пятизначные номера – составить каталог. Сколько различных пятизначных номеров может со-
ставить мальчик?
Решение. Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр {1, 3, 7}. Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:
3. Перестановки без повторений
Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно
выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?
Определение. Размещения, в которых участвуют все n элементов генеральной совокупности, называются перестанов-
ками без повторений из n элементов. Перестановки состоят из одних и тех же элементов, но отличаются между собой порядком.
Задача
. Пусть имеется множество букв {A, B, C}. Записать все возможные перестановки.
Решение. Этому множеству букв соответствует 6 перестановок: (АВС), (ACB), (BAC), (BCA), (CBA), (CAB).
Теорема . Число перестановок n различных элементов равно n!, т. е. Рn = n!
Доказательство. Так как перестановки являются частным случаем размещений, то при n = m получаем
Замечание. При больших n для подсчета факториала исполь- зуют таблицу логарифмов факториалов либо приближенную формулу Стирлинга
Задача . Сколько можно составить четырехбуквенных «слов» из букв слова «брак»?
Решение . Генеральной совокупностью являются 4 буквы слова «брак» {б, р, а, к}.
Число «слов» определяется перестановками этих 4 букв, т. е. Р4 = 4! = 1 x 2 x 3 x 4 = 24.
Задача . Сколькими способами можно расставить девять различных книг на полке, чтобы определенные четыре книги стояли рядом?
Решение . В исходной генеральной совокупности – 9 разных книг.
Тогда для остальных 6 книг существует Р6 = 6! = 720 перестановок.
Однако четыре определенные книги можно переставить между собой Р4 = 4! = 24 способами.
По правилу умножения имеем Р6 x Р4 = 720 x 24 = 17280.
4. Перестановки с повторениями
Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на
n различных местах, если среди n предметов имеются k различных типов (k < n), т. е. есть одинаковые предметы.
Определение. Перестановками с повторениями называются соединения из генеральной совокупности, каждое из которых содержит n элементов, среди которых элемент
а1 повторяется n1 раз,
а2 повторяется n2 раз,
. . . . . . . . . . . . . . . . . . .
аn повторяется nk раз
n1 + n2 + ... + nk = n
и которые отличаются друг от друга только порядком расположения различных элементов.
Теорема. Число перестановок с повторениями
Доказательство. Доказательство очевидно, так как перестановки одинаковых элементов в перестановке с повторениями не дают новой перестановки.
Задача .
Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?
Решение. Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв.
Следовательно, число перестановок с повторениями равно
5. Сочетания без повторений
Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из п различных предметов?
Определение. Сочетаниями из n различных элементов по m называются соединения из n элементов по m (m <=n), которые
отличаются друг от друга только составом элементов.
Задача. Пусть имеется множество, содержащее 4 буквы {A, B, C, D}. Запишем все возможные сочетания из указанных
букв по 3.
Решение. Таких сочетаний 4: ABC, ACD, ABD, BCD.
Здесь в число сочетаний не включены, например, АСВ,ВСА, так как они не отличаются по составу от последовательно-
сти букв АВС, потому что перестановка элементов нового сочетания не дает.
Теорема. Число сочетаний из n элементов по m равно
Доказательство.
Вспомним, что и сочетания, и размещения из n элементов по m – это выборки объема m из генеральной совокупности объема n и разница между ними в том, что в случае размещений важен и состав, и порядок элементов, тогда как в случае сочетаний важен только состав элементов. Пусть имеется какое-то одно сочетание. Для того, чтобы образовать все размещения с такими же элементами, нужно осуществить всевозможные перестановки элементов этого сочетания. Поскольку в сочетании m элементов, то существует m! перестановок. Следовательно, одному сочетанию, состоящему из m элементов, соответствует m! размещений с этими элементами. Поэтому
Числа называются биномиальными коэффициентами: они являются коэффициентами в разложении бинома Ньютона
Задача . Необходимо выбрать в подарок 4 из 10 имеющих- ся различных книг. Сколькими способами можно это сделать?
Решение . Генеральной совокупностью является 10 раз- личных книг. Из них нужно выбрать 4, причем порядок выбора книг не играет роли. Нужно найти число сочетаний из 10 элементов по
Задача . Имеется 10 белых и 5 черных шаров. Сколькими способами можно выбрать 7 шаров, чтобы среди них были 3 черных?
Решение . Имеем 15 шаров: 10 белых и 5 черных. Нужно выбрать 7 шаров: 4 белых и 3 черных.
Разобьем 15 шаров на 2 генеральные совокупности:
1) 10 белых шаров;
2) 5 черных шаров.
4 белых шара будем выбирать из I генеральной совокупности, порядок выбора безразличен, их можно выбрать
Способами. 3 черных шара будем выбирать из II генеральной совокупности, их можно выбрать
Способами.
Тогда по правилу умножения искомое число способов равно .
Решение этой задачи можно схематически представить следующим образом
Задача . Десять команд участвуют в розыгрыше первенства по футболу, лучшие из которых занимают 1-е, 2-е и 3-е место.
Две команды, занявшие последние места, не будут участвовать в следующем таком же первенстве.
Сколько разных вариантов результата первенства может быть, если учитывать только положение первых трех и последних двух команд.
Решение . Имеется генеральная совокупность объема 10 команд. Из нее будем выбирать 5 команд в 2 этапа:
1) сначала на первые 3 места из 10 с учетом состава и порядка команд;
2) затем на последние 2 места из оставшихся 7 с учетом только состава (порядок выбывших команд не важен).
Первые 3 места могут быть распределены способами.
Число способов исключить 2 команды из оставшихся 7 равно .
Согласно правилу умножения получаем, что число разных результатов неравенства равно 0.
Задача .
Сколько существует вариантов опроса 11 учащихся на одном занятии, если ни одни из них не будет подверг нут опросу дважды и на занятии может быть опрошено любое количество учащихся, причем порядок, в котором опрашивают- ся учащиеся, безразличен?
Решение .
I способ. Имеется генеральная совокупность объема 11 учащихся. Преподаватель может не опросить ни одного из 11 учащихся, что является одним из вариантов. Этому случаю соответствует . Преподаватель может опросить только одного из учащихся, таких вариантов .
Если преподаватель опросит двух учащихся, то число вариантов опроса . Для опроса трех учащихся существует вариантов и т. д.
Наконец, могут быть опрошены все учащиеся. Число вариантов в этом случае .
Число всех возможных вариантов опроса можно найти по пра- вилу сложения
Решение этой задачи можно схематически представить следующим образом:
II способ. Имеется генеральная совокупность, состоящая из 2 элементов:
{а, в}, где а – ученик опрошен, в – ученик не опрошен на данном занятии.
Опыт состоит в 11-кратном выборе с возвращением одного из элементов этого множества – каждый из 11 учеников либо опрошен, либо не опрошен.
В данной задаче важно не только то, какие выбраны элементы множества (сколько учеников опрошено и сколько нет),
но и в каком порядке (т. е. какой именно ученик опрошен или нет).
Число способов такого выбора определяется числом размещений с повторениями из 2 элементов по 11; .
6. Сочетания с повторениями
Рассмотрим задачу о числе сочетаний с повторениями:
имеется по r одинаковых предметов каждого из n различных типов;
сколькими способами можно выбрать m (m <= r) из этих (n x r) предметов?
Определение . Сочетаниями с повторениями называются соединения из n элементов по m (выбор с возвращением m элементов), которые отличаются только составом и при этом отдельные соединения могут содержать повторяющиеся элементы.
Задача
. Имеются 2 буквы А, 2 буквы В, 2 буквы С. Сколькими способами можно выбрать две из этих шести букв?
Решение. Существует 6 способов выбора 2 букв из 6 с повторениями: (АА), (AB), (AC), (BC), (BB), (CC). Порядок следо-
вания букв не учитывается.
Теорема . Число сочетаний с повторениями равно
Доказательство. Пусть имеются предметы n различных типов. Сколько соединений по m элементов можно из них сделать, если не принимать во внимание порядок элементов. Расположим в каждом сочетании элементы по типам (сначала все элементы 1-го типа, потом 2-го и т. д.). После этого перенумеруем все элементы в сочетании, но к номерам элементов второ- го типа прибавим 1, третьего типа – 2 и т. д. Тогда из каждого сочетания с повторениями получится сочетание без повторений, состоящее из чисел 1, 2,..., n + m – 1, причем в каждое сочетание входит m элементов.
Отсюда следует, что
Задача . В технической библиотеке имеются книги по ма- тематике, физике, химии и т. д., всего по 16 разделам науки.
Поступили очередные 4 заказа на литературу. Сколько сущест- вует вариантов такого заказа?
Решение. Так как 4 заказанные книги могут быть и из одно- го раздела науки, и из разных разделов, при этом порядок выбора разделов не важен, то число вариантов заказа определяется чис- лом сочетаний с повторениями из 16 элементов по 4, т. е.
Задача . В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?
Решение . Очевидно, что порядок, в котором выбираются пирожные, не существен, причем в комбинации могут входить повторяющиеся элементы (например, можно купить 7 эклеров). Следовательно, число способов покупки 7 пирожных определяется числом сочетаний с повторениями из 4 элементов по 7, т. е
7. Комбинаторика разбиений
Рассмотрим в этом классе задач две следующие задачи:
1. Даны n различных предметов и k различных групп. Сколькими способами можно распределить n различных предметов по k различным группам, если допускаются пустые группы. Ниже покажем, что число способов равно k^n .
2. Даны n различных предметов и k различных групп. Сколькими способами можно распределить n различных пред- метов по k группам, если в первой группе n1 предметов, во второй – n2 , в k-й – nk , где n1 + n2 +... + nk = n . Ниже покажем, что число способов равно
Рассмотрим решение первой задачи. Пусть генеральной совокупностью будет k различных групп {1, 2,..., k}. Можно считать, что опыт состоит в n-кратном выборе с возвращением номера группы для каждого предмета. Заметим, что поскольку предметы разные, то важно не только, какие группы выбираются для предметов, но и в каком порядке выбираются эти группы. Таким образом, число способов раз- бить n различных предметов на k групп определяется числом размещений с повторениями и k элементов по n:
Рассмотрим решение второй задачи.
Разбиение n предметов по k группам можно выполнить следующим образом. Сначала положим все n предметов в ряд. После этого возьмем первые n1 предметов и поместим их в первую группу, вторые n2 предмета – во вторую группу, ..., последние nk предметов в k-ю группу. Ясно, что меняя положение предметов в ряду, можно получить всевозможные разбиения предметов. Так как число перестановок из n элементов равно n!, то число расположения предметов в ряд равно n! При этом заметим, что любая перестановка первых n1 предметов ничего не меняет, так же как и вторых n2, ..., и последних nk. В силу правила произведения получим n1!n2!...nk! перестановок предметов, не меняющих результата раздела. Таким образом, число способов разбиения на группы равно
Формула совпадает с формулой для числа перестановок с повторениями. К этому же результату можно прийти иначе. Первые n1 предметов выбираем из n предметов. Так как порядок выбранных предметов безразличен, то имеет выборов. После этого следующие n2 предмета выбираем из оставшихся n – n1. Это можно сделать способами, и т. д.
Наконец, последние nk предметов выбираем из оставшихся nk. Это можно сделать , т. е. единственным способом. По правилу произведения получаем, что число способов разбиения на группы равно
Как видим, задачи о разбиениях привели к уже известным формулам комбинаторики.
Задача. 7 одинаковых шариков случайным образом рас- сыпаются по 4 лункам (в одну лунку может поместиться любое число шаров). Сколько существует различных способов распре- деления 7 шариков по 4 лункам?
Решение. Мы имеем 7 шариков, которые распределяем по 4 лункам (лунки могут быть пустые), т. е. это соответствует первой задаче о разбиениях, число способов равно 4^7 = 16348
Задача. При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать?
Решение. Это задача о разделе 28 костей между 4 игрока- ми по 7 костей. Используя полученную выше формулу для числа способов такого раздела (задача 2), имеем
8. Рекомендации по решению задач
Решение комбинаторных задач представляет известную трудность для начинающих. Причин много, но одна из них очевидна – при изложении комбинаторики используется своя специфическая терминология (генеральная совокупность, выборка, правила выбора). В задаче же этих терминов, как правило, нет –сформулирована она на обычном литературном языке и комби-
наторные понятия присутствуют в ней в неявной форме. Поэтому после усвоения содержания задачи нужно ее «перевести»
на математический язык.
Для этого необходимо выяснить,
1) что является генеральной совокупностью - она всегда будет присутствовать в задаче, т. е. комбинаторные задачи свя-
заны с выбором объектов, а этот выбор из чего-то (генеральной совокупности) производится; каков объем генеральной сово-
купности;
2) одна или несколько генеральных совокупностей;
3) что является выборкой и каков объем выборки;
4) правила выбора: допустимы или нет повторы, важен ли порядок выбираемых элементов, возможно ли изменение состава.
После этого полезно для себя переформулировать задачу на языке генеральных совокупностей и выборок. В зависимости
от ситуации выбрать нужную формулу (см. таблицу). Иногда в более сложных задачах приходится использовать совместно не-
сколько формул.
В заключение приведем основные свойства чисел .
Прежде всего, построим таблицу таких чисел, используя формулу (3.11).
Таблица чисел имеет треугольную форму и называется треугольником Паскаля по имени математика Блеза Паскаля (1623-1662). Анализируя треугольник Паскаля, легко видеть основные свойства чисел .
Свойства 1 – 2 вытекают из определения сочетания как подмножества, содержащего m элементов множества, имеющего n элементов.
Свойства 3 – 5 доказываются методом математической индукции.
В силу свойства 4 треугольник Паскаля легко продолжить вниз на любое число шагов.
рис 3.2 схема определения вида расстановок и выбора формул
Цель занятия: уметь применять основные формулы комбинаторики и знать условия применения этих формул; знать свойства биномиальных коэффициентов и уметь определять разложение бинома при конкретных значениях n.
План занятия:
1. Число размещений.
2. Число перестановок.
3. Число сочетаний.
4. Повторения.
5. Бином Ньютона. Треугольник Паскаля.
Методические указания по изучению темы
Во многих практических случаях возникает необходимость подсчитать количество возможных комбинаций объектов, удовлетворяющих определенным условиям. Такие задачи называются комбинаторными. Разнообразие комбинаторных задач не поддается исчерпывающему описанию, но среди них есть целый ряд особенно часто встречающихся, для которых известны способы подсчета.
Комбинаторика – область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из элементов, принадлежащих данному множеству. Термин «комбинаторика» происходит от латинского слова combina – сочетать, соединять.
Пусть есть некоторое множество из n элементов: x 1, x 2, x 3, …, x n .
Из этого множества можно образовать различные подмножества, то есть выборки, каждая из которых содержит m элементов (0 ≤ m ≤ n). Различают упорядоченные выборки (размещения), перестановки и неупорядоченные выборки (сочетания).
Размещения
Размещениями n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком.
Число размещений из n элементов по m элементов обозначают (А – первая буква французского слова arrangement, что означает размещение, приведение в порядок) и вычисляют по формуле:
Понятие факториала
Произведение n натуральных чисел от 1 до n обозначается символом n ! (n факториал), то есть
Например, 2!=
5!= 
Заметим, что удобно рассчитывать 0!, полагая по определению, 0!=1.
Примеры:
Из последних двух формул следует, что
Пример.
В однокруговом турнире по футболу участвуют 8 команд. Сколько существует вариантов призовой тройки?
Решение : Так как порядок команд в призовой тройке важен, то мы имеем дело с размещениями. Тогда
(вариантов).
Пример.
Сколькими способами можно выбрать три лица на три различные должности из десяти кандидатов?
Решение:
(способов).
Пример.
Сколько можно составить телефонных номеров из 5 цифр так, чтобы в каждом отдельно взятом номере все цифры были различными?
(телефонных номеров).
Перестановки
Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения.
Число всех возможных перестановок из n элементов обозначают P n (P – первая буква французского слова permutation, что означает перестановка) и вычисляют по формуле:
Пример.
В финальном забеге на 100 метров участвуют 8 спортсменов. Сколько существует вариантов протокола забега?
Решение:
В данном случае речь идёт обо всех перестановках из 8 элементов. Тогда (вариантов)
Пример.
Сколькими различными способами могут разместиться на скамейке10 человек?
Решение:
(способов)
Пример.
Сколькими способами можно разместить 7 лиц за столом, на котором поставлено 7 столовых приборов?
Решение:
(способов).
Сочетания
Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом.
Число сочетаний вычисляют по формуле: 
(С - первая буква французского слова combinasion).
Пример.
Сколькими способами можно выбрать три лица на три одинаковые должности из десяти кандидатов?
Решение :
(способов).
Пример.
Сколькими способами можно выбрать три детали из ящика, содержащего 15 деталей?
Решение:
(способов).
Другой вид формул числа размещений и числа сочетаний
; 
, то есть 
.
Свойства числа сочетаний:
5) 
При решении задач комбинаторики используют следующие правила:
Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов n способами, а другой объект В – k способами, то объект «либо А, либо В» можно выбрать n+k способами.
Правило произведения. Если некоторый объект А может быть выбран из совокупности объектов n способами и после каждого такого выбора другой объект В – k способами, то пара объектов (А, В) в указанном порядке может быть выбрана n×k способами.
Если некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам.
Размещения с повторениями
Число размещений по m
элементов с повторениями из n
различных элементов равно n m
,то есть 
Пример.
Из цифр 1,2,3,4,5 можно составить 5 3 =125 трехзначных чисел, если в одном и том же числе могут попадаться и одинаковые цифры.
Перестановки с повторениями
Если среди n элементов есть n 1 элементов одного вида, n 2 элементов другого вида и т.д., то число перестановок с повторениями
где 
Пример.
Сколько различных перестановок букв можно сделать в слове «математика»?
Решение:
Сочетания с повторениями
Число сочетаний с повторениями из n различных элементов по m элементов равно числу сочетаний без повторений из (n +m -1) различных элементов по m элементов:
Пример.
Найти число сочетаний с повторениями из четырех элементов a , b , c , d по 3 элемента.
Решение:
Искомое число будет 
Бином Ньютона
Для произвольного положительного целого числа n справедлива следующая формула:
Это бином Ньютона. Коэффициенты называются биномиальными коэффициентами.
При n = 2 получим формулу ;
При n = 3 получим формулу .
Пример. Определить разложение при n=4.
Решение:
Биномиальные коэффициенты обладают рядом свойств:
2. 
;
Рассмотрим следующий треугольник:
………………………….
Строка под номером n содержит биномиальные коэффициенты разложения . Воспользовавшись свойством , можно заметить, что каждый внутренний элемент треугольника равен сумме двух элементов, расположенных над ним, а боковые элементы треугольника – единицы:
……………………….
Это треугольник Паскаля. Он позволяет быстро найти значения биномиальных коэффициентов.
В русскоязычной литературе перестановки, составленные из n различных элементов выбором по m элементов, которые отличаются либо составом элементов, либо их порядком, обычно называют размещениями, а под перестановками понимают всю совокупность комбинаций, состоящих из одних и тех же n различных элементов и отличающихся только порядком их расположения. В этом смысле число всех возможных перестановок для множества из n различных элементов считается по формуле факториала Pn = n! или в Excel «=ФАКТР(N)» (см. рис. № 1)
Например, если ввести «=ПЕРЕСТ(3;2)», получим 6. Это 6 комбинации: (1,2), (2,1), (1,3), (3,1), (2,3), (3,2).
А вот встроенная функция «=ЧИСЛКОМБ(N;K)» выдает комбинаторную формулу, называемую у нас «Число сочетаний». В русскоязычной литературе так именуют перестановки, составленные из n различных элементов выбором по m элементов, которые отличаются только составом элементов, а порядок их выбора безразличен (см. рис, №4)
При использовании встроенных функций пользуйтесь «Справкой по этой функции». Например:
Задачи для самостоятельного решения
1. Вычислить: 
2. Вычислить:
3. Вычислить: 
4. Найти n , если 5С n 3 =
5. Найти n , если
6. Найти n , если
7. Найти n
, если 
8. Найти n
, если 
, k n
9. Решить уравнение 
10. Решить систему
11. Сколько можно составить сигналов из 6 флажков различного цвета, взятых по 2?
12. Сколькими способами можно выбрать четыре лица на четыре различные должности из девяти кандидатов?
13. Сколько можно составить телефонных номеров из 6 цифр так, чтобы в каждом отдельно взятом номере все цифры были различны?
14. В классе 10 учебных предметов и 5 разных уроков в день. Сколькими способами могут быть распределены уроки в один день?
15. Сколько можно записать четырёхзначных чисел, используя без повторения все 10 цифр?
16. Фирма производит выбор из девяти кандидатов на три различные должности. Сколько существует способов такого выбора?
17. В восьмом классе изучается 15 предметов. Сколькими способами можно составить расписание на среду, если известно, что в этот день должно быть 6 уроков?
18. В высшей лиге чемпионата страны по футболу 16 команд. Борьба идет за золотые, серебряные и бронзовые медали. Сколькими способами медали могут быть распределены между командами?
19. Сколькими способами можно разместить 9 лиц за столом, на котором поставлено 9 приборов?
20. На собрании выступят 6 ораторов. Сколькими способами их фамилии можно расположить в списке?
21. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, если каждая цифра входит в изображение числа только один раз?
22. Сколькими различными способами можно расставить 10 различных книг на полке, чтобы определённые 4 книги стояли рядом?
23. В однокруговом турнире по футболу участвуют 8 команд. Сколько всего матчей будет сыграно?
24. Из 25 студентов нужно выбрать трех делегатов на конференцию. Сколькими способами это можно сделать?
25. Сколькими способами можно выбрать две детали из ящика, содержащего 10 деталей?
26. В колоде 36 карт, из них 4 туза. Сколькими способами можно извлечь 6 карт так, чтобы среди них было 2 туза?
27. Комплексная бригада состоит из двух маляров, трёх штукатуров и одного столяра. Сколько различных бригад можно создать из рабочего коллектива, в котором 15 маляров, 10 штукатуров и 5 столяров?
28. В отборочном турнире за 3 путёвки на чемпионат мира участвуют 10 команд. Сколько существует вариантов «счастливой тройки»?
29. Из 12 человек выбирают четверых для назначения на 4 одинаковые должности. Сколькими способами можно сделать такой выбор?
30. Сколькими различными способами можно составить разведывательную группу из 3-х солдат и одного командира, если имеется 12 солдат и 3 командира?
31. На плоскости дано n точек, из которых никакие три не лежат на одной прямой. Найти число прямых, которые можно получить, соединяя точки попарно.
32. Буквы азбуки Морзе образуются как последовательность точек и тире. Сколько различных букв можно образовать, если использовать 5 символов?
33. Сколько существует различных семизначных телефонных номеров?
34. Пусть буквы некоторой азбуки образуются как последовательность точек, тире и пробелов. Сколько различных букв можно образовать, если использовать 5 символов?
35. При игре в бридж между четырьмя игроками распределяется колода карт в 52 листа по 13 карт каждому игроку. Сколько существует различных способов раздать карты?
36. В почтовом отделении продаются открытки пяти видов. Определить число способов покупки семи открыток.
37. Два коллекционера обмениваются марками. Найти число способов обмена, если первый коллекционер обменивает 3 марки, а второй – 6 марок. (Обмен происходит по одной марке).
38. У одного студента 6 книг по математике, а у другого – 5. Сколькими способами они могут обменять 2 книги одного на 2 книги другого?
39. Сколько различных перестановок букв можно сделать в словах: «замок», «ротор», «обороноспособность», «колокол», «семинар»?
40. Сколькими различными способами можно разместить в 9 клетках следующие 9 букв: а, а, а, б, б, б, в, в, в?
41. В автомашине 6 мест. Сколькими способами 6 человек могут сесть в эту машину, если занять место водителя могут только двое из них?
42. Сколькими способами из колоды в 52 карты можно извлечь 6 карт, содержащих туза и короля одной масти?
43. Определить разложение при n=5.
44. Определить разложение при n=8.
45. Найти член разложения , не содержащий x (то есть содержащий x в нулевой степени).
46. Найти шестой член разложения 
, если биномиальный коэффициент третьего от конца члена равен 45.
47. В разложении 
коэффициент третьего члена на 44 больше коэффициента второго члена. Найти свободный член, то есть член разложения, не зависящий от x (членом, не зависящим от x, будет тот, который содержит x в нулевой степени).
48. В разложении бинома 
найти члены, не содержащие иррациональности.
49. Найти номер того члена разложения 
, который содержит a и b в одинаковых степенях.
Практическое занятие №2
(интерактивное занятие в малых группах)
Булевы функции
Цель занятия: уметь строить различные булевы функции, проверять эквивалентность булевых формул (используя таблицу истинности), определять существенные и фиктивные переменные.
План занятия:
1. Основные операции
2. Булевы функции от n переменных
3. Основные эквивалентности
Рассмотрим задачу подсчета числа выборок из данного множества в общем виде. Пусть имеется некоторое множество N , состоящее из n элементов. Любое подмножество, состоящее из m элементов можно рассматривать без учета их порядка, так и с его учетом, т.е. при изменении порядка переходим к другой m – выборке.
Сформулируем следующие определения:
Размещения без повторения
Размещением без повторения из n элементов по m N , содержащее m различных элементов .
Из определения следует, что два размещения отличаются друг от друга, как элементами, так и их порядком, даже если элементы одинаковы.
Теорема 3 . Число размещений без повторения равно произведению m сомножителей, наибольшим из которых является число n . Записывают:
Перестановки без повторений
Перестановками из n элементов называются различные упорядочения множества N .
Из этого определения следует, что две перестановки отличаются только порядком элементов и их можно рассматривать как частный случай размещений.
Теорема 4 . Число различных перестановок без повторений вычисляется по формуле
Сочетания без повторений
Сочетанием без повторения из n элементов по m называется любое неупорядоченное подмножество множества N , содержащее m различных элементов.
Из определения следует, что два сочетания различаются только элементами, порядок не важен.
Теорема 5 . Число сочетаний без повторений вычисляют по одной из следующих формул:
Пример 1 . В комнате 5 стульев. Сколькими способами можно разместить на них
а) 7 человек; б) 5 человек; в) 3 человека?
Решение:
а) Прежде всего надо выбрать 5 человек
из 7 для посадки на стулья. Это можно
сделать
способом. С каждым выбором конкретной
пятерки можно произвести
перестановок местами. Согласно теореме
умножения искомое число способов посадки
равно.
Замечание: Задачу можно решать, используя только теорему произведения, рассуждая следующим образом: для посадки на 1-й стул имеется 7 вариантов, на 2-й стул-6 вариантов, на 3-й -5, на 4-й -4 и на 5-й -3. Тогда число способов посадки 7 человек на 5 стульев равно . Решения обоими способами согласуются, так как
б) Решение очевидно
-
в)
- число выборов занимаемых стульев.
- число размещений
трех человек на трех выбранных стульях.
Общее число выборов равно .
Не трудно проверить
формулы
;
;
Число всех подмножеств множества, состоящего из n элементов.
Размещения с повторением
Размещением с повторением из n элементов по m называется всякое упорядоченное подмножество множества N , состоящее из m элементов так, что любой элемент ожжет входить в это подмножество от 1 до m раз, либо вообще в нем отсутствовать .
Число
размещений с повторением обозначают
и вычисляют по формуле, представляющей
собой следствие из теоремы умножения:
Пример 2
.
Пусть дано множество из трех букв N
= {a,
b,
c}.
Назовем словом любой набор из букв,
входящих в это множество. Найдем
количество слов длиной 2, которые можно
составить из этих букв:
.
Замечание:
Очевидно, размещения с повторением
можно рассматривать и при
.
Пример 3 . Требуется из букв {a, b}, составить всевозможные слова длиной 3. Сколькими способами это можно сделать?
Ответ
:
Следует отметить, что комбинаторика является самостоятельным разделом высшей математики (а не частью тервера) и по данной дисциплине написаны увесистые учебники, содержание которых, порой, ничуть не легче абстрактной алгебры. Однако нам будет достаточно небольшой доли теоретических знаний, и в данной статье я постараюсь в доступной форме разобрать основы темы с типовыми комбинаторными задачами. А многие из вас мне помогут;-)
Чем будем заниматься? В узком смысле комбинаторика - это подсчёт различных комбинаций, которые можно составить из некоторого множества дискретных объектов. Под объектами понимаются какие-либо обособленные предметы или живые существа - люди, звери, грибы, растения, насекомые и т.д. При этом комбинаторику совершенно не волнует, что множество состоит из тарелки манной каши, паяльника и болотной лягушки. Принципиально важно, что эти объекты поддаются перечислению - их три (дискретность) и существенно то, что среди них нет одинаковых.
С множеством разобрались, теперь о комбинациях. Самыми распространёнными видами комбинаций являются перестановки объектов, их выборка из множества (сочетание) и распределение (размещение). Давайте прямо сейчас посмотрим, как это происходит:
Перестановки, сочетания и размещения без повторений
Не пугайтесь малопонятных терминов, тем более, некоторые из них действительно не очень удачны. Начнём с хвоста заголовка - что значит «без повторений »? Это значит, что в данном параграфе будут рассматриваться множества, которые состоят из различных объектов. Например, … нет, кашу с паяльником и лягушкой предлагать не буду, лучше что-нибудь повкуснее =) Представьте, что перед вами на столе материализовалось яблоко, груша и банан (при наличии таковых ситуацию можно смоделировать и реально). Выкладываем фрукты слева направо в следующем порядке:
яблоко / груша / банан
Вопрос первый : сколькими способами их можно переставить?
Одна комбинация уже записана выше и с остальными проблем не возникает:
яблоко / банан / груша
груша / яблоко / банан
груша / банан / яблоко
банан / яблоко / груша
банан / груша / яблоко
Итого : 6 комбинаций или 6 перестановок .
Хорошо, здесь не составило особого труда перечислить все возможные случаи, но как быть, если предметов больше? Уже с четырьмя различными фруктами количество комбинаций значительно возрастёт!
Никаких мучений - 3 объекта можно переставить способами.
Вопрос второй : сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт?
Зачем выбирать? Так нагуляли же аппетит в предыдущем пункте - для того, чтобы съесть! а) Один фрукт можно выбрать, очевидно, тремя способами - взять либо яблоко, либо грушу, либо банан.
Формальный подсчёт проводится по формуле количества сочетаний
:
Запись в данном случае следует понимать так: «сколькими способами можно выбрать 1 фрукт из трёх?»
б) Перечислим все возможные сочетания двух фруктов:
яблоко и груша;
яблоко и банан;
груша и банан.
Количество комбинаций легко проверить по той же формуле:
Запись понимается аналогично: «сколькими способами можно выбрать 2 фрукта из трёх?».
в) И, наконец, три фрукта можно выбрать единственным способом:
Кстати, формула количества сочетаний сохраняет смысл и для пустой выборки:
способом можно выбрать ни одного фрукта - собственно, ничего не взять и всё.
г) Сколькими способами можно взять хотя бы один
фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта или все 3 фрукта:
способами можно выбрать хотя бы один фрукт.
Для ответа на следующий вопрос мне требуется два добровольца… …Ну что же, раз никто не хочет, тогда буду вызывать к доске =)
Вопрос третий : сколькими способами можно раздать по одному фрукту Даше и Наташе?
Для того чтобы раздать два фрукта, сначала нужно их выбрать. Согласно пункту «бэ» предыдущего вопроса, сделать это можно способами, перепишу их заново:
яблоко и груша;
яблоко и банан;
груша и банан.
Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов:
яблоком можно угостить Дашу, а грушей - Наташу;
либо наоборот - груша достанется Даше, а яблоко - Наташе.
И такая перестановка возможна для каждой пары фруктов.
В данном случае работает формула количества размещений
:
Она отличается от формулы тем, что учитывает не только количество способов, которым можно выбрать несколько объектов, но и все перестановки объектов в каждой возможной выборке. Так, в рассмотренном примере, важно не только то, что можно просто выбрать, например, грушу и банан, но и то, как они будут распределены (размещены) между Дашей и Наташей.
Постарайтесь хорошо уяснить разницу между перестановками, сочетаниями и размещениями. В простейших случаях можно пересчитать все возможные комбинации вручную, но чаще всего это становится неподъемной задачей, именно поэтому и нужно понимать смысл формул.
Также напоминаю, что сейчас речь идёт о множестве с различными объектами, и если яблоко/грушу/банан заменить на 3 яблока или даже на 3 очень похожих яблока, то в контексте рассмотренной задачи они всё равно будут считаться различными .
Остановимся на каждом виде комбинаций подробнее:
Перестановки
Перестановками называют комбинации, состоящие из одних и тех же различных объектов и отличающиеся только порядком их расположения. Количество всех возможных перестановок выражается формулой
Отличительной особенностью перестановок является то, что в каждой из них участвует ВСЁ множество, то есть, все объектов. Например, дружная семья:
Задача 1
Сколькими способами можно рассадить 5 человек за столом?
Решение : используем формулу количества перестановок:
Ответ : 120 способами
Невероятно, но факт. Обратите внимание, что здесь не имеет значения круглый ли стол, квадратный, или вообще все люди сели на скамейку вдоль одной стены - важно лишь количество объектов и их взаимное расположение. Помимо перестановок людей, часто встречается задача о перестановках различных книг на полке, но это было бы слишком просто даже для чайника:
Задача 2
Сколько четырёхзначных чисел можно составить из четырёх карточек с цифрами 0, 5, 7, 9?
Для того чтобы составить четырёхзначное число нужно задействовать все четыре карточки (цифры на которых различны! ) , и это очень важная предпосылка для применения формулы Очевидно, что, переставляя карточки, мы будем получать различные четырёхзначные числа, … стоп, а всё ли тут в порядке? ;-)
Хорошенько подумайте над задачей! Вообще, это характерная черта комбинаторных и вероятностных задач - в них НУЖНО ДУМАТЬ. И зачастую думать по-житейски, как, например, в разборе вступительного примера с фруктами. Нет, конечно, я не призываю тупо прорабатывать другие разделы математики, однако должен заметить, что те же интегралы можно научиться решать чисто механически.
Решение и ответ в конце урока.
Увеличиваем обороты:
Сочетания
В учебниках обычно даётся лаконичное и не очень понятное определение сочетаний, поэтому, в моих устах формулировка будет не особо рациональной, но, надеюсь, доходчивой:
Сочетаниями
называют различные комбинации из объектов, которые выбраны из множества различных объектов, и которые отличаются друг от друга хотя бы одним объектом. Иными словами, отдельно взятое сочетание - это уникальная выборка из элементов, в которой не важен их порядок
(расположение). Общее же количество таких уникальных сочетаний рассчитывается по формуле 
.
Задача 3
В ящике находится 15 деталей. Сколькими способами можно взять 4 детали?
Решение : прежде всего, снова обращаю внимание на то, что по логике условия, детали считаются различными - даже если они на самом деле однотипны и визуально одинаковы (в этом случае их можно, например, пронумеровать) .
В задаче речь идёт о выборке из 4-х деталей, в которой не имеет значения их «дальнейшая судьба» - грубо говоря, «просто выбрали 4 штуки и всё». Таким образом, у нас имеют место сочетания деталей. Считаем их количество:
Здесь, конечно же, не нужно ворочать огромные числа .
В похожей ситуации я советую использовать следующий приём: в знаменателе выбираем наибольший факториал (в данном случае ) и сокращаем на него дробь. Для этого числитель следует представить в виде . Распишу очень подробно:
Способами можно взять 4 детали из ящика.
Ещё раз: что это значит? Это значит, что из набора 15-ти различных деталей можно составить одну тысячу триста шестьдесят пять уникальных сочетания 4-х деталей. То есть, каждая такая комбинация из 4-х деталей будет отличаться от других комбинаций хотя бы одной деталью.
Ответ : 1365 способами
Формуле необходимо уделить самое пристальное внимание, поскольку она является «хитом» комбинаторики. При этом полезно понимать и без всяких вычислений записывать «крайние» значения: . Применительно к разобранной задаче:
Единственным способом можно взять ни одной детали;
способами можно взять 1 деталь (любую из 15-ти);
способами можно взять 14 деталей (при этом какая-то одна из 15-ти останется в ящике);
- единственным способом можно взять все пятнадцать деталей.
Рекомендую внимательно ознакомиться с биномом Ньютона и треугольником Паскаля , по которому, к слову, очень удобно выполнять проверку вычислений при небольших значениях «эн».
Задача 4
Сколькими способами из колоды в 36 карт можно выбрать 3 карты?
Это пример для самостоятельного решения. Чем приятны многие комбинаторные задачи, так это краткостью - главное, разобраться в сути. И суть, бывает, открывается с различных сторон. Разберём весьма поучительный пример:
Задача 4
В шахматном турнире участвует человек и каждый с каждым играет по 1-й партии. Сколько всего партий сыграно в турнире?
Поскольку я сам играю в шахматы и неоднократно принимал участие в круговых турнирах, то сразу же сориентировался по турнирной таблице размером клеток, в которой результат каждой партии учитывается дважды и, кроме того, затушёвываются клетки «главной диагонали» (т.к. участники не играют сами с собой) . Исходя из проведённых рассуждений, общее количество сыгранных партий рассчитывается по формуле . Такое решение полностью корректно (см. соответствующий файл банка готовых решений ) и на долгое время я забыл о нём по принципу «решено, да и ладно».
Однако один из посетителей сайта заметил, что на самом деле здесь можно руководствоваться самыми что ни на есть банальными сочетаниями:
различных пар можно составить из соперников (кто играет белыми, кто чёрными - не важно)
.
Эквивалентной является задача о рукопожатиях: в отделе работает мужчин и каждый с каждым здоровается за руку, сколько рукопожатий они совершают? К слову, шахматисты тоже пожимают друг другу руку перед каждой партией.
Ну а вывода тут два:
Во-первых, не всё очевидное - очевидно;
И во-вторых, не бойтесь решать задачи «нестандартно»!
Большое спасибо за ваши письма, они помогают улучшить качество учебных материалов!
Размещения
Или «продвинутые» сочетания. Размещениями называют различные комбинации из объектов, которые выбраны из множества различных объектов, и которые отличаются друг от друга как составом объектов в выборке, так и их порядком . Количество размещений рассчитывается по формуле
Что наша жизнь? Игра:
Задача 5
Боря, Дима и Володя сели играть в «очко». Сколькими способами им можно сдать по одной карте? (колода содержит 36 карт)
Решение : ситуация похожа на Задачу 4, но отличается тем, что здесь важно не только то, какие три карты будут извлечены из колоды, но и то, КАК они будут распределены между игроками. По формуле размещений:
Способами можно раздать 3 карты игрокам.
Есть и другая схема решения, которая, с моей точки зрения, даже понятнее:
способами можно извлечь 3 карты из колоды.
Теперь давайте рассмотрим, какую-нибудь одну из семи тысяч ста сорока комбинаций, например: король пик, 9 червей, 7 червей. Выражаясь комбинаторной терминологией, эти 3 карты можно «переставить» между Борей, Димой и Володей способами:
КП, 9Ч, 7Ч;
КП, 7Ч, 9Ч;
9Ч, КП, 7Ч;
9Ч, 7Ч, КП;
7Ч, КП, 9Ч;
7Ч, 9Ч, КП.
И аналогичный факт справедлив для любого уникального набора из 3-х карт. А таких наборов, не забываем, мы насчитали . Не нужно быть профессором, чтобы понять, что найденное количество сочетаний следует умножить на шесть:
Способами можно сдать по одной карте 3-м игрокам.
По существу, получилась наглядная проверка формулы , окончательный смысл которой мы проясним в следующем параграфе.
Ответ : 42840
Возможно, у вас остался вопрос, а кто же раздавал карты? …Наверное, преподаватель =)
И чтобы никому не было обидно, в следующей задаче примет участие вся студенческая группа:
Задача 6
В студенческой группе 23 человека. Сколькими способами можно выбрать старосту и его заместителя?
Задача о «размещении» должностей в коллективе встречается очень часто и является самым настоящим баяном. Краткое решение и ответ в конце урока.
Аналоги комбинаторных концепций и методов используются и в топологии, при изучении дерева принятия решений, частично упорядоченных множеств, раскрасок графа и др.
25) Что называют перестановками?
Перестановки - различные упорядоченные множества, которые отличаются лишь порядком элементов (т.е. могут быть получены из того же самого множества).
26) По какой формуле вычисляют число перестановок из n различных элементов?
Перестановки. Возьмём n различных элементов: a 1 , a 2 , a 3 , …, a n . Будем переставлять их всеми возможными способами, сохраняя их количество и меняя лишь порядок их расположения. Каждая из полученных таким образом комбинаций называетсяперестановкой. Общее количество перестановок из n элементов обозначается P n . Это число равно произведению всех целых чисел от 1 до n :
Символ n ! (называется факториал ) - сокращённая запись произведения: 1 · 2 · 3 · … · (n – 1) · n .
П р и м е р. Найти число перестановок из трёх элементов: a , b , c .
Р е ш е н и е. В соответствии с приведенной формулой: P
3 = 1 · 2 · 3 = 6.
Действительно, мы имеем 6 перестановок: abc, acb, bac, bca, cab, cba.
27) Что называют размещениями? Запишите формулу, по которой вычисляют число размещений из n элементов по m.
Размещения - это упрядоченные подмножества данного конечного множества.
Размещения. Будем составлять группы из m n элементов, располагая эти m взятых элементов в различном порядке. Полученные комбинации называются размещениями из n элементов по m .
Их общее количество обозначается: и равно произведению:
П р и м е р. Найти число размещений из четырёх элементов a, b, c, d по два.
Р е ш е н и е. В соответствии с формулой получим:
Вот эти размещения: ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, dc.
28) Что называют сочетаниями? Запишите формулу, по которой вычисляют число сочетаний из n элементов по m.
Сочетание без повторений из n элементов по m есть m -элементное подмножество некоторого n -элементного множества.
Коротко такие сочетания называют "сочетания из m по n " и их число обозначают или . Далее n -элементное множество будем обозначать как n -множество.
Сочетания. Будем составлять группы из m различных элементов, взятых из множества, состоящего из n элементов, не принимая во внимание порядок расположения этих m элементов. Тогда мы получим сочетания из n элементов по m .
Их общее количество обозначается и может быть вычислено по формуле:
Из этой формулы ясно, что
Заметим, что можно составить только одно сочетание из n элементов по n , которое содержит все n элементов. Формула числа сочетаний даёт это значение, если только принять, что 0! = 1 , что является определением 0! .
В соответствии с этим определением получим:
Общее число сочетаний можно вычислить, пользуясь и другим выражением:
П р и м е р. Найти число сочетаний из пяти элементов: a, b, c, d, e по три.
Р е ш е н и е:
Эти сочетания: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde.
29) По какой формуле вычисляется число перестановок из n элементов, если элементы повторяются?
Перестановками из n элементов называются размещения из этих n элементов по n (Перестановки - частный случай размещений).
Число перестановок без повторений (n
Пример . Возьмем буквы Б, А, Р . Какие перестановки из этих букв можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) буква А повторяется два раза?
Решение.
1. Получатся наборы: БАР, БРА, АРБ, АБР, РАБ, РБА.
По формуле (3.3) получаем: 
наборов.
2. Получатся наборы: БАРА, БРАА, БААР, ААРБ, ААБР, АБАР, АРАБ, АРБА, АБРА, РАБА, РААБ, РБАА.
По формуле (3.4) получаем: 
наборов.
Пример . Сколько шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5 так, чтобы цифры в числе не повторялись?
Решение. Из данных шести цифр можно составить Р 6 = 6! = 720 перестановок. Но числа, начинающиеся на нуль, не являются шестизначными. Такие числа отличаются друг от друга перестановкой пяти остальных цифр, значит, их будет Р 5 = 120. Поэтому шестизначных чисел будет 720 - 120 = 600 чисел.
Пример . Сколькими способами можно расставить белые фигуры (2 ладьи, 2 коня, 2 слона, ферзь и король) на первой линии шахматной доски?
Решение. Первая линия шахматной доски представляет собой 8 клеток, на которых и надо расположить эти 8 фигур. Различные варианты расположения будут отличаться только порядком фигур, значит, это будут перестановки с повторениями Р 8 (2,2,2).
По формуле (3.4) получаем: способов.
30) Какой формулой определяется число размещений с повторениями из n элементов по m элементов?
Размещения
Размещениями из n элементов по m элементов (m < n ) называются комбинации, составленные из данных n элементов по m элементов, которые отличаются либо самими элементами, либо порядком элементов.
Число размещений без повторений из n по m (n различных элементов) вычисляется по формуле:
Пример . Возьмем буквы Б, А, Р . Какие размещения из этих букв, взятых по две, можно получить? Сколько таких наборов получиться, если: 1) буквы в наборе не повторяются; 2) буквы могут повторяться?
Решение.
1. Получатся следующие наборы: БА, БР, АР, АБ, РБ, РА .
По формуле (3.1) получаем: 
наборов.
2. Получатся наборы: ББ, БА, БР, АА, АБ, АР, РР, РБ, РА.
По формуле (3.2) получаем: наборов.
Пример. Вдоль дороги стоят 6 светофоров. Сколько может быть различных комбинаций их сигналов, если каждый светофор имеет 3 состояния: "красный", "желтый", "зеленый"?
Решение. Выпишем несколько комбинаций: КККЖЗЗ, ЗЗЗЗЗЗ, КЖЗКЖЗ... Мы видим, что состав выборки меняется и порядок элементов существенен (ведь если, например, в выборке КЖЗКЖЗ поменять местами К и Ж, ситуация на дороге будет другой). Поэтому применяем формулу (3.2) и вычисляем число размещений с повторениями из 3 по 6, получаем комбинаций.
31) Какой формулой определяется число сочетаний с повторениями из n элементов по m элементов?
Сочетания
Сочетаниями из n элементов по m элементов называются комбинации, составленные из данных n элементов по m элементов, которые различаются хотя бы одним элементом (отличие сочетаний от размещений в том, что в сочетаниях не учитывается порядок элементов).
Число сочетаний без повторений (n различных элементов, взятых по m ) вычисляется по формуле:
Пример . Возьмем буквы Б, А, Р . Какие сочетания из этих букв, взятых по две, можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) можно брать по два одинаковые буквы.
Решение .
1. Получатся наборы: БА (БА и АБ - один и тот же набор), АР и РБ
По формуле (3.5) получаем: 
наборов.
2. Получатся наборы: ББ, БА, БР, АА, АР, РР.
По формуле (3.6) получаем: наборов.
Пример . Из 20 учащихся надо выбрать двух дежурных. Сколькими способами это можно сделать?
Решение. Надо выбрать двух человек из 20. Ясно, что от порядка выбора ничего не зависит, то есть Иванов-Петров или Петров-Иванов - это одна и та же пара дежурных. Следовательно, это будут сочетания из 20 по 2.
По формуле (3.5) получаем: 
способов.
Пример . В хлебном отделе имеются булки белого и черного хлеба. Сколькими способами можно купить 6 булок хлеба?
Решение. Обозначая булки белого и черного хлеба буквами Б и Ч, составим несколько выборок: ББББББ, ББЧЧББ, ЧЧЧЧЧБ, ... Состав меняется от выборки к выборке, порядок элементов несущественен, значит это - сочетания с повторениями из 2 по 6. По формуле (3.6) получаем способов.
Cделаем проверку и выпишем все варианты покупки: ББББББ, БББББЧ, ББББЧЧ, БББЧЧЧ, ББЧЧЧЧ, БЧЧЧЧЧ, ЧЧЧЧЧЧ. Их действительно 7.
32) Что называют суммой двух событий?
Суммойдвух событийи
называют событие, состоящее в появлении события , или события , или обоих этих событий.
Суммой нескольких событий
называют событие, состоящее в появлении хотя бы одного из этих событий.
33) Что называют произведением двух событий?
Произведением двух событийи называют событие , состоящее в совместном появлении этих событий.
34) Чему равна вероятность суммы двух несовместных событий?
Событие
называют независимым от события
, если появление события не меняет вероятности появления события , то есть если условная вероятность события равна его безусловной вероятности:
.
Свойство независимости событий взаимно: если событие не зависит от события , то и событие не зависит от события .
Теорема.
Вероятность совместного появления двух независимых событий равна произведению вероятности этих событий:
.
Несколько событий называют попарно независимыми
, если каждые два из них независимы.
Несколько событий называют независимыми в совокупности
, если независимы каждые два из них и независимы каждое событие и все возможные произведения остальных.
35) Сформулируйте теорему сложения?
Вероятность р (А + В ) суммы событий А и В равна
Р (А + В ) = р (А ) + р (В ) – р (АВ ). (2.2)
Доказательство.
Докажем теорему сложения для схемы случаев. Пусть п – число возможных исходов опыта, т А – число исходов, благоприятных событию А , т В – число исходов, благопри-ятных событию В , а т АВ – число исходов опыта, при которых происходят оба события (то есть исходов, благоприятных произведению АВ ). Тогда число исходов, при которых имеет место событие А + В , равно т А + т В – т АВ (так как в сумме (т А + т В ) т АВ учтено дважды: как исходы, благоприятные А , и исходы, благоприятные В ). Следовательно, вероятность суммы можно определить по формуле 2,2 что и требовалось доказать.
Loading...