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


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


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


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


Два кортежа (aОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage453.gif; aОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage454.gif;…; aОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage091.gif) и (bОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage453.gif; bОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage454.gif;…; bОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage091.gif) называют равными, если они имеют одинаковую длину, т.е. m = n, и каждая компонента первого кортежа равна компоненте второго кортежа с тем же номером, т.е. aОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage453.gif= bОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage453.gif, aОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage454.gif=  bОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage454.gif, … aОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage091.gif= bОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage091.gif.


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


Пусть даны множества ХОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage453.gifОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage454.gif, …, ХОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage091.gif из элементов которых составляются кортежи, которые могут иметь общие элементы. В частности, все они могут совпадать с одним и тем же множеством Х, содержащим m элементов. Найдем количество кортежей длины n, которые можно составить из m-элементов множества Х. Чтобы решить эту задачу, надо найти число  кортежей в декартовом произведении ХОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif ХОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif …Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif  Х, содержащем n множителей. По правилу произведения это число элементов равно n(X)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage441.gif n(X)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage441.gif n(X)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage441.gif… n(X). Так как по условию n(X) = m (множество состоит из m элементов), то n(ХОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif ХОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif …Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif  Х) = mОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage441.gifmОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage441.gifmОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage441.gifОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage441.gifm = mОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage456.gif.


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


Количество кортежей длины n, составленных из элементов m множества Х, называют размещениями с повторениями из m элементов по n, а их число обозначают  АОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage459.gif и вычисляют по формуле:


Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage460.gif








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


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


АОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage461.gif=5Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage462.gif=5Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif5Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif5Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif5=625 – способов обивки кресел.


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


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


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


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


Два размещения без повторений из m элементов по m состоят из одних и тех же элементов, расположенных в различном порядке. Поэтому такие размещения называют перестановками без повторений из m элементов и обозначают РОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage463.gif.


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


 РОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage463.gifОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage465.gif=mОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif(m–1)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif(m–2)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif … Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif1=m!

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

Каждый способ задается перестановками 8 чисел – указываются номера горизонталей занятых полей на первой, второй, … , восьмой вертикалях. Число таких перестановок РОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage466.gif=8!= 8Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif7Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif6Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif5Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif4Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif3Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif2Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif1=40320.

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

У первого человека есть право выбора из 12 мест, у второго – из 11, третьего – из 10, … Последний занимает оставшееся одно место. Значит, в задаче речь идет о перестановках без повторений из 12 элементов: РОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage467.gif=12!=12Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif11Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif10Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif9Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gifОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif1=479001600 способами можно рассадить 12 человек за круглым столом.

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

Решение: Так как количество всех чисел из данного набора 6 цифр задается перестановками без повторений, то их будет равно  РОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage468.gif=6!=720.

Но среди этих чисел, есть числа, кратные 5, т.е. которые оканчиваются на цифру 5. Их количество выберется из цифр 1, 2, 3, 4, 6 и будет равно РОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage469.gif=5!=120.

Значит чисел, не кратных 5, можно найти как РОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage468.gif – РОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage469.gif=720–120=600.

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

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

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

Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage459.gif=mОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif (m–1)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif (m–2)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif … Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif(m–n+1)

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

     АОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage459.gif=Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage473.gif, где m!=mОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif (m–1)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif (m–2)Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif …Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif1.

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

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

АОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage474.gif=40 Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif39 Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage094.gif38=59280 – столько способов выделить актив класса.

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

Рассмотрим задачу: четыре цифры 1,2,3,4 можно переставлять друг с другом РОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage475.gif=4!=24 способами.

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

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

                              Р(nОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage453.gif,nОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage454.gif,…nОписание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage463.gif)= Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage477.gif.

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

Это слово состоит из 10 букв две буквы «м», три – «а», две – «т», и по одной – «е», «и», «к».

Значит состав слова «математика» – (2, 3, 2, 1, 1, 1). Тогда количество перестановок можно найти следующим образом:

Р (2, 3, 2, 1, 1, 1)= Описание: E:Для сайтаПрограммыЗеброид 4tempword_1.filesimage478.gif=151200.

Итак, количество кортежей при перестановке букв в слове «математика» равно 151200.





Просмотров 9242 Комментариев 0
Познавательно:
Скажи свое мнение:
Добавить комментарий
Имя:* E-Mail:*

Вопрос:
1+1=
Ответ:*
Введите два слова, показанных на изображении: *