Формулы комбинаторики все: Основные формулы комбинаторики, с примерами

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   

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

   

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

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

   

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

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

   

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

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

   

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

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

   

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

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

Как видим, в сочетаниях в отличие от размещений не учитывается порядок элементов. Число всех сочетаний из элементов по элементов в каждом обозначается (от начальной буквы французского слова “combinasion”, что значит “сочетание”). 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. девочек и мальчиков рассаживаются произвольным образом в ряду из мест. Сколькими способами можно их рассадить так, чтобы все девочки сидели рядом?

Подготовка школьников к ЕГЭ и ОГЭ (Справочник по математике — Алгебра

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

Размещения

      Рассмотрим следующую задачу.

      Задача.   9   карточек пронумерованы числами   1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 .   Из этих карточек четыре наугад взятых карточки выкладываем в ряд. Сколько при этом можно получить различных четырехзначных чисел?

      Решение.Сначала слева направо пронумеруем места в ряду, куда выкладываем карточки: первое место, второе, третье, четвертое.

      На первое место можно положить одну из   9   карточек. Для этого есть   9   способов. В каждом из этих   9   способов на второе место можно положить одну из оставшихся   8   карточек. Таким образом, существует

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

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

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

      Ответ:   3024.

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

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

      Если обозначить символом  число размещений из   n   элементов по   k   элементов, то будет справедлива формула:

(1)

      В соответствии с определением факториала, формулу (1) можно также записать в виде:

      В задаче множеством из   n   элементов является исходный набор из   9   пронумерованных карточек, а упорядоченным подмножеством из   k   элементов –   4   карточки, выложенные в ряд.

      Таким образом, при решении задачи мы на частном примере подсчитали, чему равно число размещений из   9   элементов по   4   элемента, т.е. число

      В соответствии с формулой (1),

что и было получено в задаче.

      Замечание 1.  Введенные в данном разделе размещения также называют размещениями без повторений.

      Замечание 2. Из формул для числа перестановок и числа размещений вытекает формула

смысл которой заключается в следующем.

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

Сочетания

      Определение 2. Рассмотрим множество, состоящее из   n   элементов. Каждое его подмножество, содержащее   k   элементов, называют сочетанием из   n   элементов по   k   элементов.

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

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

      Таким образом, справедлива формула:

      Следовательно,

откуда вытекает формула

(2)

      Теперь рассмотрим несколько примеров подсчета числа сочетаний, которые непосредственно вытекают из формулы (2):

      В заключение приведем часто используемое равенство, также непосредственно вытекающее из формулы (2):

      Замечание 4. С разделом справочника «Сочетания» близко связан раздел «Бином Ньютона», где приведены и доказаны свойства чисел сочетаний.

   С понятиями факториала числа   n   и перестановок из   n   элементов можно познакомиться в разделе «Комбинаторика: факториалы и перестановки» нашего справочника.

 

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

Решение задач с использованием формул комбинаторики

 Способ 1      Каждый из 15 -и  человек пожал руки 14-и . Однако произведение 15 * 14 =210 дает удвоенное число рукопожатий (так как в этом расчете учтено, что первый пожал руку второму, а затем второй первому, на самом же деле было одно рукопожатие). Итак, число рукопожатий равно: (15 * 14) : 2 =105. 

Способ 2     Первый ученик пожал руки 14-и, второй – 13-и (плюс рукопожатие с первым, которое уже учтено), третий – 12-и и т.д.  14-й ограничился одним рукопожатием, а на долю 15-го  выпала пассивная роль – принимать приветствия. Таким образом, общее число рукопожатий выражается суммой:  N = 14 + 13 + 12 + … + 3 + 2 + 1 или    N = 1 + 2 + 3 + … + 12 + 13 + 14.     мы с вами столкнулись с комбинаторной задачей.      

тема урока:   Решение задач с использованием формул комбинаторики  (перестановки, размещения, сочетания).  

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

ЭПИГРАФ УРОКА:  «Путь в тысячу ли начинается с первого шага. Нужно найти силы сделать   первый шаг, и дорога появиться сама собой».                                                                                 Лао Цзы   

Деление на группы  Дифференциация по классификации (группы учеников с похожими интересами)    Класс делится на 5 групп:    На столе  № 1 будут разноуровневые задания с перестановками      на  столе  №2   разноуровневые задания с размещениями   на столе  № 3 –  разноуровневые задания с сочетаниями  Учащиеся по желанию выбирают стол, за которым будут работать.      Учитель назначает спикера в каждой группе и группу  Каждая группа выбирает: редактора (который будет оформлять графический органайзер), помощника спикера (который выполняет основную вычислительную работу),  также тайм-менеджера (который следит за временем).     На столах лежат   маршрутные листы и конверты с заданиями.    

 Устная работа:   Презентация   Слайд  5-10  

1.  Найти значение выражения:    4!  

2 Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5:   120 + 

3. Сколькими способами могут разместиться 6 человек в салоне автобуса на 6  свободных местах:  720 + 

4. Сколькими способами могут разместиться 3 человека в четырехместном купе на свободных местах:  24 +    

5. Найти значение выражения:    4!- 2!

«где отсутствует точное знание, там действуют догадки, а из десяти догадок девять – ошибки».   М. Горький 

РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ комбинаторных задач (слайды11-13)

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

Правило суммы: если элемент А можно выбрать п способами, а элемент В можно выбрать m способами, то выбрать либо А, либо В можно (п + m) способами.  

Правило произведения (умножения): если элемент А можно выбрать п способами, а элемент В можно выбрать m способами, то два элемента (пару) А и В можно выбрать п · m способами. 

Типы соединений:  Перестановками из п разных элементов называют соединения,   где число объектов остается неизменными, меняется только их порядок( расположение этих элементов в определенном порядке),  а   их число равно:  Pn=n!     

Размещения:  Если из n различных объектов будем выбирать по  m объектов и переставлять всеми возможными способами между собой, то есть меняется и состав выбранных объектов, и их порядок (в определенном порядке). Получившиеся комбинации называются размещениями из n объектов по m(m не больше  п), а их число равно (читается «А из п по m») т.е.  равно произведению к последовательных натуральных чисел, наибольшим из которых является п.  

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

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

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

1 группе необходимо   решить 3 задачи на размещение. 

2 группе – 3 задачи на перестановку. 

3 группе – 3 задачи на сочетания.  Подготовьте графический органайзер ( постер) по предложенным заданиям.   По истечению 10  минут спикер от каждой группы защищает  задание  у доски.

Дескриптор

балл

Распознает тип комбинации

1

Знает и вычисляет по формуле

1

Решает задачи, требующие  распознавания и дополнительных преобразований.

1

записывает ответ

1

Метод: «Две звезды — одно желание».   Учащиеся изучают графические органайзеры других групп и оценивают их. Отмечают два положительных момента и одно пожелание. 

Обратная связь: взаимооценивание, учитель.  Учитель поддерживает, выделяет ответы и интересные вопросы некоторых учащихся.     Вывод: Ученики делают вывод о возможностях применять формул при решении практических задач. Ясно, что сочетаний всегда меньше чем размещений (так как при размещениях порядок важен, а для сочетаний — нет), причем именно в m!  раз, то есть получилась такая изящная формула, объединяющая три   формулы комбинаторики (три концепции: размещений, сочетаний и перестановок)  

 Самостоятельная работа   Учащимся предлагается выполнить работу индивидуально, которая предполагает анализ предложенных заданий и   определение типа и формулы(тестирование по BILIM LAND)   Обратная связь:   Где были допущены ошибки? Что было трудным?   Учитель проводит коррекцию.     

 

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

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

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

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

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

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

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

Разделы

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

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

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

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

Среди формул комбинаторики можно найти и довольно простые, с которыми мы достаточно давно знакомы. Примером является правило суммы. Предположим, что нам даны два действия (С и Е), если они взаимоисключаемы, действие С выполнимо несколькими способами (например а), а действие Е выполнимо 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. То есть у нас есть семь способов взять со стола хотя бы один фрукт.

Важнейшие формулы комбинаторики / Теория вероятности [Калинин В.М., Тихомиров С.Р.] / 3dstroyproekt.ru

Рассмотрим пару множеств $ { \rm A } =\left\{ { a_1 ,a_2 \ldots a_n }\right\} , { \rm B } =\left\{ { b_1 ,b_2 \ldots b_m }\right\} $ размерности $n\left({\rm A }\right)=n$ и $n\left({\rm B }\right)=m$

Следуя терминологии, принятой в Т. 6=531441. $

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

Решение. Генеральная совокупность — количество букв, содержащихся в слове математика — ее объем $n(A)=10$. Из условия задачи ясно, что при составлении разных буквосочетаний объем генеральной совокупности не меняется. Здесь — 1 буква «е», 2 буквы «м», 3 буквы «а», 2 буквы «т», 1 буква «и», 1 буква «к». Среди выбираемых элементов есть одинаковые { выборка с возвращением } , чтобы получить разные буквосочетания, важен порядок расположения букв, поэтому количество таких буквосочетаний равно числу перестановок с повторениями из 9-и букв { формула 6 } .

$ P_ { 9,k_1 \ldots k_m } =\frac { n! } { k_1 !\ldots k_m ! } = P_ { 9,1,2,3,2,1,1 } =\frac { 9! } { 1!\cdot 2!\cdot 3!\cdot 2!\cdot 1!\cdot 1! } =15120. $

Задача 6. В кафе имеются торты четырех разных сортов: «Анастасия», «Тайна», «Астория» и «Фантазия». Сколькими способами можно купить 8 тортов?

Решение. 8 =\frac { ( { 4+8-1 } )\,! } { 8\,!( { 4-1 } )\,! } =\frac { 11! } { 8\,!\cdot 3\,! } =165 $

Задача 7. Из Москвы до Новосибирска можно добраться поездом и самолетом. Из Новосибирска в Томск — поездом, самолетом, автобусом, пароходом. Сколькими способами можно осуществить путешествие по маршруту Москва — Новосибирск — Томск?

Решение. Пусть первую генеральную совокупность образуют поезд и самолет, которыми можно добраться из Москвы до Новосибирска, ее объем $n(A)=2$. Вторую генеральную совокупность образуют поезд, самолет, автобус и пароход, которыми можно добраться из Новосибирска в Томск, ее объем $n { B } =4$. Очевидно, что путешествие по маршруту Москва — Новосибирск — Томск обязательно должно производится двумя видами транспорта, причем по одному из каждой генеральной совокупности. Следовательно, число способов будет равно числу комбинаций, образованных двумя элементами, взятыми по одному из каждой генеральной совокупности { формула 4 } .

$ { \rm N } =n_A \cdot n_B $

$ { \rm N } =2\cdot 4=8 $

Сочетание без повторений | matematicus.

7$

 

Итак, получаем число способов составления суточного наряда

Комбинаторика в Excel

Комбинаторика в Excel

Комбинаторика — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения элементов) и отношения на них. Термин комбинаторика был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». Excel поддерживает ряд функций комбинаторики. Чтобы разобраться, какую формулу использовать, следует ответить на ряд вопросов:

  1. Исходное множество содержит только уникальные элементы, или некоторые из них могут повторяться?
  2. Операция выполняется со всеми элементами множества, или только с некоторой выборкой из них?
  3. Важен ли порядок элементов в выборке?
  4. После выбора элемента мы его возвращаем назад?

Рис. 1. Дерево решений, какую формулу комбинаторики использовать

Скачать заметку в формате Word или pdf, примеры в формате Excel

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

Возьмем несколько различных элементов (предметов) и будем переставлять их всевозможными способами, оставляя неизменным их число и меняя только их порядок (рис. 2). Каждая из получившихся таким образом комбинаций носит название перестановки. Перестановкой из n элементов называется упорядоченное множество, составленное из всех элементов множества.

Рис. 2. Перестановки (картинка взята здесь)

Если все n элементы разные, то число перестановок обозначается Pn от perturbation.

С другой стороны, произведение n первых натуральных чисел называется n-факториал и обозначается n!

Например

По определению: 1! = 1; 0! = 1.

Функция в Excel =ФАКТР(n). Факториал растет очень быстро. Существенно быстрее экспоненты (рис. 3).

Рис. 3. Расчет числа перестановок без повторений с помощью факториала

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

Если в основном n множестве не все элементы разные, то число перестановок будет меньше n! Например, если наше множество состоит из трех яблок и одной груши, то всего возможно 4 перестановки (рис. 4). Груша может быть первой, второй, третьей или четвертой, а яблоки неразличимы).

Рис. 4. Перестановки с повторениями (картинка найдена здесь)

В общем случае, можно сказать: последовательность длины n, составленная из k разных символов, первый из которых повторяется n1 раз, второй – n2 раз, третий – n3 раз, …, k-й – nk раз (где n1 + n2 + … + nk = n) называется перестановкой с повторениями из n элементов.

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

Решение. Буквы а и н повторяются 2 раза, а буква м один раз.

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

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

Например, два элемента из трех можно выбрать и расположить шестью способами (рис. 4):

Рис. 5. Размещение без повторений (картинка из презентации)

Если m = n количество элементов совпадает с количеством имеющихся мест для размещения. Знаменатель в формуле (4) превращается в 0! = 1. Остается только числитель n! А это – изученная выше перестановка без повторений; см. формулу (1).

Название функции в Excel несколько обескураживает. Но… что поделаешь: =ПЕРЕСТ(n;m)

Рис. 6. Размещение без повторений; обратите внимание на смешанные ссылки, которые позволяют протянуть формулу на всю таблицу

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

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

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

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

В общем случае размещение с повторениями или выборка с возвращением – это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз. По правилу умножения количество размещений с повторениями из n по k:

В Excel используется функция ПЕРЕСТА(n;k).

Задача. Сколько различных номеров можно составить в одном коде региона?

Подсказка. В номере используется 12 букв алфавита, также существующих и в латинском алфавите (А, В, Е, К, М, Н, О, Р, С, Т, У, Х).

Рис. 8. Номер автомобиля

Решение. Можно воспользоваться формулой для размещения с повторениями:

Каждую цифру можно выбрать 10 способами, а всего цифр 3, при этом они могут повторяться, и их порядок важен. Каждую букву можно выбрать 12 способами, при этом буквы могут повторяться, и их порядок важен.

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

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

Например, два элемента из 4 сочетаются 6 способами (порядок следования не важен):

Рис. 9. Сочетания без повторений из 4 по 2

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

где n – номер строки, m – номер элемента в строке, начиная с нулевого. Например, в строке 7:

Рис. 10. Треугольник Паскаля; чтобы увеличить изображение кликните на нем правой кнопкой мыши и выберите Открыть картинку в новой вкладке

В Excel используется функция =ЧИСЛКОМБ(n;m).

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

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

Например, два предмета из четырех можно выбрать 10 способами, если после каждого выбора предмет возвращается назад (рис. 11).

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

В общем случае, число сочетаний с повторениями:

Для нашего примера с фруктами

В Excel для подсчета числа сочетаний с повторениями используется функция =ЧИСЛКОМБА(n;m). В нашем примере =ЧИСЛКОМБА(4;2) = 10.

Мир математики — Mathigon

Введение

Леонард Эйлер (1707 — 1783)

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

Первые комбинаторные задачи изучались математиками Древней Индии, Арабской и Греции. Интерес к этому предмету увеличился в течение 19 и 20 веков вместе с развитием теории графов и таких проблем, как теорема о четырех цветах.Среди ведущих математиков — Блез Паскаль (1623–1662), Якоб Бернулли (1654–1705) и Леонард Эйлер (1707–1783).

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

Факториалы

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

В классе находится В.CombA1 учеников и стульев V.CombA1 , стоящих в ряд. В скольких различных порядках ученики могут сидеть на этих стульях?

Перечислим возможности — в этом примере V.CombA1 разных зрачков представлены V.CombA1 разных цветов стульев.

Существует {2: 2, 3: 6, 4: 24, 5: 120} [V.CombA1] различных возможных порядков. Обратите внимание, что количество возможных порядков очень быстро увеличивается по мере увеличения количества учеников. У 6 учеников есть 720 различных возможностей, и перечислять их все становится непрактично. Вместо этого нам нужна простая формула, которая говорит нам, сколько имеется заказов на n человек, чтобы сесть на n стульев. Тогда мы можем просто заменить 3, 4 или любое другое число на на , чтобы получить правильный ответ.

Предположим, у нас есть стулья V.CombB1 , и мы хотим разместить V.CombB1 == 1? ‘Один ученик’: V.CombB1 == 2? ‘Два ученика’: V.CombB1 == 3? ‘Три ученика ‘: V.CombB1 == 4? ‘Четыре ученика’: V.CombB1 == 5? ‘Пять учеников’: V.CombB1 == 6? ‘Шесть учеников’: ‘семь учеников’ на них.

{7: «Семь учеников могут сесть на первый стул. Затем есть 6 учеников, которые могли бы сесть на второй стул. Есть 5 вариантов для третьего стула, 4 варианта для четвертого стула, 3 варианта для пятого стула, 2 варианта для шестого стула и только один вариант для последнего стула. ‘,
6: «Есть 6 учеников, которые могли бы сесть на первый стул. Затем есть 5 учеников, которые могли бы сесть на второй стул.Есть 4 варианта для третьего стула, 3 варианта для четвертого стула, 2 варианта для пятого стула и только один вариант для последнего стула. ‘,
5: «Пятеро учеников могли бы сесть на первый стул. Затем есть 4 ученика, которые могут сесть на второй стул. Есть 3 варианта для третьего стула, 2 варианта для четвертого стула и только один вариант для последнего стула. ‘,
4: «Есть 4 ученика, которые могли бы сесть на первый стул. Затем есть 3 ученика, которые могут сесть на второй стул.Есть 2 варианта для третьего стула и только один вариант для последнего стула. ‘,
3: «Есть 3 ученика, которые могут сесть на первый стул. Затем есть 2 ученика, которые могут сесть на второй стул. Наконец, остался только один ученик, чтобы сесть на третий стул. ‘,
2: «Есть 2 ученика, которые могут сесть на первый стул. Далее остается только один ученик, который может сесть на второй стул. ‘,
1: ‘Это только один вариант для одиночного стула. ‘} [V.CombB1]

Всего

возможности.Чтобы упростить обозначения, математики используют знак «!» называется факториалом. Например, 5! («Пять факториалов») то же самое, что 5 × 4 × 3 × 2 × 1. Выше мы только что показали, что существует n ! возможности заказать н объектов.

Насколько разными способами 23 ребенка могут сесть на 23 стула в классе математики? Если у вас 4 урока в неделю, а в году 52 недели, сколько лет нужно, чтобы изучить все возможности? Примечание: возраст Вселенной составляет около 14 миллиардов лет.

Для 23 детей, чтобы сесть на 23 стула, их 23! = 25 852 016 738 884 800 000 000 возможностей (это число слишком велико для отображения на экране калькулятора). Испытание всех возможностей займет

23! 4 × 52 = 124 288 542 000 000 000 000 лет.

Это почти в 10 миллионов раз больше нынешнего возраста Вселенной!

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

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

Сколько различных возможностей существует для любого Math.min (V.CombC1, V.CombC2) из V.CombC1 учеников, чтобы сесть на Math.min (V.CombC1, V.CombC2) стулья? Обратите внимание, что Math.max (0, V.CombC1-V.CombC2) останется включенным, и мы не должны включать его при перечислении возможностей.

Давайте начнем снова, перечислив все возможности:

Комбинации

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

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

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

, итого их 10. Если бы мы вычислили 5 P 3 = 60, мы бы дважды подсчитали некоторые возможности, как показано в следующей таблице:

При перестановках мы считаем каждую комбинацию из трех футболок 6 раз, потому что их 3! = 6 способов заказать три футболки.Чтобы получить количество комбинаций из количества перестановок, нам просто нужно разделить на 6. Мы пишем

5 C 3 = 5 P 33! = 606 = 10.

Здесь C означает «комбинацию c ». В общем, если мы хотим выбрать r объектов из общего числа n , будет

n C r = n P r r ! = n ! р ! ( n r )!

различных комбинаций.Вместо n C r математики часто пишут n C r = ( n r ), как дробь в скобках, но без промежуточной линии. (Для упрощения набора мы продолжим использовать первую строчную нотацию.)

(a) В вашем классе 10 детей, но вы можете пригласить только пятерых на свой день рождения. Сколько разных комбинаций друзей вы могли бы пригласить? Объясните, следует ли использовать комбинации или перестановки.

(б) На вечеринке 75 человек. Каждый раз всем пожимает руку. Как часто в целом рукопожатие? Подсказка: сколько людей участвует в рукопожатии?

(a) Количество комбинаций друзей, которых вы можете пригласить, составляет 10 C 5 = 252. Мы использовали комбинации, потому что не имеет значения, в каком порядке мы приглашаем друзей, на какие мы приглашаем.

(b) Вы хотите найти количество всех возможных пар гостей вечеринки.Это просто 75 C 2 = 2775. (Это много рукопожатий!)

Комбинаторика и треугольник Паскаля

Рассчитаем несколько значений n C r . Начнем с 0 C 0. Затем находим 1 C 0 и 1 C 1. Затем 2 C 0, 2 C 1 и 2 C 2. Затем 3 C 0 , 3 C 1, 3 C 2 и 3 C 3. Все эти результаты можно записать в таблицу:

0 С 0 = 1
1 С 0 = 1 1 С 1 = 1
2 С 0 = 1 2 С 1 = 2 2 С 2 = 1
3 С 0 = 1 3 С 1 = 3 3 С 2 = 3 3 С 3 = 1
4 С 0 = 1 4 С 1 = 4 4 С 2 = 6 4 С 3 = 4 4 С 4 = 1
5 С 0 = 1 5 С 1 = 5 5 С 2 = 10 5 С 3 = 10 5 С 4 = 5 5 С 5 = 1

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

Теперь мы также знаем, что r -е число в n -й строке также задается n C r (но мы всегда должны начинать отсчет с 0, поэтому первая строка или столбец фактически нулевой ряд). Если мы применим то, что мы знаем о создании треугольника Паскаля, к нашим комбинациям, мы получим

( n r )
+
( n r + 1)
знак равно
( n + 1 r + 1)

.

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

Мы хотим выбрать r + 1 объектов из набора n + 1 объектов. Это в точности то же самое, что пометить один объект из n + 1 , который будет называться X, и либо выбрать X плюс r других (из оставшихся n), либо не выбрать X и r + 1 других ( от оставшихся n).

У многих задач комбинаторики есть простое решение, если вы подумаете о нем правильно, и очень сложное решение, если вы просто попытаетесь использовать алгебру…

Звезды и полосы

Решение

Пример

Зеленщик на рынке хранит большое количество из различных видов фруктов. Какими способами мы можем сделать сумку из или фруктов? Обратите внимание, что r может быть меньше, равно или больше n .

Обратите внимание, что с r n существует n C r способов выбрать по одному фрукту каждого вида. Однако мы также можем съесть более одного фрукта каждого вида, например, два яблока, одну клубнику и один банан.

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

★★★ | ★★ | | ★★ |
3 типа 1 2 типа 2 0 типа 3 2 типа 4 1 типа 5

Всего имеется r звезд (представляющих r фруктов, которые нам разрешено брать) и n — 1 столбик (деление на разных фруктов).Это составляет r + n — всего 1 место. Любой заказ r звездочек и n — 1 батончик соответствует ровно одному действительному выбору фруктов.

Теперь мы можем применить наши комбинаторные инструменты: имеется r + n — 1 разрядов, и мы хотим выбрать n — 1 из них в качестве столбцов (все остальные — звездочки). Что есть ровно ( r + n — 1) C ( n — 1) возможностей для этого!

Предположим, есть пять видов фруктов, и мы хотим взять десять штук.Исходя из того, что мы подсчитали выше, всего

(10 + 5-1) C (5-1) = 14 C 4 = 24 024

возможности. Подумайте об этом в следующий раз, когда пойдете за покупками!

Комбинаторика и вероятность

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

P ( X ) = вероятность того, что произойдет X = количество исходов, при которых случится X , общее количество возможных исходов

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

Четверо детей, которых зовут A, B, C и D, случайным образом сидят на четырех стульях. Какова вероятность того, что А сядет на первый стул?

Мы уже показали, что всего существует 24 способа сесть на четыре стула. Если вы посмотрите на наше решение, вы также обнаружите, что А сидит на первом стуле в шести случаях. Следовательно,

P (A сидит на первом стуле) = количество результатов, где A сидит на первом стуле, общее количество возможных результатов = 624 = 14.

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

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

(b) В лотерее нужно угадать 6 номеров из 49.Какова вероятность того, что вы все сделаете правильно? Если каждую неделю отправлять 100 догадок, сколько времени в среднем вам понадобится, чтобы выиграть?

(a) Всего 4! = 24 способа случайного распределения букв и только один способ получить их все правильно. Таким образом, вероятность того, что каждое письмо будет доставлено в нужный дом, составляет 1/24 = 0,0417 = 4,17%.

Определить вероятность того, что каждое письмо будет доставлено не в тот дом, немного сложнее.Это не просто 1 — 0,0417, так как во многих случаях один или два, но не , все домов получают правильную букву. В этом простом случае самым простым решением было бы записать все 24 варианта. Вы обнаружите, что в 9 из 24 случаев каждый дом получает неправильную букву, что дает вероятность 0,375 = 37,5%. Если домов слишком много, чтобы записать все возможности, вы можете использовать идею под названием «Принцип включения-исключения» .

(b) Существует 49 C 6 = 13 983 816 возможных результатов лотереи, поэтому вероятность получения правильного решения составляет 1/49 C 6 = 0.000000072.

В среднем также потребуется 13 983 816 попыток, чтобы выиграть. Если мы отправляем 100 предположений каждую неделю, это соответствует 139 838 неделям, что равняется 2689 годам. Урок, который нужно усвоить: не играйте в лото!

перестановок и комбинаций | Описание, примеры и формула

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

Подробнее по этой теме

комбинаторика: биномиальные коэффициенты

… n объектов называется перестановкой n вещей, взятых по r за раз.Количество перестановок …

Концепции и различия между перестановками и комбинациями могут быть проиллюстрированы путем изучения всех различных способов, которыми пара объектов может быть выбрана из пяти различимых объектов, таких как буквы A, B, C, D и E. учитываются как выбранные буквы, так и порядок выбора, тогда возможны следующие 20 результатов:

Каждый из этих 20 различных возможных вариантов выбора называется перестановкой.В частности, они называются перестановками пяти объектов, взятых по два за раз, и количество таких возможных перестановок обозначается символом 5 P 2 , читается как «5 перестановок 2». В общем, если имеется n объектов, доступных для выбора, и перестановки ( P ) должны быть сформированы с использованием k объектов одновременно, количество различных возможных перестановок обозначается символом n P k .Формула для его оценки: n P k = n ! / ( n k )! Выражение n ! — читать « n факториал» — означает, что все последовательные положительные целые числа от 1 до n включительно должны быть умножены вместе, и 0! определяется равным 1. Например, используя эту формулу, количество перестановок пяти объектов, взятых по два за раз, равно

(для k = n , n P k = n ! Таким образом, для 5 объектов имеется 5! = 120 расположений.)

Получите подписку Britannica Premium и получите доступ к эксклюзивному контенту.
Подпишитесь сейчас

Для комбинаций k объектов выбираются из набора из n объектов для создания подмножеств без упорядочивания. В отличие от предыдущего примера перестановки с соответствующей комбинацией, подмножества AB и BA больше не являются отдельными выборками; за счет исключения таких случаев остается только 10 различных возможных подмножеств — AB, AC, AD, AE, BC, BD, BE, CD, CE и DE.

Количество таких подмножеств обозначено как n C k , читать « n выбрать k .”Для комбинаций, начиная с k объектов имеют k ! аранжировки, есть к ! неразличимые перестановки для каждого выбора k объектов; следовательно, делим формулу перестановки на k ! дает следующую формулу комбинации:

Это то же самое, что и биномиальный коэффициент ( n , k ) ( см. биномиальную теорему ; эти комбинации иногда называют k -подмножествами). Например, количество комбинаций пяти объектов, взятых по два за раз, равно

Вызываются формулы для n P k и n C k . формулы подсчета, поскольку они могут использоваться для подсчета количества возможных перестановок или комбинаций в данной ситуации без необходимости перечислять их все.

Определение, формула и практический пример

Что такое комбинация?

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

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

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

Формула для комбинирования

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

Где:

  • n — общее количество элементов в наборе
  • k — количество выбранных объектов (порядок объектов не важен)
  • ! — факториал

Факториал (обозначенный как «!») — это произведение всех положительных целых чисел, меньших или равных числу, предшествующему знаку факториала.Например, 3! = 1 x 2 x 3 = 6.

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

Пример комбинации

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

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

Принятие инвестиционного решения является примером проблемы объединения. Поскольку вы собираетесь разработать портфель, в котором все акции будут иметь равный вес, порядок выбранных акций не влияет на портфель. Например, портфели ABC и CBA будут равны друг другу из-за схожего веса (по 33,3% каждый) каждой акции.

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

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

Дополнительные ресурсы

CFI предлагает аналитика по финансовому моделированию и оценке (FMVA) ™ Стать сертифицированным аналитиком финансового моделирования и оценки (FMVA) ® Сертификат CFI по анализу финансового моделирования и оценки (FMVA) ® поможет вам обрести уверенность в себе. необходимость в вашей финансовой карьере. Запишитесь сегодня! программа сертификации для тех, кто хочет вывести свою карьеру на новый уровень. Чтобы продолжить обучение и продвигаться по карьерной лестнице, вам будут полезны следующие ресурсы CFI:

  • Инвестирование: руководство для начинающих Инвестирование: руководство для начинающих Руководство CFI по инвестициям для начинающих научит вас основам инвестирования и научит их начинать.Узнайте о различных стратегиях и методах торговли, а также о различных финансовых рынках, на которые вы можете инвестировать.
  • Маржинальная торговля Маржинальная торговля Маржинальная торговля — это заимствование средств у брокера с целью инвестирования в финансовые ценные бумаги. Приобретенные акции служат залогом по ссуде. Основная причина заимствования денег — получение большего капитала для инвестирования
  • Начальная цена Страйк-цена Страйк-цена — это цена, по которой держатель опциона может реализовать опцион на покупку или продажу базовой ценной бумаги, в зависимости от
  • Типы рынков — Дилеры, брокеры, биржи Типы рынков — дилеры, брокеры, биржи Рынки включают брокеров, дилеров и биржи.Каждый рынок работает с разными торговыми механизмами, которые влияют на ликвидность и контроль. Различные типы рынков допускают разные торговые характеристики, описанные в этом руководстве.

Функция COMBIN — служба поддержки Office

В этой статье описаны синтаксис формулы и использование функции КОМБИНАТ в Microsoft Excel.

Описание

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

Синтаксис

COMBIN (число; число_выбранных)

Аргументы функции ЧАСТИЧНОЕ ЧИСЛО имеют следующие аргументы:

Замечания

  • Числовые аргументы усекаются до целых чисел.

  • Если какой-либо из аргументов не является числовым, КОМБИН возвращает # ЗНАЧ! значение ошибки.

  • Если number <0, number_chosen <0 или number

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

  • Количество комбинаций следующее, где number = n и number_chosen = k:

    где:

Пример

Скопируйте данные примера из следующей таблицы и вставьте их в ячейку A1 нового листа Excel.Чтобы формулы отображали результаты, выберите их, нажмите F2, а затем нажмите Enter. При необходимости вы можете настроить ширину столбца, чтобы увидеть все данные.

Формула

Описание

Результат

= COMBIN (8,2)

Возможны команды из двух человек, которые могут быть сформированы из 8 кандидатов.

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

Ваш адрес email не будет опубликован.