Как составить задачи на комбинаторику

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

Содержание:

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

Перестановки:

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

Иными словами, это такое множество, для которого указано, какой элемент находится на первом месте, какой — на втором, …, какой — на n-м.

Формула числа перестановок

Пример:

Количество различных шестизначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, не повторяя эти цифры в одном числе, равно

Размещения:

Размещением из n элементов по k называется любое упорядоченное множество из k элементов, состоящее из элементов данного n-элементного множества.

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

Формула числа размещений

Пример:

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

Сочетания:

Сочетанием без повторений из n элементов по k называется любое k-элементное подмножество данного n-элементного множества.

Формула числа сочетаний

(по определению считают, что

Пример:

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

Некоторые свойства числа сочетаний без повторений

(в частности, )

Схема поиска плана решения простейших комбинаторных задач:

Выбор правила:

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

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

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

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

Объяснение и обоснование:

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

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

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

Решение многих комбинаторных задач базируется на двух основных правилах — правиле суммы и правиле произведения.

Правило суммы. Если на тарелке лежат 5 груш и 4 яблока, то выбрать один фрукт (грушу или яблоко) можно 9 способами (5 + 4 = 9). В общем виде справедливо такое утверждение:

• если элемент А можно выбрать m способами, а элемент В — n способами (при этом выбор элемента А исключает одновременный выбор элемента В), то А или В можно выбрать m + n способами.

Уточним содержание этого правила, используя понятие множеств и операций над ними.

Пусть множество А состоит из m элементов, а множество В -из n элементов. Если множества А и В не пересекаются (то есть ), то множество А В состоит изэлементов.

Правило произведения. Если в киоске продают ручки 5 видов и тетради 4 видов, то выбрать набор из ручки и тетради (то есть пару — ручка и тетрадь) можно 5æ4 = 20 способами (поскольку с каждой из 5 ручек можно взять любую из 4 тетрадей). В общем виде имеет место такое утверждение:

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

Это утверждение означает, что если для каждого из m элементов А можно взять в пару любой из n элементов В, то количество пар равно произведению .

В терминах множеств полученный результат можно сформулировать следующим образом. Если множество А состоит из т элементов, а множество В — из n элементов, то множество всех упорядоченных пар* (а; b), где первый элемент принадлежит множеству А (а ∈ А), а второй  множеству В (b ∈ В), состоит из элементов.

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

Упорядоченные множества:

При решении комбинаторных задач приходится рассматривать не только множества, в которых элементы можно записывать в любом порядке, но и так называемые упорядоченные множества. Для упорядоченных множеств существенным является порядок следования их элементов, то есть то, какой элемент записан на первом месте, какой на втором и т. д. В частности, если одни и те же элементы записать в разном порядке, то мы получим различные упорядоченные множества. Чтобы различить записи упорядоченного и неупорядоченного множеств, элементы упорядоченного множества часто записывают в круглых скобках, например (1; 2; 3) ≠ (1; 3; 2).

Рассматривая упорядоченные множества, следует учитывать, что одно и то же множество можно упорядочить по-разному. Например, множество из трех чисел {–5; 1; 3} можно упорядочить по возрастанию: (–5; 1; 3), по убыванию: (3; 1; –5), по возрастанию абсолютной величины числа: (1; 3; –5) и т. д.

* Множество всех упорядоченных пар (а; b), где первый элемент принадлежит множеству А (а ∈ А), а второй — множеству В (b ∈ В), называют декартовым произведением множеств А и В и обозначают А × В. Отметим, что декартово произведение В × А также состоит из m*n элементов.

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

Размещения:

Размещением из n элементов по k называется любое упорядоченное множество из k элементов, состоящее из элементов заданного n-элементного множества.

Например, из множества, содержащего три цифры {1; 5; 7}, можно составить следующие размещения из двух элементов без повторений:

(1; 5), (1; 7), (5; 7), (5; 1), (7; 1), (7; 5).

Количество размещений из n элементов по k обозначается (читается: «А из n по k», A — первая буква французского слова arrangement, что означает «размещение, приведение в порядок»). Как видим,

Выясним, сколько всего можно составить размещений из n элементов по k без повторений. Составление размещения представим себе как последовательное заполнение k мест, которые будем изображать в виде клеточек (рис. 21.1). На первое место можем выбрать один из n элементов данного множества (то есть элемент для первой клеточки можно выбрать n способами).

Если элементы нельзя повторять, то на второе место можно выбрать только один элемент из оставшихся, то есть из n – 1 элементов. Теперь уже два элемента использованы и на третье место можно выбрать только один из n – 2 элементов и т. д. На k-е место можно выбрать только один из n – (k –1) = n – k +1 элементов (см. рис. 21.1).

Поскольку требуется выбрать элементы и на первое место, и на второе, …, и на k-е, то используем правило произведения и получим следующую формулу числа размещений из n элементов по k:

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

1. Учитывается ли порядок следования элементов в соединении?
2. Все ли заданные элементы входят в полученное соединение?

Если, например, порядок следования элементов учитывается и из n данных элементов в соединении используется только k элементов, то по определению это — размещение из n элементов по k.

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

Примеры решения задач:

Пример:

На соревнования по легкой атлетике приехала команда из 12 спортсменок. Сколькими способами тренер может определить, кто из них побежит в эстафете 4 × 100 м на первом, втором, третьем и четвертом этапах?

Решение:

Количество способов выбрать из 12 спортсменок четырех для участия в эстафете равно количеству размещений из 12 элементов по 4 (без повторений), то есть

Комментарий:

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

Пример:

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

Решение:

Количество трехзначных чисел, которые можно составить из семи цифр 1, 2, 3, 4, 5, 6, 7, равно числу размещений из 7 элементов по 3, то есть

Комментарий:

Для выбора формулы выясняем, что для чисел, которые мы будем составлять, порядок следования цифр учитывается и не все элементы выбираются (только 3 из заданных семи). Следовательно, соответствующее соединение — размещение из 7 элементов по 3 (без повторений).

Пример:

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

Комментарий:

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

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

Решение:

Количество трехзначных чисел, которые можно составить из семи цифр (среди которых нет цифры 0), если цифры в числе не повторяются, равно числу размещений из 7 элементов по 3, то есть

Но среди данных цифр есть цифра 0, с которой не может начинаться трехзначное число. Поэтому из размещений из 7 элементов по 3 необходимо исключить те размещения, в которых первым элементом является цифра 0. Их количество равно числу размещений из 6 элементов по 2, то есть Следовательно, искомое количество трехзначных чисел равно

Пример:

Решите уравнение

Решение:

ОДЗ: x ∈ N, . Тогда получаем:

На ОДЗ это уравнение равносильно уравнениям:

(x – 2) (x – 3) = 6,

x2 – 5x = 0,

x (x – 5) = 0.

Тогда x = 0 или x = 5. В ОДЗ входит только x = 5.

Ответ: 5.

Комментарий:

Уравнения, в запись которых входят выражения, обозначающие количество соответствующих соединений из x элементов, считаются определенными только при натуральных значениях переменной x. Чтобы выражение имело смысл, следует выбирать натуральные значения (в этом случае также существует и, конечно, Ax 2 ≠ 0). Для преобразования уравнения используем формулы:

Объяснение и обоснование:

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

Напомним, что упорядоченное множество — это такое множество, для которого указано, какой элемент находится на первом месте, какой на втором, …, какой на n-м.

Например, переставляя цифры в числе 236 (в котором множество цифр {2; 3; 6} уже упорядоченное), можно составить такие перестановки без повторений: (2; 3; 6), (2; 6; 3), (3; 2; 6), (3; 6; 2), (6; 2; 3), (6; 3; 2) — всего 6 перестановок* .

Количество перестановок без повторений из n элементов обозначается (P — первая буква французского слова permutation — перестановка). Как видим, = 6.

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

*Отметим, что каждая из перестановок определяет трехзначное число, составленное из цифр 2, 3, 6 таким образом, что цифры в числе не повторяются.

Например, (что совпадает с соответствующим значением, полученным выше).

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

(1)

запишем в другом виде. Для этого умножим и разделим выражение в формуле (1) на произведение тогда

Следовательно, формула числа размещений без повторений из n элементов по k может быть записана так:

(2)

Для того чтобы этой формулой можно было пользоваться при всех значениях k, в частности при k = n – 1 и k = n, договорились считать, что

1! = 1 и 0! = 1.

Например, по формуле (2)

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

Примеры решения задач:

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

1. Учитывается ли порядок следования элементов в соединении?
2. Все ли заданные элементы входят в полученное соединение?

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

Пример:

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

Решение:

Количество способов равно числу перестановок из 8 элементов, то есть

Комментарий:

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

Пример:

Найдите количество различных четырехзначных чисел, которые можно составить из цифр 0, 3, 7, 9 (цифры в числе не повторяются).

Решение:

Из четырех цифр 0, 3, 7, 9, не повторяя заданные цифры, можно получить перестановок. Перестановки, начинающиеся с цифры 0, не являются записью четырехзначного числа — их количество . Тогда искомое количество четырехзначных чисел равно

Комментарий:

Поскольку порядок следования элементов учитывается и для получения четырехзначного числа надо использовать все элементы, то искомые соединения — это перестановки из 4 элементов. Их количество — . При этом необходимо учесть, что в четырехзначном числе на первом месте не может стоять цифра 0. Таких чисел будет столько, сколько раз мы сможем выполнить перестановки из 3 оставшихся цифр, то есть

Пример:

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

Решение:

Сначала будем рассматривать учебники как одну книгу. Тогда на полке надо расставить не 10, а 7 книг. Это можно сделать способами. В каждом из полученных наборов книг можно выполнить еще перестановок учебников. По правилу умножения искомое количество способов равно

Комментарий:

Задачу можно решать в два этапа. На первом будем условно считать все учебники одной книгой.

Тогда получим 7 книг (6 не учебников + 1 условная книга — учебник). Порядок следования элементов учитывается и используются все элементы (поставить на полку необходимо все книги). Следовательно, соответствующие соединения — это перестановки из 7 элементов. Их количество — .

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

Объяснение и обоснование:

1. Сочетания без повторений:

Сочетанием без повторений из n элементов по k называется любое k-элементное подмножество заданного n-элементного множества.

Например, из множества {a, b, c, d} можно составить следующие сочетания без повторений из трех элементов: {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}.

Количество сочетаний без повторений из n элементов по k элементов обозначается символом (читается: «число сочетаний из п по k» или «це из п по k», С — первая буква французского слова combinaison — сочетание). Как видим,

Выясним, сколько всего можно составить сочетаний без повторений из n элементов по k. Для этого используем известные нам формулы числа размещений и перестановок. Составление размещения без повторений из n элементов по k проведем в два этапа. Сначала выберем k разных элементов из заданного n-элементного множества, не учитывая порядок выбора этих элементов (то есть выберем kэлементное подмножество из n-элементного множества — сочетание без повторений из n-элементов по k). По нашему обозначению это можно сделать способами. После этого полученное множество из k разных элементов упорядочим. Его можно упорядочить способами. Получим размещения без повторений из n элементов по k. Следовательно, количество размещений без повторений из n элементов по k в k! раз больше числа сочетаний без повторений из n элементов по k, то естьОтсюда Учитывая, что по формуле (2) , получаем:

(3)

Например, что совпадает со значением, полученным выше.

Используя формулу (3), можно легко обосновать свойство 1 числа сочетаний без повторений, приведенное в табл. 28.

1) Поскольку то

(4)

Для того чтобы формулу (4) можно было использовать и при k = n, договорились считать, что Тогда

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

Когда мы выбираем k предметов из n, то n – k предметов мы оставляем. Если же, напротив, выбранные предметы оставим, а другие n – k -выберем, то получим способ выбора n – k предметов из n. Мы получили взаимно-однозначное соответствие способов выбора k и n – k предметов из n. Значит, количество одних и других способов одинаково. Но количество одних — , а других , поэтому .

Если в формуле (3) сократить числитель и знаменатель на (n – k)!, то получим формулу, по которой удобно вычислять при малых значениях k:

(5)

Например,

2. Вычисление числа сочетаний без повторений с помощью треугольника Паскаля:

Для вычисления числа сочетаний без повторений можно применять формулу (3): , а можно последовательно вычислять соответствующие значения, пользуясь следующим свойством:

(6)

Для обоснования равенства (6) можно записать сумму, используя формулу (3), и после приведения полученных дробей к общему знаменателю получить формулу для правой части равенства (6) (проделайте это самостоятельно). Также формулу (6) можно получить без вычислений с помощью комбинаторных рассуждений.

— это количество способов выбрать k +1 предмет из n + 1. Подсчитаем это количество, зафиксировав один предмет (назовем его «фиксированным»). Если мы не берем фиксированный предмет, то нам нужно выбрать k +1 предмет из n тех, что остались, а если мы его берем, то нужно выбрать из n тех, что остались, еще k предметов. Первое можно сделать способами, второеспособами. Всего как раз способов, следовательно,

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

Каждая строка этой таблицы начинается с единицы и заканчивается единицей

Если какая-либо строка уже заполнена, например третья, то в четвертой строке надо записать на первом месте единицу. На втором месте запишем число, равное сумме двух чисел третьей строки, стоящих над ним левее и правее (поскольку по формуле (6) На третьем месте запишем число, равное сумме двух следующих чисел третьей строки, стоящих над ним левее и правее , и т. д. (а на последнем месте снова запишем единицу).

Примеры решения задач:

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

1. Учитывается ли порядок следования элементов в соединении?
2. Все ли заданные элементы входят в полученное соединение?

Чтобы выяснить, является ли заданное соединение сочетанием, достаточно ответить только на первый вопрос (см. схему в табл. 28). Если порядок следования элементов не учитывается, то по определению это сочетание из n элементов по k элементов.

Пример:

Из 12 членов туристической группы надо выбрать трех дежурных. Сколькими способами можно сделать этот выбор?

Решение:

Количество способов выбрать из 12 туристов трех дежурных равно количеству сочетаний из 12 элементов по 3 (без повторений), то есть

Комментарий:

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

Пример:

Из вазы с фруктами, в которой лежат 10 разных яблок и 5 разных груш, требуется выбрать 2 яблока и 3 груши. Сколькими способами можно сделать такой выбор?

Решение:

Выбрать 2 яблока из 10 можно способами. При каждом выборе яблок груши можно выбрать способами. Тогда по правилу произведения выбор требуемых фруктов можно выполнить способами. Получаем

Комментарий:

Сначала отдельно выберем 2 яблока из 10 и 3 груши из 5.

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

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

Бином Ньютона:

Поскольку (при x ≠ 0 и a ≠ 0), то формулу бинома Ньютона можно записать еще и так:

Общий член разложения степени бинома имеет вид

(где ). Коэффициенты называют биномиальными коэффициентaми.

Свойства биномиальных коэффициентов:

1. Число биномиальных коэффициентов (а следовательно, и число слагаемых) в разложении n-й степени бинома равно n + 1.
2. Коэффициенты членов, равноудаленных от начала и конца разложения, равны между собой (поскольку )
3. Сумма всех биномиальных коэффициентов равна
4. Сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме биномиальных коэффициентов, стоящих на нечетных местах.
5. Для вычисления биномиальных коэффициентов можно воспользоваться треугольником Паскаля, в котором вычисления коэффициентов основываются на формуле

Объяснение и обоснование:

Бином Ньютона:

Двучлен вида a + x также называют биномом. Из курса алгебры известно, что:

Можно заметить, что коэффициенты разложения степени бинома при n = 1, 2, 3 совпадают с числами в соответствующей строке треугольника Паскаля. Оказывается, что это свойство выполняется для любого натурального n, то есть справедлива формула

(7)

Формулу (7) называют биномом Ньютона. Правая часть этого равенства называется разложением степени бинома, а числа (при k = 0, 1, 2, …, n) называют биномиальными коэффициентами.

Общий член разложения степени бинома имеет вид

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

Приведем также комбинаторные рассуждения для обоснования формулы бинома Ньютона.

По определению степени с натуральным показателем (всего n скобок). Раскрывая скобки, получаем в каждом слагаемом произведение n букв, каждая из которых — а или х. Если, например, в каком-либо слагаемом количество букв x равно k, то количество букв а в нем — n – k, то есть каждое слагаемое имеет вид при некотором k от 0 до n. Покажем, что для каждого такого k число слагаемых anравно , откуда после приведения подобных членов и получаем формулу бинома. Произведение получаем, взяв букву x из k скобок и букву а из n – k тех скобок, которые остались. Разные такие слагаемые получим путем разного выбора первых k скобок, а k скобок из n можно выбрать именно способами. Следовательно, общий член разложения бинома действительно имеет вид где k = 0, 1, 2, …, n.

Именно из-за бинома Ньютона числа часто называют биномиальными коэффициентами.

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

Например,

Так как , формулу бинома Ньютона можно записать в виде:

(8)

Если в формуле бинома Ньютона (8) заменить x на (–x), то получим формулу возведения в степень разности a – x:

Например, (знаки членов разложения чередуются!).

Свойства биномиальных коэффициентов:

1. Число биномиальных коэффициентов (а следовательно, и число слагаемых) в разложении n-й степени бинома равно n + 1, поскольку разложение содержит все степени x от 0 до n (и других слагаемых не содержит).
2. Коэффициенты членов, равноудаленных от начала и конца разложения, равны между собой, поскольку
3. Сумма всех биномиальных коэффициентов равна

Для обоснования полагаем в равенстве (7) значения a = x = 1 и получаем:

Например,

4. Сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме биномиальных коэффициентов, стоящих на нечетных местах.

Для обоснования возьмем в равенстве (7) значения a = 1, x = –1:

Тогда

Примеры решения задач:

Пример:

По формуле бинома Ньютона найдите разложение степени.

Комментарий:

Для нахождения коэффициентов разложения можно использовать треугольник Паскаля (табл. 30) или вычислять их по общей формуле. По треугольнику Паскаля коэффициенты равны: 1, 6, 15, 20, 15, 6, 1. Учитывая, что при возведении разности в степень знаки членов разложения чередуются, получаем:

Для упрощения записи ответа можно избавиться от иррациональности в знаменателях полученных выражений (см. решение) или сначала учесть, что ОДЗ данного выражения: x > 0. Тогда то есть данное выражение можно записать так: и возвести в степень последнее выражение.

Решение:

Пример:

В разложении степени найдите член, содержащий

Решение:

ОДЗ: b > 0. Тогда

.

Общий член разложения:

По условию член разложения должен содержать , следовательно, Отсюда k = 6.

Тогда член разложения, содержащий , равен

Комментарий:

На ОДЗ (b > 0) каждое слагаемое в данном двучлене можно записать как степень с дробным показателем. Это позволит проще записать общий член разложения степени

(где k = 0, 1, 2, …, n), выяснить, какой из членов разложения содержит и записать его. Чтобы упростить запись общего члена разложения, запишем:

Всё о комбинаторике

Пусть имеется несколько множеств элементов:

Вопрос: сколькими способами можно составить новое множество взяв из каждого исходного множества по одному элементу? Ответ на этот вопрос дают следующие рассуждения.

Элемент из первого множества можно выбрать способами, элемент из второго – s способами, элемент с можно выбрать способами и т. д. Пару элементов можно составить • s способами. Это следует из табл. 1.1, в которой перечислены все способы такого выбора.

Способы выбора трех элементов аbc перечислены в табл. 1.2.

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

Основной комбинаторный принцип. Если некоторый первый выбор можно сделать способами, для каждого первого выбора некоторый второй можно сделать s способами, для каждой пары первых двух – третий выбор можно сделать способами и т.д., то число способов для последовательности таких выборов равно •s •….

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

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

При повторном выборе каждый по порядку элемент может быть выбран  способами. Согласно комбинаторному принципу, такую выборку можно сделать способами. Например, повторную выборку объема 2 из трех элементов можно сделать 3² =9 способами:  

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

Число называют числом размещений из элементов по .

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

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

называют числом перестановок из  элементов.

Например, пять человек могут встать в очередь способами. Три элемента можно переставить способами:

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

Это число называют числом сочетаний из элементов по и обозначают через  Если в формуле (1.2) умножить числитель и знаменатель на , то

Например, сочетаний из четырех элементов по два существует . Это 

Так как из элементов выбрать элементов можно единственным образом, то  откуда следует, что 

Величины называют биномиальными коэффициентами. Название связано с формулой бинома Ньютона

Из формулы (1.3) следует, что

Биномиальные коэффициенты образуют так называемый треугольник Паскаля, который имеет вид:

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

Биномиальные коэффициенты обладают свойством симметрии:

Это наглядно демонстрирует треугольник Паскаля. Равенство (1.4) подтверждает тот очевидный факт, что выбор элементов из n равносилен выбору тех – элементов из , которые следует удалить, чтобы остались элементов.

При повторном выборе из элементов число выборок объема , которые отличаются только составом равно  Еще раз подчеркнем, что речь идет о выборках, которые отличаются хотя бы одним элементом, а порядок выбора этих элементов во внимание не принимается. Число таких выборок можно подсчитать следующим образом. Между элементами поставим разграничительные знаки, например, нули: Таких знаков (нулей) понадобится . На месте каждого элемента поставим столько единиц, сколько раз предполагается выбрать этот элемент. Например, комбинация   означает, что элемент выбран четыре раза, элемент выбран один раз, элемент не выбран, …, элемент выбран два раза. Заметим, что в такой записи число единиц равно объему выборки . Для перебора всех возможных комбинаций нужно из мест выбрать место и поставить на них нули, а на остальных местах разместить единицы. Это можно сделать способами.

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

Пусть – множества, число элементов в каждом из которых равно соответственно Составить множество B из элементов множества А₁, элементов множества А₂, …, элементов множества А_k, можно, согласно основному комбинаторному принципу, способами.

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

Например, число словарей, необходимых для непосредственного перевода с одного на другой, для пяти языков определяется из следующих рассуждений. Для составления словаря выбираем из пяти языков (= 5) любые два (=2). Выбор бесповторный, причем при выборе важен и состав выбора и порядок выбора. Поэтому искомое число словарей равно

Комбинаторные задачи с решением

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

Рассмотрим примеры задач комбинаторики.

Пример №1

Сколькими способами можно выбрать путь из начала координат 0(0,0) в точку В(6,4), если каждый шаг равен единице, но его можно совершать только вправо или вверх? Сколько таких путей проходит через точку А(2,3)?

Решение. Весь путь занимает 10 шагов (четыре вверх и шесть вправо). Для планирования пути следует решить, какие именно по счету четыре шага следует сделать вверх, а остальные шесть — вправо. Выбор бесповторный и нас интересует только состав выбора. Поэтому в описанных условиях всего путей из точки О в точку В будет

Рассуждая подобным образом легко видеть, что путей из точки О в точку А существует а путь из точки А в точку В можно выбрать способами. По комбинаторному принципу всего путей через точку А существует 10 • 5 = 50.

Ответ. 210; 50.

Пример №2

Сколькими способами можно выбрать путь из начала координат 0(0,0) в точку если каждый шаг равен 1, но его можно совершать только вправо или вверх? Сколько таких путей проходит через точку (См. пример 1.1 и исходные данные.)

Исходные данные к задаче 1.1.

Пример №3

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

Решение. Каждый человек пройдет N улиц и окажется на одном из перекрестков Координаты перекрестков указаны в предположении, что точка А служит началом координат.

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

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

Ответ.

Пример №4

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

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

Ответ.

Пример 1.4.

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

Решение. Яблоки в соответствии с формулой (1.5) можно распределить способами, груши — , а сливы способами. По комбинаторному принципу всего способов  Если необходимо, чтобы каждый ребенок получил по меньшей мере одно яблоко, одну грушу и одну сливу, то в соответствии с формулой предыдущего примера имеем способов.

Ответ. 83160; 7560.

Пример №5

Сколько цифр в первой тысяче не содержат в своей записи цифры 5?

Решение. Для записи любой из цифр 000, 001, 002, …, 999 необходимо трижды выбрать повторным способом одну из десяти цифр, поэтому и получается всего чисел. Если цифру 5 исключить, то выбор можно производить только из девяти цифр: 0, 1,2, 3, 4, 6, 7, 8, 9. Поэтому всего получится чисел в первой тысяче, в записи которых нет цифры 5.

Ответ. 729.

Пример №6

Сколько шестизначных чисел содержат в записи ровно три различных цифры?

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

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

Учтем теперь возможность использования нуля. К нулю нужно добавить две цифры, что можно сделать способами. Если, например, были выбраны цифры 0, 2, 5, то первой цифрой должна быть 2 или 5. К этой первой цифре в соответствии с формулой (1.7) можно добавить комбинаций остальных пяти цифр. Тогда всего шестизначных чисел, состоящих из 0, 2, 5 будет Всего же шестизначных чисел, записанных тремя цифрами, среди которых встречается нуль, ровно Всего чисел, удовлетворяющих условиям задачи, имеется

Ответ. 58320.

Пример №7

В саду есть цветы десяти наименований (розы, флоксы, ромашки и т. д.).

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

б)    Сколькими способами можно составить букет из пяти различных цветков?

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

Решение. а) Если запрета на повторение цветков нет, то мы имеем дело с повторным выбором и нас интересует только состав. Поэтому по формуле (1.5) получаем способа.

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

в)    Отберем по одному цветку каждого из двух названных наименований. Три остальных цветка можно выбрать из 10 возможных способами.

Ответ. а) 2002; б) 504; в) 220.

Пример №8

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

Решение. Ясно, что яблоки можно разложить способом (в первую корзину можно не положить яблок совсем, положить одно яблоко, два яблока, …, все яблоки). Те же рассуждения в отношении груш и персиков дают соответственно комбинаций. По комбинаторному принципу всего будет способов.

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

Ответ.

Пример №9

Требуется найти число натуральных делителей натурального числа .

Решение. Разложим на простые множители:

где – различные простые числа. (Например, )

Заметим, что при разделении числа на любые два множителя и простые сомножители распределятся между и . Если сомножитель ,  в число  входит то разложение (1.8) примет вид:

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

Ответ. .

Пример №10

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

Очевидно, что выбрать одну из имеющихся пар обуви, кроссовки или кеды, можно 5 + 2 = 7 способами.

Обобщая, приходим к комбинаторному правилу сложения:

Это правило справедливо также для трех и более элементов.

Пример №11

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

Пирожок можно выбрать 4 способами и к каждому пирожку выбрать сок 3 способами (рис. 76). Следовательно, учащийся имеет вариантов выбора завтрака.

Обобщая, приходим к комбинаторному правилу умножения:

Это правило справедливо также для трех и более элементов.

Пример №12

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

Решение:

1) Первую цифру можем выбрать 4 способами (рис.77). Так как после выбора первой цифры их останется три (ведь цифры в нашем случае повторяться не могут), то вторую цифру можем выбрать 3 способами.И наконец, третью цифру можем выбрать из оставшихся двух — то есть 2 способами. Следовательно, количество искомых трехзначных у чисел будет равно .

2) Применим комбинаторное правило умножения. Так как цифры в числе могут повторяться, то каждую из цифр искомого числа можно выбрать 4 способами (рис. 78), и тогда таких чисел будет .

Ответ. 1) 24 числа; 2) 64 числа.

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

Пример №13

Сколько четных пятизначных чисел можно составить из цифр 5, 6, 7, 8, 9, если цифры в числе не повторяются?

Решение:

Четное пятизначное число можно получить, если последней его цифрой будет 6 или 8. Чисел, у которых последней является цифра 6, будет (рис. 79),

а тех, у которых последней является цифра 8, — также 24. По комбинаторному правилу сложения всего четных чисел будет .

Ответ. 48.

Пример №14

Азбука племени АБАБ содержит всего две буквы — «а» и «б». Сколько слов в языке этого племени состоит: 1) из двух букв; 2) из трех букв?

Решение:

1) аа, ба, аб, бб (всего четыре слова); 2) ааа, ааб, аба, абб, ббб, бба, баб, баа (всего восемь слов).

Заметим, что найденное количество слов соответствует комбинаторному правилу умножения. Так как на каждое место есть два «претендента» — «а» и «б», то слов, состоящих из двух букв, будет , а из трех букв — .

Пример №15

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

Решение:

Капитаном можно выбрать любого из 11 игроков, а его заместителем — любого из 10 оставшихся игроков. Таким образом (по правилу умножения), имеем разных способов.

Пример №16

В Стране Чудес 10 городов и каждые два из них соединяет авиалиния. Сколько авиалиний в этой стране?

Решение. Так как каждая авиалиния соединяет два города, то одним из них может быть любой из 10 городов, а другим — любой из 9 оставшихся. Следовательно, количество авиалиний равно . Но при этом каждую из авиалиний мы учли дважды. Поэтому всего их будет .

Комбинаторные задачи неразрывно связаны с задачами теории вероятностей, еще одного раздела математики.

В ХIII-ХII в. до н. э. встречаются упоминания о вопросах, близких к комбинаторным. Некоторые комбинаторные задачи решали и в Древней Греции. В частности, Аристоксен из Тарента (IV в. до н. э.), ученик Аристотеля, перечислил различные комбинации длинных и коротких слогов в стихотворных размерах. А Папп Александрийский в IV в. н. э. рассматривал число пар и троек, которые можно получить из трех элементов, допуская их повторения. Некоторые элементы комбинаторики были известны и в Индии во II в. до н. э. Индийцы умели вычислять числа, известные нам как коэффициенты формулы бинома Ньютона. Позднее, в VIII в. н. э., арабы нашли и саму эту формулу, и ее коэффициенты, которые сейчас вычисляют с помощью комбинаторных формул или «треугольника Паскаля».

Свой нынешний вид упомянутые комбинаторные формулы приобрели благодаря средневековому ученому Леви бен Гершону (XIV в.) и французскому математику П. Эригону (XVII в.).

В III в. н. э. сирийский философ Порфирий для классификации понятий составил специальную схему, получившую название «древо Порфирия». Сейчас подобные деревья используются для решения определенных задач комбинаторики в разнообразных областях знаний. Некоторые ранее неизвестные комбинаторные задачи рассмотрел Леонардо Пизанский (Фибоначчи) в своей знаменитой «Книге абака» (1202 г.), в частности, о нахождении наименьшего набора различных гирь, позволяющего взвесить груз с любой целочисленной массой, не превышающей заданного числа. Со времен греческих математиков были известны две последовательности, каждый член которых получали по определенному правилу из предыдущих, — арифметическая и геометрическая прогрессии. А Фибоначчи впервые в одной из задач выразил член последовательности через два предыдущих, используя формулу, которую назвали рекуррентной. В дальнейшем метод рекуррентных формул стал одним из мощнейших для решения комбинаторных задач.

Как ни странно, развитию комбинаторики в значительной степени способствовали азартные игры, которые были очень популярны в XVI в. В частности, вопросами определения разнообразных комбинаций в игре в кости в то время занимались такие известные итальянские математики, как Д. Кардано, H. Тарталья и др. А наиболее полно изучил этот вопрос в XVII в. Галилео Галилей.

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

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

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

Например, 

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

Два множества называют равными, если они состоят из одних и тех же элементов.

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

Случается, что множества  имеют общие элементы. Если множество  содержит все общие элементы множеств  и только их, то множество  называют пересечением множеств  Записывают это так: Диаграммой Эйлера пересечение изображают, как показано на рисунке 135, б. Множество, содержащее каждый элемент каждого из множеств  и только эти

элементы, называется объединением множеств  Если  — объединение множеств   то пишут  (рис. 135, в).

Разницей множеств  называют множество, состоящее из всех элементов множества  не принадлежащих множеству  Его обозначают Например, если 

Говоря «множество», «подмножество», порядок их элементов не учитывают. Говорят, что они не упорядочены. Рассматривают и упорядоченные множества. Так называют множества с фиксированным порядком элементов. Их обозначают не фигурными, а круглыми скобками. Например, из элементов множества  можно образовать 6 трёхэлементных упорядоченных множеств: 

Как множества, все они равны, как упорядоченные множества — разные.

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

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

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

Пример №17

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

Решение:

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

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

 Если элемент некоторого множества  можно выбрать  способами, а элемент множества  способами, то элемент из множества  или из множества  можно выбрать  способами.

Правило суммы распространяется и на большее количество множеств.

Пример №18

Планируя летний отдых, семья определилась с местами его проведения: в Одессе — 1, в Евпатории — 3, в Ялте — 2, в Феодосии — 2. Сколько возможностей выбора летнего отдыха имеет семья?

Решение:

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

Пример №19

От пункта  до пункта  ведут три тропинки, а от  — две. Сколько маршрутов можно проложить от пункта  до пункта 

Решение:

Чтобы пройти от пункта  до пункта  надо выбрать одну из трёх тропинок: 1, 2 или 3 (рис. 136). После этого следует выбрать одну из двух других троп: 4 или 5. Всего от пункта  до пункта  ведут 6 маршрутов, потому что  Все эти маршруты можно обозначить с помощью пар:

Обобщим описанную ситуацию.

 Если первый компонент пары можно выбрать  способами, а . второй —  способами, то такую пару можно выбрать  способами.

Это — правило произведения, его часто называют основным правилом комбинаторики. Обратите внимание: речь идёт об упорядоченных парах, составленных из различных компонентов.

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

Описанной ситуации соответствует диаграмма, изображённая на рисунке 137. Такие диаграммы называют деревьями.

Пример №20

Сколько разных поездов можно составить из 6 вагонов, если каждый из вагонов можно поставить на любом месте?

Решение:

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

Обратите внимание на решение последней задачи. Оно свелось к вычислению произведения всех натуральных чисел от 1 до 6. В комбинаторике подобные произведения вычисляют часто.

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

Например:

Условились считать, что 

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

Если пересечение множеств  пустое, то количество элементов в их объединении  равно сумме количества элементов множеств

Если множества  имеют общие элементы, то 

Если множества  конечны, то количество возможных пар  равно произведению количества элементов множеств  

Пример №21

В розыгрыше на первенство города по баскетболу принимают участие команды из 12 школ. Сколькими способами могут быть распределены первое и второе места?

Решение:

Первое место может получить одна из 12 команд. После того, как определён обладатель первого места, второе место может получить одна из 11 команд. Следовательно, общее количество способов, которыми можно распределить первое и второе места, равно

Ответ. 132.

Пример №22

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

Решение:

Первой цифрой числа может быть одна из 5 цифр 1, 2, 3, 4, 5. Если первая цифра выбрана, то вторая может быть выбрана 5-ю способами, третья — 4-мя, четвёртая — 3-мя. Согласно правилу умножения общее число способов равно:

 Ответ. 300.

Пример №23

Упростите выражение 

Решение:

 

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

Задача:

Сколькими способами собрание из 20 человек может избрать председателя и секретаря?

Решение:

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

Обобщим задачу. Сколько упорядоченных —элементных подмножеств можно составить из  различных элементов? На первое место можно поставить любой из данных  элементов. На второе место — любой из остальных  элементов и т. д. На последнее  место можно поставить любой из остальных  элементов. Из правила произведения следует, что из данных  элементов можно получить   -элементных упорядоченных подмножеств.

Например, из 4 элементов  упорядоченных двухэлементных подмножеств можно образовать всего 

Упорядоченое -элементное подмножество элементного множества называют размещением из  элементов  Их число обозначают 

Из предыдущих рассуждений следует, что  и что для любых натуральных 

В правой части этого равенства  множителей. Поэтому результат можно сформулировать в виде такого утверждения.

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

Примеры:

 

Пример №24

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

Решение:

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

Это размещения. 

Ответ. 30 240 способами.

Число размещений из  элементов по  можно вычислять и по другой формуле:  (проверьте самостоятельно).

 Размещение  элементов по  называют перестановками из  элементов. Их число обозначают 

Например, из трёх элементов  можно образовать 6 различных перестановок:  Следовательно, 

Подставив в формулу числа размещений  получим, что 

Число перестановок из  элементов равно ! 

Примеры:

 

Пример №25

Сколькими способами можно составить список из 10 фамилий?

Решение:

 

Ответ. 3 628 800 способами.

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

Пример №26

Решите уравнение 

Решение:

Пользуясь формулой размещений, данное уравнение можно заменить таким:

По условию задачи  — натуральное число, поэтому  — посторонний корень. Следовательно, 

Пример №27

Решите уравнение 

Решение:

Запишем выражения  через произведения.

Имеем:

Поскольку по смыслу задачи  Поэтому последнее уравнение можно сократить на произведение  Тогда  Но уравнение  удовлетворяет только одно значение: 

Пример №28

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

Решение:

Речь идёт об упорядоченных 3-элементных подмножествах множества, состоящего из 30 элементов. Это — размещения. 

Пример №29

Сколькими способами можно разместить на полке 5 дисков?

Решение:

Речь идёт об упорядоченных 5-элементных множествах. Искомое количество способов равно 

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

Пример №30

Изображённое на рисунке 140 кольцо раскрашено в 7 цветов. Сколько существует таких колец, раскрашенных теми же цветами только в других последовательностях? 

Решение:

Зафиксируем одну какую-нибудь часть кольца, окрашенную одним цветом, б других частей можно раскрасить  способами.

Ответ. 720 колец.

Пример №31

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

Решение:

Способ 1. Дробей, у которых числитель не равен знаменателю, можно составить  то есть  Из этих дробей только половина — неправильных, то есть — 15.

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

Способ 2. Если знаменатель неправильной дроби 3, то его числителями могут быть все 6 данных чисел. Если знаменатель 5, то числителями неправильной дроби могут быть 5 чисел (5, 7, 9, 11, 13) и т.д. Наконец, если знаменатель — число 13, то существует только 1 неправильная дробь, со знаменателем 13. Всего таких неправильных дробей существует 

Ответ. 21 дробь.

Комбинации и бином ньютона

Пусть дано множество из трёх элементов:  Его двухэлементных подмножеств (не упорядоченных) существует всего три: Говорят, что существует 3 комбинации из трёх элементов по два. Пишут: 

 Комбинацией из  элементов по  называют любое элементное подмножество элементного множества.

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

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

число элементных комбинаций в  раз меньше числа размещений из тех же  элементов.

То есть,  отсюда

Пример №32

Вычислите: 

Решение:

Обратите внимание!  Полагают также, что  для любого 

Пример №33

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

Решение:

Здесь  порядок учеников не имеет значения.

Ответ. 300-ми способами.

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

Доказательство. Пусть дано  различных элементов:  Всего из них можно образовать  различных  элементных комбинаций. Это количество комбинаций вычислим другим способом. Из данных  элементов, кроме последнего  можно образовать  комбинаций. Остальные элементные комбинации из всех данных элементов можно образовать, если к каждой комбинации из первых элементов по  дописать элемент  Таких комбинаций 

Следовательно,  А это и требовалось доказать.

Такое комбинаторное тождество можно доказать также, воспользовавшись формулой числа комбинаций.

С комбинациями тесно связана формула бинома Ньютона. Вспомните формулу квадрата двучлена:

 Умножив  получим формулы:

Эти три формулы можно записать и так:

Оказывается, для каждого натурального значения  правильна и общая формула:

Это тождество называют формулой бинома Ньютона. а её правую часть разложением бинома Ньютона. Бином — латинское название двучлена. Пользуясь этой формулой, возведём, например, двучлен  в пятую степень. Поскольку 

Доказать формулу бинома Ньютона можно методом математической индукции.

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

Выражения в скобках преобразованы согласно формулы

Следовательно, если формула бинома Ньютона верна для  то она правильна и для  Для  она правильна, так как  Поэтому на основе аксиомы математической индукции можно утверждать, что формула верна для любого натурального показателя 

Вычислять коэффициенты разложения бинома Ньютона можно не по формуле числа комбинаций, а пользуясь числовым треугольником Паскаля — своеобразным способом вычисления коэффициентов разложения бинома Ньютона 

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

Например, прибавляя числа шестой строки (для  получим числа следующей строки (для  Следовательно,  Общий член разложения бинома  можно определить по формуле 

Например:

Пример №34

В турнире по шашкам приняли участие 5 девушек и 7 юношей. Каждый участник сыграл один раз с каждым другим. Сколько партий было: а) между девушками; б) между юношами; в) между юношами и девушками?

Решение:

а) Речь идёт о 2-элементных подмножествах (неупорядоченных) множества, состоящего из 5 элементов. Это — комбинации.  

б) Аналогично 

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

Пример №35

Для дежурства в столовой приглашают 3-х учеников из 7 класса и 2-х учеников из 10 класса. Сколькими способами это можно сделать, если в 7 классе учится 24 ученика, а в 10 классе — 18.

Решение:

Речь идёт о неупорядоченных подмножествах двух разных множеств. Это — комбинации.

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

Пример №36

Сколько разных делителей имеет число 1001?

Решение:

Разложим заданное число на простые множители:  Если число  — делитель числа 1001, то оно должно быть одним из чисел 7, 11,13 (три случая) или любым их произведением. Различных произведений может быть  Делителем данного числа есть ещё единица. Следовательно, число 1001 имеет  делителей.

Пример №37

Докажите, что выпуклый угольник имеет  диагоналей.

Решение:

Отрезков, концами которых являются  вершин данного -угольника, существует  Среди них есть и  сторон данного -угольника. Поэтому диагоналей он имеет 

Пример №38

Докажите тождество

Сделайте обобщение.

Решение:

 

Все члены разложения бинома Ньютона  такие же, как и члены разложения бинома  только их члены с чётными номерами отрицательные.

Пример №39

Найдите номер члена разложения  который не содержит 

Решение:

Воспользуемся формулой общего члена разложения бинома. Имеем:

По условию задачи  то есть  Отсюда  Следовательно, не содержит  шестой член разложения бинома.

Элементы комбинаторики

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

Определение: Перестановки — это комбинации из одних и тех же элементов, отличающиеся только порядком элементов.

Пример:

Даны три числа 1, 2, 3. Определить количество комбинаций из этих элементов, отличающиеся только порядком элементов.

Решение:

Комбинации из данных элементов, отличающиеся только порядком элементов: 123; 132; 213; 231; 321; 312. Всего таких комбинаций Если дано n элементов, то число перестановок O2. Размещения — это комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их расположением.

Пример:

Даны три числа 1, 2, 3. Определить количество размещений из этих элементов по два, отличающиеся составом или порядком элементов.

Решение:

Комбинации из данных элементов по два, отличающиеся составом или порядком элементов: 12; 21; 23; 32; 13; 31. Всего таких комбинаций 6. Если дано n элементов, то число размещений по m элементов, которые отличаются либо составом элементов, либо их расположением:

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

Пример:

Даны три числа 1, 2, 3. Определить количество размещений из этих элементов по два, отличающиеся хотя бы одним элементом.

Решение:

Комбинации из данных элементов по два, отличающиеся хотя бы одним элементом: 12; 23; 13. Всего таких комбинаций 3. Если дано n элементов, то число сочетаний по m элементов, которые отличаются хотя бы одним элементом:

Пример:

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

Решение:

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

Пример:

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

Решение:

Событие А состоит в том, что среди выбранных карт окажется один туз. Это сложное событие состоит из двух событий: выбирается один туз из четырех, а две другие карты выбираются из оставшихся 32 карт. Следовательно, число случаев, благоприятствующих появлению события A, равно Всего возможных равновероятных исходов, образующих полную группу определяется числом сочетаний из 36 карт по 3 карты, т.е. Таким образом, вероятность события А равна

Арифметика случайных событий

Будем считать, что все события, которые могут произойти в рамках данного эксперимента, располагаются внутри квадрата G, тогда невозможные события располагаются вне квадрата G (Рис. 2):

Рис. 2. Квадрат возможных событий.

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

Определение: Суммой двух случайных событий А и В называется третье случайное событие С, которое состоит в том, что произойдет (или не произойдет) или событие А, или событие В : С = А + В (Рис. 3).

Определение: Суммой n случайных событий называется случайное событие С, которое реализуется в данном опыте, если произойдет (или не произойдет) или одно событий , или любая их совокупность:

Рис. 3. Сумма случайных событий

Замечание: Если в словесном описании сложного события присутствует разделительный союз “или” между элементарными событиями, то речь идет о сумме этих элементарных событий.

Замечание: Суммой события А и ему противоположного события является достоверное событие т.е. Следовательно, противоположное событие можно записать в виде

Определение: Произведением двух случайных событий А и В называется третье случайное событие С, которое состоит в том, что произойдет (или не произойдет) и событие А, и событие В : (Рис. 4).

Рис. 4. Произведение случайных событий.

Определение: Произведением n случайных событий называется случайное событие С, которое реализуется в данном опыте, если произойдет (или не произойдет) совместная реализация событий

Замечание: Если в словесном описании сложного события присутствует соединительный союз “и” между элементарными событиями, то речь идет о произведении этих элементарных событий.

Пример №40

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

• а) приемник принят только второй сигнал (событие А );
• б) приемник принял только один сигнал (событие В);
• в) приемник принял не менее двух сигналов (2 или 3 сигнала — событие С);
• г) приемник не принял ни одного сигнала (событие D);
• д) приемник принял хотя бы один сигнал (событие E).

Решение:

Обозначим через элементарное событие, состоящее в том, что приемник принял сигнал i.

Сложное событие А состоит в том, что приемник не принял первый сигнал и принял второй сигнал, и не принял третий сигнал. Так как между элементарными событиями стоит соединительный союз “и”, то речь идет о их произведении, т.е.

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

Рассуждая аналогично, получим выражения для остальных событий: Сложное событие Е содержит в своем словесном описании слова “хотя бы один”, следовательно, оно противоположно событию, содержащему в своем словесном описании слова “ни один”, т.е. событию D:

Теорема сложения вероятностей несовместных событий

Теорема: Если случайные события А и В несовместны, то вероятность их суммы равна сумме вероятностей этих событий, т.е. Р(А + В) = Р(А) + Р(В)

Доказательство: Пусть в данном опыте имеется n равновозможных, элементарных, несовместных событий и пусть в m случаях наступает событие А, а в l случаях-событие В. Тогда появлению события А + В благоприятствует m+l исходов. Поэтому

Следствие: Если имеется N событий, то

Следствие: Если события () образуют полную группу, то

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

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

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

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

Пример:

Пусть в урне находится 5 белых шаров, 3 — красных и 4 — зеленых. Из урны наудачу вынули шар. Какова вероятность того, что данный шар цветной?

Решение:

Событие, состоящее в том, что из урны извлечен красный шар, обозначим через А. Событие, состоящее в том, что из урны извлечен зеленый шар, обозначим через В. Тогда извлечение цветного шара есть событие С. Так как события А и В несовместны, т.е. событие С состоит в том, что из урны извлечен или событие А , или событие В, то С = А + В. Используя теорему о сложении вероятностей несовместных событий, получим:

Зависимые и независимые события. Условная и безусловная вероятности

Определение: Случайные события А и В называются независимыми, если появление одного из них не влияет на вероятность появления другого события, в противном случае события называются зависимыми.

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

Пример №41

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

Решение:

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

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

Определение: Вероятность случайного события называется условной, если она вычисляется при условии, что произошло другое случайное событие. Условная вероятность обозначается

Теорема умножения вероятностей

Т.2. Вероятность совместного появления двух случайных событий А и В равна произведению вероятности одного из них на условную вероятность другого события, вычисленную при условии, что первое событие имело место:

Доказательство: Пусть событие А состоит в том, что брошенная точка наугад в квадрат G попадает в область А, которая имеет площадь Событие В состоит в том, что брошенная наугад в квадрат G точка попадает в область В с площадью Пусть весь квадрат имеет площадь S, а область совместного наступления событий имеет площадь (Рис. 5). Тогда вероятность события А равна а события В —

Рис. 5. Совместное наступление зависимых и независимых случайных событий.

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

Замечание: Если события А и В независимы, то т.е. безусловная и условная вероятности равны между собой.

В связи с вышеприведенным замечанием теорема об умножении вероятностей независимых случайных событий имеет вид:

ТЗ. Вероятность совместного наступления независимых событий равна произведению вероятностей этих событий:

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

Следствие: Методом математической индукции теоремы легко обобщается на произведение N зависимых событий:

а теорема — для независимых событий:

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

Что такое комбинаторика

Понятие множества и его элементов:

Множество можно представить как совокупность некоторых объектов, объединенных по определенному признаку. В математике множество — одно из основных неопределяемых понятий. Каждый объект, принадлежащий множеству А, называется элементом этого множества. Множество, не содержащее ни одного элемента, называется пустым множеством и обозначается .

Подмножество

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

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

Равенство множеств

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

Пересечение множеств

Пересечением множеств A и В называют их общую часть, то есть множество С всех элементов, принадлежащих как множеству А, так и множеству В

Объединение множеств

Объединением множеств А и В называют множество С, состоящее из всех элементов, принадлежащих хотя бы одному из этих множеств (А или В)

Разность множеств

Разностью множеств А и В называется множество С, которое состоит из всех элементов, принадлежащих множеству А и не принадлежащих множеству В

Дополнение множества

Если все рассматриваемые множества являются подмножествами некоторого универсального множества U, то разность U А называется дополнением множества А. Другими словами, дополнением множества А называется множество, состоящее из всех элементов, не принадлежащих множеству А (но принадлежащих универсальному множеству).

Объяснение и обоснование:

Понятие множества

Одним из основных понятий, которые используются в математике, является понятие множества. Для него не дается определения. Можно пояснить, что множеством называют произвольную совокупность объектов, а сами объекты — элементами данного множества. Так, можно говорить о множестве учеников в классе (элементы — ученики), множестве дней недели (элементы — дни недели), множестве натуральных делителей числа 6 (элементы — числа 1, 2, 3, 6) и т. д.

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

Как правило, множества обозначают прописными буквами латинского алфавита. Например, если множество М состоит из чисел 1; 2; 3, то его обозначают так: М = {1; 2; 3}. Тот факт, что число 2 входит в это множество (является элементом данного множества М) записывается с помощью специального значка следующим образом: ; а то, что число 5 не входит в это множество (не является элементом данного множества), записывается так:

Можно рассматривать также множество, не содержащее ни одного элемента, — пустое множество.

Например: множество простых делителей числа 1 — пустое множество.

Для некоторых множеств существуют специальные обозначения. Так, пустое множество обозначается символом, множество всех натуральных чисел — буквой N, множество всех целых чисел — буквой Z, множество всех рациональных чисел — буквой Q, а множество всех действительных чисел — буквой R.

Множества бывают конечными и бесконечными в зависимости от того, какое количество элементов они содержат. Так, множества А = {7} и М = {1; 2; 3} — конечные потому, что содержат конечное число элементов, а множества N, Z, Q, R — бесконечные.

Множества задают или с помощью перечисления их элементов (это можно сделать только для конечных множеств), или с помощью описания, когда задается правило (характеристическое свойство), которое позволяет определить, принадлежит или нет данный объект рассматриваемому множеству. Например, А = {-1; 0; 1} (множество задано перечислением элементов), В — множество четных целых чисел (множество задано характеристическим свойством элементов множества). Последнее множество иногда записывают так: — четное целое число} или так: — здесь после вертикальной черточки записано характеристическое свойство.

В общем виде запись множества с помощью характеристического свойства можно обозначить так: — характеристическое свойство. Например,

Равенство множеств

Пусть А — множество цифр трехзначного числа 312, то есть А = {3; 1; 2}, а В — множество натуральных чисел, меньших четырех, то есть В = {1; 2; 3}. Поскольку эти множества состоят из одних и тех же элементов, то они считаются равными. Это записывают так: А = В.

Для бесконечных множеств таким способом (сравнивая все элементы) установить их равенство невозможно. Поэтому в общем случае равенство множеств определяется следующим образом.

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

Из приведенного определения равенства множеств следует, что в множестве одинаковые элементы не различаются. Действительно, например, {1; 2; 2} = {1; 2}, поскольку каждый элемент первого множества (1 или 2) является элементом второго множества и, наоборот, каждый элемент второго множества (1 или 2) является элементом первого. Поэтому, записывая множество, чаще всего каждый его элемент записывают только один раз.

Подмножество

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

Это записывают следующим образом:

Например, (поскольку любое натуральное число — целое), (поскольку любое целое число — рациональное), (поскольку любое рациональное число — действительное).

Полагают, что всегда, то есть пустое множество является подмножеством любого множества.

Иногда вместо записи используется также запись , если множество А является подмножеством множества В или равно множеству В. Например, можно записать, что .

Сопоставим определение равенства множеств с определением подмножества. Если множества А и В равны, то: 1) каждый элемент множества А является элементом множества В, следовательно, А — подмножество В; 2) каждый элемент множества В является элементом множества А, следовательно, В — подмножество Таким образом,

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

А = В означает то же, что

Иногда соотношения между множествами удобно иллюстрировать с помощью кругов (которые часто называют кругами Эйлера-Венна). Например, рисунок 118 иллюстрирует определение подмножества, а рисунок 119-отношения между множествами

Операции над множествами

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

Пересечением множеств А и В называют их общую часть, то есть множество С всех элементов, принадлежащих как множеству А, так и множеству В.

Пересечение множеств обозначают знаком (на рисунке 120 приведена иллюстрация и символическая запись определения пересечения множеств).

Например, если А = {2; 3; 4}, В = {0; 2; 4; 6}, то

Объединением множеств А и В называют множество С, состоящее из всех элементов, принадлежащих хотя бы одному из этих множеств (А или В).

Объединение множеств обозначают знаком U (на рисунке 121 приведена иллюстрация и символическая запись определения объединения множеств).

Например, для множеств А и В из предыдущего примера Если обозначить множество иррациональных чисел через М, то М U Q = R. Разностью множеств А и В называется множество С, состоящее из всех элементов, которые принадлежат множеству А и не принадлежат множеству В.

Разность множеств обозначают знаком . На рисунке 122 приведена иллюстрация и символическая запись определения разности множеств.

Например, если А = {1; 2; 3}, В = {2; 3; 4; 5}, то АВ = {1}, а В А = {4; 5}. Если В — подмножество А, то разность А В называют дополнением множества В до множества А (рис. 123).

Например, если обозначить множество иррациональных чисел через М, то R Q = М: множество М иррациональных чисел дополняет множество Q рациональных чисел до множества R всех действительных чисел.

Все множества, которые мы рассматриваем, являются подмножествами некоторого так называемого универсального множества U. Его обычно изображают в виде прямоугольника, а все остальные множества — в виде кругов внутри этого прямоугольника (рис. 124). Разность U А называется дополнением множества А.

Дополнением множества А называется множество, состоящее из всехэлементов, не принадлежащих множеству А (но принадлежащих универсальному множеству U).

Дополнение множества А обозначается (можно читать: «А с чертой»). Например, если U = R и А = [0; 1], то Для этого примера удобно использовать традиционную иллюстрацию множества действительных чисел на числовой прямой (рис. 125).

Комбинаторика и Бином Ньютона

Элементы комбинаторики:

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

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

Перестановки:

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

Иными словами, это такое множество, для которого указано, какой элемент находится на первом месте, какой — на втором,…, какой — на п-м.

*Формулы для нахождения количества соединений с повторениями являются обязательными только для классов физико-математического профиля. Формула числа перестановок (читается: «Эн факториал»)

Пример:

Количество различных шестизначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, не повторяя эти цифры в одном числе, равно

Размещения:

Размещением из элементов по называется любое упорядоченное множество из элементов, состоящее из элементов -элементного множества Формула числа размещений

Пример:

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

Сочетания:

Сочетанием без повторений из элементов по называется любое -элементное подмножество -элементного множества Формула числа сочетаний

(по определению считают, что )

Пример:

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

Схема решения комбинаторных задач

Выбор правила:

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

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

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

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

Учитывается ли порядок следования элементов в соединении?

• Нет

Все ли элементы входят в соединение?

• Перестановки
• Размещения
• Сочетания

без повторений с повторениями без повторений с повторениями без повторений с повторениями

Объяснение и обоснование:

Понятие соединения

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

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

Решение многих комбинаторных задач базируется на двух основных правилах — правиле суммы и правиле произведения.

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

Если на тарелке лежит 5 груш и 4 яблока, то выбрать один фрукт (то есть грушу или яблоко) можно 9 способами (5 + 4 = 9). В общем виде имеет место такое утверждение:

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

Если в киоске продают ручки 5 видов и тетради 4 видов, то выбрать набор из ручки и тетради (то есть пару — ручка и тетрадь) можно 5 • 4 = 20 способами (поскольку с каждой из 5 ручек можно взять любую из 4 тетрадей). В общем виде имеет место такое утверждение:

• если элемент А можно выбрать m способами, а после этого элемент В — способами, то А и В можно выбрать m • п способами.

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

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

Следовательно, если приходится выбирать или первый элемент, или второй, или третий и т. д. элемент, количества способов выбора каждого еле-мента складывают, а когда приходится выбирать набор, в который входят и первый, и второй, и третий, и т. д. элементы, количества способов выбора каждого элемента перемножают.

Упорядоченные множества

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

Рассматривая упорядоченные множества, следует учитывать, что упорядоченность не является свойством самого неупорядоченного множества (из которого мы получили упорядоченное), поскольку одно и то же множество можно по-разному упорядочить. Например, множество из трех чисел {-5; 1; 3} можно упорядочить по возрастанию: (-5; 1; 3), по убыванию: (3; 1; — 5), по возрастанию абсолютной величины числа: (1; 3; -5) и т. д.

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

Размещения

Размещением из элементов по называется любое упорядоченное множество из элементов, состоящее из элементов -элементного множества.

Например, из множества, содержащего три цифры {1; 5; 7}, можно составить следующие размещения из двух элементов без повторений: (1;5),(1;7),(5; 7), (5; 1), (7; 1), (7; 5).

Количество размещений из элементов по обозначается (читается: «А из по », А — первая буква французского слова arrangement, что означает «размещение, приведение в порядок»). Как видим,

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

Если элементы нельзя повторять, то на второе место можно выбрать только один элемент из оставшихся, то есть из — 1 элементов. Теперь уже два элемента использованы и на третье место можно выбрать только один из — 2 элементов и т. д. На -e место можно выбрать только один из элементов.

Поскольку требуется выбрать элементы и на первое место, и на второе, …, и на-e, то используем правило произведения, получим следующую формулу числа размещений из элементов по

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

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

• — Учитывается ли порядок следования элементов в соединении?
• — Все ли заданные элементы входят в полученное соединение?

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

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

Примеры решения задач:

Пример №42

На соревнования по легкой атлетике приехала команда из 12 спортсменок. Сколькими способами тренер может определить, кто из них побежит в эстафете 4 х 100 м на первом, втором, третьем и четвертом этапах?

Решение:

Количество способов выбрать из 12 спортсменок четырех для участия в эстафете равно количеству размещений из 12 элементов по 4 (без повторений), то есть

Комментарий:

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

Пример №43

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

Решение:

Количество трехзначных чисел, которые можно составить из семи цифр 1, 2, 3, 4, 5, 6, 7, равно числу размещений из 7 элементов по 3, то есть

Комментарий:

Для выбора формулы выясняем, что для чисел, которые мы будем составлять, порядок следования цифр учитывается и не все элементы выбираются (только 3 из заданных семи). Следовательно, соответствующее соединение — размещение из 7 элементов по 3 (без повторений).

Пример №44

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

Комментарий:

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

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

• 6 возможностей
• 6 возможностей
• 5 возможностей

Решение:

Количество трехзначных чисел, которые можно составить из семи цифр (среди которых нет цифры 0), если цифры в числе не повторяются, равно числу размещений из 7 элементов по 3, то есть

Но среди данных цифр есть цифра 0, с которой не может начинаться трехзначное число. Поэтому из размещений из 7 элементов по 3 необходимо исключить те размещения, в которых первым элементом является цифра 0. Их количество равно числу размещений из 6 элементов по 2, то есть Следовательно, искомое количество трехзначных чисел равно

Пример №45

Решите уравнение

Решение:

Тогда получаем На ОДЗ это уравнение равносильно уравнениям:

Комментарий:

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

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

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

Напомним, что упорядоченное множество — это такое множество, для которого указано, какой элемент находится на первом месте, какой на втором,…, какой на

Например, переставляя цифры в числе 236 (там множество цифр {2; 3; 6} уже упорядоченное), можно составить такие перестановки без повторений: (2; 3; 6), (2; 6; 3), (3; 2; 6), (3; 6; 2), (6; 2; 3), (6; 3; 2) — всего 6 перестановок*.

Количество перестановок без повторений из элементов обозначается (Р — первая буква французского слова permutation — перестановка). Как видим,

Фактически перестановки без повторений из элементов являются размещениями из элементов по без повторений, поэтому Произведение 1 • 2 • 3 •… • обозначается

!. Поэтому полученная формула числа перестановок без повторений из элементов может быть записана так:

*Отметим, что каждая такая перестановка определяет трехзначное число, составленное из цифр 2,3,6 так, что цифры в числе не повторяются.

Например, (что совпадает с соответствующим значением, полученным выше).

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

можно записать в другом виде. Для этого умножим и разделим выражение в формуле (1) на произведение Получаем

Следовательно, формула числа размещений без повторений из элементов по может быть записана так:

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

Например, по формуле (2)

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

Например,

Примеры решения задач:

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

• — Учитывается ли порядок следования элементов в соединении?
• — Все ли заданные элементы входят в полученное соединение? Если, например, порядок следования элементов учитывается и все п заданных элементов используются в соединении, то по определению это перестановки из п элементов.

Пример №46

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

Решение:

Количество способов равно числу перестановок из 8 элементов. То есть

Комментарий:

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

Пример №47

Найдите количество разных четырехзначных чисел, которые можно составить из цифр 0, 3, 7, 9 (цифры в числе не повторяются).

Решение:

Из четырех цифр 0, 3, 7, 9, не повторяя заданные цифры, можно получить перестановок. Перестановки, начинающиеся с цифры 0, не являются записью четырехзначного числа — их количество . Тогда искомое количество четырехзначных чисел равно

Комментарий:

Поскольку порядок следования элементов учитывается и для получения четырехзначного числа надо использовать все элементы, то искомые соединения — это перестановки из 4 элементов. Их количество — . При этом необходимо учесть, что в четырехзначном числе на первом месте не может стоять цифра 0. Таких чисел будет столько, сколько раз мы сможем выполнить перестановки из 3 оставшихся цифр, то есть .

Пример №48

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

Решение:

Сначала будем рассматривать учебники как одну книгу. Тогда на полке надо расставить не 10, а 7 книг. Это можно сделать способами. В каждом из полученных наборов книг можно выполнить еще перестановок учебников. По правилу умножения искомое количество способов равно

Комментарий:

Задачу можно решать в два этапа. На первом этапе условно будем считать все учебники за 1 книгу. Тогда получим 7 книг (6 не учебников + 1 условная книга — учебник). Порядок следования элементов учитывается и используются все элементы (поставить на полку необходимо все книги). Следовательно, соответствующие соединения — это перестановки из 7 элементов. Их количество — .

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

Сочетания без повторений

Сочетанием без повторений из элементов по называется любое -элементное подмножество -элементного множества.

Например, из множества } можно составить следующие сочетания без повторений из трех элементов:

Количество сочетаний без повторений из п элементов по к элементов обозначается символом (читается: «Число сочетаний из » или «це из », С — первая буква французского слова combinaison — сочетание). Как видим,

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

Составление размещения без повторений из элементов по проведем в два этапа. Сначала выберем разных элементов из заданного -элементного множества, не учитывая порядок выбора этих элементов (то есть выберем -элементное подмножество из -элементного множества — сочетание без повторений из -элементов по ). По нашему обозначению это можно сделать способами. После этого полученное множество из к разных элементов упорядочим. Его можно упорядочить способами. Получим размещения без повторений из элементов по . Следовательно, количество размещений без повторений из элементов по в раз больше числа сочетаний без повторений из элементов по . То есть Отсюда Учитывая, что по формуле (2) , получаем

Например, совпадает со значением, полученным выше.

Используя формулу (3), можно легко обосновать свойство 1 числа сочетаний без повторений, приведенное в таблице 21.

1) Поскольку

Для того чтобы формулу (4) можно было использовать и при , договорились считать, что. Тогда по формуле (4) .

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

Например,

Вычисление числа сочетаний без повторений с помощью треугольника Паскаля

Для вычисления числа сочетаний без повторений можно применять формулу (3): , а можно последовательно вычислять соответствующие значения, пользуясь таким свойством:

Для обоснования равенства (6) найдем сумму учитывая, что

, следовательно,

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

Каждая строка этой таблицы начинается с единицы и заканчивается единицей .

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

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

Примеры решения задач:

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

1. Учитывается ли порядок следования элементов в соединении?
2. Все ли заданные элементы входят в полученное соединение?

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

Пример №49

Из 12 членов туристической группы надо выбрать трех дежурных. Сколькими способами можно сделать этот выбор?

Решение:

Количество способов выбрать из 12 туристов трех дежурных равно количеству сочетаний из 12 элементов по 3 (без повторений), то есть

Комментарий:

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

Пример №50

Из вазы с фруктами, в которой лежит 10 разных яблок и 5 разных груш, требуется выбрать 2 яблока и 3 груши. Сколькими способами можно сделать такой выбор?

Решение:

Выбрать 2 яблока из 10 можно способами. При каждом выборе яблок груши можно выбрать способами. Тогда по правилу произведения выбор требуемых фруктов можно выполнить способами. Получаем

Комментарий:

Сначала отдельно выберем 2 яблока из 10 и 3 груши из 5. Поскольку при выборе яблок или груш порядок следования элементов не учитывается, то соответствующие соединения — сочетания без повторений.

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

Бином Ньютона

Бином Ньютона:

Поскольку то формулу бинома Ньютона можно записать еще и так:

Общий член разложения степени бинома имеет вид

Коэффициенты называют биномиальными коэффициентами.

Свойства биномиальных коэффициентов:

1. Число биномиальных коэффициентов (а следовательно, и число слагаемых в разложении степени бинома) равно
2. Коэффициенты членов, равноудаленных от начала и конца разложения, равны между собой (поскольку
3. Сумма всех биномиальных коэффициентов равна
4. Сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме биномиальных коэффициентов, стоящих на нечетных местах.
5. Для вычисления биномиальных коэффициентов можно воспользоваться треугольником Паскаля, в котором вычисления коэффициентов основываются на формуле

Треугольник Паскаля

Степень:

Коэффициенты разложения:

Ориентир:

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

Объяснение и обоснование Бинома Ньютона

Двучлен вида а + х также называют биномом. Из курса алгебры известно, что:

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

Формулу (7) называют биномом Ньютона. Правая часть этого равенства называется разложением степени бинома называют биномиальными коэффициентами. Общий член разложения степени бинома имеет вид

Обосновать формулу (7) можно, например, следующим образом.

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

Чтобы найти значение подставим в обе части равенства (8) вместо х значение 0. Получаем можем записать:

Чтобы найти сначала возьмем производную от обеих частей равенства (8):

затем, подставив в обе части полученного равенства (9) х = 0, получим: Учитывая, чтоможем записать: Аналогично, чтобы найти возьмем производную от обеих частей равенства (9):

и, подставив х = 0 в равенство (10), получим Тогда Другие коэффициенты находят аналогично. Если продифференцировать раз равенство (8), то получим:

Подставляя в последнее равенство х = 0, имеем

Ориентир:

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

Умножим обе части равенства (11) на и найдем коэффициент

. Подставляя найденные значения

1, 2, …,) в равенство (8), получаем равенство (7).

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

Например,

Так как формулу бинома Ньютона можно записать в виде:

а учитывая, что, еще и так:

Если в формуле бинома Ньютона (12) заменить х на (-х), то получим формулу возведения в степень разности а — х:

. Например, ( (знаки членов разложения чередуются!).

Свойства биномиальных коэффициентов

1. Число биномиальных коэффициентов (а следовательно, и число слагаемых) в разложении -й степени бинома равно + 1, поскольку разложение содержит все степени х от 0 до (и других слагаемых не содержит).

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

3. Сумма всех биномиальных коэффициентов равна 2″.

Для обоснования полагаем в равенстве (13) (или в равенстве (7)) значения а = х = 1 и получаем

Например,

4. Сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме биномиальных коэффициентов, стоящих на нечетных местах,

Для обоснования возьмем в равенстве (13) значения а =1, х = —1. Получаем

Тогда

Примеры решения задач:

Пример №51

По формуле бинома Ньютона найдите разложение степени

Комментарий:

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

Для упрощения записи ответа можно избавиться от иррациональности в знаменателях полученных выражений (см. решение) или сначала учесть, что ОДЗ заданного выражения: х > 0, и тогда То есть заданное выражение можно записать так: и возвести в степень последнее выражение.

Решение:

Пример №52

В разложении степени найти член, содержащий

Решение:

► ОДЗ: > 0. Тогда

Общий член разложения:

По условию член разложения должен содержать, следовательно,

. Отсюда

Тогда член разложения, содержащий , равен

Комментарий:

На ОДЗ (b > 0) каждое слагаемое в заданном двучлене можно записать как степень с дробным показателем. Это позволит проще записать общий член разложения степени: (где = 0, 1, 2, …, ), выяснить, какой из членов разложения содержит , и записать его.

Чтобы упростить запись общего члена разложения, удобно отметить, что

Зачем нужна комбинаторика

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

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

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

Если элемент может быть выбран способами, элемент / способами, …, элемент способами, то выбор одного из элементов может быть осуществлен пспособами.

Пример №53

В группе 30 студентов. Известно, что 5 из них на экзамене по математике получили оценку «отлично», 10 — оценку «хорошо», остальные -«удовлетворительно». Сколько существует способов выбрать одного студента, получившего на экзамене оценку «отлично» или «хорошо»?

Решение:

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

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

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

Пример №54

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

Решение:

Старостой может быть выбран любой из 30 студентов, его заместителем – любой из оставшихся 29, а профоргом – любой из оставшихся 28 студентов, т.е. По правилу произведения общее число способов выбора старосты, его заместителя и профорга равно = = 24360 способов. ◄

Пусть дано множество из n различных элементов. Из этого множества могут быть образованы подмножества из m элементов (0 ≤ m ≤n). Например, из 5 элементов a, b, c, d, e могут быть отобраны комбинации по 2 элемента – ab, bc, cd, ba и т.д., по 3 элемента – abc, cbd, cba и т.д.

Если комбинации из n элементов по m отличаются либо составом элементов, либо порядком их расположения (либо и тем и другим), то такие комбинации называют размещениями из n элементов по m. Число размещений из n элементов по m находится по формуле где n! равно произведению n первых чисел натурального ряда, т.е. n! = 1·2·…·n.

Пример №55

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

Решение:

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

Если комбинации из n элементов по m отличаются только с о с т а в о м элементов (порядок их расположения не имеет значения), то такие комбинации называют сочетаниями из n элементов по m.

Число сочетаний из n элементов по m находится по формуле

Пример №56

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

Решение:

Из смысла задачи следует, что порядок выбора книг не имеет значения. Здесь важен только их состав. Поэтому в данном случае комбинации книг представляют собой сочетания из 5 книг по 2. Число таких комбинаций Если в размещениях из n элементов по m некоторые из элементов (или все) могут оказаться одинаковыми, то такие размещения называют размещениями с повторениями из n элементов по m. Число размещений с повторениями равно

Пример №57

Сколько можно записать трехзначных чисел, которые не содержат цифр 0 и 5?

Решение:

В данном случае трехзначное число является комбинацией из восьми цифр (0 и 5 не учитываются) по три цифры. При этом некоторые из цифр (или все) могут повторяться. Поэтому в данном случае трехзначные числа является размещениями с повторениями из восьми цифр по три. Число таких размещений с повторениями Если в сочетаниях из n элементов по m некоторые из элементов (или все) могут оказаться одинаковыми, то такие сочетания называют сочетаниями с повторениями из n элементов по m. Число сочетаний с повторениями равно где определяется по формуле (1.6).

Пример №58

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

Решение:

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

Пример №59

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

Решение:

Каждый вариант жеребьевки отличается только порядком участников конкурса, т.е. является перестановкой из 5 элементов. Их число равно Если в перестановках из общего числа n элементов есть k различных элементов, при этом 1-й элемент повторяется раз, 2-й элемент – раз, k-й элемент – раз, причем, то такие перестановки называют перестановками с повторениями из n элементов. Число перестановок с повторениями равно

Пример №60

Сколько можно составить шестизначных чисел, состоящих из цифр 3, 5, 7, в которых цифра 3 повторяется 3 раза, цифра 5 – 2 раза, цифра 7 – 1 раз?

Решение:

Каждое шестизначное число отличается от другого порядком следования цифр (причем а их сумма равна 6), т.е. является перестановкой с повторениями из 6 элементов. Их число равно

Примеры решений задач по комбинаторике

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

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

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

Калькуляторы онлайн и примеры

Число перестановок Число размещений Число сочетаний

Число перестановок с повторениями Число размещений с повторениями Число сочетаний с повторениями

Еще: Комбинаторика в Excel

Задачи по комбинаторике с решениями онлайн

Задача 1. У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней подряд
она выдает по одному фрукту. Сколькими способами это может быть сделано?

Задача 2. Предприятие может предоставить работу по одной специальности 4
женщинами, по другой — 6 мужчинам, по третьей — 3 работникам независимо от пола.
Сколькими способами можно заполнить вакантные места, если имеются 14 претендентов: 6
женщин и 8 мужчин?

Задача 3. В пассажирском поезде 9 вагонов. Сколькими способами можно рассадить в поезде 4 человека, при условии, что все они должны ехать в различных вагонах?

Задача 4. В группе 9 человек. Сколько можно образовать разных подгрупп при условии, что в подгруппу входит не менее 2 человек?

Задача 5. Группу из 20 студентов нужно разделить на 3 бригады, причем в первую бригаду должны входить 3 человека, во вторую — 5 и в третью — 12. Сколькими способами это можно сделать.

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

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

Задача 8. Сколько различных дробей можно составить из чисел 3, 5, 7, 11, 13, 17 так, чтобы в каждую дробь входили 2 различных числа? Сколько среди них будет правильных дробей?

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

Задача 10. Каких чисел от 1 до 1 000 000 больше: тех, в записи которых встречается единица, или тех, в которых она не встречается?

Готовые примеры

Нужны решенные задачи по комбинаторике? Найди в решебнике:

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

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

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

Выбор правила	Выбор правила
Правило суммы	Правило произведения
Если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор объекта либо А, либо В можно осуществить m + n способами.	Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары А и В можно осуществить m · n способами.

Задача 1.

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

Решение.

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

Ответ: 24.

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

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

Задача 2.

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

Решение.

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

Ответ: 210.

Задача 3.

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

Решение.

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

A₁₀⁷ – A₉⁶ = 10 · 9 · 8 · 7 · 6 · 5 · 4 – 9 · 8 · 7 · 6 · 5 · 4 = 544 320.

Ответ: 544 320.

Задача 4.

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

Решение.

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

Ответ: 8! · 5!

Задача 5. 

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

Решение.

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

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

Ответ: 400 400.

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

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

Зарегистрироваться

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

Содержание:

1. Примеры задач с решением по комбинаторике

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

Примеры задач с решением по комбинаторике

Пример 1.

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

Решение:

Очевидно, что выбрать одну из имеющихся пар обуви, кроссовки или кеды, можна 5 + 2 = 7 способами.

Обобщая, приходим к комбинаторному правилу сложения:

если некоторый элемент А можно выбрать способами, а элемент В (независимо от выбора элемента А) — способами, то выбрать А или В можна способами.

Это правило справедливо также для трех и более элементов.

По этой ссылке вы найдёте полный курс лекций по теории вероятности:

Пример 2.

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

Решение:

Пирожок можно выбрать 4 способами и к каждому пирожку выбрать сок 3 способами (рис. 76). Следовательно, учащийся имеет 4 • 3 = 12 вариантов выбора завтрака.

Обобщая, приходим к комбинаторному правилу умножения:

если некоторый элемент А можно выбрать способами и после каждого такого выбора (независимо от выбора элемента А) другой элемент В можно выбрать способами, то пару объектов А и В можно выбрать способами.

Это правило справедливо также для трех и более элементов.

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

Пример 3.

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

Решение:

1) Первую цифру можем выбрать 4 способами (рис.77). Так как после вы-Т Т Т бора первой цифры их останется три (ведь циф-4-3-2 ры в нашем случае повторяться не могут), то вторую цифру можем выбрать 3 способами. И наконец, третью цифру можем выбрать из .—. .—. .—. оставшихся двух — то есть 2 способами. Следовательно, количество искомых трехзначных чисел будет равно 4 • 3 • 2 = 24.

2) Применим комбинаторное правило умножения. Так как цифры в числе могут повто-Рис. 78 ряться, то каждую из цифр искомого числа можно выбрать 4 способами (рис. 78), и тогда таких чисел будет 4 * 4 * 4 = 64.

Ответ. 1) 24 числа; 2) 64 числа.

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

Пример 4.

Сколько четных пятизначных чисел можно составить из цифр 5, 6, 7, 8, 9, если цифры в числе не повторяются?

Решение:

Четное пятизначное число можно получить, если последней его цифрой будет 6 или 8. Чисел, у которых последней является цифра 6, будет 4 • 3 • 2 * 1 = 24 (рис. 79),

а тех, у которых последней является цифра 8, — также 24. По комбинаторному правилу сложения всего четных чисел будет 24 + 24 = 48.

Ответ. 48.

Пример 5.

Азбука племени АБАБ содержит всего две буквы — «а» и «б». Сколько слов в языке этого племени состоит: 1) из двух букв; 2) из трех букв?

Решение:

1) аа, ба, аб, бб (всего четыре слова); 2) ааа, ааб, аба, абб, ббб, бба, баб, баа (всего восемь слов).

Заметим, что найденное количество слов соответствует комбинаторному правилу уможения. Так как на каждое место есть два «претендента» — «а» и «б», то слов, состоящих из двух букв, будет 2 * 2 = 4, а из трех букв — 2 * 2 * 2 = 8.

Пример 6.

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

Решение:

Капитаном можно выбрать любого из 11 игроков, а его заместителем — любого из 10 оставшихся игроков. Таким образом (по правилу умножения), имеем 11 • 10 = 110 разных способов.

Пример 7.

В Стране Чудес 10 городов и каждые два из них соединяет авиалиния. Сколько авиалипий в этой страпе?

Решение:

Так как каждая авиалиния соединяет два города, то одним из них может быть любой из 10 городов, а другим — любой из 9 оставшихся. Следовательно, количество авиалиний равно 10 • 9 = 90. Но при этом каждую из авиалиний мы учли дважды. Поэтому всего их будет 90 : 2 = 45.

Комбинаторные задачи неразрывно связаны с задачами теории вероятностей, еще одного раздела математики, который мы рассмотрим на следущих страницах сайта.

В китайских рукописях, относящихся к XIII—XII в. до н. э. встречаются упоминания о вопросах, близких к комбинаторным. Некоторые комбинаторные задачи решали и в Древней Греции. В частности, Аристоксен из Тарента (IV в. до н. э.), ученик Аристотеля, перечислил различные комбинации длинных и коротких слогов в стихотворных размерах. А Папп Александрийский в IV в. н. э. рассматривал число пар и троек, которые можно получить из трех элементов, допуская их повторения. Некоторые элементы комбинаторики были известны и в Индии во II в. до н. э. Индийцы умели вычислять числа, известные нам как коэффициенты формулы бинома Ньютона. Позднее, в VIII в. н. э., арабы нашли и саму эту формулу, и ее коэффициенты, которые сейчас вычисляют с помощью комбинаторных формул или «треугольника Паскаля».

Свой нынешний вид упомянутые комбинаторные формулы приобрели благодаря средневековому ученому Леви бен Гершону (XIV в.) и французскому математику П. Эригону (XVII в.).

В III в. н. э. сирийский философ Порфирий для классификации понятий составил специальную схему, получившую название «древо Порфирия». Сейчас подобные деревья используются для решения определенных задач комбинаторики в разнообразных областях знаний. Некоторые ранее неизвестные комбинаторные задачи рассмотрел Леонардо Пизанский (Фибоначчи) в своей знаменитой «Книге абака» (1202 г.), в частности, о нахождении наименьшего набора различных гирь, позволяющего взвесить груз с любой целочисленной массой, не превышающей заданного числа. Со времен греческих математиков были известны две последовательности, каждый член которых получали по определенному правилу из предыдущих, — арифметическая и геометрическая прогрессии. А Фибоначчи впервые в одной из задач выразил член последовательности через два предыдущих, используя формулу, которую назвали рекуррентной. В дальнейшем метод рекуррентных формул стал одним из мощнейших для решения комбинаторных задач.

Как ни странно, развитию комбинаторики в значительной степени способствовали азартные игры, которые были очень популярны в XVI в. В частности, вопросами определения разнообразных комбинаций в игре в кости в то время занимались такие известные итальянские математики, как Д. Кардано, Н. Тарталья и др. А наиболее полно изучил этот вопрос в XVII в. Галилео Галилей.

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

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

Теория вероятностей — раздел математики, в котором изучаются закономерности случайных событий.

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

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

Таким образом,

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

Исходом случайного испытания является случайное событие.

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

Примерами случайных событий могут быть «выпадение единицы при подбрасывании игрального кубика», «выпадение аверса при подбрасывании монеты», «выигрыш 10 грн при покупке лотерейного билета» и т. п. Такие события, как «закипание воды при ее нагревании до 100 °C» или «уменьшение длипы провода при его охлаждении», нельзя пазвать случайными, потому что они — закономерные.

Случайные события, как правило, обозпачают большими латинскими буквами: А, В, С, D, … .

Пример 8.

В ящике лежат только белые и черные шары. Из него наугад вынимают один шар. Какие из событий А, В, С, D при этом могут произойти:

А — вынут белый шар;

В — вынут черный шар;

С — вынут зеленый шар;

D — вынут шар?

Решение:

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

Ответ. А, В, D.

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

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

В примере 1 события А и В — случайные, D — достоверное событие, С — невозможное событие.

Пример 9.

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

Решение:

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

Если в неизменных условиях проведено п случайных испытаний и событие А произошло в п(А) случаях, то число п(А) называют частотой события А, а отношение относительной частотой события А.

Пример 10.

Испытание состоит в подбрасывании игрального кубика 150 раз подряд. Пусть событием А будет выпадение шестерки. При проведении испытания это событие произошло 24 раза. Число 24 — частота события А, а отношение — относительная частота события А.

Решение:

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

Пример 11.

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

Решение:

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

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

Вероятность принято обозначать латинской буквой р (первая буква французского слова probabilite и латинского probabilitas, что в переводе означает «возможность», «вероятность»). Тогда в примере 4: р(А) = 0,5, или же р = 0,5.

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

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

Тогда относительную частоту можно считать

вероятностью попадания этого стрелка по данной мишени.

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

Пример 12.

Вероятность попадапия стрелка по мишени равна 0,781. Сколько метких выстрелов приблизительно будет у этого стрелка в серии из 50 выстрелов?

Решение:

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

Если считать, что относительная частота попаданий приблизительно равна вероятности, то , то есть

Ответ. 39 метких выстрелов.

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

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

Как наука теория вероятностей зародилась в XVII в. На ее развитие повлияли насущные потребности науки и практики того времени, в частности в деле страхования, которое распространялось благодаря бурному развитию торговых связей и путешествий. Удобной моделью для решения задач и анализа понятий теории вероятностей были для ученых азартные игры. Об этом заметил еще Гюйгенс в своей книге «О расчетах в азартной игре» (1657 г.), которая стала первой в мире книгой по теории вероятностей. Дальнейшему развитию теории вероятностей (XVII-XVIII вв.) способствовали работы Б. Паскаля, Д. Бернулли, Ж.Л. Д’Аламбера, Д. Крега, Т. Симпсона, П. Ферма, Т. Байеса и др.

Важный вклад в теорию вероятностей сделал швейцарский математик Я. Бернулли (1654-1705): он доказал закон больших чисел в самом простом случае независимых испытаний в книге «Аналитическая теория вероятностей».

В 1718 г. английский математик А. Муавр (1667-1754) опубликовал книгу «Теория случая», в которой исследовал закономерности, присущие случайным явлениям.

Впервые основы теории вероятностей изложил французский математик П. Лаплас (1749-1827).

В дальнейшем теория вероятностей развивалась благодаря работам француза С. Пуассона (1781-1840) и россиян П.Л. Чебышева (1821-1894), А.А. Маркова (1856-1922) и А.М. Ляпунова (1857-1918).

Свой вклад в развитие теории вероятностей сделали и украинские математики: Б.В. Гнеденко (1912-1996), И.И. Гихман (1918-1985), А.В. Скороход (1930-2011), М.И. Ядренко (1932-2004).

МИНИСТЕРСТВО ПРОСВЕЩЕНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего образования «Пермский государственный Гуманитарно-педагогический университет» Математический факультет Кафедра высшей математики и методики обучения математике
Курсовая работа по дисциплине (модулю) «Математический анализ»
Виды комбинаторных задач и методы их решения
		Работу выполнил: обучающаяся 121 группы направления подготовки 44.03.05 Педагогическое образование (с двумя профилями подготовки), направленность (профиль) «Математика и Информатика» Гурина Анна Олеговна ________________ (подпись)
«Допущена к защите» Заведующий кафедрой ________________ (подпись) «___»___________20__г.		Руководитель: канд. педагогических наук, доцент кафедры высшей математики и методики обучения математике Черемных Елена Леонидовна ________________ (подпись)
Оценка: _________________ Руководитель: ___________ (подпись)
	Пермь 2020

оглавление

введение 3

глава 1. комбинаторика как наука 5

1.1. Понятие комбинаторики 5

1.2. История комбинаторики 8

1.3. Классические комбинаторные задачи 11­

1.4. Разделы комбинаторики 14

глава 2. решение основных видов комбинаторных задач 16

2.1. Комбинаторные правила суммы и произведения 16

2.1. Перестановки, сочетания и размещения без повторений 18

2.2. Перестановки, сочетания и размещения с повторениями 21

2.3. Комплекс задач на применение формул комбинаторики 24

заключение 28

список литературы 30

введение

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

Комбинаторика возникла еще в древние времена и развивается по сей день. Она связана с такими областями математики, как алгебра, геометрия и теория вероятности. Её практическое значение даже в жизни обычного человека сложно переоценить. Мы часто решаем комбинаторные задачи, сами о том не подозревая. Например, рассаживая гостей на мероприятии, составляя график дежурств и т.д.

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

Для достижения поставленной цели были сформулированы следующие задачи исследования:

• анализ исторической и математической литературы по теме исследования;

• выявление основных видов комбинаторных задач и методов их решения;

• подбор примеров на каждый вид и метод решения комбинаторных задач.

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

Объектом исследования являются задачи комбинаторики.

Предметом исследования являются методы решения основных видов комбинаторных задач.

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

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

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

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

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

глава 1. комбинаторика как наука

1. Понятие комбинаторики

Согласно источнику «Статистика. Вероятность. Комбинаторика» Я. С. Бродского, комбинаторика или комбинаторный анализ — это раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка) [14, с.19-20].

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

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

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

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

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

Их используют также для решения транспортных задач (в частности задач по составлению расписаний), для составления планов производства и реализации продукции, в теории случайных процессов, статистике, вычислительной математике, планировании экспериментов, шахматных программах для ЭВМ. [6, с.23].

Согласно данным источника «Конкретная математика. Основание информатики» под редакцией Р. Грэхема, Д. Кнута и О. Паташника, правила комбинаторики также используются для составления и декодирования шифров и для решения других проблем информации. Значительную роль комбинаторные методы играют и в чисто математических вопросах – при изучении конечных геометрий, теории групп и их представлений, неассоциативных алгебр и т.д. [7, с.696-700]

По данным источника «Теоремы и задачи комбинаторной геометрии» В. Г. Болтянского и И. Ц. Гохберга, комбинаторика присутствует в программах учебных заведений различного уровня подготовки. Задачи на комбинаторику и теорию вероятностей можно найти как в учебниках младшей школы, так и средней, и старшей. Данные задачи используются в том числе и при составлении заданий Единого Государственного Экзамена. Даже в высших учебных заведениях присутствуют дисциплины, которые предусматривают изучение вопросов комбинаторики и теории вероятностей.

В повседневной жизни нередко возникают проблемы, которые имеют не один, а несколько вариантов решения. Чтобы сделать правильный выбор, очень важно не упустить ни один из них. Для этого надо уметь осуществлять перебор всех возможных вариантов или хотя бы подсчитывать их число. Такого рода задачи называют комбинаторными. [15, с.76-80]

Тематика современной комбинаторики, как гласит источник «Популярная комбинаторика» под редакцией Н.Я. Виленкина, разнообразна: перечислительные и экстремальные задачи, проблемы существования, выбора и расположения, геометрические и алгебраические интерпретации [11, с.44].

Как указывается в источнике «Комбинаторика» Н. Я. Виленкина, А. Н. Виленкина и П. А. Виленкина, в математической литературе отмечаются три отличительные черты комбинаторных задач, которые заключаются в следующем:

• все объекты, описываемые в задачах, состоят из отдельных дискретных элементов.

• множества этих элементов конечны.

• преимущество отдано двум видам операций: отбор подмножеств и упорядочению элементов множества.

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

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

[5, с.99-102]

1. История комбинаторики

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

Согласно источнику «С древнейших времен до начала Нового времени» под редакцией А.П. Юшкевича, первые упоминания комбинаторики можно заметить в символике китайской «Книги Перемен» (V век до н. э.). По мнению её авторов, всё в мире комбинируется из различных сочетаний мужского и женского начал, а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небо.

Классическая задача комбинаторики: «сколько есть способов извлечь m элементов из N возможных» упоминается ещё в сутрах древней Индии (начиная примерно с IV века до н. э.). Индийские математики, видимо, первыми открыли биномиальные коэффициенты и их связь с биномом Ньютона.

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

Хрисипп (III век до н. э.) и Гиппарх (II век до н. э.) подсчитывали, сколько следствий можно получить из 10 аксиом; методика подсчёта нам неизвестна, но у Хрисиппа получилось более миллиона, а у Гиппарха — более 100000. Какие-то комбинаторные правила пифагорейцы, вероятно, использовали при построении своей теории чисел и нумерологии (совершенные числа, фигурные числа, пифагоровы тройки и др.).

В XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями. [13, с.198-204]

В Западной Европе ряд глубоких открытий в области комбинаторики сделали два еврейских исследователя, Авраам ибн Эзра (XII век) и Герсонид (XIV век). Ибн Эзра подсчитывал число размещений с перестановками в огласовках имени Бога и обнаружил симметричность биномиальных коэффициентов, а Герсонид дал явные формулы для их подсчёта и применения в задачах вычисления числа размещений и сочетаний.

Несколько комбинаторных задач содержит «Книга абака» (Фибоначчи, 13 век). Например, он поставил задачу найти наименьшее число гирь, достаточное для взвешивания любого товара весом от 1 до 40 фунтов.

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

В источнике «Математика XVII столетия» под редакцией А. П. Юшкевича сказано, что в историю зарождавшейся теории вероятностей вошла переписка заядлого игрока шевалье де Мерэ с Пьером Ферма и Блезом Паскалем, где были затронуты несколько тонких комбинаторных вопросов. Помимо азартных игр, комбинаторные методы использовались (и продолжают использоваться) в криптографии — как для разработки шифров, так и для их взлома.

Блез Паскаль много занимался биномиальными коэффициентами и открыл простой способ их вычисления: «треугольник Паскаля». Хотя этот способ был уже известен на Востоке (примерно с X века), Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого треугольника.

Наряду с Лейбницем, он считается основоположником современной комбинаторики. Сам термин «комбинаторика» придумал Лейбниц, который в 1666 году (ему было тогда 20 лет) опубликовал книгу «Рассуждения о комбинаторном искусстве». [8, с.299-304]

По словам А. П. Юшкевича в источнике «Математика XVIII столетия», термин «комбинаторика» Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику. Ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713 г.) множество сведений по комбинаторике.

В этот же период формируется терминология новой науки. Термин «сочетание» (combination) впервые встречается у Паскаля (1653 г., опубликован в 1665 г.). Термин «перестановка» (permutation) употребил в указанной книге Якоб Бернулли. Он же использовал и термин «размещение» (arrangement).

Окончательно комбинаторика как самостоятельный раздел математики оформилась в трудах Эйлера.

Он детально рассмотрел, например, следующие проблемы:

• задача о ходе коня;

• задача о семи мостах, с которой началась теория графов;

• построение греко-латинских квадратов;

• обобщённые перестановки.

Кроме перестановок и сочетаний, Эйлер изучал разбиения, а также сочетания и размещения с условиями. [9, с.379-383]

1. Классические комбинаторные задачи

По указанным в источнике «Развитие некоторых классических комбинаторных задач» А. Е. Малых, А. А. Давыдовой данным, классическими комбинаторными задачи являются следующие задачи:

Магический квадрат (рис. 1) — квадратная таблица (n * n) целых чисел от 1 до n такая, что суммы чисел вдоль любого столбца, любой строки и двух диагоналей таблицы равны одному и тому же числу . Число n называют порядком магического квадрата. Доказано, что магический квадрат можно построить для любого .

Рис.1. Магический квадрат

Греко-латинский квадрат или эйлеров квадрат (рис. 2) — квадрат N×N в каждой клетке которого стоят 2 числа от 1 до N так, что выполняются условия:

• в каждой строке и столбце каждая цифра встречается один раз на первом месте в паре, и один раз на втором.

• каждая цифра стоит в паре с каждой другой цифрой и с самой собой по одному разу.

Рис.2. Греко-латинский квадрат

Данную тему рассматривают А. Е. Малых и А. С. Каленкова в источнике «Об исследовании Леонардом Эйлером латинских квадратов». [10, с.102-116]

Задача размещения – одна из классических комбинаторных задач, в которой требуется определить чисто способ размещения m различных предметов в n различных ячейках с заданным числом r пустых ячеек.

Задача коммивояжёра (рис. 3) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.

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

Рис.3. Частный случай задачи коммивояжёра

Бином Ньютона – формула возведения двухчлена (a + b) в целую неотрицательную степень n. Строго говоря, всю формулу нельзя назвать биномом, так как «бином» переводится как «двучлен». Кроме того, формула разложения была известна еще до Ньютона, Исаак Ньютон распространил это разложение на случай n n – дробного. Цель изучения бинома Ньютона – упрощение вычислительных действий.

Знакомая нам из школьного курса математики формула сокращенного умножения «квадрат суммы» — это частный случай бинома Ньютона для n = 2.

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

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

Назван в честь Блеза Паскаля. Числа, составляющие треугольник Паскаля, возникают естественным образом в алгебре, комбинаторике, теории вероятностей, математическом анализе, теории чисел. [12, с.82-102]

Рис.4. Общий вид треугольника Паскаля

1. Разделы комбинаторики

Как гласят источники «Дискретная математика и комбинаторика» Дж. Андерсона и «Комбинаторика» М. Холла, перечислительная или исчисляющая комбинаторика — это раздел комбинаторики, который рассматривает задачи о перечислении или подсчёте количества различных конфигураций, образуемых элементами конечных множеств, на которые могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения и т. п. Типичным примером задач данного раздела является подсчёт количества перестановок.

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

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

Вероятностная комбинаторика — это раздел дискретной математики, в котором методы теории вероятностей применяются для изучения комбинаторных объектов. В данном разделе рассматриваются также перечислительные задачи комбинаторики и вопросы существования комбинаторных объектов с заданными характеристиками. [3, с.564-569]

Топологическая комбинаторика — молодая область математики, возникшая в последней четверти 20-го века, которая занимается следующими вопросами:

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

• Топологические обобщения задач дискретной геометрии

• Дискретизация топологических понятий

Инфинитарная комбинаторика — это раздел комбинаторики, реализующий идеи и методы комбинаторики для решения задач с бесконечными (в том числе, несчётными) множествами. [4, с.323-327]

глава 2. решение основных видов комбинаторных задач

В данной главе рассмотрены основные виды комбинаторных задач, приведены примеры для каждого типа, а также составлен собственный комплекс задач по каждой теме. Приведённую ниже классификацию комбинаторных задач указывают авторы Н. Алон и Дж. Спенсер. в источнике «Вероятностный метод: учебное пособие». [2, с.120-150]

1. Комбинаторные правила суммы и произведения

Если объект A можно выбрать из некоторого множества объектов m способами, а другой объект B – n способами, то выбор объекта A или объекта B (без разницы какого) возможен m + n способами.

Если объект A можно выбрать из некоторого множества объектов m способами и после каждого такого выбора объект B можно выбрать n способами, то упорядоченная пара объектов (A; B) может быть выбрана m ∙ n способами.

Важная содержательная часть правил состоит в том, знак «плюс» понимается и читается как союз ИЛИ, а знак «умножить» – как союз И.

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

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

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

Из 10 юношей одного можно выбрать 10 способами.

Из 13 девушек 13 способами можно выбрать одну.

10 ∙ 13 = 130 способами можно составить пару из юноши и девушки.

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

Решение:

В разряд сотен можно записать любую из цифр 1 – 9. Ноль не годится, так как в этом случае число перестаёт быть трёхзначным.

В разряд десятков можно выбрать любую из 10 цифр. По условию, число должно делиться на 5. Число делится на 5, если оно заканчивается на 5 либо на 0. Таким образом, в младшем разряде нас устраивают 2 цифры.

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

Таким образом, 9 способами можно выбрать первую цифру.

Вторую цифру можно выбрать 10 способами.

Третью цифру можно выбрать только 2 способами.

Итого: 9 ∙ 10 ∙ 2 = 180 чисел, которые делятся на 5.

• Сколько существует выигрышных комбинаций из 2 карт при игре в «двадцать одно»?

Решение:

Выигрывает комбинация десятка и туз (11 очков) = 21 очко. Союз «и» подсказывает нам, что для решения задачи снова придётся обратиться к правилу умножения.

Одну десятку из 4 имеющихся в колоде можно выбрать 4 способами.

Так как туза в колоде тоже четыре, для его выбора количество способов будет таким же, поэтому окончательный результат: 4 ∙ 4 = 16 выигрышных комбинаций.

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

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

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

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

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

Приведённые в качестве примеров комбинаторные задачи были приведены в источнике «Алгебра и теория чисел. Сборник задач для математических школ» под редакцией Н. Б. Алфутовой и А. В. Устинова.

1. Перестановки, сочетания и размещения без повторений

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

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

Формула количества перестановок без повторений:

В общем виде смысл задачи можно сформулировать так: «Сколькими способами можно переставить m объектов?».

Рассмотрим примеры заданий на данный тип комбинаторных задач

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

Решение: способами

• Веселые человечки построились в ряд: Незнайка, Знайка, Тобик, Винтик, Шпунтик, Кнопочка, Сиропчик, Цветик, Гунька, Ворчун, Пончик. Сколькими способами они могли это сделать?

Решение: способами

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

Решение: способами

1. Сочетания без повторений

Формула количества сочетаний без повторений:

В общем виде смысл задачи можно сформулировать так: «Сколькими способами можно выбрать m объектов из n?».

Рассмотрим примеры заданий на данный тип комбинаторных задач

• На день рождения Лене подарили коробку конфет (в коробке 30 штук). Сколькими способами она может выбрать по одной конфете пятерым подругам?

Решение: способами

• У Малыша есть 10 видов сладостей. Он предложил Карлсону выбрать 2 вида сладостей из этого списка. Между сколькими возможностями придется выбирать Карлсону?

Решение: способами

• В «Лукойл» требуются 9 охранников. В агентстве «Альфа» есть 15 человек, подходящих на эту должность. Сколькими способами может быть набран отдел охраны «Лукойла»?

Решение: способами

1. Размещения без повторений

Формула количества размещений без повторений:

В общем виде смысл задачи можно сформулировать так: «Сколькими способами можно выбрать m объектов из n и в каждой выборке переставить их определенным образом?». Исходя из вышесказанного, справедлива следующая формула:

Рассмотрим примеры заданий на данный тип комбинаторных задач

• Боря, Дима и Володя сели играть в «двадцать одно». Сколькими способами им можно сдать по одной карте?

Решение: способами

• В цехе работают 8 токарей. Сколькими способами можно поручить трем из них изготовление различных видов деталей (по одному виду на каждого)?

Решение: способами

• Студенты института изучают в каждом семестре по десять дисциплин. В расписание занятий включаются каждый день по 3 дисциплины. Сколько различных расписаний может составить диспетчерская?

Решение: способами

1. Перестановки, сочетания и размещения с повторениями

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

1. Перестановки с повторениями

Формула количества перестановок с повторениями:

, где

В общем виде смысл задачи можно сформулировать так: «Количество способов, которыми можно переставить m объектов, среди которых один объект повторяется n₁ раз, второй объект повторяется n₂ раз, третий объект – n₃ раз и т.д.?».

Рассмотрим примеры заданий на данный тип комбинаторных задач

• Сколько различных буквосочетаний можно получить перестановкой карточек со следующими буквами: К, О, Л, О, К, О, Л, Ь, Ч, И, К??

Решение: буквосочетаний

• Алексей занимается спортом, причём четыре дня в неделю – лёгкой атлетикой, два дня – силовыми упражнениями и один день отдыхает. Сколькими способами он может составить себе расписание занятий на неделю?

Решение: способами

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

Решение: способами

1. Сочетания с повторениями

Формула количества сочетаний с повторениями:

В общем виде смысл задачи можно сформулировать так: «Для выбора предложено n множеств, каждое из которых состоит из одинаковых объектов. Сколькими способами можно выбрать m объектов?».

Рассмотрим примеры заданий на данный тип комбинаторных задач

• В студенческой столовой продают сосиски в тесте, пирожки с капустой и пирожки с яйцом и зелёным луком. Сколькими способами можно приобрести пять единиц выпечки?

Решение: = 21 способом

• В кошельке находится достаточно большое количество однорублёвых, двухрублёвых, пятирублёвых и десятирублёвых монет. Сколькими способами можно извлечь три монеты из кошелька?

Решение: = 20 способами

• Сколько целых решений в неотрицательных числах имеет уравнение

?

Решение:

Переформулируем задачу в терминах комбинаторики. Пусть у нас есть m=8 условных единиц, их нужно разместить в n=4 условных ёмкостях. Так как решение требуется в неотрицательных числах, то ёмкость в том числе может быть пустой.

Применяем формулу числа сочетаний с повторениями:

= 165 решений

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

Формула количества размещений с повторениями:

В общем виде смысл задачи можно сформулировать так: ««Дано множество, состоящее из n объектов, при этом любой объект можно выбирать неоднократно. Сколькими способами можно выбрать m объектов, если важен порядок их расположения в выборке? »

Рассмотрим примеры заданий на данный тип комбинаторных задач

• Сколько существует четырёхзначных пин-кодов? (Учитывая, что для пин-кода используются цифры от 0 до 9, то есть всего их десять).

Решение: пин-кодов

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

Решение: способом

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

Решение: пусть у нас есть m=5 нечётных цифр (1,3,5,7,9). Их нужно расставить на n=3 места, т.к. число трёхзначное, тогда:

трехзначных чисел.

1. Комплекс задач на применение формул комбинаторики

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

1. На столе лежат фрукты – киви, яблоко и банан. Сколькими способами можно их переложить?

Решение: способами.

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

Решение: способами.

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

Решение: способами.

Сочетания без повторений

1. На столе лежат фрукты – киви, яблоко и банан. Сколькими способами можно выбрать два фрукта?

Решение: = 3 способами.

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

Решение: = 5 способами.

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

Решение: = 4 способами.

Размещения без повторений

1. На столе лежат фрукты – киви, яблоко и банан. Сколькими способами можно раздать по одному фрукту Пете и Васе?

Решение: способами.

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

Решение: способами.

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

Решение: способами.

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

1. Имеется восемь шаров различных цветов. Сколькими способами можно разложить шары в три коробки так, чтобы в первой коробке было 3 шара, во второй четыре, а в третьей — один?

Решение: способами.

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

Решение: способами.

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

Решение: способами.

Сочетания с повторениями

1. Имеются шары трёх различных цветов: красные, синие и жёлтые. Сколькими способами можно достать десять шаров?

Решение: способами.

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

Решение: способами.

1. На шахматной доске расставлены фигуры четырёх видов: кони, слоны, ладьи и пешки. Сколькими способами можно выбрать 9 фигур?

Решение: способами.

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

1. Имеется пять различных шаров, их нужно разложить по двум различным ящикам (на число шаров в ящиках ограничений нет – ящик может вместить как все шары, так и остаться пустым). Сколькими способами можно это сделать?

Решение: способами.

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

Решение: способами.

1. Сколькими способами можно расставить все белые пешки (8 штук) на двух шахматных линиях? Расстановка может быть любой.

Решение: способами.

Комбинаторные правила суммы и произведения

1. В кафе подают 6 видов молочных коктейлей и 10 видов соков. Сколькими способами можно заказать напиток в этом кафе? (Заказать можно только один вид напитка).

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

Один вид сока из 10 предложенных можно выбрать 10 способами.

Один вид молочного коктейля из 6 предложенных — 6 способами.

10 + 6 = 16 способов заказать напиток в этом кафе.

1. Немного изменим условие. В кафе подают 6 видов выпечки и 10 видов соков. Сколькими способами можно сделать заказ, который будет состоять из выпечки и сока?

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

Один вид сока из 10 предложенных можно выбрать 10 способами.

Один вид выпечки из 6 предложенных — 6 способами.

10 ∙ 6 = 60 способов заказать выпечку и сок в этом кафе.

1. Сколько можно составить чётных двухзначных чисел?

Решение: по аналогии с рассмотренной в примерах задачей, будем применять правило комбинаторного умножения. Первую цифру числа можем выбрать из 9 цифр (1-9), так как ноль не подходит. Вторая цифра должна быть чётной, поэтому нам подойдут пять цифр – 0, 2, 4, 6 и 8.

Таким образом, выбрать первую цифру можно 9 способами.

Вторую цифру – 5 способами.

Итого: 9 ∙ 5 = 45 способов составить чётных двухзначных чисел.

заключение

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

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

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

Изучением комбинаторики занимались выдающиеся учёные такие, как Блез Паскаль, Пьер Ферма, Джероламо Кардано, Якоб Бернулли, Леонард Эйлер и многие другие.

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

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

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

Комбинаторика тесно связана с такой наукой, как теория вероятностей, поэтому ещё одним возможным шагом дальнейшего исследования может стать исследовательская работа по теории вероятностей­.

список литературы

1. Алгебра и теория чисел. Сборник задач для математических школ / Н.Б. Алфутова, А.В. Устинов. — М.: МЦНМО, 2002. — 264 с.

2. Вероятностный метод: учебное пособие [Электронный ресурс] / Н. Алон, Дж. Спенсер. Пер. с англ. — М.: Бином. Лаборатория знаний, 2013. — 320 с.

3. Дискретная математика и комбинаторика / Дж. Андерсон. Пер. с англ. — М.: Изд-во Вильямс, 2006. — 960 с.

4. Комбинаторика / М. Холл. Пер. с англ. — М.: Мир, 1970. — 421 с.

5. Комбинаторика / Н. Я. Виленкин, А. Н. Виленкин, П. А. Виленкин. — М.: ФИМА, МЦНМО, 2017. — 400 с.

6. Комбинаторика в жизнедеятельности человека и решение комбинаторных задач / И. И. Роганова // Международный журнал гуманитарных и естественных наук. Педагогические науки. — 2018. — № 3. — С. 20-25.

7. Конкретная математика. Основание информатики / Р. Грэхем, Д. Кнут,

О. Паташник. Пер. с англ. — М.: Мир, 1998. — 703 с.

1. Математика XVII столетия // История математики / А. П. Юшкевич,

в трёх томах. — М.: Наука, 1970. — Т. II. — 301 с.

1. Математика XVIII столетия // История математики / А. П. Юшкевич,

в трёх томах. — М.: Наука, 1972. — Т. III. — 496 с.

1. Об исследовании Леонардом Эйлером латинских квадратов/ А. Е. Малых, А. С. Каленкова // Вестник ПГГПУ. Серия № 2. Физико-математические и естественные науки. — 2017. — № 1. — С. 102-116.

2. Популярная комбинаторика / Н. Я. Виленкин. — М.: Наука, 1975. — 208с.

3. Развитие некоторых классических комбинаторных задач / А. Е. Малых, А.А. Давыдова // Вестник ПГГПУ. Серия № 2. Физико-математические и естественные науки. — 2017. — № 1. — С. 82-102.

4. С древнейших времен до начала Нового времени // История математики / А. П. Юшкевич, в трёх томах. — М.: Наука, 1970. — Т. I. — 352 с.

5. Статистика. Вероятность. Комбинаторика / Я. С. Бродский. — М.: Оникс, Мир и Образование, 2008. — 544 с.

6. Теоремы и задачи комбинаторной геометрии / В. Г. Болтянский,

И. Ц. Гохберг. — М.: Наука, 1965. — 108 с.

1