Комбинаторика сочетания перестановки размещения – Перестановки сочетания и размещения (с и без повторений) — Дискретная математика. Теория множеств . Теория графов . Комбинаторика.

Комбинаторика. Размещения, перестановки, сочетания | Математика, которая мне нравится

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

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

Французский философ, писатель, математик и физик Блез Паскаль (1623–1662) рано проявил свои выдающиеся математические способности. Круг математических интересов Паскаля был весьма разнообразен. Паскаль доказал одну
из основных теорем проективной геометрии (теорема Паскаля), сконструировал суммирующую машину (арифмометр Паскаля), дал способ вычисления биномиальных коэффициентов (треугольник Паскаля), впервые точно определил и применил для доказательства метод математической индукции, сделал существенный шаг в развитии анализа бесконечно малых, сыграл важную роль в зарождении теории вероятности. В гидростатике Паскаль установил ее основной закон (закон Паскаля). “Письма к провинциалу” Паскаля явились шедевром французской классической прозы.

Готфрид Вильгельм Лейбниц (1646–1716) — немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. В математике наряду с И. Ньютоном разработал дифференциальное и интегральное исчисление. Важный вклад внес в комбинаторику. С его именем, в частности, связаны теоретико-числовые задачи.

Готфрид Вильгельм Лейбниц имел мало внушительную внешность и поэтому производил впечатление довольно невзрачного человека. Однажды в Париже он зашел в книжную лавку в надежде приобрести книгу своего знакомого философа. На вопрос посетителя об этой книге книготорговец, осмотрев его с головы до ног, насмешливо бросил: “Зачем она вам? Неужели вы способны читать такие книги?” Не успел ученый ответить, как в лавку вошел сам автор книги со словами: “Великому Лейбницу привет и уважение!” Продавец никак не мог взять втолк, что перед ним действительно знаменитый Лейбниц, книги которого пользовались большим спросом среди ученых.

В дальнейшем важную роль будет играть следующая

Лемма. Пусть в множестве элементов, а в множестве — элементов. Тогда число всех различных пар , где будет равно .

Доказательство. Действительно, с одним элементом из множества мы можем составить таких различных пар, а всего в множестве элементов.

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

Пусть у нас есть множество из трех элементов . Какими способами мы можем выбрать из этих элементов два? .

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

Число всех размещений множества из элементов по элементов обозначается через (от начальной буквы французского слова “arrangement”, что означает размещение), где и .

Теорема. Число размещений множества из элементов по элементов равно

   

Доказательство. Пусть у нас есть элементы . Пусть — возможные размещения. Будем строить эти размещения последовательно. Сначала определим — первый элемент размещения. Из данной совокупности элементов его можно выбрать различными способами. После выбора первого элемента для второго элемента остается способов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:

   

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

Решение. Искомое число трехполосных флагов:

   

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

Так, все различные перестановки множества из трех элементов — это

   

Очевидно, перестановки можно считать частным случаем размещений при >.

Число всех перестановок из элементов обозначается (от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле

   

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

Решение. Искомое число расстановки ладей

   

по определению!

Определение. Сочетаниями из различных элементов по элементов называются комбинации, которые составлены из данных элементов по элементов и отличаются хотя бы одним элементом (иначе говоря, -элементные подмножества данного множества из элементов).

Как видим, в сочетаниях в отличие от размещений не учитывается порядок элементов. Число всех сочетаний из элементов по элементов в каждом обозначается (от начальной буквы французского слова “combinasion”, что значит “сочетание”).

Числа

Все сочетания из множества по два — .

.

Свойства чисел {\sf C}_n^k

1. .

Действительно, каждому -элементному подмножеству данного -элементного множества соответствует одно и только одно -элементное подмножество того же множества.

2. .

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

Треугольник Паскаля

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

.

Теорема.

   

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

1 способ. Выбираем первый член последовательности, затем второй, третий и т.д. член

   

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

   

   

   

Домножим числитель и знаменатель этой дроби на :

   

   

Пример. Сколькими способами можно в игре “Спортлото” выбрать 5 номеров из 36?

Искомое число способов

   

Задачи.

1. Номера машин состоят из 3 букв русского алфавита (33 буквы) и 4 цифр. Сколько существует различных номеров автомашин?
2. На рояле 88 клавиш. Сколькими способами можно извлечь последовательно 6 звуков?
3. Сколько есть шестизначных чисел, делящихся на 5?
4. Сколькими способами можно разложить 7 разных монет в три кармана?
5. Сколько можно составить пятизначных чисел, в десятичной записи которых хотя бы один раз встречается цифра 5?
6. Сколькими способами можно усадить 20 человек за круглым столом, считая способы одинаковыми, если их можно получить один из другого движением по кругу?
7. Сколько есть пятизначных чисел, делящихся на 5, в записи которых нет одинаковых цифр?
8. На клетчатой бумаге со стороной клетки 1 см нарисована окружность радиуса 100 см, не проходящая через вершины клеток и не касающаяся сторон клеток. Сколько клеток может пересекать эта окружность?
9. Сколькими способами можно расставить в ряд числа так, чтобы числа стояли рядом и притом шли в порядке возрастания?
10. Сколько пятизначных чисел можно составить из цифр , если каждую цифру можно использовать только один раз?
11. Из слова РОТ перестановкой букв можно получить еще такие слова: ТОР, ОРТ, ОТР, ТРО, РТО. Их называют анаграммами. Сколько анаграмм можно составить из слова ЛОГАРИФМ?
12. Назовем разбиением натурального числа представление его в виде суммы натуральных чисел. Вот, например, все разбиения числа :

   

Разбиения считаются разными, если они отличаются либо числами, либо порядком слагаемых.

Сколько существует различных разбиений числа на слагаемых?
13. Сколько существует трехзначных чисел с невозрастающим порядком цифр?
14. Сколько существует четырехзначных чисел с невозрастающим порядком цифр?
15. Сколькими способами можно рассадить в ряд 17 человек, чтобы и оказались рядом?
16. девочек и мальчиков рассаживаются произвольным образом в ряду из мест. Сколькими способами можно их рассадить так, чтобы никакие две девочки не сидели рядом?
17. девочек и мальчиков рассаживаются произвольным образом в ряду из мест. Сколькими способами можно их рассадить так, чтобы все девочки сидели рядом?

hijos.ru

35 Элементы комбинаторики-перестановки,размещения, сочетания

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

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

Французский философ, писатель, математик и физик Блез Паскаль (1623–1662) рано проявил свои выдающиеся математические способности. Круг математических интересов Паскаля был весьма разнообразен. Паскаль доказал одну из основных теорем проективной геометрии (теорема Паскаля), сконструировал суммирующую машину (арифмометр Паскаля), дал способ вычисления биномиальных коэффициентов (треугольник Паскаля), впервые точно определил и применил для доказательства метод математической индукции, сделал существенный шаг в развитии анализа бесконечно малых, сыграл важную роль в зарождении теории вероятности. В гидростатике Паскаль установил ее основной закон (закон Паскаля). “Письма к провинциалу” Паскаля явились шедевром французской классической прозы.

Готфрид Вильгельм Лейбниц (1646–1716) — немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. В математике наряду с И. Ньютоном разработал дифференциальное и интегральное исчисление. Важный вклад внес в комбинаторику. С его именем, в частности, связаны теоретико-числовые задачи.

Готфрид Вильгельм Лейбниц имел мало внушительную внешность и поэтому производил впечатление довольно невзрачного человека. Однажды в Париже он зашел в книжную лавку в надежде приобрести книгу своего знакомого философа. На вопрос посетителя об этой книге книготорговец, осмотрев его с головы до ног, насмешливо бросил: “Зачем она вам? Неужели вы способны читать такие книги?” Не успел ученый ответить, как в лавку вошел сам автор книги со словами: “Великому Лейбницу привет и уважение!” Продавец никак не мог взять втолк, что перед ним действительно знаменитый Лейбниц, книги которого пользовались большим спросом среди ученых.

В дальнейшем важную роль будет играть следующая

Лемма. Пусть в множестве элементов, а в множестве—элементов. Тогда число всех различных пар, гдебудет равно.

Доказательство. Действительно, с одним элементом из множества мы можем составитьтаких различных пар, а всего в множествеэлементов.

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

Пусть у нас есть множество из трех элементов . Какими способами мы можем выбрать из этих элементов два?.

Определение.

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

Число всех размещений множества из элементов поэлементов обозначается через(от начальной буквы французского слова “arrangement”, что означает размещение), гдеи.

Теорема. Число размещений множества из элементов поэлементов равно

Доказательство. Пусть у нас есть элементы . Пусть— возможные размещения. Будем строить эти размещения последовательно. Сначала определим— первый элемент размещения. Из данной совокупностиэлементов его можно выбратьразличными способами. После выбора первого элементадля второго элементаостаетсяспособов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:

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

Решение. Искомое число трехполосных флагов:

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

Так, все различные перестановки множества из трех элементов — это

Очевидно, перестановки можно считать частным случаем размещений при .

Число всех перестановок из элементов обозначается(от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле

Пример. Сколькими способами можно расставить 8 ладей на шахматной доске так, чтобы они не били друг друга?

Решение. Искомое число расстановки 8 ладей

по определению!

Определение. Сочетаниями из различных элементов поэлементов называются комбинации, которые составлены из данныхэлементов поэлементов и отличаются хотя бы одним элементом (иначе говоря,-элементные подмножества данного множества изэлементов).

Как видим, в сочетаниях в отличие от размещений не учитывается порядок элементов. Число всех сочетаний из элементов поэлементов в каждом обозначается(от начальной буквы французского слова “combinasion”, что значит “сочетание”).

Числа

Все сочетания из множества по два —.

.

studfiles.net

Комбинаторика: основные правила и формулы.

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

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

 

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

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

 

Пример 1.

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

Решение

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

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

 

Правило произведения.

 Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n1 способами, второе действие n2 способами, третье – n3 способами и так до k-го действия, которое можно выполнить nk  способами, то все 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. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?

Решение

Можно  считать,  что  опыт  состоит  в 5-кратном выборе  с возращением одной из 3 цифр (1, 3, 7). Таким образом,  число  пятизначных  номеров  определяется  числом  размещений с повторениями из 3 элементов по 5:

.

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

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

Пример 7.

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

Решение

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

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

Пример 8.

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

Решение

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

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

ya-znau.ru

Элементы комбинаторики. Перестановки, размещения, сочетания

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

Число перестановок из n

 

Число размещений из n по m

 

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

 

Число сочетаний из n по m

 

Сохранить share extension

Итак, есть множество из n элементов.

Вариант упорядочивания данного множества называется перестановкой (permutation).
Например, есть множество, состоящее из 3 элементов — А, В, и С. Пример перестановки — СВА. Число всех перестановок из n элементов:

Пример: Для случая А, В, С число всех перестановок 3! = 6. Перестановки: АВС, АСВ, ВАС, ВСА, САВ, СВА

Если из множества n элементов выбирают m в определенном порядке, это называется размещением (arrangement).
Пример размещения из 3 по 2: АВ или ВА — это два разных размещения. Число всех размещений из n по m

Пример: Для случая А, В, С число всех размещений из 3 по 2 равно 3!/1! = 6. Размещения: АВ, ВА, АС, СА, ВС, СВ

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

Пример: Для случая А, В, С число всех размещений из 3 по 2 с повторениями равно 3*3 = 9. Размещения: AA, АВ, АС, ВА, BB, ВС, СА, СВ, CC

Если из множества n элементов выбирают m, и порядок не имеет значения, это называется сочетанием (combination).
Пример сочетания из 3 по 2: АВ. Число всех сочетаний из n по m

Пример: Для случая А, В, С число всех сочетаний из 3 по 2 равно 3!/(2!*1!) = 3. Сочетания: АВ, АС, СВ

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

Обратите внимание, что внизу

planetcalc.ru

Элементы комбинаторики: перестановки, размещения, сочетания.

Комбинаторика – это наука о расположении элементов в определенном порядке и о подсчете числа способов такого расположения.

 

Комбинаторный принцип умножения если одну часть действия можно выполнить k способами, а другую — p способами, то все действие можно выполнить k*p числом способов.

 

 

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

Если выбор делается без возвращения, т.е. каждый элемент множества Х можно выбирать только один раз, то количество размещений из n по k обозначается и определяется равенством
(размещения без повторений).

 

Если выбор элементов множества Y из Х происходит с возвращением, т.е. каждый элемент множества Х может быть выбран несколько раз, то число размещений из n по k находится по формуле: = nk.

 

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

Справедливы равенства: , , .

 

 

Сочетание с повторениями – сколько способами можно взять из n k элементов с возвращениями и без учета порядка. Число сочетаний с повторениями из n по k равно биномиальному коэффициенту.

 

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

Pn – количество перестановок из n элементов (сколько способами можно упорядочить)

 

Основные комбинаторные схемы.

— число перестановок (упорядочивание)

— число перемещений (число размещений)

— число сочетаний (без учета порядка)

 

— число сочетаний с возвращениями с учетом порядка

 

— число сочетаний с возвращениями без учета порядка (число сочетаний с повторениями)

 

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

 

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

Множество с одной бинарной ассоциативной операцией называется полугруппой. Полугруппы иногда называют моноидами.

Полугруппа называется группой если:

а) есть нейтральный элемент

б) для любого элемента есть обратный.

 

Множество с двумя ассоциативными операциями (сложения и умножения) называется кольцом, если

а) оно является коммутативной группой относительно сложения

б) операция умножения дитрибутивна относительно операции сложения, то есть для любых элементов a,b,c исходного множества справедливы тождества:

a + (b * c) = a * c + b * c

c * (a + b) = c * a + c * b

Полем называется коммутативное кольцо (то есть обе бинарные операции коммутативны), в котором существует нейтральный элемент по умножению (1) и каждый элемент, отличный от нуля (нуль – нейтральный по сложению), имеет обратный по умножению.

Множество действительных чисел, больших нуля и операцией умножения – коммутативная группа.

Множество целых чисел с операциями сложения и умножения – коммутативное кольцо

Множество всех действительных чисел с операциями сложения и умножения является кольцом и даже полем.

Множество всех комплексных чисел с операциями сложения и умножения – поле

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

 

Свойства элементов группы. Подгруппы группы.

 

Группа – множества с одной бинарной ассоциативной операцией, с нейтральным элементом и обратным элементов для каждого элемента.

 

Подгруппа – подмножество группы, также является само группой относительно той же операции. (G > H)

 

e – нейтральный элемент. Если есть в группе, то он есть и в подгруппе. Это один и тот же элемент, и быть другим в подгруппе он не может.

g-1 – обратный, есть и в группе и в подгруппе, отличаться не может.

 

 

Отношения эквивалентности.

x1, x2 ∈ X

x1 ρ x2 – находятся в отношении

Отношение эквивалентности – это отношение, для которого выполняются 3 свойства:

1) Для любого х есть свойство быть в отношении самому с собой

x ∈ X

x ρ x

2) x ρ y à y ρ x (свойство симметричности)

3) x ρ y, y ρ x à x ρ z (свойство транзитивности)

 

 


lektsia.com

Глава I. Перечислительная комбинаторика.

    1. Перестановки, размещения, сочетания и разбиения.

A1

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

Перестановки. Пусть задано конечное множество из , элементов, которые будем называть символами. Перестановкой на символах называется последовательностьсимволов, выписанных в определенном порядке. Таким образом, число перестановок насимволах, обозначаемое, это число способов введения линейного порядка на множестве из элементов. Вот 6 возможных упорядочиваний множества из 3 символов:

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

.

Здесь введена важнейшая для комбинаторного анализа функция ! (читается “эн-факториал”), определяемая для натуральныхкак произведение всех натуральных чисел от 1 довключительно и, по определению, равная 1 при=0:

При больших для оценки факториалов полезна асимптотическая формула Стирлинга

, .

(Символ “” означает, что отношение левой и правой частей формулы стремится к единице с ростом )

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

.

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

Сочетания. Пусть, наконец, из – элементного множества просто выбирается его– элементное подмножество без упорядочивания. Число– элементных подмножеств– элементного множества является весьма важным не только для комбинаторики, но и для всей математики. Оно обозначается через(читается, «це» изпо) и называется в комбинаторике числом сочетаний изпо. В других разделах математики по станущим понятными из дальнейшего причинам их обычно называют биномиальными коэффициентами. *

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

,

откуда получаем

.

* В научной литературе для используется также обозначение.

Запомним, что , еслиили. Заметим также, что, как сразу следует из формулы,и.

` Пусть имеется -элементное множество. Вот все его двухэлементные подмножества:, число которых в соответствии с формулой равно.

Проиллюстрируем введенные комбинаторные числа простейшими примерами.

Указать в спортивном тотализаторе 3 первые команды из 12 команд высшей лиги с указанием занятых ими мест можно способами.

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

Если футбольный матч закончился вничью и его судьба решается в серии послематчевых пенальти, то у тренера возможностей представить судье список 5 пенальтистов из 11 закончивших матч футболистов, т.к. порядок выполнения футболистами пенальти имеет значение.

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

Если тренер футбольной команды, желает одновременно заменить 3 из 10 полевых игроков, имея 5 футболистов на скамейке запасных, он может это сделать согласно правилу произведения

способами,

на первом этапе выбирая трех покидающих поле футболистов, а на втором – трех футболистов, выходящих на замену.

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

При его применении нужно лишь следить за тем, чтобы при ветвлении в каждой вершине происходило разбиение множества вариантов на непересекающиеся подмножества. Этим гарантируется, что окончательные варианты, получаемые на концах ветвей дерева, будут различными при движении по различным ветвям. Поясним это на примере. Пусть с помощью правила произведения хотят найти число двухэлементных подмножеств — элементного множества, считая, что на первом этапе формирования подмножества выбирается один элемент, а на втором – другой. Тогда на первом этапе выбор производится извозможностей, а на втором – из. Поэтому в соответствии с правилом произведения получилось бы, что число двухэлементных подмножеств равно(-1), что неверно, т.к. это число равно. Ошибка объясняется тем, что при таком порождении двухэлементных подмножеств каждое подмножество возникает дважды: при одном порядке включения входящих в него элементов и при другом. И здесь с помощью правила произведения на самом деле находится число упорядоченных двухэлементных выборок.

Мощность прямого произведения двух конечных множеств в соответствии с правилом произведения равна произведению их мощностей:

|AB| = |A||B|.

Последовательности символов. Множество двоичных последовательностей длины можно рассматривать как-ую декартову степень множества. Поэтому таких последовательностей. Их можно считать характеристическими векторами подмножеств-элементного множества. Следовательно, полное число подмножеств-элементного множества также равно.

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

Пусть теперь задано, что символ встречаетсяраз, символраз, т.д., символраз. Чему равно число последовательностей изсимволов с заданным числомвключения каждого символа?

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

.

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

Сочетания с повторениями. Пусть теперь имеется различных типов элементов, причем элементы одинакового типа считаются неразличимыми, а запас элементов каждого типа неограничен. Требуется составить-элементное множество, используятипов элементов, причем элементов каждого типа может включаться в множество любое число от 0 до. Число таких множеств называется числом сочетаний с повторениями изпои обозначается. Здесь возможен случай и .

Сочетание с повторениями называют также мультимножеством. Мультимножество на типах элементов может быть задано вектором кратностей типов:, где число элементов i-го типа в мультимножестве. Мощность мультимножества равна сумме кратностей типов: . В терминах мультимножества есть число мультимножеств мощности, построенных натипах элементов.

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

В качестве другого примера рассмотрим целочисленные неотрицательные решения уравнения

.

Связывая с каждой переменной тип элемента, а с её значением – число элементов данного типа, получаем, что число искомых решений равно .

Для того чтобы найти число , рассмотрим последовательности длиныиз двух символов «*» и «׀», у которых число звездочек равно , а число черточек –. С каждой такой последовательностью можно связать сочетание с повторениями, ставя в каждом изпромежутков между черточками вместо звездочек символы типа, соответствующего номеру промежутка. Этим устанавливается взаимно однозначное соответствие между-элементными множествами изтипов элементов и последовательностями из двух символов. Так в примере с розами покупке двух красных, одной желтой, ни одной оранжевой и двух белых роз соответствует последовательность. Поэтому

.

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

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

.

Число разбиений 4-элементного множества на два 2-элементных в соответствии с этой формулой равно . Вот все возможные разбиения множествана два 2-элементных подмножества:.

Вопросы для самопроверки.

  1. Сколькими способами может быть выбрано 5 номеров из 36?

а) ; б); в).

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

а) ; б); в).

  1. У мамы 5 яблок, 7 груш и 3 апельсина. Каждый день, в течение 15 дней, она выдает сыну по одному фрукту. Сколькими способами это может быть сделано? а) ; б); в).

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

а) ; б); в).

  1. Сколькими способами можно разделить яблоко, грушу, апельсин, сливу, лимон и айву между тремя мальчиками так, чтобы каждому досталось по 2 фрукта? а) ; б); в).

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

a) ; б); в).

studfiles.net

Основные формулы комбинаторики. Комбинаторика: формула перестановки, размещения

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

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

Комбинаторные конфигурации

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

  • размещение;
  • перестановка;
  • сочетание;
  • композиция числа;
  • разбиение числа.

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

Разделы

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

  • перечислительная;
  • структурная;
  • экстремальная;
  • теория Рамсея;
  • вероятностная;
  • топологическая;
  • инфинитарная.

В первом случае речь идет об исчисляющей комбинаторике, задачи рассматривают перечисление или подсчет разных конфигураций, которые образованы элементами множеств. На данные множества, как правило, накладываются какие-либо ограничения (различимость, неразличимость, возможность повтора и так далее). А количество этих конфигураций подсчитывается при помощи правила сложения или умножения, о которых мы поговорим немного позже. К структурной комбинаторике относятся теории графов и матроидов. Пример задачи экстремальной комбинаторики – какова наибольшая размерность графа, который удовлетворяет следующим свойствам… В четвертом пункте мы упомянули теорию Рамсея, которая изучает в случайных конфигурациях наличие регулярных структур. Вероятностная комбинаторика способна нам ответить на вопрос – какова вероятность того, что у заданного множества присутствует определенное свойство. Как нетрудно догадаться, топологическая комбинаторика применяет методы в топологии. И, наконец, седьмой пункт – инфинитарная комбинаторика изучает применение методов комбинаторики к бесконечным множествам.

Правило сложения

Среди формул комбинаторики можно найти и довольно простые, с которыми мы достаточно давно знакомы. Примером является правило суммы. Предположим, что нам даны два действия (С и Е), если они взаимоисключаемы, действие С выполнимо несколькими способами (например а), а действие Е выполнимо b-способами, то выполнить любое из них (С или Е) можно а+b способами.

В теории это понять достаточно трудно, постараемся донести всю суть на простом примере. Возьмем среднюю численность учеников одного класса — допустим, это двадцать пять. Среди них пятнадцать девочек и десять мальчиков. Ежедневно в классе назначается один дежурный. Сколько есть способов назначить дежурного по классу сегодня? Решение задачи достаточно простое, мы прибегнем к правилу сложения. В тексте задачи не сказано, что дежурными могут быть только мальчики или только девочки. Следовательно, им может оказаться любая из пятнадцати девочек или любой из десяти мальчиков. Применяя правило суммы, мы получаем достаточно простой пример, с которым без труда справится школьник начальных классов: 15 + 10. Подсчитав, получаем ответ: двадцать пять. То есть существует всего двадцать пять способов назначить на сегодня дежурного класса.

Правило умножения

К основным формулам комбинаторики относится и правило умножения. Начнем с теории. Допустим, нам необходимо выполнить несколько действий (а): первое действие выполняется с1 способами, второе – с2 способами, третье – с3 способами и так далее до последнего а-действия, выполняемого са способами. Тогда все эти действия (которых всего у нас а) могут быть выполнены N способами. Как высчитать неизвестную N? В этом нам поможет формула: N = с1 * с2 * с3 *…* са.

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

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

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

Начнем, если у нас нет шаров, то и вариантов расстановки у нас так же ноль. А если у нас шар один, то и расстановка тоже одна (математически это можно записать следующим образом: Р1 = 1). Два шара можно расставить двумя разными способами: 1,2 и 2,1. Следовательно, Р2 = 2. Три шара можно расставить уже шестью способами (Р3=6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. А если таких шаров не три, а десять или пятнадцать? Перечислять все возможные варианты очень долго, тогда нам на помощь приходит комбинаторика. Формула перестановки поможет нам найти ответ на интересующий нас вопрос. Pn = n *P (n-1). Если попытаться упростить формулу, то получаем: Pn = n* (n — 1) *…* 2 * 1. А это и есть произведение первых натуральных чисел. Такое число называется факториалом, а обозначается как n!

Рассмотрим задачу. Вожатый каждое утро выстраивает свой отряд в шеренгу (двадцать человек). В отряде есть три лучших друга – Костя, Саша и Леша. Какова вероятность того, что они будут стоять рядом? Чтобы найти ответ на вопрос, нужно вероятность «хорошего» исхода поделить на общее количество исходов. Общее число перестановок составляет 20! = 2,5 квинтиллиона. Как посчитать количество «хороших» исходов? Предположим, что Костя, Саши и Леша – это один сверхчеловек. Тогда мы имеем всего восемнадцать субъектов. Число перестановок в данном случае равняется 18 = 6,5 квадриллионов. При всем этом, Костя, Саша и Леша могут произвольно перемещаться между собой в своей неделимой тройке, а это еще 3! = 6 вариантов. Значит всего «хороших» расстановок у нас 18! * 3! Нам остается только найти искомую вероятность: (18! * 3!) / 20! Что равняется примерно 0,016. Если перевести в проценты, то это получается всего 1,6%.

Размещение

Сейчас мы рассмотрим еще одну очень важную и необходимую формулу комбинаторики. Размещение – это наш следующий вопрос, который предлагаем вам рассмотреть в данном разделе статьи. Мы идем на усложнение. Предположим, что мы хотим рассмотреть возможные перестановки, только не из всего множества (n), а из меньшего (m). То есть мы рассматриваем перестановки из n предметов по m.

Основные формулы комбинаторики стоит не просто заучивать, а понимать их. Даже несмотря на то, что они усложняются, так как у нас не один параметр, а два. Предположим, что m = 1, то и А = 1, m = 2, то А = n * (n — 1). Если далее упрощать формулу и перейти на запись при помощи факториалов, то получится вполне лаконичная формула: А = n! / (n — m)!

Сочетание

Мы рассмотрели практически все основные формулы комбинаторики с примерами. Теперь перейдем к заключительному этапу рассмотрения базового курса комбинаторики – знакомство с сочетанием. Сейчас мы будем выбирать m предметов из имеющихся у нас n, при этом всем мы будем выбирать всеми возможными способами. Чем же тогда это отличается от размещения? Мы не будем учитывать порядок. Этот неупорядоченный набор и будет являться сочетанием.

Сразу введем обозначение: С. Берем размещения m шариков из n. Мы перестаем обращать внимание на порядок и получаем повторяющиеся сочетания. Чтобы получить число сочетаний нам надо поделить число размещений на m! (m факториал). То есть С = А / m! Таким образом, способов выбрать из n шаров немножко, равняется примерно столько, сколько выбрать почти все. Этому есть логическое выражение: выбрать немножко все равно, что выкинуть почти все. Еще в данном пункте важно упомянуть и то, что максимальное число сочетаний можно достигнуть при попытке выбрать половину предметов.

Как выбрать формулу для решения задачи?

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

  1. Задайте себе вопрос: порядок размещения элементов учитывается в тексте задачи?
  2. Если ответ нет, то воспользуйтесь формулой сочетания (С = n! / (m! * (n — m)!)).
  3. Если ответ нет, то необходимо ответить на еще один вопрос: все ли элементы входят в комбинацию?
  4. Если ответ да, то воспользуйтесь формулой перестановки (Р = n!).
  5. Если ответ нет, то воспользуйтесь формулой размещения (А = n! / (n — m)!).

Пример

Мы рассмотрели элементы комбинаторики, формулы и некоторые другие вопросы. Теперь перейдем к рассмотрению реальной задачи. Представьте, что перед вами лежат киви, апельсин и банан.

Вопрос первый: сколькими способами их можно переставить? Для этого воспользуемся формулой перестановок: Р = 3! = 6 способов.

Вопрос второй: сколькими способами можно выбрать один фрукт? Это очевидно, у нас всего три варианта – выбрать киви, апельсин или банан, но применим формулу сочетаний: С = 3! / (2! * 1!) = 3.

Вопрос третий: сколькими способами можно выбрать два фрукта? Какие есть у нас вообще варианты? Киви и апельсин; киви и банан; апельсин и банан. То есть три варианта, но это легко проверить при помощи формулы сочетания: С = 3! / (1! * 2!) = 3

Вопрос четвертый: сколькими способами можно выбрать три фрукта? Как видно, выбрать три фрукта можно одним-единственным способом: взять киви, апельсин и банан. С = 3! / (0! * 3!) = 1.

Вопрос пятый: сколькими способами можно выбрать хотя бы один фрукт? Это условие подразумевает, что мы можем взять один, два или все три фрукта. Следовательно, мы складываем С1 + С2 + С3 =3 + 3 + 1 = 7. То есть у нас есть семь способов взять со стола хотя бы один фрукт.

fb.ru

Author: alexxlab

Добавить комментарий

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