Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиальновозможное количество различных вариантов развития событий.
Пусть имеется 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 элементов. Это множество в комбинаторике называется генеральной совокупностью .
Определение 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}.
Число сочетаний обозначается C n m и вычисляется по формуле:
Пример 7. Сколькими способами читатель может выбрать две книжки из шести имеющихся?
Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:
Определение 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. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?
Цель занятия: уметь применять основные формулы комбинаторики и знать условия применения этих формул; знать свойства биномиальных коэффициентов и уметь определять разложение бинома при конкретных значениях 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 элементов.
Задача
: Найти все возможные перестановки для последовательности чисел 1, 2, 3.
Существуют следующие перестановки:
1:
1 2 3
2:
1 3 2
3:
2 1 3
4:
2 3 1
5:
3 1 2
6:
3 2 1
Количество перестановок для N различных элементов составляет N! . Действительно:
Рассмотрим задачу получения всех перестановок чисел 1…N (то есть последовательности длины N ), где каждое из чисел входит ровно по 1 разу. Существует множество вариантов порядка получения перестановок. Однако наиболее часто решается задача генерации перестановок в лексикографическом порядке (см. пример выше). При этом все перестановки сортируются сначала по первому числу, затем по второму и т.д. в порядке возрастания. Таким образом, первой будет перестановка 1 2 … N , а последней — N N-1 … 1 .
Рассмотрим алгоритм решения задачи. Дана исходная последовательность чисел. Для получения каждой следующей перестановки необходимо выполнить следующие шаги:
Таким образом мы получим новую последовательность, которая будет рассматриваться в качестве исходной на следующем шаге.
Реализация на С++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include
using
namespace
std;
{
int
s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int
*a, int
n)
{
int
j = n - 2;
while
(j != -1 && a[j] >= a) j--;
if
(j == -1)
return
false; // больше перестановок нет
int
k = n - 1;
while
(a[j] >= a[k]) k--;
swap(a, j, k);
int
l = j + 1, r = n - 1;
while
(l
return
true;
}
void
Print(int
*a, int
n) // вывод перестановки
{
static int
num = 1; // номер перестановки
cout.width(3);
cout <<
num++ <<
": "
;
for
(int
i = 0; i < n; i++)
cout <<
a[i] <<
" "
;
cout <<
endl;
}
int
main()
{
int
n, *a;
cout <<
"N = "
;
cin >>
n;
a = new
int
[n];
for
(int
i = 0; i < n; i++)
a[i] = i + 1;
Print(a, n);
while
(NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return
0;
}
Результат выполнения
Особого внимания заслуживает задача генерации перестановок N элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n 1 , n 2 ... n k , где элемент n 1 повторяется r 1 раз, n 2 повторяется r 2 раз и т.д. При этом n 1 +n 2 +...+n k =N . Если мы будем считать все n 1 +n 2 +...+n k элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n 1 +n 2 +...+n k)! . Однако среди этих перестановок не все различны. В самом деле, все r 1 элементов n 1 мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n 2 , n 3 и т. д. В итоге имеем r 1 ! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n 1 . Таким образом, всякая перестановка может быть записана r 1 !·r 2 !·...·r k ! способами. Следовательно, число различных перестановок с повторениями равно
Для генерации перестановок с повторениями можно использовать алгоритм генерации перестановок без повторений, приведенный выше. Введем повторяющийся элемент в массив a. Ниже приведен код программы для генерации перестановок с повторениями (изменен только код функции main()
).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include
using
namespace
std;
void
swap(int
*a, int
i, int
j)
{
int
s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int
*a, int
n)
{
int
j = n - 2;
while
(j != -1 && a[j] >= a) j--;
if
(j == -1)
return
false; // больше перестановок нет
int
k = n - 1;
while
(a[j] >= a[k]) k--;
swap(a, j, k);
int
l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
while
(l
return
true;
}
void
Print(int
*a, int
n) // вывод перестановки
{
static int
num = 1; // номер перестановки
cout.width(3); // ширина поля вывода номера перестановки
cout <<
num++ <<
": "
;
for
(int
i = 0; i < n; i++)
cout <<
a[i] <<
" "
;
cout <<
endl;
}
int
main()
{
int
n, *a;
cout <<
"N = "
;
cin >>
n;
a = new
int
[n];
for
(int
i = 0; i < n; i++)
a[i] = i + 1;
a = 1; // повторяющийся элемент
Print(a, n);
while
(NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
return
0;
}
Результат работы приведенного выше алгоритма:
Следует отметить, что комбинаторика является самостоятельным разделом высшей математики (а не частью тервера) и по данной дисциплине написаны увесистые учебники, содержание которых, порой, ничуть не легче абстрактной алгебры. Однако нам будет достаточно небольшой доли теоретических знаний, и в данной статье я постараюсь в доступной форме разобрать основы темы с типовыми комбинаторными задачами. А многие из вас мне помогут;-)
Чем будем заниматься? В узком смысле комбинаторика – это подсчёт различных комбинаций, которые можно составить из некоторого множества дискретных объектов. Под объектами понимаются какие-либо обособленные предметы или живые существа – люди, звери, грибы, растения, насекомые и т.д. При этом комбинаторику совершенно не волнует, что множество состоит из тарелки манной каши, паяльника и болотной лягушки. Принципиально важно, что эти объекты поддаются перечислению – их три (дискретность) и существенно то, что среди них нет одинаковых.
С множеством разобрались, теперь о комбинациях. Самыми распространёнными видами комбинаций являются перестановки объектов, их выборка из множества (сочетание) и распределение (размещение). Давайте прямо сейчас посмотрим, как это происходит:
Не пугайтесь малопонятных терминов, тем более, некоторые из них действительно не очень удачны. Начнём с хвоста заголовка – что значит «без повторений »? Это значит, что в данном параграфе будут рассматриваться множества, которые состоят из различных объектов. Например, … нет, кашу с паяльником и лягушкой предлагать не буду, лучше что-нибудь повкуснее =) Представьте, что перед вами на столе материализовалось яблоко, груша и банан (при наличии таковых ситуацию можно смоделировать и реально). Выкладываем фрукты слева направо в следующем порядке:
яблоко / груша / банан
Вопрос первый : сколькими способами их можно переставить?
Одна комбинация уже записана выше и с остальными проблем не возникает:
яблоко / банан / груша
груша / яблоко / банан
груша / банан / яблоко
банан / яблоко / груша
банан / груша / яблоко
Итого : 6 комбинаций или 6 перестановок .
Хорошо, здесь не составило особого труда перечислить все возможные случаи, но как быть, если предметов больше? Уже с четырьмя различными фруктами количество комбинаций значительно возрастёт!
Пожалуйста, откройте справочный материал (методичку удобно распечатать) и в пункте № 2 найдите формулу количества перестановок.
Никаких мучений – 3 объекта можно переставить способами.
Вопрос второй : сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт?
Зачем выбирать? Так нагуляли же аппетит в предыдущем пункте – для того, чтобы съесть! =)
а) Один фрукт можно выбрать, очевидно, тремя способами – взять либо яблоко, либо грушу, либо банан. Формальный подсчёт проводится по формуле количества сочетаний
:
Запись в данном случае следует понимать так: «сколькими способами можно выбрать 1 фрукт из трёх?»
б) Перечислим все возможные сочетания двух фруктов:
яблоко и груша;
яблоко и банан;
груша и банан.
Количество комбинаций легко проверить по той же формуле:
Запись понимается аналогично: «сколькими способами можно выбрать 2 фрукта из трёх?».
в) И, наконец, три фрукта можно выбрать единственным способом:
Кстати, формула количества сочетаний сохраняет смысл и для пустой выборки:
способом можно выбрать ни одного фрукта – собственно, ничего не взять и всё.
г) Сколькими способами можно взять хотя бы один
фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта или все 3 фрукта:
способами можно выбрать хотя бы один фрукт.
Читатели, внимательно изучившие вводный урок по теории вероятностей , уже кое о чём догадались. Но о смысле знака «плюс» позже.
Для ответа на следующий вопрос мне требуется два добровольца… …Ну что же, раз никто не хочет, тогда буду вызывать к доске =)
Вопрос третий : сколькими способами можно раздать по одному фрукту Даше и Наташе?
Для того чтобы раздать два фрукта, сначала нужно их выбрать. Согласно пункту «бэ» предыдущего вопроса, сделать это можно способами, перепишу их заново:
яблоко и груша;
яблоко и банан;
груша и банан.
Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов:
яблоком можно угостить Дашу, а грушей – Наташу;
либо наоборот – груша достанется Даше, а яблоко – Наташе.
И такая перестановка возможна для каждой пары фруктов.
Рассмотрим ту же студенческую группу, которая пошла на танцы. Сколькими способами можно составить пару из юноши и девушки?
Способами можно выбрать 1 юношу;
способами можно выбрать 1 девушку.
Таким образом, одного юношу и
одну девушку можно выбрать: 
способами.
Когда из каждого множества выбирается по 1 объекту, то справедлив следующий принцип подсчёта комбинаций: «каждый объект из одного множества может составить пару с каждым объектом другого множества».
То есть, Олег может пригласить на танец любую из 13 девушек, Евгений – тоже любую из тринадцати, и аналогичный выбор есть у остальных молодых людей. Итого: возможных пар.
Следует отметить, что в данном примере не имеет значения «история» образования пары; однако если принять во внимание инициативу, то количество комбинаций нужно удвоить, поскольку каждая из 13 девушек тоже может пригласить на танец любого юношу. Всё зависит от условия той или иной задачи!
Похожий принцип справедлив и для более сложных комбинаций, например: сколькими способами можно выбрать двух юношей и двух девушек для участия в сценке КВН?
Союз И недвусмысленно намекает, что комбинации необходимо перемножить:
Возможных групп артистов.
Иными словами, каждая пара юношей (45 уникальных пар) может выступать с любой парой девушек (78 уникальных пар). А если рассмотреть распределение ролей между участниками, то комбинаций будет ещё больше. …Очень хочется, но всё-таки воздержусь от продолжения, чтобы не привить вам отвращение к студенческой жизни =).
Правило умножения комбинаций распространяется и на бОльшее количество множителей:
Задача 8
Сколько существует трёхзначных чисел, которые делятся на 5?
Решение : для наглядности обозначим данное число тремя звёздочками: ***
В разряд сотен можно записать любую из цифр (1, 2, 3, 4, 5, 6, 7, 8 или 9). Ноль не годится, так как в этом случае число перестаёт быть трёхзначным.
А вот в разряд десятков («посерединке») можно выбрать любую из 10 цифр: .
По условию, число должно делиться на 5. Число делится на 5, если оно заканчивается на 5 либо на 0. Таким образом, в младшем разряде нас устраивают 2 цифры.
Итого, существует : трёхзначных чисел, которые делятся на 5.
При этом произведение расшифровывается так: «9 способами можно выбрать цифру в разряд сотен и 10 способами выбрать цифру в разряд десятков и 2 способами в разряд единиц »
Или ещё проще: «каждая из 9 цифр в разряде сотен комбинируется с каждой из 10 цифр разряда десятков и с каждой из двух цифр в разряде единиц ».
Ответ : 180
А теперь…
Да, чуть не забыл об обещанном комментарии к задаче № 5, в которой Боре, Диме и Володе можно сдать по одной карте способами. Умножение здесь имеет тот же смысл: способами можно извлечь 3 карты из колоды И в каждой выборке переставить их способами.
А теперь задача для самостоятельного решения… сейчас придумаю что-нибудь поинтереснее, …пусть будет про ту же русскую версию блэкджека:
Задача 9
Сколько существует выигрышных комбинаций из 2 карт при игре в «очко»?
Для тех, кто не знает: выигрывает комбинация 10 + ТУЗ (11 очков) = 21 очко и, давайте будем считать выигрышной комбинацию из двух тузов.
(порядок карт в любой паре не имеет значения)
Краткое решение и ответ в конце урока.
Кстати, не надо считать пример примитивным. Блэкджек – это чуть ли не единственная игра, для которой существует математически обоснованный алгоритм, позволяющий выигрывать у казино. Желающие могут легко найти массу информации об оптимальной стратегии и тактике. Правда, такие мастера довольно быстро попадают в чёрный список всех заведений =)
Пришло время закрепить пройденный материал парой солидных задач:
Задача 10
У Васи дома живут 4 кота.
а) сколькими способами можно рассадить котов по углам комнаты?
б) сколькими способами можно отпустить гулять котов?
в) сколькими способами Вася может взять на руки двух котов (одного на левую, другого – на правую)?
Решаем : во-первых, вновь следует обратить внимание на то, что в задаче речь идёт о разных объектах (даже если коты – однояйцовые близнецы). Это очень важное условие!
а) Молчание котов. Данной экзекуции подвергаются сразу все коты
+ важно их расположение, поэтому здесь имеют место перестановки:
способами можно рассадить котов по углам комнаты.
Повторюсь, что при перестановках имеет значение лишь количество различных объектов и их взаимное расположение. В зависимости от настроения Вася может рассаживать животных полукругом на диване, в ряд на подоконнике и т.д. – перестановок во всех случаях будет 24. Желающие могут для удобства представить, что коты разноцветные (например, белый, чёрный, рыжий и полосатый) и перечислить все возможные комбинации.
б) Сколькими способами можно отпустить гулять котов?
Предполагается, что коты ходят гулять только через дверь, при этом вопрос подразумевает безразличие по поводу количества животных – на прогулку могут выйти 1, 2, 3 или все 4 кота.
Считаем все возможные комбинации:
Способами можно отпустить гулять одного кота (любого из четырёх);
способами можно отпустить гулять двух котов (варианты перечислите самостоятельно);
способами можно отпустить гулять трёх котов (какой-то один из четырёх сидит дома);
способом можно выпустить всех котов.
Наверное, вы догадались, что полученные значения следует просуммировать:
способами можно отпустить гулять котов.
Энтузиастам предлагаю усложнённую версию задачи – когда любой кот в любой выборке случайным образом может выйти на улицу, как через дверь, так и через окно 10 этажа. Комбинаций заметно прибавится!
в) Сколькими способами Вася может взять на руки двух котов?
Ситуация предполагает не только выбор 2 животных, но и их размещение по рукам:
способами можно взять на руки 2 котов.
Второй вариант решения: способами можно выбрать двух котов и
способами посадить каждую
пару на руки: 
Ответ : а) 24, б) 15, в) 12
Ну и для очистки совести что-нибудь поконкретнее на умножение комбинаций…. Пусть у Васи дополнительно живёт 5 кошек =) Сколькими способами можно отпустить гулять 2 котов и 1 кошку?
То есть, с каждой парой котов можно выпустить каждую кошку.
Ещё один баян для самостоятельного решения:
Задача 11
В лифт 12-этажного дома сели 3 пассажира. Каждый независимо от других с одинаковой вероятностью может выйти на любом (начиная со 2-го) этаже. Сколькими способами:
1) пассажиры могут выйти на одном и том же этаже (порядок выхода не имеет значения)
;
2) два человека могут выйти на одном этаже, а третий – на другом;
3) люди могут выйти на разных этажах;
4) пассажиры могут выйти из лифта?
И тут часто переспрашивают, уточняю: если 2 или 3 человека выходят на одном этаже, то очерёдность выхода не имеет значения. ДУМАЙТЕ, используйте формулы и правила сложения/умножения комбинаций. В случае затруднений пассажирам полезно дать имена и порассуждать, в каких комбинациях они могут выйти из лифта. Не нужно огорчаться, если что-то не получится, так, например, пункт № 2 достаточно коварен.
Полное решение с подробными комментариями в конце урока.
Заключительный параграф посвящён комбинациям, которые тоже встречаются достаточно часто – по моей субъективной оценке, примерно в 20-30% комбинаторных задач:
Перечисленные виды комбинаций законспектированы в пункте № 5 справочного материала Основные формулы комбинаторики , однако некоторые из них по первому прочтению могут быть не очень понятными. В этом случае сначала целесообразно ознакомиться с практическими примерами, и только потом осмысливать общую формулировку. Поехали:
В перестановках с повторениями, как и в «обычных» перестановках, участвует сразу всё множество объектов , но есть одно но: в данном множестве один или бОльшее количество элементов (объектов) повторяются. Встречайте очередной стандарт:
Задача 12
Сколько различных буквосочетаний можно получить перестановкой карточек со следующими буквами: К, О, Л, О, К, О, Л, Ь, Ч, И, К?
Решение : в том случае, если бы все буквы были различны, то следовало бы применить тривиальную формулу , однако совершенно понятно, что для предложенного набора карточек некоторые манипуляции будут срабатывать «вхолостую», так, например, если поменять местами любые две карточки с буквами «К» в любом слове, то получится то же самое слово. Причём, физически карточки могут сильно отличаться: одна быть круглой с напечатанной буквой «К», другая – квадратной с нарисованной буквой «К». Но по смыслу задачи даже такие карточки считаются одинаковыми , поскольку в условии спрашивается о буквосочетаниях.
Всё предельно просто – всего: 11 карточек, среди которых буква:
К – повторяется 3 раза;
О – повторяется 3 раза;
Л – повторяется 2 раза;
Ь – повторяется 1 раз;
Ч – повторяется 1 раз;
И – повторяется 1 раз.
Проверка: 3 + 3 + 2 + 1 + 1 + 1 = 11, что и требовалось проверить.
По формуле количества перестановок с повторениями
:
различных буквосочетаний можно получить. Больше полумиллиона!
Для быстрого расчёта большого факториального значения удобно использовать стандартную функцию Экселя: забиваем в любую ячейку =ФАКТР(11) и жмём Enter .
На практике вполне допустимо не записывать общую формулу и, кроме того, опускать единичные факториалы:
Но предварительные комментарии о повторяющихся буквах обязательны!
Ответ : 554400
Другой типовой пример перестановок с повторениями встречается в задаче о расстановке шахматных фигур, которую можно найти на складе готовых решений в соответствующей pdf-ке. А для самостоятельного решения я придумал менее шаблонное задание:
Задача 13
Алексей занимается спортом, причём 4 дня в неделю – лёгкой атлетикой, 2 дня – силовыми упражнениями и 1 день отдыхает. Сколькими способами он может составить себе расписание занятий на неделю?
Формула здесь не годится, поскольку учитывает совпадающие перестановки (например, когда меняются местами силовые упражнения в среду с силовыми упражнениями в четверг). И опять – по факту те же 2 силовые тренировки могут сильно отличаться друг от друга, но по контексту задачи (с точки зрения расписания) они считаются одинаковыми элементами.
Двухстрочное решение и ответ в конце урока.
Характерная особенность этого вида комбинаций состоит в том, что выборка проводится из нескольких групп, каждая из которых состоит из одинаковых объектов.
Сегодня все хорошо потрудились, поэтому настало время подкрепиться:
Задача 14
В студенческой столовой продают сосиски в тесте, ватрушки и пончики. Сколькими способами можно приобрести пять пирожков?
Решение : сразу обратите внимание на типичный критерий сочетаний с повторениями – по условию на выбор предложено не множество объектов как таковое, а различные виды объектов; при этом предполагается, что в продаже есть не менее пяти хот-догов, 5 ватрушек и 5 пончиков. Пирожки в каждой группе, разумеется, отличаются – ибо абсолютно идентичные пончики можно смоделировать разве что на компьютере =) Однако физические характеристики пирожков по смыслу задачи не существенны, и хот-доги / ватрушки / пончики в своих группах считаются одинаковыми.
Что может быть в выборке? Прежде всего, следует отметить, что в выборке обязательно будут одинаковые пирожки (т.к. выбираем 5 штук, а на выбор предложено 3 вида). Варианты тут на любой вкус: 5 хот-догов, 5 ватрушек, 5 пончиков, 3 хот-дога + 2 ватрушки, 1 хот-дог + 2 + ватрушки + 2 пончика и т.д.
Как и при «обычных» сочетаниях, порядок выбора и размещение пирожков в выборке не имеет значения – просто выбрали 5 штук и всё.
Используем формулу 
количества сочетаний с повторениями:
способом можно приобрести 5 пирожков.
Приятного аппетита!
Ответ : 21
Какой вывод можно сделать из многих комбинаторных задач?
Порой, самое трудное – это разобраться в условии.
Аналогичный пример для самостоятельного решения:
Задача 15
В кошельке находится достаточно большое количество 1-, 2-, 5- и 10-рублёвых монет. Сколькими способами можно извлечь три монеты из кошелька?
В целях самоконтроля ответьте на пару простых вопросов:
1) Могут ли в выборке все монеты быть разными?
2) Назовите самую «дешевую» и самую «дорогую» комбинацию монет.
Решение и ответы в конце урока.
Из моего личного опыта, могу сказать, что сочетания с повторениями – наиболее редкий гость на практике, чего не скажешь о следующем виде комбинаций:
Из множества, состоящего из элементов, выбирается элементов, при этом важен порядок элементов в каждой выборке. И всё бы было ничего, но довольно неожиданный прикол заключается в том, что любой объект исходного множества мы можем выбирать сколько угодно раз. Образно говоря, от «множества не убудет».
Когда так бывает? Типовым примером является кодовый замок с несколькими дисками, но по причине развития технологий актуальнее рассмотреть его цифрового потомка:
Задача 16
Сколько существует четырёхзначных пин-кодов?
Решение : на самом деле для разруливания задачи достаточно знаний правил комбинаторики: способами можно выбрать первую цифру пин-кода и способами – вторую цифру пин-кода и столькими же способами – третью и столькими же – четвёртую. Таким образом, по правилу умножения комбинаций, четырёхзначный пин-код можно составить: способами.
А теперь с помощью формулы. По условию нам предложен набор из цифр, из которого выбираются цифры и располагаются в определенном порядке
, при этом цифры в выборке могут повторяться (т.е. любой цифрой исходного набора можно пользоваться произвольное количество раз)
. По формуле количества размещений с повторениями: 
Ответ : 10000
Что тут приходит на ум… …если банкомат «съедает» карточку после третьей неудачной попытки ввода пин-кода, то шансы подобрать его наугад весьма призрачны.
И кто сказал, что в комбинаторике нет никакого практического смысла? Познавательная задача для всех читателей сайт:
Задача 17
Согласно государственному стандарту, автомобильный номерной знак состоит из 3 цифр и 3 букв. При этом недопустим номер с тремя нулями, а буквы выбираются из набора А, В, Е, К, М, Н, О, Р, С, Т, У, Х (используются только те буквы кириллицы, написание которых совпадает с латинскими буквами) .
Сколько различных номерных знаков можно составить для региона?
Не так их, кстати, и много. В крупных регионах такого количества не хватает, и поэтому для них существуют по несколько кодов к надписи RUS.
Решение и ответ в конце урока. Не забываем использовать правила комбинаторики;-) …Хотел похвастаться эксклюзивом, да оказалось не эксклюзивом =) Заглянул в Википедию – там есть расчёты, правда, без комментариев. Хотя в учебных целях, наверное, мало кто прорешивал.
Наше увлекательное занятие подошло к концу, и напоследок я хочу сказать, что вы не зря потратили время – по той причине, что формулы комбинаторики находят ещё одно насущное практическое применение: они встречаются в различных задачах по теории вероятностей
,
и в задачах на классическое определение вероятности
– особенно часто =)
Всем спасибо за активное участие и до скорых встреч!
Решения и ответы :
Задача 2: Решение
: найдём количество всех возможных перестановок 4 карточек:
Когда карточка с нулём располагается на 1-м месте, то число становится трёхзначным, поэтому данные комбинации следует исключить. Пусть ноль находится на 1-м месте, тогда оставшиеся 3 цифры в младших разрядах можно переставить способами.
Примечание
: т.к. карточек немного, то здесь несложно перечислить все такие варианты:
0579
0597
0759
0795
0957
0975
Таким образом, из предложенного набора можно составить:
24 – 6 = 18 четырёхзначных чисел
Ответ
: 18
Задача 4: Решение
: способами можно выбрать 3 карты из 36.
Ответ
: 7140
Задача 6: Решение
: 
способами.
Другой вариант решения
: способами можно выбрать двух человек из группы и
и
2) Самый «дешёвый» набор содержит 3 рублёвые монеты, а самый «дорогой» – 3 десятирублёвые.
Задача 17: Решение
: 
способами можно составить цифровую комбинацию автомобильного номера, при этом одну из них (000) следует исключить: .
способами можно составить буквенную комбинацию автомобильного номера.
По правилу умножения комбинаций, всего можно составить:
автомобильных номера
(каждая
цифровая комбинация сочетается с каждой
буквенной комбинацией).
Ответ
: 1726272
Перестановки. Формула для числа перестановок
Перестановки из n элементов
Пусть множество Х состоит из n элементов.
Определение. Размещение без повторений из n элементов множества X по n называется перестановкой из n элементов.
Заметим, что в любую перестановку входят все элементы множества Х , причём ровно по одному разу. То есть перестановки одна от другой отличаются только порядком следования элементов и могут получиться одна из другой перестановкой элементов (отсюда и название).
Число всех перестановок из n элементов обозначается символом .
Так как перестановки – это частный случай размещений без повторений при , то формулу для нахождения числа получим из формулы (2), подставляя в неё :
Таким образом,
(3)
Пример. Сколькими способами можно разместить на полке 5 книг?
Решение. Способов размещения книг на полке существует столько, сколько существует различных перестановок из пяти элементов: способов.
Замечание. Формулы (1)-(3) запоминать не обязательно: задачи на их применение всегда можно решить с помощью правила произведения. Если у учащихся существуют проблемы с составлением комбинаторных моделей задач, то лучше сделать более узким множество используемых формул и правил (чтобы было меньше возможности ошибиться). Правда, задачи, в которых используются перестановки и формула (3), обычно решаются без особых проблем.
Задачи
1. Ф. Сколькими способами могут встать в очередь в билетную кассу: 1) 3 человека; 2) 5 человек?
Решение.
Различные варианты расположения п человек в очереди отличаются один от другого только порядком расположения людей, т. е. являются различными перестановками из п элементов.
Три человека могут встать в очередь Р3 = 3! = 6 различными способами.
Ответ: 1) 6 способов; 2) 120 способов.
2. Т. Сколькими способами 4 человека могут разместиться на четырехместной скамейке?
Решение.
Количество человек равно количеству мест на скамейке, поэтому количество способов размещения равно числу перестановок из 4 элементов: Р4 = 4! = 24.
Можно рассуждать по правилу произведения: для первого человека можно выбрать любое из 4 мест, для второго - любое из 3 оставшихся, для третьего - любое из 2 оставшихся, последний займет 1 оставшееся место; всего есть = 24 разных способов Размещения 4 человек на четырехместной скамейке.
Ответ: 24 способами.
3. М. У Вовы на обед - первое, второе, третье блюда и пирожное. Он обязательно начнет с пирожного, а все остальное съест в произвольном порядке. Найдите число возможных вариантов обеда.
М- задачи из уч. пособия А.Г.Мордковича
Т- под ред. С.А.Теляковского
Ф- М.В.Ткачевой
Решение.
После пирожного Вова может выбрать любое из трех блюд, затем - из двух, и закончить оставшимся. Общее число возможных вариантов обеда: =6.
Ответ: 6.
4. Ф. Сколько различных правильных (с точки зрения русского языка) фраз можно составить, изменяя порядок слов в предложении: 1) «Я пошел гулять»; 2) «Во дворе гуляет кошка»?
Решение.
Во втором предложении предлог «во» должен всегда стоять перед существительным «дворе», к которому он относится. Поэтому, считая пару «во дворе» за одно слово, можно найти количество различных перестановок трех условных слов: Р3 = 3! = 6. Таким образом, и в этом случае можно составить 6 правильных предложений.
Ответ: 1) 6; 2) 6.
5. Сколькими способами можно с помощью букв К, L, М, Н обозначить вершины четырехугольника?
Решение.
Будем считать, что вершины четырехугольника пронумерованы, за каждой закреплен постоянный номер. Тогда задача сводится к подсчету числа разных способов расположения 4 букв на 4 местах (вершинах), т. е. к подсчету числа различных перестановок: Р4 = 4! =24 способа.
Ответ: 24 способа.
6. Ф. Четыре друга купили билеты в кино: на 1-е и 2-е места в первом ряду и на 1-е и 2-е места во втором ряду. Сколькими способами друзья могут занять эти 4 места в кинотеатре?
Решение.
Четыре друга могут занять 4 разных места Р4 = 4! = 24 различными способами.
Ответ: 24 способа.
7. Т. Курьер должен разнести пакеты в 7 различных учреждений. Сколько маршрутов может он выбрать?
Решение.
Под маршрутом следует понимать порядок посещения курьером учреждений. Пронумеруем учреждения номерами от 1 до 7, тогда маршрут будет представляться последовательностью из 7 Цифр, порядок которых может меняться. Количество маршрутов равно числу перестановок из 7 элементов: Р7= 7! = 5 040.
Ответ: 5 040 маршрутов.
8. Т. Сколько существует выражений, тождественно равных произведению abcde, которые получаются из него перестановкой множителей?
Решение.
Дано произведение пяти различных сомножителей abcde, порядок которых может меняться (при перестановке множителей произведение не меняется).
Всего существует Р5 = 5! = 120 различных способов расположения пяти множителей; один из них (abcde) считаем исходным, остальные 119 выражений тождественно равны данному.
Ответ: 119 выражений.
9. Т. Ольга помнит, что телефон подруги оканчивается цифрами 5, 7, 8, но забыла, в каком порядке эти цифры следуют. Укажите наибольшее число вариантов, которые ей придется перебрать, чтобы дозвониться подруге.
Решение.
Три последних цифры телефонного номера могут быть расположены в одном из Р3 =3! =6 возможных порядков, из которых только один верный. Ольга может сразу набрать верный вариант, может набрать его третьим, и т. д. Наибольшее число вариантов ей придется набрать, если правильный вариант окажется последним, т. е. шестым.
Ответ: 6 вариантов.
10. Т. Сколько шестизначных чисел (без повторения цифр) можно составить из цифр: а) 1,2, 5, 6, 7, 8; б) 0, 2, 5, 6, 7, 8? Решение.
а) Дано 6 цифр: 1, 2, 5, 6, 7, 8, из них можно составлять разные шестизначные числа, только переставляя эти цифры местами. Количество различных шестизначных чисел при этом равно Р6 = 6! = 720.
б) Дано 6 цифр: 0, 2, 5, 6, 7, 8, из них нужно составлять различные шестизначные числа. Отличие от предыдущей задачи состоит в том, что ноль не может стоять на первом месте.
Можно напрямую применить правило произведения: на первое место можно выбрать любую из 5 цифр (кроме нуля); на второе место - любую из 5 оставшихся цифр (4 «ненулевые» и теперь считаем ноль); на третье место - любую из 4 оставшихся после первых двух выборов цифр, и т. д. Общее количество вариантов равно: = 600.
Можно применить метод исключения лишних вариантов. 6 цифр можно переставить Р6 = 6! = 720 различными способами. Среди этих способов будут такие, в которых на первом месте стоит ноль, что недопустимо. Подсчитаем количество этих недопустимых вариантов. Если на первом месте стоит ноль (он фиксирован), то на последующих пяти местах могут стоять в произвольном порядке «ненулевые» цифры 2, 5, 6, 7, 8. Количество различных способов, которыми можно разместить 5 цифр на 5 местах, равно Р5 = 5! = 120, т. е. количество перестановок чисел, начинающихся с нуля, равно 120. Искомое количество различных шестизначных чисел в этом случае равно: Р6 - Р5 = 720 - 120 = 600.
Ответ: а) 720; б) 600 чисел.
11. Т. Сколько среди четырехзначных чисел (без повторения цифр), составленных из цифр 3, 5, 7, 9, таких, которые: а) начинаются с цифры 3;
б) кратны 15?
Решение.
а) Из цифр 3, 5, 7, 9 составляем четырехзначные числа, начинающиеся с цифры 3.
Фиксируем цифру 3 на первом месте; тогда на трех оставшихся местах в произвольном порядке могут располагаться цифры 5, 7 9 Общее количество вариантов их расположения равно Р 3 = 3!=6. Столько и будет разных четырехзначных чисел, составленных из данных цифр и начинающихся с цифры 3.
б) Заметим, что сумма данных цифр 3 + 5 + 7 + 9 = 24 делится на 3, следовательно, любое четырехзначное число, составленное из этих цифр, делится на 3. Для того, чтобы некоторые из этих чисел делились на 15, необходимо, чтобы они заканчивались цифрой 5.
Фиксируем цифру 5 на последнем месте; остальные 3 цифры можно разместить на трех местах перед 5 Рз = 3! = 6 различными способами. Столько и будет разных четырехзначных чисел, составленных из данных цифр, которые делятся на 15.
Ответ: а) 6 чисел; б) 6 чисел.
12. Т. Найдите сумму цифр всех четырехзначных чисел, которые можно составить из цифр 1, 3, 5, 7 (без их повторения).
Решение.
Каждое четырехзначное число, составленное из цифр 1, 3, 5, 7 (без повторения), имеет сумму цифр, равную 1+3 + 5 + 7=16.
Из этих цифр можно составить Р4 = 4! = 24 различных числа, отличающихся только порядком цифр. Сумма цифр всех этих чисел будет равна
16 = 384.
Ответ: 384.
13. Т. Семь мальчиков, в число которых входят Олег и Игорь, становятся в ряд. Найдите число возможных комбинаций, если:
а) Олег должен находиться в конце ряда;
б) Олег должен находиться в начале ряда, а Игорь - в конце ряда;
в) Олег и Игорь должны стоять рядом.
Решение.
а) Всего 7 мальчиков на 7 местах, но один элемент фиксирован, не переставляется (Олег находится в конце ряда). Число возможных комбинаций при этом равно числу перестановок 6 мальчиков, стоящих перед Олегом: Р6=6!=720.
пару как единый элемент, переставляемый с другими пятью элементами. Число возможных комбинаций тогда будет Р6 = 6! = 720.
Пусть теперь Олег и Игорь стоят рядом в порядке ИО. Тогда получим еще Р6 = 6! = 720 других комбинаций.
Общее число комбинаций, в которых Олег и Игорь стоят рядом (в любом порядке) равно 720 + 720 = 1 440.
Ответ: а) 720; б) 120; в) 1 440 комбинаций.
14. М. Одиннадцать футболистов строятся перед началом матча. Первым становится капитан, вторым - вратарь, а остальные - случайным образом. Сколько существует способов построения?
Решение.
После капитана и вратаря третий игрок может выбрать любое из 9 оставшихся мест, следующий - из 8, и т. д. Общее число способов построения по правилу произведения равно:
1 =362 880, или Р 9 = 9! = 362 880.
Ответ: 362 880.
15. М. Сколькими способами можно обозначить вершины куба буквами А, В, С, D, E, F, G, K?
Решение.
Для первой вершины можно выбрать любую из 8 букв, для второй - любую из 7 оставшихся, и т. д. Общее число способов по правилу произведения равно =40 320, или Р8 = 8!
Ответ: 40 320.
16. Т. В расписании на понедельник шесть уроков: алгебра, геометрия, биология, история, физкультура, химия. Сколькими способами можно составить расписание уроков на этот день так, чтобы два урока математики стояли рядом?
Решение.
Всего 6 уроков, из них два урока математики должны стоять рядом.
«Склеиваем» два элемента (алгебра и геометрия) сначала в порядке АГ, затем в порядке ГА. При каждом варианте «склеивания» получаем Р5 = 5! = 120 вариантов расписания. Общее число способов составить расписание равно120 (AГ) +120 (ГА) = 240.
Ответ: 240 способов.
17. Т. Сколько существует перестановок букв слова «конус», в которых буквы К, О, Н стоят рядом?
Решение.
Дано 5 букв, из которых три буквы должны стоять рядом. Три буквы К, О, Н могут стоять рядом одним из Р3 = 3! = 6 способов. Для каждого способа «склеивания» букв К, О, Н получаем Р3 = 3! = 6 способов перестановки букв, «склейка», У, С. Общее число различных перестановок букв слова «конус», в которых буквы К, О, Н стоят рядом, равно 6 6 = 36 перестановок- анаграмм.
Ответ: 36 анаграмм.
18. Т. Сколькими способами 5 мальчиков и 5 девочек могут занять в театре в одном ряду места с 1 по 10? Сколькими способами они могут это сделать, если мальчики будут сидеть на нечетных местах, а девочки - на четных?
Решение.
Каждый вариант расположения мальчиков может сочетаться с каждым из вариантов расположения девочек, поэтому по правилу произведения общее число способов рассадить детей в этом случае равно 120 20= 14400.
Ответ: 3 628 800 способов; 14 400 способов.
19. Т. Пять мальчиков и четыре девочки хотят сесть на девятиместную скамейку так, чтобы каждая девочка сидела между двумя мальчиками. Сколькими способами они могут это сделать?
Решение.
По условию задачи мальчики и девочки должны чередоваться, т. е. девочки могут сидеть только на четных местах, а мальчики -только на нечетных. Поэтому меняться местами девочки могут только с девочками, а мальчики - только с мальчиками. Четырех девочек можно рассадить на четырех четных местах Р4 = 4! = 24 способами, а пятерых мальчиков на пяти нечетных местах Р5 = 5! = 120 способами.
Каждый способ размещения девочек может сочетаться с каждым способом размещения мальчиков, поэтому по правилу произведения общее число способов равно: Р4
20 = 2 880 способов.
Ответ: 2 880 способов.
20. Ф. Разложить на простые множители числа 30 и 210. Сколькими способами можно записать в виде произведения продых множителей число: 1) 30; 2) 210?
Решение.
Разложим данные числа на простые множители:
30 = 2 ; 210 = 2 .
Число 30 можно записать в виде произведения простых множителей
Р 3 = 3! = 6 разными способами (переставляя множители).
Число 210 можно записать в виде произведения простых
множителей
Р
4
= 4!
= 24 разными способами.
Ответ: 1) 6 способов; 2) 24 способа.
21. Ф. Сколько различных четных четырехзначных чисел с неповторяющимися цифрами можно записать, используя цифры 1, 2, 3, 5?
Решение.
Чтобы число было четным, оно должно заканчиваться четной цифрой, т. е. 2. Зафиксируем двойку на последнем месте, остальные три цифры должны стоять перед ней в произвольном порядке. Количество различных перестановок из 3 цифр равно P3 = 3! = 6; следовательно, различных четных четырехзначных чисел будет также 6 (к каждой перестановке из трех цифр добавляется цифра 2).
Ответ: 6 чисел.
22. Ф. Сколько различных нечетных пятизначных чисел, в которых нет одинаковых цифр, можно записать с помощью Цифр 1,2, 4, 6, 8?
Решение.
Чтобы составленное число было нечетным, необходимо, чтобы оно оканчивалось нечетной цифрой, т. е. единицей. Остальные 4 Цифры можно переставлять местами, располагая каждую перестановку перед единицей.
Общее число нечетных пятизначных чисел равно числу перестановок: Р4 = 4! =24.
23. Ф. Сколько различных шестизначных чисел с неповторяющимися цифрами можно записать с помощью цифр 1; 2 3, 4, 5, 6, если: 1) число должно начинаться с 56; 2) цифры 5 и 6 в числе должны стоять рядом?
Решение.
Две цифры 5 и 6 фиксируем в начале числа и дописываем к ним различные перестановки из 4 оставшихся цифр; количество различных шестизначных чисел равно: Р4 = 4! = 24.
Общее количество различных шестизначных чисел, в которых цифры 5 и 6 стоят рядом (в любом порядке), равно 120 + 120 = 240 чисел. (Варианты 56 и 65 несовместны, не могут реализоваться одновременно; применяем комбинаторное правило суммы.)
Ответ: 1) 24 числа; 2) 240 чисел.
24. Ф. Сколько различных четных четырехзначных чисел, в записи которых нет одинаковых цифр, можно составить из цифр 1,2,3,4?
Решение.
Четное число должно оканчиваться четной цифрой. Фиксируем на последнем месте цифру 2, тогда 3 предшествующие цифры можно переставить Р3 = 3! = 6 различными способами; получим 6 чисел с двойкой на конце. Фиксируем на последнем месте цифру 4, получим Р3 = 3! = 6 различных перестановок трех предшествующих цифр и 6 чисел, оканчивающихся цифрой 4.
Общее количество четных четырехзначных чисел будет 6 + 6 = 12 различных чисел.
Ответ: 12 чисел.
Замечание. Общее количество вариантов мы находим, пользуясь комбинаторным правилом суммы (6 вариантов чисел, оканчивающихся двойкой, 6 вариантов чисел, оканчивающихся четверкой; способы построения чисел с двойкой и с четверкой на конце являются взаимоисключающими, несовместными, поэтому общее количество вариантов равно сумме числа вариантов с двойкой на конце и числа вариантов с 4 на конце). Запись 6 + 6 = 12 лучше отражает основания наших действий, чем запись Р .
25. Ф. Сколькими способами можно записать в виде произведения простых множителей число 1) 12; 2) 24; 3) 120?
Решение.
Особенностью этой задачи является то, что в разложении каждого из данных чисел есть одинаковые, повторяющиеся множители. При образовании различных перестановок из множителей мы не получим новую перестановку, если поменяем местами какие-нибудь два одинаковых множителя.
1) Число 12 разлагается на три простых множителя, два из которых одинаковы: 12 = .
Если бы все множители были различны, то их можно было бы переставить в произведении Р3 = 3! = 6 различными способами. Чтобы перечислить эти способы, условно «различим» две двойки, подчеркнем одну из них: 12 = 2 .
Тогда возможны следующие 6 вариантов разложения на жители:
Но на самом деле подчеркивание цифр не имеет в математике никакого значения, поэтому полученные 6 перестановок в обычной записи имеют вид:
т. е. фактически мы получили не 6, а 3 различные перестановки Количество перестановок уменьшилось в два раза за счет того, что мы не должны учитывать перестановки двух двоек между собой.
Обозначим Р
х
искомое число перестановок из трех элементов среди которых два одинаковых; тогда полученный нами результат можно записать так: Рз = Р
х
Но 2 - это количество разных перестановок из двух элементов, т. е. 2 =
= 2! = Р
2
, поэтому Р3, = Р
х
Р
2
, отсюда Р
х
=
. (это формула для числа перестановок с повторениями).
Можно рассуждать иначе, основываясь только на комбинаторном правиле произведения.
Чтобы составить произведение из трех множителей, сначала выберем место для множителя 3; это можно сделать одним из трех способов. После этого оба оставшихся места заполняем двойками; это можно сделать 1 способом. По правилу произведения общее число способов равно: 3-1 =3. , Р х =20.
Второй способ. Составляя произведение из пяти множителей, сначала выберем место для пятерки (5 способов), затем для тройки (4 способа), а оставшиеся 3 места заполним двойками (1 способ); по правилу произведения 5 4 1 = 20.
Ответ: 1) 3; 2) 4; 3) 20.
26. Ф. Сколькими способами можно закрасить 6 клеток таким образом, чтобы 3 клетки были красными, а 3 оставшиеся были закрашены (каждая своим цветом) белым, черным или зеленым?
Решение.
Перестановки из 6 элементов, среди которых три - одинаковые:
Иначе: для закраски белым цветом можно выбрать одну из 6 клеток, черным - из 5, зеленым - из 4; три оставшиеся клетки закрашиваем красным цветом. Общее число способов: 6 5 4 1 = 120.
Ответ: 120 способов.
27.Т. Пешеход должен пройти один квартал на север и три квартала на запад. Выпишите все возможные маршруты пешехода. = 4.
Ответ: 4 маршрута.
28. М. а) На дверях четырех одинаковых кабинетов надо повесить таблички с фамилиями четырех заместителей директора. Сколькими способами это можно сделать?
б) В 9 «А» классе в среду 5 уроков: алгебра, геометрия, физкультура, русский язык, английский язык. Сколько можно составить вариантов расписания на этот день?
в) Сколькими способами четыре вора могут разбежаться по одному на все четыре стороны?
г) Адъютант должен развезти пять копий приказа генерала пяти полкам. Сколькими способами он может выбрать маршрут доставки копий приказа?
Решение.
а) Для первой таблички можно выбрать любой из 4 кабинетов,
Для второй - любой из трех оставшихся, для третьей - любой из двух оставшихся, для четвертой - один оставшийся; по правилу
произведения общее число способов равно: 4 3 2 1 = 24, или Р4 = 4! = 24.
= 120, или Р5 = 5! = 120.
Ответ: а) 24; б) 120; в) 24; г) 120.
Литература
Афанасьев В.В. Теория вероятностей в примерах и задачах, - Ярославль: ЯГПУ, 1994.
Баврин И. И. Высшая математика: Учебник для студентов химико-математических специальностей педагогических вузов-2-е издание, переработанное. - М.:Просвещение, 1993.
Бунимович Е. А., Булычёв В.А. Вероятность и статистика. 5-9 классы: Пособие для общеобразовательных учебных заведений, - М.:Дрофа, 2005.
Виленкин Н. Я. и другие. Алгебра и математический анализ для 10 класса: Учебное пособие для учащихся школ и классов с углублённым изучением математики. - М.:Просвещение,1992.
Виленкин Н. Я. и другие. Алгебра и математический анализ для 11 класса: Учебное пособие для учащихся школ и классов с углублённым изучением математики - М.:Просвещение, 1990.
Глейзер Г.И. История математики в школе: 9-10 класс. Пособие для учителей. - М.: Просвещение 1983.
Дорофеев Г.В., Суворова С.Б., Бунимович Е.А. Математика 9:Алгебра. Функции. Анализ данных - М.: Дрофа, 2000.
Колягин и другие. Алгебра и начала анализа 11 класс. Математика в школе - 2002 - №4 - с.43,44,46.
Люпшкас В.С. Факультативные курсы по математике: теория вероятностей: Учебное пособие для 9-11 классов.- М.,1991.
Макарычев Ю.Н., Миндюк Н.Г. Элементы статистики и теории вероятностей: Учебное пособие для учащихся 7-9 классов.- М.: Просвещение, 2005.
Мордкович А.Г., Семенов П.В. Алгебра и начала анализа 10 класс: Учебник для общеобразовательных учреждений (профильный уровень) – М.: Мнемозина, 2005.
Ткачева М.В., Федорова Н.Е. Элементы статистики и вероятность: Учебное пособие для учащихся 7-9 классов.- М.: Просвещение, 2005.
