КОМБИНАТОРИКА

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

Правила сложения и умножения в комбинаторике

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

Пример 1.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?

Решение

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n 1 способами, второе действие n 2 способами, третье - n 3 способами и так до k-го действия, которое можно выполнить n k способами, то все k действий вместе могут быть выполнены:

способами.

Пример 2.

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

Решение

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

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

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.

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

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?

Пример 3.

Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?

Решение

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

.

Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?

.

Пример 4.

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

Решение

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

.

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

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

Пример 5.

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

Решение.

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

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно вы б рать и разместить по m различным местам m из n предметов, с реди которых есть одинаковые?

Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера- составить каталог. Сколько различных пятизначных номеров может составить мальчик?

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

Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?

Пример 7.

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

Решение

Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.

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

Пример 8.

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

Решение

Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно

ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ "КОМБИНАТОРИКА"

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

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

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

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

1-й объект можно выбрать k 1 способами,

2-ой объект - k 2 способами,

n -ый объект - k n способами. (1.1)

Тогда произвольный набор, перечисленных n объектов из данного множества можно выбрать k 1 , k 2 , …, k n способами.

Пример 1. Сколько существует трехзначных чисел с разными цифрами?

Решение . В десятичной системе исчисления десять цифр: 0,1,2,3,4,5,6,7,8,9. На первом месте может стоять любая из девяти цифр (кроме нуля). На втором месте - любая из оставшихся 9 цифр, кроме выбранной. На последнем месте любая из оставшихся 8 цифр.

По правилу произведения 9·9·8 = 648 трёхзначных чисел имеют разные цифры.

Пример 2. Из пункта в пункт ведут 3 дороги, а из пункта в пункт - 4 дороги. Сколькими способами можно совершить поездку из в через ?

Решение . В пункте есть 3 способа выбора дороги в пункт , а в пункте есть 4 способа попасть в пункт . Согласно принципу умножения, существует 3×4 = 12 способов попасть из пункта в пункт .

Правило суммы: при выполнении условий (1.1), любой из объектов можно выбрать k 1 +k 2 +…+k n способами.

Пример 3. Сколько существует способов выбора одного карандаша из коробки, содержащей 5 красных, 7 синих, 3 зеленых карандаша.

Решение . Один карандаш, по правилу суммы, можно выбрать 5+7+3 = 15 способами.

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

Решение . Все условия принципа сложения здесь выполнены, поэтому, в соответствии с этим принципом, получим 1+2+3 = 6 способов.

Рассмотрим пример, иллюстрирующий различие принципов умножения и сложения.

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

Решение . Один телевизор можно выбрать тремя способами, а магнитофон - другими двумя способами. Тогда телевизор или магнитофон можно купить 3+2=5 способами.

Во втором случае один телевизор можно выбрать тремя способами, после этого видеомагнитофон можно выбрать двумя способами. Следовательно, в силу принципа умножения, купить телевизор и видеомагнитофон можно 3×2 = 6 способами.

Рассмотрим теперь примеры, в которых применяются оба правила комбинаторики: и принцип умножения, и принцип сложения.

Пример 6. В корзине лежат 12 яблок и 10 апельсинов. Ваня выбирает либо яблоко, либо апельсин. После чего Надя выбирает из оставшихся фруктов и яблоко и апельсин. Сколько возможно таких выборов?

Решение . Ваня может выбрать яблоко 12 способами, апельсин - 10 способами. Если Ваня выбирает яблоко, то Надя может выбрать яблоко 11 способами, а апельсин - 10 способами. Если Ваня выбирает апельсин, то Надя может выбрать яблоко 12 способами, а апельсин - 9 способами. Таким образом, Ваня и Надя могут сделать свой выбор способами.

Пример 7. Есть 3 письма, каждое из которых можно послать по 6 адресам. Сколькими способами это можно сделать?

Решение . В данной задаче мы должны рассмотреть три случая:

а) все письма рассылаются по разным адресам;

б) все письма посылаются по одному адресу;

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

Если все письма рассылаются по разным адресам, то число таких способов легко находится из принципа умножения: n 1 = 6×5×4 = 120 способов. Если все письма посылаются по одному адресу, то таких способов будет n 2 = 6. Таким образом, остается рассмотреть только третий случай, когда только 2 письма посылаются по одному адресу. Выбрать какое-либо письмо мы можем 3 способами, и послать его по какому-либо выбранному адресу можем 6 способами. Оставшиеся два письма мы можем послать по оставшимся адресам 5 способами. Следовательно, послать только два письма по одному адресу мы можем n 3 =3×6×5=90 способами. Таким образом, разослать 3 письма по 6 адресам в соответствие с принципом сложения можно

способами.

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

1. Схема выбора без возвращений

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

Число размещений из n элементов по k обозначается и вычисляется по формуле

(1.2)

где n ! = 1×2×3×…×n , 1! = 1, 0! = 1.

Пример 8. В соревнованиях участвует 10 человек, трое из них займут 1, 2, 3 место. Сколько существует различных вариантов?

Решение . В этом случае важен порядок распределения мест. Число различных вариантов равно

Перестановкой из n элементов называют размещение из n элементов по n. Число перестановок из n элементов обозначают P n и вычисляют по формуле

(1.3)

Пример 9. Сколько существует способов расстановки 10 книг на полке?

Решение . Общее число способов расстановки определяется как число перестановок (1.3) из 10 элементов и равно Р 10 = 10! = 3628 800.

2. Схема выбора с возвращениями

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

Число размещений с повторениями:

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

Решение . Каждый следующий гость из 4 может быть помещён в любую из 10 комнат, так как рассматривается идеализированный опыт, поэтому общее число размещений, по формуле размещений с повторениями (1.5), равно

.

Если при выборе k элементов из n элементы возвращаются обратно без последующего упорядочивания, то говорят, что это сочетания с nовторениями. Число сочетаний с повторениями из n элементов по k определяется:

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

Решение . Число равновозможных заказов по формуле (1.6) равно

.

Цель занятия: уметь применять основные формулы комбинаторики и знать условия применения этих формул; знать свойства биномиальных коэффициентов и уметь определять разложение бинома при конкретных значениях n.

План занятия:

1. Число размещений.

2. Число перестановок.

3. Число сочетаний.

4. Повторения.

5. Бином Ньютона. Треугольник Паскаля.

Методические указания по изучению темы

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

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

Пусть есть некоторое множество из n элементов: x 1, x 2, x 3, …, x n .

Из этого множества можно образовать различные подмножества, то есть выборки, каждая из которых содержит m элементов (0 ≤ m ≤ n). Различают упорядоченные выборки (размещения), перестановки и неупорядоченные выборки (сочетания).

Размещения

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

Число размещений из n элементов по m элементов обозначают (А – первая буква французского слова arrangement, что означает размещение, приведение в порядок) и вычисляют по формуле:

Понятие факториала

Произведение n натуральных чисел от 1 до n обозначается символом n ! (n факториал), то есть

Например, 2!=

5!=

Заметим, что удобно рассчитывать 0!, полагая по определению, 0!=1.

Примеры:

Из последних двух формул следует, что

Пример.

В однокруговом турнире по футболу участвуют 8 команд. Сколько существует вариантов призовой тройки?

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

(вариантов).

Пример.

Сколькими способами можно выбрать три лица на три различные должности из десяти кандидатов?

Решение:

(способов).

Пример.

Сколько можно составить телефонных номеров из 5 цифр так, чтобы в каждом отдельно взятом номере все цифры были различными?

(телефонных номеров).

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

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

Число всех возможных перестановок из n элементов обозначают P n (P – первая буква французского слова permutation, что означает перестановка) и вычисляют по формуле:

Пример.

В финальном забеге на 100 метров участвуют 8 спортсменов. Сколько существует вариантов протокола забега?

Решение:

В данном случае речь идёт обо всех перестановках из 8 элементов. Тогда (вариантов)

Пример.

Сколькими различными способами могут разместиться на скамейке10 человек?

Решение:

(способов)

Пример.

Сколькими способами можно разместить 7 лиц за столом, на котором поставлено 7 столовых приборов?

Решение:

(способов).

Сочетания

Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом.

Число сочетаний вычисляют по формуле: (С - первая буква французского слова combinasion).

Пример.

Сколькими способами можно выбрать три лица на три одинаковые должности из десяти кандидатов?

Решение :

(способов).

Пример.

Сколькими способами можно выбрать три детали из ящика, содержащего 15 деталей?

Решение:

(способов).

Другой вид формул числа размещений и числа сочетаний

; , то есть .

Свойства числа сочетаний:

5)

При решении задач комбинаторики используют следующие правила:

Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов n способами, а другой объект В – k способами, то объект «либо А, либо В» можно выбрать n+k способами.

Правило произведения. Если некоторый объект А может быть выбран из совокупности объектов n способами и после каждого такого выбора другой объект В – k способами, то пара объектов (А, В) в указанном порядке может быть выбрана n×k способами.

Если некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам.

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

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

Пример.

Из цифр 1,2,3,4,5 можно составить 5 3 =125 трехзначных чисел, если в одном и том же числе могут попадаться и одинаковые цифры.

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

Если среди n элементов есть n 1 элементов одного вида, n 2 элементов другого вида и т.д., то число перестановок с повторениями

где

Пример.

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

Решение:

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

Число сочетаний с повторениями из n различных элементов по m элементов равно числу сочетаний без повторений из (n +m -1) различных элементов по m элементов:

Пример.

Найти число сочетаний с повторениями из четырех элементов a , b , c , d по 3 элемента.

Решение:

Искомое число будет

Бином Ньютона

Для произвольного положительного целого числа n справедлива следующая формула:

Это бином Ньютона. Коэффициенты называются биномиальными коэффициентами.

При n = 2 получим формулу ;

При n = 3 получим формулу .

Пример. Определить разложение при n=4.

Решение:

Биномиальные коэффициенты обладают рядом свойств:

2. ;

Рассмотрим следующий треугольник:

………………………….

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

……………………….

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

В русскоязычной литературе перестановки, составленные из n различных элементов выбором по m элементов, которые отличаются либо составом элементов, либо их порядком, обычно называют размещениями, а под перестановками понимают всю совокупность комбинаций, состоящих из одних и тех же n различных элементов и отличающихся только порядком их расположения. В этом смысле число всех возможных перестановок для множества из n различных элементов считается по формуле факториала Pn = n! или в Excel «=ФАКТР(N)» (см. рис. № 1)

Например, если ввести «=ПЕРЕСТ(3;2)», получим 6. Это 6 комбинации: (1,2), (2,1), (1,3), (3,1), (2,3), (3,2).

А вот встроенная функция «=ЧИСЛКОМБ(N;K)» выдает комбинаторную формулу, называемую у нас «Число сочетаний». В русскоязычной литературе так именуют перестановки, составленные из n различных элементов выбором по m элементов, которые отличаются только составом элементов, а порядок их выбора безразличен (см. рис, №4)

При использовании встроенных функций пользуйтесь «Справкой по этой функции». Например:

Задачи для самостоятельного решения

1. Вычислить:

2. Вычислить:

3. Вычислить:

4. Найти n , если 5С n 3 =

5. Найти n , если

6. Найти n , если

7. Найти n , если

8. Найти n , если , k n

9. Решить уравнение

10. Решить систему

11. Сколько можно составить сигналов из 6 флажков различного цвета, взятых по 2?

12. Сколькими способами можно выбрать четыре лица на четыре различные должности из девяти кандидатов?

13. Сколько можно составить телефонных номеров из 6 цифр так, чтобы в каждом отдельно взятом номере все цифры были различны?

14. В классе 10 учебных предметов и 5 разных уроков в день. Сколькими способами могут быть распределены уроки в один день?

15. Сколько можно записать четырёхзначных чисел, используя без повторения все 10 цифр?

16. Фирма производит выбор из девяти кандидатов на три различные должности. Сколько существует способов такого выбора?

17. В восьмом классе изучается 15 предметов. Сколькими способами можно составить расписание на среду, если известно, что в этот день должно быть 6 уроков?

18. В высшей лиге чемпионата страны по футболу 16 команд. Борьба идет за золотые, серебряные и бронзовые медали. Сколькими способами медали могут быть распределены между командами?

19. Сколькими способами можно разместить 9 лиц за столом, на котором поставлено 9 приборов?

20. На собрании выступят 6 ораторов. Сколькими способами их фамилии можно расположить в списке?

21. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, если каждая цифра входит в изображение числа только один раз?

22. Сколькими различными способами можно расставить 10 различных книг на полке, чтобы определённые 4 книги стояли рядом?

23. В однокруговом турнире по футболу участвуют 8 команд. Сколько всего матчей будет сыграно?

24. Из 25 студентов нужно выбрать трех делегатов на конференцию. Сколькими способами это можно сделать?

25. Сколькими способами можно выбрать две детали из ящика, содержащего 10 деталей?

26. В колоде 36 карт, из них 4 туза. Сколькими способами можно извлечь 6 карт так, чтобы среди них было 2 туза?

27. Комплексная бригада состоит из двух маляров, трёх штукатуров и одного столяра. Сколько различных бригад можно создать из рабочего коллектива, в котором 15 маляров, 10 штукатуров и 5 столяров?

28. В отборочном турнире за 3 путёвки на чемпионат мира участвуют 10 команд. Сколько существует вариантов «счастливой тройки»?

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

30. Сколькими различными способами можно составить разведывательную группу из 3-х солдат и одного командира, если имеется 12 солдат и 3 командира?

31. На плоскости дано n точек, из которых никакие три не лежат на одной прямой. Найти число прямых, которые можно получить, соединяя точки попарно.

32. Буквы азбуки Морзе образуются как последовательность точек и тире. Сколько различных букв можно образовать, если использовать 5 символов?

33. Сколько существует различных семизначных телефонных номеров?

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

35. При игре в бридж между четырьмя игроками распределяется колода карт в 52 листа по 13 карт каждому игроку. Сколько существует различных способов раздать карты?

36. В почтовом отделении продаются открытки пяти видов. Определить число способов покупки семи открыток.

37. Два коллекционера обмениваются марками. Найти число способов обмена, если первый коллекционер обменивает 3 марки, а второй – 6 марок. (Обмен происходит по одной марке).

38. У одного студента 6 книг по математике, а у другого – 5. Сколькими способами они могут обменять 2 книги одного на 2 книги другого?

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

40. Сколькими различными способами можно разместить в 9 клетках следующие 9 букв: а, а, а, б, б, б, в, в, в?

41. В автомашине 6 мест. Сколькими способами 6 человек могут сесть в эту машину, если занять место водителя могут только двое из них?

42. Сколькими способами из колоды в 52 карты можно извлечь 6 карт, содержащих туза и короля одной масти?

43. Определить разложение при n=5.

44. Определить разложение при n=8.

45. Найти член разложения , не содержащий x (то есть содержащий x в нулевой степени).

46. Найти шестой член разложения , если биномиальный коэффициент третьего от конца члена равен 45.

47. В разложении коэффициент третьего члена на 44 больше коэффициента второго члена. Найти свободный член, то есть член разложения, не зависящий от x (членом, не зависящим от x, будет тот, который содержит x в нулевой степени).

48. В разложении бинома найти члены, не содержащие иррациональности.

49. Найти номер того члена разложения , который содержит a и b в одинаковых степенях.

Практическое занятие №2

(интерактивное занятие в малых группах)

Булевы функции

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

План занятия:

1. Основные операции

2. Булевы функции от n переменных

3. Основные эквивалентности

Подсчитаем в MS EXCEL количество перестановок из n элементов. С помощью формул выведем на лист все варианты перестановок (английский перевод термина: permutation).

Перестановкой множества из n элементов называется расположение элементов в определенном порядке.

Элементами множества могут быть числа, буквы и вообще любые объекты. Главное, чтобы эти элементы были различными. Т.к. любому объекту можно сопоставить число, то для Перестановок обычно используют конечное множество целых чисел, например, {1; 2; 3; 4; 5}. Хотя множества из букв также можно часто встретить в литературе. Например, все различные Перестановки множества из трех элементов {a, b, c} – это abc , acb , bac , bca , cab , cba .

Число Перестановок n элементов равно n! (факториал).

Для вычисления факториала в MS EXCEL есть функция =ФАКТР() , английский вариант FACT(). Понятно, что число перестановок растет очень быстро с ростом n: для n=7 число перестановок равно 5040. Справедливости ради, нужно отметить, что зачастую сами варианты перестановок находить не требуется, главное – найти их количество.

Примечание : Перестановки можно считать частным случаем размещений при n=k (см. статью ). Поэтому для вычисления количества перестановок можно использовать функцию ПЕРЕСТ() . Для n=7 число Перестановок вычисляется по формуле =ПЕРЕСТ(7;7)

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

В файле примера создана универсальная формула для вывода всех Перестановок для заданного n. Например, для n=3.

Задача

6 машин разных марок участвуют в гонках на выживание: LADA Granta, Hyundai Solaris, KIA Rio, Renault Duster, Lada Kalina, Volkswagen Polo. Определить число возможных вариантов распределения мест между всеми участниками.

Нам нужно определить число перестановок 6 машин на 6-и местах. Т.е. n=6. Оказывается, что таких перестановок 720: =ПЕРЕСТ(6;6) или 6! =ФАКТР(6)

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

Произвольным образом сопоставим маркам машин числовые значения и сделаем сокращения названий марок: LADA Granta (LG=1), Hyundai Solaris (HS=2), …

Введя в ячейке В5 значение 6, определим все варианты расстановок машин на занятых ими в гонке местах.

Примечание : О Размещениях можно прочитать в статье , а о Сочетаниях в статье .

Перебор всех возможных перестановок может потребоваться для решения различных задач (см. статью и ).

Инверсии перестановок

Для каждой перестановки a 1, a 2, a 3,..., a n из n целых чисел 1, 2, 3, ..., n , инверсией называется пара (a i, a j) если для i < j выполняется a i > a j. Число инверсией в перестановке показывает насколько перестановка является "несортированной" по возрастанию.

Например, число инверсий в перестановке 1, 2, 3, 4 равно 0 (перестановка из 4-х целых чисел отсортирована по возрастанию от 1 до 4), а число инверсий в перестановке 4, 3, 1, 2 равно 5, т.к.:

• первый элемент (i=1) равен 4 и он больше 3-х чисел (с j=2, 3, 4), которые расположены правее (4>3, 4>1, 4>2), т.е. мы имеем 3 инверсии;
• второй элемент (i=2) равен 3 и он больше2-х чисел (с j=3, 4), которые расположены правее (3>1, 3>2), т.е. мы имеем еще 2 инверсии;
• так третий элемент (i=3) равен 1 и он меньше числа с j=4, которое расположено правее (1<2), то эта пара не является инверсией. Т.е. у перестановки 4, 3, 1, 2 число инверсий равно 3+2+0=5.

В файле примера для каждой Перестановки подсчитывается число инверсией.

Чтобы в материале было легче ориентироваться, добавлю содержание данной темы:

Введение. Множества и выборки.

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

Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме "Понятие множества. Способы задания множеств" .

Очень краткий рассказ про множества : показать\скрыть

Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 11115555999 будет таким: $\{1,5,9 \}$. Множество согласных букв в слове "тигрёнок" таково: $\{т, г, р, н, к\}$. Запись $5\in A$ означает, что элемент 5 принадлежит множеству $A=\{1,5,9 \}$. Количество элементов в конечном множестве называют мощностью этого множества и обозначают $|A|$. Например, для множества $A=\{1,5,9 \}$, содержащего 3 элемента, имеем: $|A|=3$.

Рассмотрим некое непустое конечное множество $U$, мощность которого равна $n$, $|U|=n$ (т.е. в множестве $U$ имеется $n$ элементов). Введём такое понятие, как выборка (некоторые авторы именуют её кортежем). Под выборкой объема $k$ из $n$ элементов (сокращённо $(n,k)$-выборкой) будем понимать набор элементов $(a_1, a_2,\ldots, a_k)$, где $a_i\in U$. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Две упорядоченные выборки, различающиеся лишь порядком элементов, являются различными. Если порядок следования элементов выборки не является существенным, то выборку именуют неупорядоченной.

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

Для примера рассмотрим множество $U=\{a,b,c,d,e\}$. Множество $U$ содержит 5 элементов, т.е. $|U|=5$. Выборка без повторений может быть такой: $(a,b,c)$. Данная выборка содержит 3 элемента, т.е. объём этой выборки равен 3. Иными словами, это $(5,3)$-выборка.

Выборка с повторениями может быть такой: $(a,a,a,a,a,c,c,d)$. Она содержит 8 элементов, т.е. объём её равен 8. Иными словами, это $(5,8)$-выборка.

Рассмотрим ещё две $(5,3)$-выборки: $(a,b,b)$ и $(b,a,b)$. Если мы полагаем наши выборки неупорядоченными, то выборка $(a,b,b)$ равна выборке $(b,a,b)$, т.е. $(a,b,b)=(b,a,b)$. Если мы полагаем наши выборки упорядоченными, то $(a,b,b)\neq(b,a,b)$.

Рассмотрим ещё один пример, немного менее абстрактный:) Предположим, в корзине лежат шесть конфет, причём все они различны. Если первой конфете поставить в соответствие цифру 1, второй конфете - цифру 2 и так далее, то с конфетами в корзине можно сопоставить такое множество: $U=\{1,2,3,4,5,6\}$. Представьте, что мы наугад запускаем руку в корзинку с целью вытащить три конфеты. Вытащенные конфеты - это и есть выборка. Так как мы вытаскиваем 3 конфеты из 6, то получаем (6,3)-выборку. Порядок расположения конфет в ладони совершенно несущественен, поэтому эта выборка является неупорядоченной. Ну, и так как все конфеты различны, то выборка без повторений. Итак, в данной ситуации говорим о неупорядоченной (6,3)-выборке без повторений.

Теперь подойдём с иной стороны. Представим себе, что мы находимся на фабрике по производству конфет, и на этой фабрике производятся конфеты четырёх сортов. Множество $U$ в этой ситуации таково: $U=\{1,2,3,4 \}$ (каждая цифра отвечает за свой сорт конфет). Теперь вообразим, что все конфеты ссыпаются в единый жёлоб, около которого мы и стоим. И, подставив ладони, из этого потока отбираем 20 конфет. Конфеты в горсти – это и есть выборка. Играет ли роль порядок расположения конфет в горсти? Естественно, нет, поэтому выборка неупорядоченная. Всего 4 сорта конфет, а мы отбираем двадцать штук из общего потока - повторения сортов неизбежны. При этом выборки могут быть самыми различными: у нас даже могут оказаться все конфеты одного сорта. Следовательно, в этой ситуации мы имеем дело с неупорядоченной (4,20)-выборкой с повторениями.

Рассмотрим ещё пару примеров. Пусть на кубиках написаны различные 7 букв: к, о, н, ф, е, т, а. Эти буквы образуют множество $U=\{к,о,н,ф,е,т,а\}$. Допустим, из данных кубиков мы хотим составить "слова" из 5 букв. Буквы этих слов (к примеру, «конфе», «тенко» и так далее) образуют (7,5)-выборки: $(к,о,н,ф,е)$, $(т,е,н,к,о)$ и т.д. Очевидно, что порядок следования букв в такой выборке важен. Например, слова «нокфт» и «кфтон» различны (хотя состоят из одних и тех же букв), ибо в них не совпадает порядок букв. Повторений букв в таких «словах» нет, ибо в наличии только семь кубиков. Итак, набор букв каждого слова представляет собой упорядоченную (7,5)-выборку без повторений.

Еще один пример: мы составляем всевозможные восьмизначные числа из четырёх цифр 1, 5, 7, 8. Например, 11111111, 15518877, 88881111 и так далее. Множество $U$ таково: $U=\{1,5,7,8\}$. Цифры каждого составленного числа образуют (4,8)-выборку. Порядок следования цифр в числе важен, т.е. выборка упорядоченная. Повторения допускаются, поэтому здесь мы имеем дело с упорядоченной (4,8)-выборкой с повторениями.

Размещения без повторений из $n$ элементов по $k$

Размещение без повторений из $n$ элементов по $k$ - упорядоченная $(n,k)$-выборка без повторений.

Так как элементы в рассматриваемой выборке повторяться не могут, то мы не можем отобрать в выборку больше элементов, чем есть в исходном множестве. Следовательно, для таких выборок верно неравенство: $n≥ k$. Количество размещений без повторений из $n$ элементов по $k$ определяется следующей формулой:

\begin{equation}A_{n}^{k}=\frac{n!}{(n-k)!} \end{equation}

Что обозначает знак "!"? : показать\скрыть

Запись "n!" (читается "эн факториал") обозначает произведение всех чисел от 1 до n, т.е.

$$ n!=1\cdot2\cdot 3\cdot \ldots\cdot n $$

По определению полагается, что $0!=1!=1$. Для примера найдём 5!:

$$ 5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120. $$

Пример №1

Алфавит состоит из множества символов $E=\{+,*,0,1,f\}$. Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв.

Под трёхсимвольными словами будем понимать выражения вида "+*0" или "0f1". В множестве $E$ пять элементов, поэтому буквы трехсимвольных слов образуют (5,3)-выборки. Первый вопрос: эти выборки упорядочены или нет? Слова, которые отличаются лишь порядком букв, полагаются различными, поэтому порядок элементов в выборке важен. Значит, выборка является упорядоченной. Второй вопрос: допускаются повторения или нет? Ответ на этот вопрос даёт условие: слова не должны содержать повторяющихся букв. Подводим итоги: буквы каждого слова, удовлетворяющего условию задачи, образуют упорядоченную (5,3)-выборку без повторений. Иными словами, буквы каждого слова образуют размещение без повторений из 5 элементов по 3. Вот примеры таких размещений:

$$ (+,*,f), \; (*,+,f), \; (1,+,0) $$

Нас же интересует общее количество этих размещений. Согласно формуле (1) количество размещений без повторений из 5 элементов по 3 будет таким:

$$ A_{5}^{3}=\frac{5!}{(5-3)!}=\frac{5!}{2!}=60. $$

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

Ответ : 60.

Размещения с повторениями из $n$ элементов по $k$

Размещение с повторениями из $n$ элементов по $k$ - упорядоченная $(n,k)$-выборка с повторениями.

Количество размещений с повторениями из $n$ элементов по $k$ определяется следующей формулой:

\begin{equation}\bar{A}_{n}^{k}=n^k \end{equation}

Пример №2

Сколько пятизначных чисел можно составить из множества цифр $\{5,7,2\}$?

Из данного набора цифр можно составить пятизначные числа 55555, 75222 и так далее. Цифры каждого такого числа образуют (3,5)-выборку: $(5,5,5,5,5)$, $(7,5,2,2,2)$. Зададимся вопросом: что это за выборки? Во-первых, цифры в числах могут повторяться, поэтому мы имеем дело с выборками с повторениями. Во-вторых, порядок расположения цифр в числе важен. Например, 27755 и 77255 - разные числа. Следовательно, мы имеем дело с упорядоченными (3,5)-выборками с повторениями. Общее количество таких выборок (т.е. общее количество искомых пятизначных чисел) найдём с помощью формулы (2):

$$ \bar{A}_{3}^{5}=3^5=243. $$

Следовательно, из заданных цифр можно составить 243 пятизначных числа.

Ответ : 243.

Перестановки без повторений из $n$ элементов

Перестановка без повторений из $n$ элементов - упорядоченная $(n,n)$-выборка без повторений.

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

\begin{equation}P_{n}=n! \end{equation}

Эту формулу, кстати, легко получить, если учесть, что $P_n=A_{n}^{n}$. Тогда получим:

$$ P_n=A_{n}^{n}=\frac{n!}{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n! $$

Пример №3

В морозилке лежат пять порций мороженого от различных фирм. Сколькими способами можно выбрать порядок их съедения?

Пусть первому мороженому соответствует цифра 1, второму - цифра 2 и так далее. Мы получим множество $U=\{1,2,3,4,5\}$, которое будет представлять содержимое морозилки. Порядок съедения может быть таким: $(2,1,3,5,4)$ или таким: $(5,4,3,1,2)$. Каждый подобный набор есть (5,5)-выборка. Она будет упорядоченной и без повторений. Иными словами, каждая такая выборка есть перестановка из 5 элементов исходного множества. Согласно формуле (3) общее количество этих перестановок таково:

$$ P_5=5!=120. $$

Следовательно, существует 120 порядков выбора очередности съедения.

Ответ : 120.

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

Перестановка с повторениями – упорядоченная $(n,k)$-выборка с повторениями, в которой элемент $a_1$ повторяется $k_1$ раз, $a_2$ повторяется $k_2$ раза так далее, до последнего элемента $a_r$, который повторяется $k_r$ раз. При этом $k_1+k_2+\ldots+k_r=k$.

Общее количество перестановок с повторениями определяется формулой:

\begin{equation}P_{k}(k_1,k_2,\ldots,k_r)=\frac{k!}{k_1!\cdot k_2!\cdot \ldots \cdot k_r!} \end{equation}

Пример №4

Слова составляются на основе алфавита $U=\{a,b,d\}$. Сколько различных слов из семи символов может быть составлено, если в этих словах буква "a" должна повторяться 2 раза; буква "b" - 1 раз, а буква "d" - 4 раза?

Вот примеры искомых слов: "aabdddd", "daddabd" и так далее. Буквы каждого слова образуют (3,7)-выборку с повторениями: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d)$ и т.д. Каждая такая выборка состоит из двух элементов "a", одного элемента "b" и четырёх элементов "d". Иными словами, $k_1=2$, $k_2=1$, $k_3=4$. Общее количество повторений всех символов, естественно, равно объёму выборки, т.е. $k=k_1+k_2+k_3=7$. Подставляя эти данные в формулу (4), будем иметь:

$$ P_7(2,1,4)=\frac{7!}{2!\cdot 1!\cdot 4!}=105. $$

Следовательно, общее количество искомых слов равно 105.

Ответ : 105.

Сочетания без повторений из $n$ элементов по $k$

Сочетание без повторений из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка без повторений.

Общее количество сочетаний без повторений из $n$ элементов по $k$ определяется формулой:

\begin{equation}C_{n}^{k}=\frac{n!}{(n-k)!\cdot k!} \end{equation}

Пример №5

В корзине размещены карточки, на которых написаны целые числа от 1 до 10. Из корзины вынимают 4 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины?

Итак, в данной задаче исходное множество таково: $U=\{1,2,3,4,5,6,7,8,9,10\}$. Из этого множества мы выбираем четыре элемента (т.е., четыре карточки из корзины). Номера вытащенных элементов образуют (10,4)-выборку. Повторения в этой выборке не допускаются, так как номера всех карточек различны. Вопрос вот в чём: порядок выбора карточек играет роль или нет? Т.е., к примеру, равны ли выборки $(1,2,7,10)$ и $(10,2,1,7)$ или не равны? Тут нужно обратиться к условию задачи. Карточки вынимаются для того, чтобы потом найти сумму элементов. А это значит, что порядок карточек не важен, так как от перемены мест слагаемых сумма не изменится. Например, выборке $(1,2,7,10)$ и выборке $(10,2,1,7)$ будет соответствовать одно и то же число $1+2+7+10=10+2+1+7=20$. Вывод: из условия задачи следует, что мы имеем дело с неупорядоченными выборками. Т.е. нам нужно найти общее количество неупорядоченных (10,4)-выборок без повторений. Иными словами, нам нужно найти количество сочетаний из 10 элементов по 4. Используем для этого формулу (5):

$$ C_{10}^{4}=\frac{10!}{(10-4)!\cdot 4!}=\frac{10!}{6!\cdot 4!}=210. $$

Следовательно, общее количество искомых наборов равно 210.

Ответ : 210.

Сочетания с повторениями из $n$ элементов по $k$

Сочетание с повторениями из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка с повторениями.

Общее количество сочетаний с повторениями из $n$ элементов по $k$ определяется формулой:

\begin{equation}\bar{C}_{n}^{k}=\frac{(n+k-1)!}{(n-1)!\cdot k!} \end{equation}

Пример №6

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

Если принять, что первому сорту соответствует число 1, второму сорту - число 2 и так далее, то исходное множество в нашей задаче таково: $U=\{1,2,3,4\}$. Из этого множества мы выбираем 20 элементов (т.е., те самые 20 конфет с конвейера). Пригоршня конфет образует (4,20)-выборку. Естественно, повторения сортов будут. Вопрос в том, играет роль порядок расположения элементов в выборке или нет? Из условия задачи следует, что порядок расположения элементов роли не играет. Нам нет разницы, будут ли в горсти располагаться сначала 15 леденцов, а потом 4 шоколадных конфеты, или сначала 4 шоколадных конфеты, а уж потом 15 леденцов. Итак, мы имеем дело с неупорядоченной (4,20) выборкой с повторениями. Чтобы найти общее количество этих выборок используем формулу (6):

$$ \bar{C}_{4}^{20}=\frac{(4+20-1)!}{(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771. $$

Следовательно, общее количество искомых комбинаций равно 1771.