Вход или регистрация

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

Если задано множество Х, то из его элементов можно составлять не только упорядоченные пары, но и упорядоченные тройки, четверки … элементов. Например, буквы слова «телефон» образуют упорядоченную семерку.

Пусть даны множества Х, Х, Х…Х. Возьмем какой-нибудь элемент a из множества Х, потом a из множества Х,… aиз множества Х. Выбранные элементы расположим по порядку: (a; a;…; a). Мы получим упорядоченную n–ку (энку) элементов, выбранных из множеств Х,Х, …, Х. Вместо слова «упорядоченная энка» говорят короче – «кортеж». Число n называют длиной кортежа, а элементы a; a;…; a – его компонентами.

В математике примером кортежа может служить набор цифр, входящих в десятичную запись какого-нибудь числа. Этот кортеж составлен из цифр 0,1,2,3,4,5,6,7,8,9, причем цифры могут повторяться, а при перестановке цифр может получиться иное число. Так, кортеж числа 112231 имеет вид (1; 1; 2; 2; 3; 1).

Два кортежа (a; a;…; a) и (b; b;…; b) называют равными, если они имеют одинаковую длину, т.е. m = n, и каждая компонента первого кортежа равна компоненте второго кортежа с тем же номером, т.е. a= b, a= b, … a= b.

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

Пусть даны множества Х,Х, …, Х из элементов которых составляются кортежи, которые могут иметь общие элементы. В частности, все они могут совпадать с одним и тем же множеством Х, содержащим m элементов. Найдем количество кортежей длины n, которые можно составить из m-элементов множества Х. Чтобы решить эту задачу, надо найти число кортежей в декартовом произведении Х Х … Х, содержащем n множителей. По правилу произведения это число элементов равно n(X) n(X) n(X)… n(X). Так как по условию n(X) = m (множество состоит из m элементов), то n(Х Х … Х) = mmm…m = m.

Например, из 33 букв русского алфавита можно составить 33 слов длины 2 (аа, аб, ав,…, ая, ба, бб,…, яя), 33слов длины 3 и т.д. Точно так же из 10 цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 можно составить 10двузначных номеров (00,01,02,…,99), 10 трехзначных и т.д.

Количество кортежей длины n, составленных из элементов m множества Х, называют размещениями с повторениями из m элементов по n, а их число обозначают А и вычисляют по формуле:

Данная формула позволяет решать различные задачи. Например, имеется 4 различных кресла и 5 рулонов декоративной ткани разных цветов. Сколькими способами можно осуществить обивку кресел?

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

А=5=5555=625 – способов обивки кресел.

Конечное множество Х называется упорядоченным, если его элементы перенумерованы некоторым образом: Х = (х; х;…; х). Понятие упорядоченного множества – частный случай понятия кортежа. Оно выделяется из общего понятия кортежа условием, что в упорядоченном множестве все элементы различны. Например, кортеж (1, 5, 2, 4, 3) не является упорядоченным множеством, а (1, 2, 3, 4, 5) – упорядоченное множество.

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

Сколькими способами можно упорядочить множество Х? Каждое упорядочивание заключается в том, что какой-то элемент получает номер 1, какой-то – номер 2, …, какой-то – номер m. Номер 1 может получить любой из элементов множества Х. Значит, выбор первого элемента можно сделать m способами. Тогда второй можно выбрать (m – 1) способами, третий – (m – 2) способами и т.д. Последний элемент, который занимает m место, можно выбрать лишь одним способом.

По правилу произведения получаем, что общее число способов упорядочивания равно m(m–1)(m–2) … 1. Произведение первых m натуральных чисел в математике называют «m-факториал» и обозначают m! Например, 4! = 4321 = 24. Таким образом, число упорядочиваний множества Х равно m! Они состоят из одних и тех же элементов, а отличаются друг от друга лишь порядком следования. При этом элементы в них не повторяются. Поэтому их число называют перестановками без повторений.

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

Их количество подсчитывается по формуле:

Р=А=m(m–1)(m–2) … 1=m!

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

Каждый способ задается перестановками 8 чисел – указываются номера горизонталей занятых полей на первой, второй, … , восьмой вертикалях. Число таких перестановок Р=8!= 87654321=40320.

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

У первого человека есть право выбора из 12 мест, у второго – из 11, третьего – из 10, … Последний занимает оставшееся одно место. Значит, в задаче речь идет о перестановках без повторений из 12 элементов: Р=12!=1211109…1=479001600 способами можно рассадить 12 человек за круглым столом.

Решим следующую задачу. Сколько шестизначных чисел, не кратных 5, можно образовать из цифр 1, 2, 3, 4, 5, 6 при условии, что каждая цифра входит в шестизначное число только один раз?

Решение: Так как количество всех чисел из данного набора 6 цифр задается перестановками без повторений, то их будет равно Р=6!=720.

Но среди этих чисел, есть числа, кратные 5, т.е. которые оканчиваются на цифру 5. Их количество выберется из цифр 1, 2, 3, 4, 6 и будет равно Р=5!=120.

Значит чисел, не кратных 5, можно найти как Р – Р=720–120=600.

Рассмотрим более сложную задачу: сколько упорядоченных
n-множеств можно составить из элементов m-множества Х?

Отличие этой задачи от предыдущей заключается в том, что составление упорядоченного n-множества заканчивается, когда мы выберем n элементов. Поэтому, чтобы найти число таких упорядоченных подмножеств, надо перемножить n чисел: m, m – 1, m – 2 и т.д. Последнее из них равно m – n + 1. Эти упорядоченные n-множества называют размещения без повторений.

Кортежи длины n, составленные из неповторяющихся элементов множества Х, содержащего m элементов, называют размещениями без повторений из m элементов по n. Число таких размещений обозначают А и подсчитывают по формуле:

=m (m–1) (m–2) … (m–n+1)

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

А=, где m!=m (m–1) (m–2) …1.

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

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

А=40 39 38=59280 – столько способов выделить актив класса.

Среди задач, связанных с применением формул по перестановкам или размещениям, рассматриваются задачи и вычислительные. Причем считают, что 1!=1 и 0!=1.

Рассмотрим задачу: четыре цифры 1,2,3,4 можно переставлять друг с другом Р=4!=24 способами.

В слове «мама» четыре буквы. Но перестановок из этих букв можно составить не 24, а только 6: «м а м а», «м а а м», «м м а а», «а а м м», «а м м а», «а м а м». В этом легко убедиться, если в соответствие цифрам 1 и 2 поставить букву «м», а цифрам 3 и 4 – букву «а».

Рассмотрим теперь задачу в общем виде. Пусть дан кортеж длины n, составленный из элементов множества Х = {х; х;…; х}, причем буква х входит в этот кортеж nраз, …буква х – nраз. Тогда n = n + … + n. Если переставлять в этом кортеже буквы, будут получаться новые кортежи, имеющие тот же состав, т.е. такие, что буква хвходит n раз, …, буква хвходит nраз. Мы будем называть эти кортежи перестановками с повторениями из букв х; х;…; х, имеющими состав (n, …, n). Число таких перестановок обозначается Р(n,n,…n). С помощью правила произведения находим, что число перемещений букв, не меняющих данную перестановку, равно n!... n! Но n чисел можно переставлять друг с другом n! способами. Поэтому число различных перестановок букв, имеющих состав (n,n,…n), т.е. Р(n,n,…n), в n!.... n! раз меньше, чем n!: