Вопрос 18.

Перестановки без повторений.

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

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

Задача о шляпах: перечислить все способы, которыми три человека могут надеть три шляпы. Каждый такой способ можно считать перестановкой из трех шляп или трех чисел 1, 2, 3 (если закодировать шляпы числами): 123, 132, 213, 231, 312, 321.

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

Полученное выражение представляет собой произведение всех натуральных чисел от 1 до . В математике это произведение называется факториалом числа и обозначается (читается «эн факториал»). Заметим, что 1!=1. Интересно, что для удобства (вы оцените его чуть позже) полагают и 0!=1.

Отметим одну важную особенность этой замечательной функции – ее быстрый рост. Приведем для примера несколько значений факториала для возрастающих значений : 0 1 2 3 4 5 6 7 8 9 10 11 12 1 1 2 6 24 120 720 5040 40 320 362 880 3 628 800 39 916 800 479 001 600

Пример:

Дано слово РОСТ. Нужно получить слова, которые можно получить из него всевозможными перестановками букв. Каждое такое слово будет перестановкой из четырех заданных букв. Всего таких перестановок будет 4!=24.

Вопрос 19.

Перестановки с повторениями.

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

Начнем со случая, когда эти элементов делятся на 2 группы, внутри которых они неотличимы друг от друга.

Пусть имеется 4 карточки, на которых написаны буквы A, A, B, B. Попробуем выписать все возможные «слова», которые можно получить из этих четырех карточек, выкладывая их в разном порядке. Обратите внимание, что эти комбинации

• во-первых, не будут перестановками, т.к. при перестановке букв A или букв B между собой слово не меняется;

• во-вторых, не будут размещениями с повторениями, т.к. количество букв A и букв B в слове равно количеству соответствующих карточек.

То, что мы получим, называется перестановками с повторениями: AABB, ABAB, ABBA, BAAB, BABA, BBAA.

Пусть имеется карточек, на из которых написана буква A, а на остальных карточках - буква B (разумеется, . Сколько разных слов можно составить, переставляя их между собой? Если бы все карточки были разные, то каждое их расположение в ряд было бы перестановкой из элементов, и всего таких расположений мы насчитали бы Поскольку карточки с буквами А (равно как и с буквой B) выглядят для нас одинаковыми, то их перестановки между собой (A с A, B с B) не изменяют слова. Следовательно, при подсчете перестановок каждое слово (перестановка с повторениями) было посчитано столько раз, сколькими способами можно переставить букв A между собой и букв B между собой, т.е. раз. Поделив на , получаем интересующее нас количество перестановок с повторениями: . При доказательстве формулы мы воспользовались еще одним замечательным комбинаторным правилом: если при подсчете комбинаций каждая из них была посчитана раз, то нужно поделить найденное количество на . Оно называется правилом деления. Правило очевидное, но очень полезное при выводе многих комбинаторных формул.

Рассмотрим теперь общий случай перестановок с повторениями. Пусть имеется элементов, которые делятся на групп по элементов в каждой, причем внутри одной группы элементы друг от друга неотличимы (разумеется, ). Общее число перестановок, которые можно отличить друг от друга, будет равно: Р (n1, n2, …, nk) = . Действительно, если бы все элементы были разными, то общее число перестановок было бы . Какие же из них неотличимы друг от друга? Те, что отличаются перестановками элементов внутри каждой из групп. В первой группе элементы можно переставить способами, во второй - и так далее. Значит, каждая перестановка повторятся в нашем подсчете раз. Чтобы посчитать ее только один раз, нужно, по правилу деления, поделить на .

Пример: 3 красных карандаша, 4 синих, 2 желт.

Р (3;4;2)=

Вопросы 20,21

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

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

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

Пример

Коля, Оля, Артем и Наташа должны с помощью жребия распределить между собой два выигранных в конкурсе приза: мобильный телефон и MP3-плеер. Каждый исход такого жребия – это размещение из четырех по два. В самом деле, мы должны выбрать из четырех человек тех двоих, кто получит призы, а затем решить, кто из них заберет телефон, а кто – плеер. Все такие размещения несложно закодировать и выписать:

КО, ОК, КА, АК, КН, НК, ОА, АО, ОН, НО, АН, НА.

Первый человек в каждой такой паре получает телефон, второй – плеер (скажем, АК означает, что Артем получает телефон, а Коля – плеер).

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

было равно , последний сомножитель должен равняться . Таким образом, количество размещений из по , которое принято обозначать (читается – «а из эн по ка»), можно найти по формуле

.

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

…

Последнее равенство лишний раз напоминает о том, что размещение из по есть не что иное, как перестановка из элементов. И еще интересное наблюдение: размещений из по столько же, сколько из по .

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

Пример с чемпионатом Европы по футболу. Для группы, в которой играют команды А, Н, И, М, Р, Х, Э (именно так мы их закодировали) нужно найти все варианты распределения двух первых мест.

Каждый такой вариант – размещение из 7 по 2. Общее количество таких размещений - .

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

Эти комбинации имеют в комбинаторике специальное название – размещения с повторениями из по . Пишут: .

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

Дан алфавит из четырех букв – A, B, C, D. Нужно составить из него все двухбуквенные «слова». Этими словами будут размещения с повторениями из четырех по два. Их несложно перечислить:

AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, DD.

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

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

Пример: размещения с повторениями из 6-ти по 3, их количество - .