Как найти сумму сочетаний

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

Содержание:

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

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

Перестановкой из 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 элементов. Их число равно

Сочетания.

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

Определение
3: Сочетания
из
элементов поэлементов
()
– это расстановки, отличающиеся друг
от другасоставом,
но не порядком
элементов. Обозначают:
.

Теорема
4: Число
сочетаний находится по следующей
формуле:

.

Доказательство: .

Следствие:
Выведенная формула совпадает с формулой
для числа повторений из
элементов одного типа иэлементов второго типа:

.

Иными
словами справедливо равенство:
.

Примеры:
Выбор делегации, число призеров в
соревновании и т. д.

Замечание:
,
.

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

2) Сочетания с
повторениями.

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

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

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

.

Для числа сочетаний
с повторениями существует формула:

.

§2. Свойства сочетаний. Бином Ньютона.

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

1.
.

2.
.

Доказательство:

1)
.

2)
.

Сочетания
можно встретить и в школьном курсе
математики. Например, в качестве
коэффициентов бинома Ньютона выступают
именно сочетания. Формула бинома Ньютона
в общем виде и её доказательство
приводятся в следующей теореме.

Теорема
1: .

Доказательство:
Применим индукцию по
.

При
:.

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

.

Покажем,
что формула выполняется для
—
й степени:

.

В
доказательстве можно также использовать
свойство:
.

Следствие:
Рассмотрим некоторые частные случаи
формулы бинома Ньютона:

1)
если
,
то.

2)
если
,
то.

Определение
1: Коэффициенты
бинома Ньютонаназываются
биномиальными коэффициентами.

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

1 n
= 0

1 1 n
= 1

1 2 1 n
= 2

1
3 3 1 n
= 3

1 4 6 4 1 n
= 4

1 5 10 10 5 1 n
= 5

. . . . . . . . . . . . . . . . . . . . . . . . .

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

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

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

.

Если
числа
получаются перестановкой из чисел,
то считается, что

.

Пример:
Возвести в пятую степень сумму трёх
слагаемых.

Здесь
учитывается, что 5 можно разбить на 3
слагаемых пятью способами:

;;;;.

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

.

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

Замечание:
Сумма полиномиальных коэффициентов
может быть найдена по формуле:

.

Для коэффициентов
из рассмотренного примера можно
проверить:

,

.

Рассмотрим
—
сочетания с повторениями, составленные
из элементовтипа, например избуквы.
Число таких сочетаний равно:.
Разобьём все эти сочетания на классы,
отнеся к‑
му классу сочетания, в которыхраз входит буква.
Остальныемест могут быть заняты оставшимися
буквами,
число которых равно.
Поэтому в—
й класс входит столько сочетаний, сколько
можно составитьсочетаний с повторениями из элементовтипов, т.е..

Значит
общее число всех таких сочетаний равно:

,
т.е.

.

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

.

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

Если
,
то искомая зависимость имеет вид:

.

Для
имеем:

,

или окончательно:

.

Для
получаем:

,

или после
преобразований:

.

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

Соседние файлы в папке 26-03-2013_00-36-55

• #
• #
• #
• #

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

• Факториал, правила суммы и произведения
• Перестановка
• Размещение
• Сочетание
• Как использовать перестановки, размещения и сочетания в анализе данных
• Совет эксперта

Самые популярные факториалы

Рекуррентная формула факториала

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

Правило суммы — если объект A можно выбрать способами, а объект B можно выбрать способами, то объект «A или B» можно выбрать n + m способами.

Правило произведения — если объект A можно выбрать n способами и после каждого такого выбора объект B можно выбрать m способами, то для пары «A и B» есть n ∙ m вариантов выбора.

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

Получить больше практики по расчёту количества комбинаций можно в модуле «Комбинаторика» тренажёра «Основы математики для цифровых профессий».

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

Решение. Три футболки можно расположить на странице способами: P₃ = 3! = 1 ∙ 2 ∙ 3.

Пример. Чтобы выполнить ежедневный квест, игроку нужно принести магу корзину с четырьмя кристаллами разного цвета. Первой необходимо найти корзину, а кристаллы можно сложить в неё в произвольном порядке. Как найти число способов выполнить задание?

Решение. Для выполнения квеста нужно 5 предметов. Корзину всегда находят первой, поэтому её позиция зафиксирована. Порядок сбора 4 оставшихся предметов равен числу перестановок 4 элементов. Всего есть 4! = 24 способа выполнить задание.

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

Порядок выбора элементов важен, когда:

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

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

Решение. Порядок выбора важен, поэтому выбрать четыре ресторана поможет правило произведения: существует 9 ∙ 8 ∙ 7 ∙ 6 = 3024 способа. Это как раз и есть количество размещений из 9 по 4.

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

Решение. Выбрать упорядоченную тройку можно 10 ∙ 9 ∙ 8 = 720 способами. По формуле для количества размещений это считается так:

Несколько частных значений для количества сочетаний:

Порядок выбора или расстановки не важен, когда:

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

Пример. Из 9 актёров выбирают четырёх для массовки. Порядок выбранных людей не важен. Сколько есть способов выбрать актёров?

Решение. Чтобы получить количество вариантов выбора 4 из 9 без учёта порядка, нужно

Это количество сочетаний из 9 по 4: сначала нашли количество способов выбрать 4 из 9, потом «склеили» все варианты с одним набором актёров, но разным порядком.

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

Решение. Общее количество перестановок для 6 элементов нужно разделить на (6 – 4)! и ещё на 4!, так как не нужно учитывать ни перестановки «невыбираемых» кружек, ни порядок среди выбираемых.

Поэтому для выбора 4 кружек из 6 есть

А если надо выбрать только 2 разные кружки?

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

У этого есть и логическое обоснование: например, выбрать 4 кружки из 6 (и купить их) — это то же самое, что выбрать 2 кружки из 6 (и не купить их).

Аналогично получится, что

В общем виде это свойство выглядит так:

Его называют свойством симметрии для количества сочетаний.

Совет эксперта

Диана Миронидис
Выбирать приходится каждый день: сколько блюд получится сделать из продуктов в холодильнике, сколькими способами можно добраться до работы — ответы на все эти вопросы даёт комбинаторика. Это отличный фундамент для изучения анализа данных и тех областей математики, которые связаны с теорией вероятностей и статистикой. Например, чтобы работать с биномиальным распределением, нужно знать, что такое биномиальные коэффициенты и как их находить. А это как раз комбинаторные задачи.

Автор и методист курсов по математике

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

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

Основные теоремы комбинаторики

Подмножества и выборки: Пусть задано произвольное множество из -объектов, которое мы обозначим за А, с элементами Последовательность произвольных элементов

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

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

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

Неупорядоченное m-подмножество n-множества называется m-сочетанием из m-элементов (или сочетанием из n-элементов по m). Число упорядоченных m-подмножеств n-множества равно

Если то число таких подмножеств есть

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

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

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

Пример:

Сколько вариантов расположения слов допускает предложение: «Редактор вчера внимательно прочитал рукопись»? Так как в данном предложении нет никаких грамматических ограничений на порядок слов, то на первое место можно поставить любое слово (5 вариантов), на второе -любое другое, кроме выбранного (4 варианта) и т. д.; всего

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

Число упорядоченных m-выборок из n-множеств равно

Пример:

Сколько всего телефонных номеров можно иметь в городе, если номер имеет шесть цифр? Решение. Каждый телефонный номер может содержать любые шесть цифр из десяти (0, 1, 2, …, 9). При этом одинаковые цифры могут повторяться до шести раз, и, кроме того, телефонные номера различны, даже если они отличаются лишь порядком цифр. На основании этого задача сводится к подсчету количества 6-выборок 10-множества, т. е.

Число неупорядоченных m-подмножеств n-множества (число сочетаний) равно

Сочетания — это соединения из n-элементов по m-элементов, которые отличаются друг от друга только самими элементами. Числа обычно называют биномиальными коэффициентами. Если в этой формуле заменить m на разность n — m, то получим »отношение

Рекуррентная формула для сочетаний

Принято считать, что при или при

Числа часто условно записывают в следующем виде:

Хотя величина не имеет комбинаторного смысла, понятие чисел можно распространить на отрицательные значения n, а именно:

Пример:

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

Пример:

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

Пример:

Читатель отобрал по каталогу 8 книг. Однако в библиотеке выдают одному читателю не более 5 книг. Сколько альтернатив взять книги есть у этого читателя? Решение. Поскольку читатель отобрал книг больше разрешенного числа, то он должен выбрать из них 5 книг. Естественно, что все книги, разные и все равно, в каком порядке их взять. Следовательно, каждая альтернатива есть неупорядоченное 5 — подмножество из 8 и число вариантов в выборе книг (число альтернатив) равно

Число неупорядоченных m-выборок из n-множества равно

Пример:

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

Набор целых чисел называется разбиением числа n, если например 6=1+2+3.

Число разбиений. Число R упорядоченных — разбиений n-множества равно.

Замечание:

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

В частном случае, когда имеем соотношение

Число (m, n — m) — разбиений n-множества равно числу его упорядоченных m-подмножеств.

Пример:

Число различных слов, которое получим, переставляя буквы слова «математика», равно

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

Число неупорядоченных подмножеств. Число всех неупорядоченных подмножеств n-множества равно

Пример:

В комнате 4 различных светильника. Сколько вариантов включения светильников может быть реализовано?

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

Основные правила комбинаторики

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

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

Пусть существует разбиение множества изучаемых комбинаций на классы, т. е. каждая комбинация входит в один и только в один класс. Тогда полное число комбинаций равно сумме количества комбинаций, входящих в каждый из классов. Иными словами, если некоторый объект типа а можно выбрать m-способами, а объект типа b можно выбрать n-способами, то выбор одного из этих объектов можно осуществить — способами:

Это правило сумм справедливо лишь в том случае, если классы разбиения не пересекаются. Если же классы разбиения пересекаются, т. е. способы выбора объекта типа а совпадают со способами выбора объекта типа b, то из формулы (1.4) следует вычесть число k таких совпадений:

Пример:

Пусть а — число, делящееся на два; b — число, делящееся на три. Сколькими способами можно выбрать или а, или b, если задано множество Решение. Согласно формуле (1.4), имеем: (числа 2 и 4) и (число 3), т. е.

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

Обобщая формулы на случай i классов, получим формулу сумм

где — число способов выбора объектов i-го типа; — число совпадений способов выбора объектов i-го и j-го типа.

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

Если объект типа а можно выбрать m способами и если после каждого такого выбора объект типа b можно выбрать n способами, то выбор в указанном порядке пары можно осуществить -способами:

Если же при i-м способе выбора объекта типа а объект b может быть выбран -способами, то число способов такого выбора пары равно

Пример:

Сколько существует целых четырехзначных чисел, не делящихся на 5? Целое число не делится на 5, если оно не заканчивается на 5 или на 0. Поэтому первую значащую цифру можно выбирать девятью способами (все цифры, кроме нуля), вторую и третью — десятью способами, а четвертую лишь восемью (все цифры, кроме 0 и 5). Следовательно, искомое число есть

Комбинации объектов

Размещения с повторениями — это упорядоченные m-выборки из n-множества. Таких выборок будет штук.

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

где — число повторений в перестановке элементов i-го типа.

Очевидно, что

Пример:

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

Решение:

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

Поэтому искомое число есть

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

Имеет место также следующее рекуррентное соотношение:

Пример:

Число целых неотрицательных решений уравнениях, равно числу сочетаний из m-элементов по n-элементов с повторениями. Это, в частности, означает, что уравнение имеет решений.

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

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

Пример:

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

Решение:

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

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

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

Пример:

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

Решение:

Представим себе, что гости входят в комнату по одному. Первому из входящих гостей предоставляется выбор из 12 различных стульев, т. е. 12 возможностей, как и в предыдущем примере. Однако уже для следующего гостя остаются не те же две­ надцать возможностей, что и для первого, а всего лишь одиннадцать, поскольку один из стульев оказывается уже занятым. По-прежнему каждое место, занятое первым гостем, может комбини­роваться с любым другим местом, занятым вторым; поэтому общее число различных способов, с помощью которых можно рассадить двух гостей, равно 12 • 11 = 132.

Дальнейший ход решения теперь уже ясен. Для гостя, входя­щего третьим, останется только 10 различных возможностей, так как из 12 мест два места окажутся уже занятыми. Поэтому для трех гостей число различных способов рассадить их составляет 12 • 11 • 10 = 1320. Продолжая аналогичные рассуждения, найдем, что общее число различных способов рассадить 12 гостей на 12 стульях составляет 12 • 11 • … • 2 • 1 = 12!= 479001600.

Пример:

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

Решение этой задачи очень похоже на решение предыду­щей. Действительно, если назначить сначала старшего по наряду, то для его выбора у нас имеется 12 различных возможностей: каж­дый солдат отделения может быть назначен старшим наряда. Пос­ле того как старший наряда назначен, вторым в наряд может быть назначен любой из оставшихся одиннадцати. Как и во всех предыдущих случаях, общее число различных нарядов составляет 12- И = 132.

Пример:

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

Решение:

Легко понять, что число таких нарядов должно быть меньше, чем в предыдущем примере. Действительно, наряды —Иванов (старший) и Петров или Петров (старший) и Иванов — различны, тогда как, если не требуется назначать старшего, эти два солдата в обоих случаях составляют один и тот же наряд. Каждый парный наряд без старшего можно превратить в два различных на­ряда со старшим. Поэтому число различных парных нарядов со старшим в два раза больше, чем нарядов без старших. Отсюда сле­дует, что интересующее нас в данном примере число различных пар­ных нарядов из 12 солдат отделения в два раза меньше, чем получено в предыдущем примере, т. е. равно

Пример:

Клавиатура пианино состоит из 88 клавиш. Сколько различных музыкальных фраз можно составить из 6 нот, допуская повторения одних и тех же нот в одной фразе?

Решение:

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

Пример:

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

Решение этой задачи так же отличается от решения предыдущей, как решение задачи примера 2 от примера 1. Действи­тельно, при составлении произвольной музыкальной фразы для первой ноты мы имеем по-прежнему 88 возможностей. Для второй ноты число возможностей уменьшится уже до 87, так как нота, использованная первой, не должна больше употребляться. После того как выбрана вторая нота, для третьей остается уже только 86 возможностей. Теперь ясно, что общее число различных музыкальных фраз из 6 нот без повторений равно произведению 88 • 87 • 86 • 85 • 84 • 83 = 390 190489920.

Пример:

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

Решение:

Аккорд отличается от музыкальной фразы тем, что все ноты, в него входящие, звучат одновременно. Отсюда сле­дует, что все ноты аккорда должны быть различными. Кроме то­го, различные музыкальные фразы могут приводить к одному и тому же аккорду, если они состоят из одних и тех же нот, но рас­положенных в фразе в различном порядке. Поэтому, подобно при­меру 4, так как число различных музыкальных фраз уже известно, нам остается определить, сколько различных музыкальных фраз могут «склеиваться» в один и тот же аккорд, или, наоборот, сколь­ко различных фраз получается из одного и того же аккорда.

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

Теперь уже ясно, что число различных музыкальных фраз, которые можно получить из одного аккорда из шести нот, равно 6 • 5 • 4 • 3 • 2 • 1 =6!= 720. Это означает, что 6! различных музыкальных фраз склеиваются в один и тот же аккорд, так что число возможных аккордов будет в 61 раз меньше, чем число раз­личных музыкальных фраз. Итак, мы получаем, что число различ­ных возможных аккордов из 6 нот равно:

Пример:

Из города А в город В ведет k дорог, а в город С — l дорог. В город D из города В ведет m дорог, а из города С — n дорог. Города В и С дорогами не соединяются. Сколько различных автобусных маршрутов можно провести между городами А и D?

Решение:

Число автобусных маршрутов определяется чис­лом различных дорог между городами. Всего из города А выхо­дит k + l дорог, а в город D входит m + n дорог. Мы не можем, однако, сказать, что общее число дорог равно произведению этих чисел, так как здесь невозможно комбинировать любую дорогу, выходящую из A, с любой дорогой, входящей в D . Если же рассматривать отдельно дороги, проходящие через В или через С, то такая комбинация возможна.

Рассмотрим всевозможные маршруты, идущие из A в D через В. Из A в В ведет k дорог, а из В в D —m дорог. Каждую из таких дорог, выходящих из A, можно комбинировать с любой дорогой,, входящей в D поэтому общее число различных маршрутов, как и во всех предыдущих задачах, получается перемножением числа возможностей и равно km, Следовательно, число различных маршрутов, идущих из A в D через В, равно km.

Аналогично подсчитывается число различных маршрутов, иду­щих из A в D через С; оно равно ln. Далее, мы замечаем, что всякий автобусный маршрут, соединяющий города A и D, должен проходить или через В, или через С, и, значит, он должен входить либо в число km маршрутов, идущих через В, либо в число ln мар­шрутов, идущих через С. Общее число различных маршрутов равнo тогда сумме km + ln.

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

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

Другое общее правило имеет следующий вид: если некоторый выбор может быть сделан т различными способами, а другой выбор—n различными способами {отличными от предыдущих), то общее число способов, которыми можно осущест­вить какой-нибудь один из этих выборов, равен сумме m +n.

Это правило также применялось нами в предыдущем параграфе (см. пример 8).

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

Пример:

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

Решение:

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

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

Представим себе сначала, что назначаемых в наряд солдат мы вызываем по одному и строим в шеренгу. Тогда легко подсчитать, что при вызове первого солдата у нас есть 50 различных возможностей; после того как один солдат уже вызван, для выбора второго остается 49 возможностей, а для выбора третьего — лишь 48. Таким образом, применяя правило умножения, находим, что все­го для выбора трех солдат в определенном порядке число возможностей равно произведению 50 • 49 • 48. На этом и заканчивается первая часть решения, но отнюдь не все решение.

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

Остается, следовательно, определить, в каком числе случаев будет получаться один и тот же наряд. Это можно подсчитать, решая в каком-то смысле обратную задачу: каким числом способов можно расставить в шеренгу трех солдат уже выбранного наряда. Очевидно, что это число равно требуемому. Но это число легко под считать, пользуясь обычным приемом: чтобы поставить какого-либо солдата на первое место, есть три различные возможности, на второе место остается два солдата и на третье — только один Поэтому общее число возможных перестановок трех солдат в ше­ренге равно 3 • 2 • 1 = 3! = 6.

Итак, каждый наряд из трех солдат можно расставить в шерен­гу 3! различными способами, а, значит, в произведении 50 • 49 • 48, показывающем число возможностей при выборе трех человек в определенном порядке, каждый наряд считается ровно 3! раз. Поэтому общее число различных способов, которыми можно назначить в наряд трех солдат из пятидесяти, равно

Число различных нарядов из одного сержанта и трех солдат
равно теперь

Пример:

Сколько членов, содержащих две буквы, полу­чится после раскрытия скобок в выражении

Решение:

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

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

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

Пример:

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

Решение этой задачи аналогично решению предыдущей. Тем же методом можно подсчитать, что выбор четырех букв в определенном порядке может быть сделан 6 • 5 • 4 • 3 = 360 различными способами. С другой стороны, каждая четверка счи­тается здесь несколько раз, именно столько, каким числом спосо­бов можно ее упорядочить. Число способов упорядочить четверку букв равно произведению 4 • 3 • 2 • 1 = 24. Поэтому число сла­гаемых, содержащих четыре буквы, равно

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

Пример:

В классе m мест. Каким числом способов можно рассадить в нем n учеников (n < m)?

Решение:

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

Представим себе, что ученики входят в класс по одному. Тогда для первого из них имеется m возможностей выбрать место. После того как первый выбрал какое-то место, для второго остается m — 1 возможностей. Далее, для третьего будет m — 2 различных возможностей и т. д. Искомое число способов рассадить всех учеников выразится произведением

Найдем последний сомножитель этого произведения. Его мож­но определить по-разному, например так: каждый сомножитель на единицу меньше предыдущего и получается вычитанием из m числа, на единицу меньшего, чем номер сомножителя. Поэтому сом­ножитель с номером п получается вычитанием из т числа n — 1, то есть равен m — (n — 1) = m — n + 1.

Можно рассуждать и иначе: после того как все ученики рассядутся, в классе должно остаться m — n свободных мест. Перед входом последнего ученика свободных мест было на 1 больше, то есть m — n + 1. Таково же число возможностей для выбора мест последним учеником, то есть последний сомножитель в про­изведении.

Итак, искомое число различных способов рассадить n учеников на m местах равно произведению п последовательных целых чисел от m до m — n + 1 включительно:

Пример:

В комнате имеется пять лампочек. Сколько су­ществует различных способов освещения?

Решение:

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

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

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

Дальнейшие рассуждения теперь уже совершенно очевидны. Каждая из лампочек может находиться в двух состояниях. Поэтому, присоединяя новую лампочку к уже рассмотренным предыду­щим, мы увеличиваем число возможных способов освещения вдвое. Следовательно, при трех лампочках будет различных способов освещения, при четырех — и, наконец, при пяти лампочках = 32 способа освещения.

Пример:

Чему равен коэффициент при и при в выражении после раскрытия скобок.

Решение:

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

Выражение можно рассматривать как произведение 88 скобок; из каждой нужно выбрать в качестве множителя одно из слагаемых: либо а, либо b. Если мы ищем коэффициент при то нужно определить, каким числом способов можно выбрать из 88 букв а и b ровно шесть букв а. Но именно этот вопрос мы решали в примере 7 предыдущего параграфа, когда нужно было опреде­лить число различных аккордов из 6 нот.

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

Шесть букв а можно разместить на 88 возможных местах числом способов, равным произведению

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

Число возможных способов переставлять между собой шесть букв на шести местах, как мы уже видели, равно 6! Поэтому число различных способов выбрать шесть букв а из 88, а значит, и коэф­фициент при члене в разложении равно

Легко догадаться, что коэффициент при равен тому же числу. Соответствующее рассуждение уже приводилось в примере 4: способов выбрать по 82 буквы а из 88 равно столько же, сколько способов выбрать по 6, так как каждой группе по 6 букв соответствует определенная группа по 82 буквы, состоящая из оставшихся 82 мест. Но мы можем и не обращаться к этому рассуждению, рас­сматривая для члена не выбор 82 букв а, а, наоборот, выбор шести букв b. Отсюда снова вытекает, что коэффициенты при и а одинаковы.

Определения и формулы

Примеров, рассмотренных в двух предыдущих параграфах, вполне достаточно, чтобы заметить некоторые общие закономерности и поставить общие задачи. Заметим прежде всего, что во всех рассмотренных примерах нам приходилось иметь дело с некоторыми конечными множествами и различными их под­ множествами.

Нас интересовало или число всех возможных подмножеств (пример 5 из § 2), или число подмножеств, обладающих определен­ным количеством элементов (примеры 4, 7 из § 1, примеры 1, 2, 3, 6 из § 2). В других случаях нужно было рассматривать упорядо­ченные подмножества, в которых элементы были расположены определенным образом (при­меры 3, 6 из § 1, пример 4 из § 2). Здесь нам нужно было знать чис­ло различных упорядоченных подмножеств, считая различным образом упорядоченные подмножества различными. Наконец, встречалась и задача, в которой нужно было определить количество раз­личных способов упорядочить данное конечное множество, то есть расположить его элементы в определенном порядке (пример 2, § 1). Все эти задачи можно теперь рассмотреть в общем виде.

Рассмотрим прежде всего точное определение упоминавшегося выше термина упорядоченное множество.

Конечное множество, состоящее из n элементов, называется упорядоченным, если его элементы каким-либо образом занумерованы, числами 1, 2, …, n.

«Номера», которые при этом приписываются элементам множества, позволяют мыслить элементы этого множества «расположен­ными» в каком-то «порядке»: первый элемент «предшествует» вто­рому (а второй «следует» за первым), второй предшествует третьему и т. д.

Одно и то же конечное множество можно, разумеется, упорядочить раз­ными способами. Например, множество учеников данного класса можно упо­рядочить по росту (опять-таки двумя противоположными способами), по весу, по возрасту, по алфавиту фамилий и т. д. и т. п.

Не следует, однако, думать, что каждый такой «порядок» связан непре­менно с каким-либо «естественным правилом» упорядочения. Скажем, мно­жество шахматных фигур (каждого цвета по отдельности или все 32) можно, конечно, упорядочить слева направо в порядке их расстановки на доске или по силе (а фигуры одинаковой силы — слева направо или еще как угодно), но можно считать «упорядочением» и «беспорядочную» последовательность, в которой мы случайно поставили их на доску для данной партии. А можно было бы их просто расставить в ряд в произвольном «порядке». Аналогично множество учеников данного класса можно считать упорядоченным в соот­ветствии с тем (в достаточной мере случайным!) порядком, в котором они се­годня пришли в школу.

Короче говоря, «нумерация», о которой говорится в определении упоря­доченного множества, не предполагает, вообще говоря, никакого заранее известного «закона» — упорядочивая конечное множество, мы просто приписываем каким-либо образом номера его элементам. И если в приве­денных примерах легко было все же указать некоторые «естественные» спо­собы упорядочения, то для упорядочения, например, множества муравьев в муравейнике или рыб в озере трудно указать более «естественный» способ, чем переловить их всех по очереди и перенумеровать в порядке попадания их в банку или на удочку…

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

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

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

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

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

1) Для любых двух различных элементов а и b данного множества ли­бо а предшествует b, либо b предшествует а.

2) Для любых элементов а, b и с данного множества из того, что а пред­шествует Ь, а Ь предшествует с, следует, что а предшествует с.

Примером упорядоченного множества может служить множество N натуральных чисел, «естественным» образом упорядоченное по величине: мы считаем, что n предшествует m , если n < m (можно, конечно, было бы выбрать и упорядочение, обратное «естественному», то есть считать, что n предшествует m , когда n > m ). Точно так же упорядочивается множество D всех действительных чисел. Множество K комплексных чисел, не обладаю­щее никаким «естественным» порядком, можно, например, упорядочить, положив, что а+bi предшествует с+di, если а< с, а при а = с, если b < d. Все эти множества можно, разумеется, упорядочить и иными способами.

Введем теперь следующее

Определение:

Пусть дано конечное множество М, состоящее из m элементов. Размещением из m элементов по n эле­ментов называют всякое упорядоченное подмножество множества М, состоящее из n элементов.

Из этого определения следует, что и что различные размещения отличаются друг от друга составом входящих в них эле­ментов или порядком их расположения. Как видно из предыдущих параграфов, в комбинаторных задачах требуется знать число раз­личных размещений из т элементов по n элементов. Это число при­нято обозначать символом (А — первая буква французского слова аrrаngement, что означает размещение, приведение в порядок).

Теорема:

Число различных размещений из т элементов по n элементов равно произведению п последовательных натуральных чи­сел, начиная от m и до m — n + 1 включительно:

Доказательство:

Формула (1) была уже получена нами при разборе примера 4 в § 2. Здесь мы дадим вывод этой формулы, основанный на методе полной математической индукции. Индук­цию будем вести по индексу n.

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

Далее, из каждого размещения по одному элементу можно получить различные размещения по два элемента, присоединяя к выбранному первому элементу второй. Так как для выбора второго элемента мы имеем уже m — 1 возможностей (один из элементов уже использован!), то

Предположим теперь, что для некоторого значения n — k справедлива формула

и докажем, что такая же формула имеет место и для n = k + 1. Пусть образованы все размещения из m элементов по k элементов. Размещения по k + 1 элементу могут быть получены присоедине­нием к каждому из полученных еще одного элемента на (k + 1)-е место.

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

Воспользовавшись предположенной по индукции формулой для , найдем:

что и утверждалось. Справедливость этой формулы для n = 1 и n =2 была уже установлена выше; из принципа математической индукции следует, что формула (1) верна для всех

Определение:

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

Таким образом, различные перестановки отличаются друг от друга лишь порядком элементов. Число возможных различных пе­рестановок из п элементов обозначается символом (от француз­ского слова permutation— перестановка, перемещение).

Теорема:

Число различных перестановок из n элементов равно произведению всех последовательных целых чисел, начиная от n и до 1 включительно:

Доказательство этой теоремы окажется излишним, если мы заметим, что перестановки являются частным случаем размещений, а именно, при m = n. Значит, согласно формуле (1),

Впрочем, нетрудно доказать эту теорему и независимо от понятия раз­мещения. Рассмотрим всевозможные перестановки из n элементов и подсчи­таем, сколько из них начинаются одним и тем же определенным элементом. Если поставить выделенный элемент перед каждой из перестановок из ос­тальных элементов, то мы получим все возможные перестановки, начинаю­щиеся данным элементом. Следовательно, число всех перестановок из n эле­ментов, начинающихся одним определенным элементом, равно . Но тогда для числа всех возможных перестановок из n элементов находим:

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

Формулу (3) можно использовать для доказательства нашей теоремы, пользуясь индукцией по числу элементов множества. Очевидно, что так как один элемент может находиться только на первом месте. Допустим, что формула (2) верна для множества, содержащего n — 1 элемент, то есть что

На основании формулы (3) найдем, что

Таким образом, формула (2) верна для любого n.

Теорема:

Число различных размещений из m элементов по n элементов равно числу перестановок из m элементов, деленному на число перестановок из m — n элементов:

Доказательство:

Формулу (4) легко получить из фор­мул (1) и (2). Действительно,

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

Пусть дано некоторое множество из т элементов и все размещения его элементов по n. Из каждого такого размещения можно получить перестанов­ку элементов множества, присоединив к нему в произвольном порядке ос­тальные m — n элементов. В результате мы получим в с е перестановки из m элементов множества.

Следовательно, каждое размещение из m элементов по n элементов по­рождает столько перестановок по m элементов, сколькими различными спо­собами к нему можно присоединить m — n оставшихся элементов. Так как это можно сделать различными способами, то общее число перестановок из m элементов равно

откуда и следует равенство (4).

Определение:

Пусть дано конечное множество M, состоящее из m элементов. Сочетанием из m элементов по n элемен­тов называется любое подмножество УИ, содержащее п элемен­тов.

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

Теорема:

Число всех возможных сочетаний из m элементов по n элементов равно произведению n последовательных натуральных чисел от m до m — n + 1, деленному на произведе­ние n последовательных натуральных чисел от n до 1:

Доказательство этой теоремы сводится к доказатель­ству следующего утверждения: число сочетаний из m элементов по n элементов равно числу размещений из m элементов по n элементов, деленному на число перестановок из n элементов. В самом деле, из этого утверждения, пользуясь формулами (1) и (2), легко получаем формулу (5).

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

что и требовалось доказать.

Формулу (5) обычно приводят к более удобному для записи симметричному виду, умножая числитель и знаменатель на произве­дение всех натуральных чисел от m — n до 1 включительно. Тогда мы приходим к формуле:

Формула (7) означает, что

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

Как было указано в формулировке теоремы 4, символ име­ет смысл при и означает количество подмножеств множества М , содержащих ровно по n элементов. Ясно, что это следует и из формулы (5), но формулу (7) в этом случае приме­ нить нельзя, так как она будет содержать бессмысленный символ О!. Для общности принято полагать 0! = 1. В этом случае формула (7) дает для то же значение 1.

Удобно также ввести в рассмотрение символ , что означает число пустых подмножеств множества М, то есть = 1. То же самое получится и из формулы (7), если воспользоваться принятым условием 0! = 1.

Принимаемое условие 0! = 1 имеет на самом деле более глубокий смысл, чем просто возможность вычислять или по формуле (7).

Более существенное основание для того, чтобы считать выражение 0! равным единице, состоит в следующем. Выражение n! можно рассматривать как функцию, определенную лишь для натурального аргумента В своей области определения она удовлетворяет функцио­нальному уравнению справедливость которого легко проверяется для всех натуральных Действительно, Если же в этом равенстве положить n = 1, то мы получим

Однако все эти соображения являются не слишком убедительными, так как нельзя быть уверенным в том, что нам не встретится другая формула, в которой будет удобно полагать 0! равным какому-нибудь другому числу. Окончательное решение можно получить, идя вот каким путем. Естественно поставить вопрос: можно ли построить непрерывную функцию, определенную для всех значений х, и такую, которая для целых значений аргумента совпадает с то есть доопределить функцию расширив ее область определения? Напомним, что в математическом анализе такое расширение производится, например, для показательной функции которая вначале бы­ла определена лишь для натурального показателя степени.

Поставленный вопрос был решен Эйлером и Гауссом. С помощью различ­ных формул (Эйлер — через интеграл, а Гаусс — через бесконечное произве­дение) они определили функцию, обладающую нужным свойством, и доказали единственность такой функции при некоторых естественных предположениях. Эта функция называется гамма-функцией и обозначается Г(х). Она опреде­лена для всех х > 0 и удовлетворяет функциональному уравнению Г(х)= хГ(х — 1), а для натуральных n принимает значения Г(n) = (n — 1)!.

Обе формулы, определяющие функцию Г(х), имеют смысл при х=1 и определяют значение Г(1) = 1. Но в силу равенства Г(n) = (n — 1)! под выражением 0! следует понимать именно значение Г(1).

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

Теорема:

Число сочетаний из т элементов по п элементов рав­но числу сочетаний из m элементов по m — n элементов:

Доказательство:

Формально равенство (9) легко по­лучить из формулы для числа сочетаний, записанной в виде (7). Действительно,

Комбинаторный смысл этого равенства также достаточно ясен. Каждо­му подмножеству из n элементов соответствует единственное определенное подмножество из m — n элементов—именно, тех, которые не вошли в перво­начальное. Поэтому количество тех и других возможных подмножеств оди­наково. При рассмотрении примеров (см. примеры 3 и 6 из § 2) мы фактически уже пользовались этим соображением.

Равенство (9) позволяет сокращать вычисления в тех случаях, когда n > m — n.

Теорема:

Число сочетаний из т элементов по п элементов рав­но сумме числа сочетаний из (m — 1) элементов по n элементов и по (n — 1) элементов:

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

Второе доказательство состоит в следующем. Выделим некоторый фик­сированный элемент а множества М и рассмотрим сочетания из m элементов по n элементов, содержащие или не содержащие этот элемент. Число сочетаний по n элементов, не содержащих элемента а, равно, очевидно, так как здесь рассматриваются подмножества по n элементов, образованные из элементов множества, содержащего m — 1 элемент (множество М без элемента а). Сочетания, содержащие а, можно получить так: образовать всевоз­можные сочетания по n — 1 элементу из того же множества М без элемента а и к каждому из них присоединить а. Отсюда ясно, что число таких сочетаний равно Так как каждое сочетание по n элементов либо содержит данный элемент а, либо не содержит его, то оно принадлежит либо одной, либо дру­гой группе. Поэтому

что и утверждалось

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

Соединения с повторениями

Если рассмотреть теперь снова задачи, разобранные в §§ 1 и 2, то мы увидим, что решение почти всех из них не требует уже ни­каких рассуждений, а получается непосредственным применением нужной формулы из выведенных в предыдущем параграфе. Соб­ственно говоря, все рассуждения, которые приводились при реше­нии задач, были не чем иным, как именно выводом соответствующей формулы, но только для данного конкретного случая. Формулы § 3 потому и являются общими, что они применимы ко всем соедине­ниям одного типа, и рассуждения, проведенные при выводе формул, освобождают нас от необходимости повторять их при решении каждой отдельной задачи.

Однако в числе приведенных там примеров есть и такие, которые не укладываются в уже рассмотренные схемы. К ним отно­сятся, скажем, примеры 1 и 5 из § 1. Дело в том, что при определе­нии различных видов соединений в предыдущем параграфе мы брали некоторое определенное множество, элементы которого существо­ вали «в единственном экземпляре» и в каждое данное соединение могли входить только один раз. Между тем в некоторых случаях элементы в соединении могут повторяться, как например ноты в музыкальной фразе в примере 5 из § 1. Для того чтобы охватить общей теорией и такие задачи, необходимо рассмотреть соедине­ния с повторениями, которым и посвящен настоящий параграф.

Пусть имеется m непересекающихся множеств каждое из которых содержит не менее чем n элементов. Для простоты мы будем называть элементы множества элементами 1-го сорта, элементы множества — элементами 2-го сорта, …, эле­менты множества — элементами m-го сорта. Иначе говоря, мы рассматриваем разбиение (см. п. 7 Введения) некоторого множества на непересекающиеся подмножества состоящие из элементов различных «сортов». Все эле­менты каждого подмножества, то есть элементы одного и того же сорта, будем считать одинаковыми, или совпадающими между собой.

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

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

Из элементов множества A, то есть элементов, входящих в различные его подмножества можно составлять различные упо­рядоченные множества, содержащие по n элементов в каждом. Та­кие упорядоченные множества принято называть размещениями с повторениями из элементов m сортов по n элементов, или, более коротко, просто размещениями с повторениями из m элементов по n.

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

Для наглядности будем представлять себе, что элементами рассматриваемых множеств являются буквы. Если, например, m=3, то это могут быть буквы а, b, с. Тогда возможны следующие размещения с повторениями этих трех элементов по n = 2:

Размещения с повторениями можно рассматривать и в случае n > m, то есть неравенство которое считалось необходимым в предыдущем параграфе, здесь необходимым уже не является. На­ пример, из m = 2 элемента а, b можно образовать размещения по n = 3 элемента. Они будут иметь вид:

Число различных возможных размещений с повторениями из m элементов по n элементов будем обозначать

Теорема:

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

Доказательство:

Прежде всего заметим, что разме­щения с повторениями по n элементов могут быть получены из раз­мещений по (n — 1) элементу присоединением еще одного элемента. Так как к каждому размещению по (n — 1) элементу можно при­соединить любой из имеющихся m элементов, то каждое размещение по (n — 1) элементу порождает т различных размещений по n элементов, то есть

Проведем теперь доказательство формулы (1) по индукции. Ясно, что при n = 1 число размещений равно m:

Допустим, что для некоторого числа n справедливо равенство

и найдем число размещений с повторениями из m элементов по n. Пользуясь формулой (2), получаем:

Таким образом, формула (1) справедлива для n — 1 и из ее справедливости для некоторого п следует и справедливость для n+1. Теорема доказана.

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

Определение:

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

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

Занумеруем сначала все элементы а номерами буквы b — номерами …, и т. д. и будем считать все эти элементы различными. Тогда мы имеем множество, состоящее из

n различных элементов, и число перестановок этого множества, в силу теоремы 2 предыдущего параграфа, равно n!, причем

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

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

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

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

Теорема:

Число различных перестановок из п элементов, в ко­ торых элементы а, b, с, …, l повторяются соответственно раз, выражается формулой

Определение:

Сочетанием с повторениями из m элементов по n элементов называется всякое множество, содержащее n элементов, каждый из которых является элементом одного из данных m сортов.

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

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

Из тех же трех элементов сочетания с повторениями по три эле­ мента будут следующими:

Ясно, что из элементов а, b, с можно составлять сочетания с повторениями и по четыре элемента и вообще по любому чис­лу n элементов, так что для сочетаний с повторениями неравенство не является необходимым, а можно рассматривать и случай m < n.

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

Теорема:

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

Доказательство:

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

Например, если имеются элементы четырех сортов, то сочета­ние вполне определится, если сказать, что оно содержит два эле­ мента первого сорта, четыре элемента второго, ни одного элемента третьего и один элемент четвертого сорта. Это есть одно из возможных сочетаний с повторениями из четырех элементов по семи. Та­кое сочетание можно условно записать комбинацией четырех чисел (2, 4, 0, 1), показывающей, сколько элементов каждого сор­та берется.

Другие сочетания определятся, например, комбинациями (3, 0, 0, 4) или (1, 1,2, 3). Первая из них определяет сочетание, состоящее из трех элементов первого сорта и четырех элементов чет­вертого. Элементы второго и третьего сорта в это сочетание не входят. Вторая комбинация определяет сочетание, содержащее один элемент первого сорта, один — второго, два — третьего и три элемента четвертого сорта. Заметим еще, что, пока мы рассматриваем сочетания из четырех элементов по семи, условная запись пред­ставляет комбинацию всегда четырех чисел — по одному числу на каждый имеющийся сорт элементов, и сумма этих чисел всегда равна семи, то есть общему числу элементов, входящих в сочетание.

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

Такую комбинацию мы будем записывать в виде

Комбинацию , определяющую сочетание, можно записать, пользуясь только цифрами 1 и 0. Сделаем это следующим образом. Вместо числа а 4, означающего количество элементов первого сорта в сочетании, напишем такое же число единиц. За­тем таким же способом запишем число элементов второго сорта, а между этими двумя группами единиц поставим нуль для их разде­ления. Так же будем поступать и дальше. Комбинация (1, 1, 2, 3) изобразится тогда как (1010110111), а комбинация (2, 1, 2, 2) — как (1101011011). Запись (1011011101) соответствует комбинации (1, 2, 3, 1).

Если какое-либо из чисел равно нулю, то есть элементы данного сорта в сочетание не входят, то единиц на этом месте писать не будем, и два или несколько нулей могут тогда оказаться рядом. На­пример, комбинация (2, 4, 0, 1) запишется в виде (1101111001). Запись (1111000111) соответствует комбинации (4, 0, 0, 3).

Запись из нулей и единиц, соответствующая сочетанию из m элементов по n элементов, будет содержать ровно n единиц и m — 1 нулей. Действительно, количество единиц равно числу элементов в сочетании, а количество нулей на единицу меньше числа сортов элементов, поскольку нуль употребляется лишь для их разделения. Поэтому число сочетаний с повторениями из m элементов по n эле­ментов равно числу перестановок из n единиц и m — 1 нулей. Как уже известно из теоремы 2, это число равно

Теорема доказана.

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

Таким образом, число сочетаний с повторениями из m элементов по n элементов равно числу сочетаний без повторений из n + m — 1 элементов по m — 1 элементов.

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

Пример:

В некотором государстве каждые два человека отличаются набором зубов. Каково максимально возможное число жителей этого государства, если наибольшее число зубов у человека равно 32?

Решение:

Эту задачу можно решить двумя способами. Пер­вый способ заключается в том, что мы сначала ищем, сколько людей может иметь k зубов, а потом просуммируем полученные результа­ты от k= 0 до k=32. Ясно, что k мест из 32 можно выбрать способами. Поэтому ровно кkзубов имеют не более чем жителей. А тогда общее число жителей не превосходит

Полученный этим способом ответ оказался очень громоздким. Выгоднее избрать другой путь, которым мы уже пользовались при решении примера 5 в § 2, — применить метод индукции.

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

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

Обозначим число возможных наборов k зубов через Предыдущими рассуждениями мы доказали, что Допустим, что для некоторого k справедливо равенство и докажем, что аналогичное равенство справедливо и для случая k + 1 зубов. Среди всех различных наборов, входящих в имеется ровно наборов, в которых отсутствует (k+1)-й зуб, и столько же наборов, в которых (k+1)-й зуб имеется. Поэтому

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

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

Более того, из приведенного выше доказательства по индукции вытекает, что аналогичное равенство справедливо при любом n, то есть что имеет место формула

Пример:

Дана прямоугольная сетка квадратов размером m х n. Каково число различных дорог на этой сетке, ведущих из левого верхнего угла в правый нижний (рис. 46)? (Все звенья дороги предполагаются идущими или вправо, или вниз — без возвращений; сходная ситуация возникает, скажем, при выборе одного из кратчайших маршрутов между двумя городскими перекрестками.)

Решение:

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

Можно было бы рассматривать число способов выбора не n вертикальных, а m горизонтальных отрезков и тогда мы получили бы ответ Но формула (9) из § 3 показывает, что

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

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

Найдем число возможных дорог, идущих через точку Если нумерация точек произведена снизу вверх, ка это показано на рис. 47, то точка отстоит от нижней горизонта­ли на расстоянии k, считая за единицу измерения длину стороны квадрата сетки. От правой вертикали ее отделяют тогда n— k го­ризонтальных отрезка.

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

Сравнивая полученную сумму с найденным выше выражением для числа дорог, мы придем к формуле:

Пример:

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

Решение:

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

Сначала рассмотрим случай, когда учитывается, кто в каком вагоне находится, то есть когда случаи «пассажир А в первом вагоне, а пассажир В — во втором» и «пассажир В в первом вагоне, а пассажир А — во втором» считаются различными.

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

Иной результат получится в том случае, если нас интересует лишь число пассажиров в каждом вагоне, так что случай «один пас­сажир в первом вагоне и один во втором» является единственным, независимо от того, кто из пассажиров где находится. Здесь нужно подсчитывать уже не размещения, а Сочетания с повто­рениями. По формуле (4) из §4 находим, что число различных способов распределения пассажиров в этом случае равно

Пример:

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

Решение:

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

способов раздела костей.

Эту задачу можно решить иначе. Упорядочим все кости и отдадим первые 7 костей первому игроку, вторые 7 костей — второму игроку и т. д. Так как 28 костей можно упорядочить 28! способа­ми, то получаем 28! способов раздела. Но некоторые из этих спо­собов приводят к одинаковым результатам — игрокам неважно, в каком порядке приходят к ним кости, а важно лишь, какие имен­но кости они получат. Поэтому результат не изменится, если мы как угодно переставим друг с другом первые 7 костей, потом вторые 7 костей и т. д. Первые 7 костей можно переставить 7! способами, вторые 7 костей — тоже 7! способами и т. д. Всего получим перестановок, дающих то же распределение костей, что и данная. Поэтому число способов раздела костей равно

Пример:

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

Решение:

Возьмем три одинаковые перегородки и рассмо­трим всевозможные перестановки 43 предметов: 40 яблок и 3 пере­ городок. Каждой такой перестановке соответствует свой способ раздела: первый мальчик получает все яблоки от начала до первой перегородки, второй — все яблоки между первой и второй перего­родками, третий — все яблоки между второй и третьей пере­городками, а четвертый — все остальные яблоки. (Если, например, первая и вторая перегородки оказались рядом, то второй мальчик ничего не получает.) Значит, число способов раздела равно числу перестановок 40 яблок и 3 перегородок. По формуле числа переста­новок с повторениями получаем, что это число равно

Пример:

Сколькими способами можно разделить 40 яблок между 4 мальчиками так, чтобы каждый получил по крайней мере 3 яблока (все яблоки по-прежнему считаются одинаковыми)?

Решение:

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

способов раздела.

Пример:

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

Решение:

Добавим к m флагам k — 1 перегородку и рас­смотрим всевозможные перестановки из m различных флагов и k одинаковых перегородок. Как ив примере 5, каждой перестановке соответствует свой сигнал (на первую мачту вывешиваются по по­рядку все флаги от начала до первой перегородки и т. д.). Поэтому число сигналов равно числу таких перестановок, то есть равно

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

Бином Ньютона и его обобщения

В главе I (§ 1, п. была выведена формула бинома Ньютона:

Через мы обозначили коэффициент при в разложении Для было получено соотношение которое позволяет вычислять эти коэффициенты один за другим. Сей­час мы получим явную формулу для — для этого мы покажем, что коэффициенты — не что иное, как число сочетаний из n эле­ментов по k (именно поэтому в гл. I и было выбрано обозначение

В самом деле, запишем в виде произведения n сомножителей:

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

или

Видно, что в формулу (3) входят все размещения с повторения­ми из букв х и а, по две буквы в каждом размещении , а в формулу (4) — размещения с повторениями из тех же букв, содержащие по три буквы. То же самое будет в общем случае — после раскрытия скобок в формуле (2) получаются все размещения с повторениями из букв х и а, по n букв в каждом размещении.

Приведем подобные члены. Подобными будут члены, содержа­щие одинаковое количество букв а (тогда и букв х в них будет поровну). Найдем число членов, содержащих k букв а (и, следователь­но, n — k букв х). Эти члены являются всевозможными перестановками с повторениями, составленными из k букв а и n — k букв Их число равно

Отсюда вытекает, что после приведения подобных членов коэффициент при окажется равным , то есть числу сочетаний из n элементов по k. Тем самым доказано, что числа в фор­муле (1) действительно являются числами сочетаний из n элементов по k .

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

Пример:

Определить коэффициент при в разложении

Решение:

Запишем данное нам выражение в виде:

где Отсюда видно, что может получиться только из члена, содержащего . В соответствии с формулой (1) этот член имеет вид:

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

Пример:

С каким коэффициентом входит в разложе­ние

Решение:

Выясним сначала, каким числом способов можно представить в виде произведений для чего надо знать, какими способами можно представить число 30 в виде суммы сла­гаемых 3 и 7. Очевидно, что 30 можно представить в виде суммы де­сяти троек, и без участия слагаемого 7 других представлений нет. С участием 7 возможно только одно представление 30 = 7+7+7+3+3+3, так как число семерок, входящих в сумму, должно быть кратно трем, иначе сумма не будет делиться на 3.

Итак, для нахождения коэффициента при в нам нужно определить коэффициенты при членах

Как и в предыдущем примере, перепишем наше выражение в виде и воспользуемся формулой (1):

Слагаемое есть только в последнем из выписанных нами чле­нов, и коэффициент при нем равен Еще одно слагаемое вида входит в слагаемое

при раскрытии произведения

Так как в этой последней скобке коэффициент при равен то коэффициент при члене равен произведению

Окончательно, искомый коэффициент при есть сумма

Подставляя в (1) х=1, получим другой вывод формулы (1) из § 5. Аналогично, приняв в (1) х = — 1, получим еще одну любопытную формулу:

или, иначе,

то есть для любого n сумма сочетаний из n элементов по четному числу элементов равна сумме сочетаний из п элементов по нечетному числу элементов.

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

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

Пусть, например, n = 2. Тогда получаем:

При n = 3 находим:

Таким образом, мы получили формулы для квадрата и куба суммы трех слагаемых, которые имеют вид:

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

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

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

Показатели степени а удовлетворяют, очевидно, усло­виям и

то есть все они суть целые неотрицательные числа и их сумма равна n.

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

Каждому произведению (до приведения подобных членов) поставим в соответствие перестановку из элементов 1, 2, …, m . При этом если из первой скобки берется, например, множитель из второй — из третьей — и т. д., то перестановка имеет вид 2, 3, 1 … . Иначе говоря, в перестановке на первом месте ставится номер элемента, взятого из первой скобки, на втором — номер эле­мента из второй скобки и т.д. Например, произведению соответствует перестановка 1, 2, 4, 1, 4, 3.

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

Из сказанного вытекает, что произведение встречается среди слагаемых столько раз, сколько существует различ­ных перестановок с повторениями из п элементов, в которых элемент 1 повторяется раз, элемент 2 повторяется раз,…, элемент m повторяется раз, то есть

(см. формулу (3) из § 4). Это же число служит коэффициентом при произведении в разложении n-й степени суммы m слагаемых.

Полученное можно выразить в виде следующей теоремы.

Теорема:

Результат возведения суммы m слагаемых в n-ю сте­пень имеет вид:

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

Эту теорему называют полиномиальной, а коэффициенты (5) — полиномиальными коэффициентами.

Легко убедиться в том, что формула бинома Ньютона является частным случаем полиномиальной формулы (6).

Решение заданий и задач по предметам:

• Математика
• Высшая математика
• Математический анализ
• Линейная алгебра

Дополнительные лекции по высшей математике:

1. Тождественные преобразования алгебраических выражений
2. Функции и графики
3. Преобразования графиков функций
4. Квадратная функция и её графики
5. Алгебраические неравенства
6. Неравенства
7. Неравенства с переменными
8. Прогрессии в математике
9. Арифметическая прогрессия
10. Геометрическая прогрессия
11. Показатели в математике
12. Логарифмы в математике
13. Исследование уравнений
14. Уравнения высших степеней
15. Уравнения высших степеней с одним неизвестным
16. Комплексные числа
17. Непрерывная дробь (цепная дробь)
18. Алгебраические уравнения
19. Неопределенные уравнения
20. Соединения
21. Бином Ньютона
22. Число е
23. Непрерывные дроби
24. Функция
25. Исследование функций
26. Предел
27. Интеграл
28. Двойной интеграл
29. Тройной интеграл
30. Интегрирование
31. Неопределённый интеграл
32. Определенный интеграл
33. Криволинейные интегралы
34. Поверхностные интегралы
35. Несобственные интегралы
36. Кратные интегралы
37. Интегралы, зависящие от параметра
38. Квадратный трехчлен
39. Производная
40. Применение производной к исследованию функций
41. Приложения производной
42. Дифференциал функции
43. Дифференцирование в математике
44. Формулы и правила дифференцирования
45. Дифференциальное исчисление
46. Дифференциальные уравнения
47. Дифференциальные уравнения первого порядка
48. Дифференциальные уравнения высших порядков
49. Дифференциальные уравнения в частных производных
50. Тригонометрические функции
51. Тригонометрические уравнения и неравенства
52. Показательная функция
53. Показательные уравнения
54. Обобщенная степень
55. Взаимно обратные функции
56. Логарифмическая функция
57. Уравнения и неравенства
58. Положительные и отрицательные числа
59. Алгебраические выражения
60. Иррациональные алгебраические выражения
61. Преобразование алгебраических выражений
62. Преобразование дробных алгебраических выражений
63. Разложение многочленов на множители
64. Многочлены от одного переменного
65. Алгебраические дроби
66. Пропорции
67. Уравнения
68. Системы уравнений
69. Системы уравнений высших степеней
70. Системы алгебраических уравнений
71. Системы линейных уравнений
72. Системы дифференциальных уравнений
73. Арифметический квадратный корень
74. Квадратные и кубические корни
75. Извлечение квадратного корня
76. Рациональные числа
77. Иррациональные числа
78. Арифметический корень
79. Квадратные уравнения
80. Иррациональные уравнения
81. Последовательность
82. Ряды сходящиеся и расходящиеся
83. Тригонометрические функции произвольного угла
84. Тригонометрические формулы
85. Обратные тригонометрические функции
86. Теорема Безу
87. Математическая индукция
88. Показатель степени
89. Показательные функции и логарифмы
90. Множество
91. Множество действительных чисел
92. Числовые множества
93. Преобразование рациональных выражений
94. Преобразование иррациональных выражений
95. Геометрия
96. Действительные числа
97. Степени и корни
98. Степень с рациональным показателем
99. Тригонометрические функции угла
100. Тригонометрические функции числового аргумента
101. Тригонометрические выражения и их преобразования
102. Преобразование тригонометрических выражений
103. Вычислительная математика
104. Прямая линия на плоскости и ее уравнения
105. Прямая и плоскость
106. Линии и уравнения
107. Прямая линия
108. Уравнения прямой и плоскости в пространстве
109. Кривые второго порядка
110. Кривые и поверхности второго порядка
111. Числовые ряды
112. Степенные ряды
113. Ряды Фурье
114. Преобразование Фурье
115. Функциональные ряды
116. Функции многих переменных
117. Метод координат
118. Гармонический анализ
119. Вещественные числа
120. Предел последовательности
121. Аналитическая геометрия
122. Аналитическая геометрия на плоскости
123. Аналитическая геометрия в пространстве
124. Функции одной переменной
125. Высшая алгебра
126. Векторная алгебра
127. Векторный анализ
128. Векторы
129. Скалярное произведение векторов
130. Векторное произведение векторов
131. Смешанное произведение векторов
132. Операции над векторами
133. Непрерывность функций
134. Предел и непрерывность функций нескольких переменных
135. Предел и непрерывность функции одной переменной
136. Производные и дифференциалы функции одной переменной
137. Частные производные и дифференцируемость функций нескольких переменных
138. Дифференциальное исчисление функции одной переменной
139. Матрицы
140. Линейные и евклидовы пространства
141. Линейные отображения
142. Дифференциальные теоремы о среднем
143. Теория устойчивости дифференциальных уравнений
144. Функции комплексного переменного
145. Преобразование Лапласа
146. Теории поля
147. Операционное исчисление
148. Системы координат
149. Рациональная функция
150. Интегральное исчисление
151. Интегральное исчисление функций одной переменной
152. Дифференциальное исчисление функций нескольких переменных
153. Отношение в математике
154. Математическая логика
155. Графы в математике
156. Линейные пространства
157. Первообразная и неопределенный интеграл
158. Линейная функция
159. Выпуклые множества точек
160. Система координат