Формулы для подсчета

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

Введем принятые в математике обозначения.

Р" — это число всех перестановок данного //-элементного множества.

Р"(п, и₂, …, th) — число всех перестановок с повторениями указанного состава. Каждая такая перестановка содержит к различных элементов.

А™ — число всех размещений (без повторений) из п по т.

А™ - число всех размещений с повторениями из п по т.

Получим формулу для числа А*. На каждую позицию размещения можно записать один из /? элементов данного множества. Всего имеем т позиций. Значит, записать на /// позиций по одному элементу можно //•//•…-п=п^т числом способов. Имеем формулу.

Пример 10.2.1. Число строк таблицы истинности формулы, содержащей к переменных, равно 2^к, так как каждой строке соответствует ровно одно размещение с повторениями из двух элементов множества {u_yi} по к элементов. •.

Пусть требуется найти число упорядоченных наборов, все элементы которых различны. В этом случае на первую позицию можно поставить один из т элементов, на вторую — один из (/м-1) элементов (элемент, выбранный на первом шаге, использовать нельзя), на третью позицию можно поставить уже один из (м7−2) элементов (два рапсе выбранных элемента нс рассматриваются) и т. д. Таким образом, по принципу умножения получаем произведение т множителей, так как выполняется т действий, при этом первый множитель равен //, а каждый последующий на единицу меньше предыдущего.

Пример 10.2.2. Вычислим А$. Для этого составим произведение из трех множителей по указанному выше правилу: 7−6-5=210. •.

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

Будем последовательно выбирать четырех человек, первый из которых будет президентом, второй — вице-президентом, третий — секретарем, четвертый — казначеем. Имеем размещение из 20 по 4. Число способов сделать указанный выбор равно числу А*₀ = 20−19−18−17 = 116 280.

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

Чтобы вычислить число размещений по сформулированному правилу, можно не задумываться о том, какой вид имеет последний множитель. Однако для того, чтобы записать формулу (2) в более красивом виде, выразим последний множитель через п и т. Он будет равен (п-(т-1)) или (п— т+1). Преобразуем правую часть равенства (2), умножив и разделив ее на выражение (п-т) Напомним, что при любом натуральном значении а выражение а обозначает произведение всех натуральных чисел, не превосходящих а (взятых по одному разу), и называется факториалом числа а. После указанного преобразования правая часть равенства будет иметь точно такое же числовое значение, но представится в виде дроби: в числителе будет стоять произведение всех натуральных чисел от 1 до я, то есть я!, а знаменатель будет равен (п-т). Таким образом, имеем формулу:

Проиллюстрируем формулу на примере:

Найдем число всех перестановок из л элементов. Рассуждения точно такие же, как при подсчете числа размещений без повторений. На последнюю л-ю позицию перестановки остается для выбора одинединственный элемент, поэтому произведение имеет вид л-(и-1)…-2−1. Итак, имеет место формула:

Удобно считать, что 0! равен 1. В этом случае формула (3) является частным случаем формулы (2') при п=т.

Пример 10.2.4. Сколькими способами можно расставить на полке 6 томов сочинений некоторого автора?

Каждая расстановка соответствует перестановке 6-й степени. Всего имеем 61=720 расстановок книг.

Из данной задачи можно получить множество других задач, уточняя, какие способы расстановки считать различными. Иногда симметричные расстановки считаются одинаковыми. Например, одинаковыми можно считать такие перестановки: 123 456 и 654 321, так как они нс нарушают порядок следования томов. В этом случае имеем не взаимно однозначное соответствие между интуитивным понятием расстановки объектов и математическим понятием перестановки. Чтобы решить подобного рода задачи, нужно вначале четко определить, какие расстановки считаются одинаковыми. •.

Перейдем к нахождению числа Р"(п₉ л₂, …, л*). Обозначим это число через х.

Рассмотрим такую произвольную перестановку и предположим, что все ее л элементов различны (например, закрасим элементы в разные цвета). Тогда число «новых» перестановок из л различных элементов равно л! Найдем это число другим способом.

Выполним последовательность действий: возьмем произвольную «старую» перестановку (это можно сделать л; способами), затем расположим элементы первого типа в каком-то порядке (то есть рассмотрим перестановку из п элементов, это можно сделать п способами), потом расположим элементы второго типа в каком-то порядке (то есть рассмотрим перестановку из л₂ элементов, это можно сделать л₂! способами) и т. д. В результате такой последовательности действий будут перебраны все «новые» перестановки. По правилу произведения указанные действия можно осуществить лг-Л1 ?*л₂!*___-л*! числом способов.

Таким образом, п = дг*Я|!*И2!‘…'Л*!. Выражая из этого равенства лг, получаем формулу:

Пример 10.2.5. В примере были получены все перестановки состава (2,3), составленные из элементов а и Ь. Найдем число перестановок по формуле (4):

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

Пример 10.2.6. Найдем число анаграмм слова МАТЕМАТИКА.

Для этого сосчитаем число перестановок букв М, А, Т, Е, И, К состава (2,3,2,1,1,1). Имеем:

Используя комбинаторные рассуждения, получим алгоритм, позволяющий находить коэффициенты многочлена, получаемого после раскрытия скобок и приведения подобных членов выражения (*i+*2+…+?**)", где п — натуральное число.

Для того чтобы представить выражение Cvi+*2⁺-• .+**)" в виде многочлена, нужно перемножить п выражений, равных *i+jc2+…+.Xa. После этого получится сумма одночленов вида х"' ? •…•***, при этом некоторые одночлены будут подобны. С учетом того, что коэффициенты перед одночленами после раскрытия скобок равны 1, подобные одночлены являются равными слагаемыми.

Пример 10.2.7. Рассмотрим выражение (*1+луК*з)³— Имеем:

После перемножения скобок в силу правила произведения получится 3−3-3=27 слагаемых. Каждое слагаемое можно отождествить с упорядоченной тройкой, первая координата которой выбирается из первой скобки, вторая — из второй скобки, третья — из третьей скобки. Некоторые из троек определяют равные слагаемые, так как порядок множителей в произведении не изменяет выражение.

Например, слагаемых, равных хухуху будет 6: х-х₂-х$, xyxyx_2f х₂хуху хуХуХи хуХ]-х₂, хуХуХ. Слагаемых, равных, х,²х₂, будет 3: ХуХуХ₂, хуХуХу ХуХуХ. •.

Из рассмотренного примера видно, что число слагаемых, равных произведению х" '? х%^! при фиксированных значениях щ, п₂, …" л*,.

равно числу перестановок состава (я|, я₂,п_к), составленных из переменных х₉ х₂, …, х*. Сумма чисел /ij, п₂, …, «а равна л. Если какое-то из чисел п, равно 0, то соответствующая переменная х, не входит в перестановку. При этом количество нс подобных слагаемых будет столько, сколькими способами число п можно представить в виде суммы к целых неотрицательных слагаемых с учетом порядка следования слагаемых.

Возвращаясь к примеру 10.2.7, видим, что 3 = 3+0+0 = 2+1+0 = 2+0+1 = = 1+2+0 =1+1+1 = 1+0+2 = 0+3+0 = 0+2+1= 0+1+2 = 0+0+3.

Подсчитав соответствующее число перестановок, имеем следующее разложение выражения (х+х₂+х^)^у:

Пример 10.2.8. Найдем коэффициент при многочлене x²_y³z⁵ после возведения в степень и приведения подобных членов выражения (x+y+z)¹⁰. Коэффициент равен числу перестановок.