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

Содержание

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

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

Как выбрать формулу комбинаторики?

Мы подготовили для вас наглядную схему с примерами решений по каждой формуле комбинаторики:

  • алгоритм выбора формулы (сочетания, перестановки, размещения с повторениями и без),
  • рекомендации по изучению комбинаторики,
  • 6 задач с решениями и комментариями на каждую формулу.

Нужна помощь в решении задач по комбинаторике?

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

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

$$P_n=n!=1\cdot 2\cdot 3 \cdot … \cdot (n-1) \cdot n$$

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

Пример всех перестановок из $n=3$ объектов (различных фигур) — на картинке справа. Согласно формуле, их должно быть ровно $P_3=3!=1\cdot 2\cdot 3 =6$, так и получается.

С ростом числа объектов количество перестановок очень быстро растет и изображать их наглядно становится затруднительно. Например, число перестановок из 10 предметов — уже 3628800 (больше 3 миллионов!).

Еще: онлайн калькулятор перестановок.

Размещения

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

$$A_n^m=\frac{n!}{(n-m)!}=n\cdot (n-1)\cdot .m \cdot P_m.$$

Удобный и бесплатный онлайн калькулятор сочетаний.

Решебник задач по комбинаторике

Изучаем комбинаторику: полезные ссылки

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

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

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

 

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

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

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

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

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

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

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

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

Вы искали все формулы комбинаторики? На нашем сайте вы можете получить ответ на любой математический вопрос здесь. Подробное
решение с описанием и пояснениями поможет вам разобраться даже с самой сложной задачей и задачи комбинаторика, не
исключение. Мы поможем вам подготовиться к домашним работам, контрольным, олимпиадам, а так же к поступлению
в вуз.
И какой бы пример, какой бы запрос по математике вы не ввели — у нас уже есть решение.
Например, «все формулы комбинаторики».

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

Где можно решить любую задачу по математике, а так же все формулы комбинаторики Онлайн?

Решить задачу все формулы комбинаторики вы можете на нашем сайте https://pocketteacher.ru. Бесплатный
онлайн решатель позволит решить онлайн задачу любой сложности за считанные секунды. Все, что вам необходимо
сделать — это просто
ввести свои данные в решателе. Так же вы можете посмотреть видео инструкцию и узнать, как правильно ввести
вашу задачу на нашем сайте. А если у вас остались вопросы, то вы можете задать их в чате снизу слева на странице
калькулятора.

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

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

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

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

 

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

 

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

 

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

 

content_copy Ссылка save Сохранить 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. Сочетания: АВ, АС, СВ

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

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

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

 Способ 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. То есть у нас есть семь способов взять со стола хотя бы один фрукт.

Калькулятор комбинаций и перестановок

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

Примечание. Здесь находится старая версия Flash.

Для более подробного объяснения, пожалуйста, посетите «Комбинации и перестановки».

Опытные пользователи!

Теперь вы можете добавить «Правила», которые уменьшат список:

Правило «имеет» , которое гласит, что определенные элементы должны быть включены (чтобы запись была включена).

Пример: имеет 2, a, b, c. означает, что запись должна иметь как минимум две из букв a, b и c.

Правило «нет» , которое означает, что некоторые элементы из списка не должны встречаться вместе.

Пример: no 2, a, b, c означает, что запись должна содержать , а не , две или более букв a, b и c.

Правило «шаблона» используется для наложения некоторого шаблона на каждую запись.

Пример: шаблон c, * означает, что буква c должна быть первой (может следовать все остальное)

Поместите правило в отдельной строке:

Пример: правило «имеет»

a, b, c, d, e, f, g
имеет 2, a, b

Комбинации a, b, c, d, e, f, g, которые имеют по крайней мере 2 из a, b или c

Правила в деталях

Правило «имеет»

За словом «имеет» следует пробел и число.Затем запятая и список элементов, разделенных запятыми.

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

Пример имеет 1, a, b, c

Допускается, если есть a , или b , или c , или a и b , или a и c , или b и c , или все три a, b и с .

Другими словами, он настаивает на том, чтобы в результате присутствовали a, b или c.

Итак, {a, e, f} принято, но {d, e, f} отклонено.

Пример имеет 2, a, b, c

Допустим, если есть a и b , или a и c , или b и c , или все три a, b и c .

Другими словами, он настаивает на том, чтобы в результате было как минимум 2 из a, b или c.

Итак, {a, b, f} принято, но {a, e, f} отклонено.

Правило «нет»

Слово «нет», за которым следует пробел и число. Затем запятая и список элементов, разделенных запятыми.

Число указывает, сколько (минимум) из списка необходимо для отклонения.

Пример: n = 5, r = 3, Order = no, Replace = no

Что обычно дает:

{a, b, c} {a, b, d} {a, b, e} {a, c, d} {a, c, e} {a, d, e} {b, c, d } {b, c, e} {b, d, e} {c, d, e}

Но когда мы добавляем такое правило «нет»:

а, б, в, г, д, е, г
№ 2, а, б

Получаем:

{a, c, d} {a, c, e} {a, d, e} {b, c, d} {b, c, e} {b, d, e} {c, d, e }

Записи {a, b, c}, {a, b, d} и {a, b, e} отсутствуют, потому что правило говорит, что у нас не может быть 2 из списка a, b (имея a или b нормально, но не вместе)

Пример: № 2, а, б, в

Разрешает только это:

{a, d, e} {b, d, e} {c, d, e}

Он отклонил любой с a и b , или a и c , или b и c , или даже все три a, b и c .

Итак, {a, d, e) разрешено (в нем только один из a, b и c)

Но {b, c, d} отклоняется (у него 2 из списка a, b, c)

Пример: № 3, а, б, в

Разрешает все эти:

{a, b, d} {a, b, e} {a, c, d} {a, c, e} {a, d, e} {b, c, d} {b, c, e } {b, d, e} {c, d, e}

Отсутствует только {a, b, c}, потому что это единственный, у которого 3 из списка a, b, c

Правило «шаблона»

Слово «шаблон», за которым следует пробел и список элементов, разделенных запятыми.

Вы можете включить эти «особые» предметы:

  • ? (вопросительный знак) означает любой предмет. Это похоже на «подстановочный знак».
  • * (звездочка) означает любое количество элементов (0, 1 или более). Как «супер-шаблон».

Пример: узор?, C, *, f

Означает «любой элемент, за которым следует c, за которым следует ноль или более элементов, затем f»

Итак, {a, c, d, f} разрешено

И {b, c, f, g} также разрешены (между c и f нет элементов, и это нормально)

Но {c, d, e, f} нет, потому что перед c нет элемента.

Пример: сколькими способами можно выстроить Алекса, Бетти, Кэрол и Джона в ряд, с Джоном после Алекса.

Использование: n = 4, r = 4, order = yes, replace = no.

Алекс, Бетти, Кэрол, Джон
узор *, Алекс, *, Джон

Результат:

{Алекс, Бетти, Кэрол, Джон} {Алекс, Бетти, Джон, Кэрол} {Алекс, Кэрол, Бетти, Джон} {Алекс, Кэрол, Джон, Бетти} {Алекс, Джон, Бетти, Кэрол} {Алекс, Джон , Кэрол, Бетти} {Бетти, Алекс, Кэрол, Джон} {Бетти, Алекс, Джон, Кэрол} {Бетти, Кэрол, Алекс, Джон} {Кэрол, Алекс, Бетти, Джон} {Кэрол, Алекс, Джон, Бетти} {Кэрол, Бетти, Алекс, Джон}

Лотереи

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

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

Правила

У разных лотерей разные правила.

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

Пример:

Вы участвуете в лотерее, купив билет и выбрав свои шесть чисел.

Вы выбираете: 1, 2, 12, 14, 20 и 21

В субботу проводится розыгрыш лотереи, и выпадают выигрышных номеров :

3, 12, 18, 20, 32 и 43

Вы сопоставили два чисел (12 и 20):

  • Этого достаточно, чтобы выиграть что-нибудь?
  • Обычно вы должны угадать не менее трех чисел , чтобы получить небольшой приз.
  • Если угадать четырех номеров , вы получите больший приз,
  • Соответствие пяти еще больше.
  • Но если вы угадаете ВСЕ ШЕСТЬ номеров, вы можете выиграть миллионов .

Шансы на выигрыш всех 6 номеров равны 1 из 13 983 816 (рассчитано ниже).

Выбор чисел

Они могут выиграть.

Цифры не знают, какие они!

Лотерея , так же вероятно, что выпадет «1,2,3,4,5,6», как «9,11,16,23,27,36»

Серьезно!

Вместо чисел это могут быть символы или цвета, лотерея все равно будет работать.

На самом деле получился результат ниже (Florida Fantasy 5 от 21 марта 2011 г.):

Так что неважно, какие числа вы выберете, шансы одинаковы.

Более вероятные номера?

Значит, вы читали, что одни числа встречаются чаще, чем другие? Ну, конечно, есть, это случайный случай.

У организаторов лотерей есть строгие правила, запрещающие «фальсификацию» результатов. Но случайный случай может иногда приводить к странным результатам.

Например, с помощью Spinner я сделал 1000 вращений на 10 чисел и получил следующее:

Ух ты! 7 выпало 115 раз, ,
и 8 только 81 раз.

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

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

Популярные номера

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

дней рождения — популярный выбор, поэтому люди выбирают 1–12 и 1–31 чаще. Также счастливые числа.

Так что, возможно, вам стоит выбрать непопулярных номеров , чтобы, когда вы ДЕЙСТВИТЕЛЬНО выиграете, вы получите больше денег.

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

Сожаление

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

Мой совет:

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

Синдикаты

«Синдикат» — это группа людей, которые все вкладывают небольшие деньги, чтобы группа могла купить много билетов. Шансы на выигрыш повышаются, но каждый раз ваша выплата меньше (потому что вы делитесь).

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

Еще одна веская причина для присоединения к синдикату — это то, что ваши шансы на выигрыш повышаются (но то, что вы выигрываете, снижается).

Подумайте об этом … выигрыш Десяти миллионов действительно изменит вашу жизнь, но Один миллион также значительно улучшит вашу жизнь. Вы можете предпочесть десятикратный шанс выиграть миллион.

Вероятность выиграть большой приз

ОК. Каковы шансы на то, что вы выиграете большой приз?

Шансы на выигрыш всех 6 номеров равны 1 из 13 983816

Вы можете использовать калькулятор комбинаций и перестановок, чтобы вычислить это (используйте n = 49 , r = 6 , «Нет» для параметра «Важен ли порядок?» И «Нет» для параметра «Разрешено ли повторение?»)

Фактический расчет таков:

49 С 6 = 49! / (43! X 6!) = 13983816

Итак, сколько раз вам нужно сыграть, чтобы выиграть?

1 неделя

Предположим, вы играете каждую неделю

Вероятность выигрыша через 1 неделю:

1
13983816
= 0.0000000715 …

Таким образом, вероятность того, что не выиграют через 1 неделю, составляет:

1 —
1
13983816
= 0,9999999285 …

50 лет

Допустим, вы играете 50 лет, это 2600 недель.

Вероятность того, что не выиграют за 2600 недель, составляет:

(1 —
1
13983816
) 2600 = 0,999814 …

Это означает, что вероятность выигрыша (через 50 лет) составляет: 1 — 0.999814 … = 0,000186 …

Еще только около 0,02%

И вы бы потратили тысячи на этот маленький шанс.

Вы могли хорошо провести отпуск за эти деньги.

НО это весело думать: «Я могу выиграть на этой неделе!»

Просто оставь это как развлечение , хорошо?

Твоя очередь

Теперь ваша очередь:

  • Узнайте правила выигрыша в лотерею в вашем регионе.
  • Сколько номеров вам нужно выбрать и из скольких номеров вы выбираете?
  • Рассчитайте вероятность выигрыша в любую неделю.
  • Подсчитайте вероятность выигрыша, если вы будете играть каждую неделю в течение 50 лет.
  • Сколько денег вы сэкономите, не играя? Что можно купить за эти деньги?

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

Одним из самых интересных образов чисел является треугольник Паскаля (названный в честь Блеза Паскаля , известного французского математика и философа).

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

Каждое число — это числа непосредственно над ним, сложенные вместе.

(здесь я выделил, что 1 + 3 = 4)

Узоры внутри треугольника

Диагонали

Первая диагональ, конечно же, всего лишь «1» с

На следующей диагонали расположены счетные числа (1,2,3 и т. Д.).

На третьей диагонали расположены треугольные числа

(Четвертая диагональ, не выделенная, имеет тетраэдрические числа.)

Симметричный

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

Суммы по горизонтали

Что вы заметили в горизонтальных суммах?

Есть узор?

Они удваивают каждый раз (степени двойки).

Показатели из 11

Каждая строка также является степенью (показателем) 11:

  • 11 0 = 1 (первая строка — просто «1»)
  • 11 1 = 11 (вторая строка — «1» и «1»)
  • 11 2 = 121 (третья строка — «1», «2», «1»)
  • и т. Д.!

Но что происходит с 11 5 ? Простой! Цифры просто перекрываются, вот так:

То же самое происходит с 11 6 и т. Д.

Квадраты

Для второй диагонали квадрат числа равен сумме чисел рядом с ним и под ними обоих.

Примеры:

  • 3 2 = 3 + 6 = 9,
  • 4 2 = 6 + 10 = 16,
  • 5 2 = 10 + 15 = 25,

Есть и веская причина … ты можешь придумать?
(Подсказка: 4 2 = 6 + 10, 6 = 3 + 2 + 1 и 10 = 4 + 3 + 2 + 1)

Последовательность Фибоначчи

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

(Последовательность Фибоначчи начинается с «0, 1», а затем продолжается добавлением двух предыдущих чисел, например 3 + 5 = 8, затем 5 + 8 = 13 и т. Д.)

Шансы и эвены

Если вы раскрасите четные и нечетные числа, вы получите узор, такой же, как треугольник Серпинского

Использование треугольника Паскаля

Голова и решка

Треугольник Паскаля может показать вам, сколько способов совмещения орла и решки.Это может показать вам вероятность любой комбинации.

Например, если вы подбрасываете монету три раза, есть только одна комбинация, которая даст вам три решки (HHH), но есть три, которые дадут две решки и одну решку (HHT, HTH, THH), а также три, которые дают одну голову и два решки (HTT, THT, TTH) и по одному для всех решек (TTT). Это образец «1,3,3,1» в Треугольнике Паскаля.

Боссы Возможные результаты (сгруппированные) Треугольник Паскаля
1 H
T
1, 1
2 HH
HT TH
TT
1, 2, 1
3 HHH
HHT, HTH, THH
HTT, THT, TTH
TTT
1, 3, 3, 1
4 HHHH
HHHT, HHTH, HTHH, THHH
HHTT, HTHT, HTTH, THHT, THTH, TTHH
HTTT, THTT, TTHT, TTTH
TTTT
1, 4, 6, 4, 1
… и т.д …

Пример: Какова вероятность выпадения ровно двух орлов при подбрасывании 4 монет?

Есть 1 + 4 + 6 + 4 + 1 = 16 (или 2 4 = 16) возможных результатов, и 6 из них дают ровно две решки. Таким образом, вероятность составляет 6/16, или 37,5%

Комбинации

Треугольник также показывает, сколько комбинаций объектов возможно.

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

Ответ: спуститесь в начало строки 16 (верхняя строка — 0), а затем по трем разрядам (первое место — 0) и там значение будет вашим ответом, 560 .

Вот отрывок из строки 16:

 1 14  ...
1 15 105 455 1365 ...
1 16 120  560  1820 4368 ... 

Формула для любого входа в треугольник

На самом деле существует формула из Комбинации для вычисления значения в любом месте треугольника Паскаля:

Обычно его называют «n выберите k» и записывают так:

Обозначение: «n выберите k» также можно написать C (n, k) , n C k или даже n C k .

Знак «!» является «факториалом» и означает умножение ряда убывающих натуральных чисел. Примеры:

  • 4! = 4 × 3 × 2 × 1 = 24
  • 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
  • 1! = 1

Таким образом, Треугольник Паскаля также может быть
треугольником «n выбрать k» , подобным этому.

(обратите внимание, что верхняя строка — это , нулевая строка
, а также крайний левый столбец — нулевой)

Пример: строка 4, член 2 в треугольнике Паскаля равен «6» …

… посмотрим, работает ли формула:

Да, работает! Попробуйте другое значение для себя.

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

Полиномы

Треугольник Паскаля также может показать вам коэффициенты в биномиальном разложении:

Мощность Биномиальное разложение Треугольник Паскаля
2 (x + 1) 2 = 1 x 2 + 2 x + 1 1, 2, 1
3 (x + 1) 3 = 1 x 3 + 3 x 2 + 3 x + 1 1, 3, 3, 1
4 (x + 1) 4 = 1 x 4 + 4 x 3 + 6 x 2 + 4 x + 1 1, 4, 6, 4, 1
… и т.д …

Первые 15 строк

Для справки, я включил строки с 0 по 14 треугольника Паскаля

.

1

10

45

120

210

252

210

120

45

10

1

1

11

55

165

330

462

462

330

165

55

11

1

1

12

66

220

495

792

924

792

495

220

66

12

1

1

13

78

286

715

1287

1716

1716

1287

715

286

78

130009 13

1

14

91

364

1001

2002

3003

3432

3003

2002

1001

364

91

364

91

Китайцы знали об этом

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

Это с лицевой стороны книги Чу Ши-Чи « Ssu Yuan Yü Chien» (Драгоценное зеркало четырех элементов) , написанной в году нашей эры 1303 (более 700 лет назад и более чем на 300 лет до Паскаля!) В книге говорится, что треугольник был известен более чем за два столетия до этого.

Квинканкс

Удивительная маленькая машина, созданная сэром Фрэнсисом Гальтоном, представляет собой треугольник Паскаля, сделанный из колышков. Он называется Quincunx.

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

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

Биномиальное распределение

«Би» означает «два» (как у велосипеда два колеса) …
… так это про вещи с два результата .

Подбрасывание монеты:

  • Получили ли мы головы (H) или
  • Хвосты (Т)

Мы говорим, что вероятность выпадения монеты H составляет ½
А вероятность выпадения монеты T составляет ½

Бросая кубик:

  • Мы получили четверку…?
  • … или нет?

Мы говорим, что вероятность четыре равна 1/6 (одна из шести граней равна четверке)
И вероятность того, что не четыре составляет 5/6 (пять из шести граней не четыре)

Обратите внимание, что матрица имеет 6 сторон, но здесь мы рассмотрим только два корпуса : «четыре: да» или «четыре: нет»

Подбросим монетку!

Подбросьте справедливую монету трижды … каков шанс получить две головы ?

Трижды подбрасывая монету ( H для орла, T для решки) можно получить любой из этих 8 результатов :

Какие результаты мы хотим?

«Две головы» могут быть в любом порядке: «HHT», «THH» и «HTH» имеют две головы (и один хвост).

Итак, 3 результата дают «Две головы».

Какова вероятность каждого исхода?

Каждый исход одинаково вероятен, а их 8, поэтому каждый исход имеет вероятность 1/8

Таким образом, вероятность события «Две головы» составляет:

Количество желаемых результатов Вероятность
каждого исхода
3 × 1/8 = 3/8

Таким образом, шанс получить две головы составляет 3/8

Мы использовали специальные слова:

  • Результат : любой результат трех подбрасываний монеты (8 различных возможностей)
  • Событие : «Две головы» из трех подбрасываний монеты (3 исхода имеют это)

3 головы, 2 головы, 1 голова, нет

Расчеты (P означает «Вероятность»):

  • P (три головки) = P ( HHH ) = 1/8
  • P (две головки) = P ( HHT ) + P ( HTH ) + P ( THH ) = 1/8 + 1/8 + 1/8 = 3/8
  • P (одна головка) = P ( HTT ) + P ( THT ) + P ( TTH ) = 1/8 + 1/8 + 1/8 = 3/8
  • P (нулевой напор) = P ( TTT ) = 1/8

Мы можем записать это в терминах случайной переменной, X, = «Количество голов при 3 подбрасываниях монеты»:

  • P (X = 3) = 1/8
  • P (X = 2) = 3/8
  • P (X = 1) = 3/8
  • P (X = 0) = 1/8

А вот как это выглядит в виде графика:

Он симметричный!

Создание формулы

А теперь представьте, что нам нужны шансы 5 решек за 9 бросков : перечисление всех 512 исходов займет много времени!

Итак, давайте составим формулу.

В нашем предыдущем примере, как мы можем получить значения 1, 3, 3 и 1?

Что ж, они действительно находятся в Треугольнике Паскаля!

Можем ли мы сделать их по формуле?

Конечно, можем, и вот он:

Его часто называют «n choose k»

  • n = общее количество
  • k = число, которое мы хотим
  • знак «!» означает «факториал», например 4! = 1 × 2 × 3 × 4 = 24

Подробнее …
об этом в Комбинации и Перестановки.

Попробуем:

Пример: при 3 бросках, каковы шансы на 2 решки?

У нас есть n = 3 и k = 2 :

н! к! (Н-к)! = 3! 2! (3-2)!

= 3 × 2 × 1 2 × 1 × 1

= 3

Итак, есть 3 исхода с «2 головами»

(Мы это уже знали, но теперь у нас есть формула.)

Давайте ответим на более сложный вопрос:

Пример: при 9 бросках каковы шансы на 5 выпадений?

У нас есть n = 9 и k = 5 :

н! к! (Н-к)! = 9! 5! (9-5)!

= 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 5 × 4 × 3 × 2 × 1 × 4 × 3 × 2 × 1

= 126

Значит, у 126 исходов будет 5 голов

А для 9 бросков всего 2 9 = 512 исходов, поэтому получаем вероятность:

Количество желаемых результатов Вероятность
каждого исхода
126 × 1 512 = 126 512

Итак:

P (X = 5) = 126 512 = 0.24609375

Примерно с вероятностью 25% .

(Легче, чем перечислить их все.)

Смещение!

До сих пор шансы на успех или неудачу равнялись и равны .

Но что, если монеты смещены (больше на одну сторону, чем на другую) или выбор не равен 50/50.

Пример: вы продаете бутерброды. 70% выбирают курицу, остальные выбирают что-то другое.

Какова вероятность продать 2 бутерброда с курицей следующим 3 покупателям?

Это похоже на пример орла и решки, но с 70/30 вместо 50/50.

Нарисуем древовидную диаграмму:

Ящики «Две курицы» выделены.

Вероятности для «двух цыплят» равны 0,147 , потому что мы умножаем два 0,7 и один 0,3 в каждом случае. Другими словами

0,147 = 0,7 × 0,7 × 0,3

Или, используя экспоненты:

= 0,7 2 × 0,3 1

0,7 — это вероятность каждого выбора, который мы хотим, назовем это p

2 — это количество вариантов, которое мы хотим, назовем его k

А у нас (пока):

= p k × 0.3 1

0,3 — вероятность противоположного выбора, так что это: 1 − p

1 — это количество противоположных вариантов, так что это: n − k

Что дает нам:

= p k (1-p) (n-k)

Где

  • p — вероятность каждого выбора, который мы хотим
  • k — это количество вариантов, которое мы хотим
  • n — общее количество вариантов

Пример: (продолжение)

  • р = 0.7 (шанс курицы)
  • k = 2 (выбор курицы)
  • n = 3 (всего вариантов)

Получаем:

п к (1-р) (н-к) = 0,7 2 (1-0,7) (3-2)

= 0,7 2 (0,3) (1)

= 0,7 × 0,7 × 0,3

= 0,147

, что у нас было раньше, но теперь используется формула

Теперь мы знаем, что вероятность каждого исхода равна 0,147

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

Пример: (продолжение)

Общее количество исходов «два цыпленка»:

н! к! (Н-к)! = 3! 2! (3-2)!

= 3 × 2 × 1 2 × 1 × 1

= 3

И получаем:

Количество желаемых результатов Вероятность
каждого исхода
3 × 0.147 = 0,441

Таким образом, вероятность события «2 человека из 3 выбирают курицу» = 0,441

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

Пример: Сэм говорит: «70% выбирают курицу, поэтому 7 из следующих 10 клиентов должны выбрать курицу» … каковы шансы, что Сэм прав?

Итак имеем:

И получаем:

п к (1-п) (н-к) = 0.7 7 (1-0,7) (10-7)

= 0,7 7 (0,3) (3)

= 0,0022235661

Это вероятность каждого исхода.

И общее количество этих исходов:

н! к! (Н-к)! = 10! 7! (10-7)!

= 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 7 × 6 × 5 × 4 × 3 × 2 × 1 × 3 × 2 × 1

= 10 × 9 × 8 3 × 2 × 1

= 120

И получаем:

Количество желаемых результатов Вероятность
каждого исхода
120 × 0.0022235661 = 0,266827932

Таким образом, вероятность того, что 7 из 10 выберут курицу, составляет всего около 27%

Мораль истории: даже при том, что долгосрочное среднее значение составляет 70%, не ожидайте 7 из следующих 10.

Собираем вместе

Теперь мы знаем, как вычислить , сколько :

н! к! (Н-к)!

И вероятность каждого :

п к (1-р) (н-к)

При умножении получаем:

Вероятность k из n способов:

П (k из n) = n! к! (Н-к)! п к (1-р) (н-к)

Общая формула биномиальной вероятности

Важные примечания:

  • Испытания независимые,
  • В каждом испытании есть только два возможных исхода,
  • Вероятность «успеха» в каждом испытании постоянна.

Quincunx

Поиграйте с Quincunx (затем прочтите Quincunx Explained), чтобы увидеть биномиальное распределение в действии.

Брось кубик

Честный кубик бросается четыре раза. Рассчитайте вероятности получения:

  • 0 двоек
  • 1 Два
  • 2 двоих
  • 3 двоих
  • 4 двойки

В данном случае n = 4 , p = P (Два) = 1/6

X — это случайная переменная «Количество двоек из четырех бросков».

Подставьте x = от 0 до 4 в формулу:

P (k из n) = n! к! (Н-к)! п к (1-р) (н-к)

Вот так (до 4 знаков после запятой):

  • P (X = 0) = 4! 0! 4! × (1/6) 0 (5/6) 4 = 1 × 1 × (5/6) 4 = 0,4823
  • P (X = 1) = 4! 1! 3! × (1/6) 1 (5/6) 3 = 4 × (1/6) × (5/6) 3 = 0.3858
  • P (X = 2) = 4! 2! 2! × (1/6) 2 (5/6) 2 = 6 × (1/6) 2 × (5/6) 2 = 0,1157
  • P (X = 3) = 4! 3! 1! × (1/6) 3 (5/6) 1 = 4 × (1/6) 3 × (5/6) = 0,0154
  • P (X = 4) = 4! 4! 0! × (1/6) 4 (5/6) 0 = 1 × (1/6) 4 × 1 = 0,0008

Резюме: «для 4 бросков существует 48% вероятность отсутствия двоек, 39% вероятность 1 два, 12% вероятность 2 двоек, 1.Вероятность 5% на 3 двойки и крошечная вероятность 0,08% того, что все броски будут двойками (но это все равно может случиться!) »

На этот раз график несимметричный:

Это несимметрично!

Перекошено, потому что p не равно 0,5

Спортивные мотоциклы

Ваша компания занимается производством спортивных мотоциклов. 90% проходят окончательную проверку (а 10% не проходят и требуют исправления).

Каково ожидаемое среднее значение и отклонение от 4 следующих проверок?

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

X — случайная переменная «Количество проходов из четырех проверок».

Подставьте x = от 0 до 4 в формулу:

P (k из n) = n! к! (Н-к)! п к (1-р) (н-к)

Как это:

  • P (X = 0) = 4! 0! 4! × 0,9 0 0,1 4 = 1 × 1 × 0,0001 = 0,0001
  • P (X = 1) = 4! 1! 3! × 0,9 1 0.1 3 = 4 × 0,9 × 0,001 = 0,0036
  • P (X = 2) = 4! 2! 2! × 0,9 2 0,1 2 = 6 × 0,81 × 0,01 = 0,0486
  • P (X = 3) = 4! 3! 1! × 0,9 3 0,1 1 = 4 × 0,729 × 0,1 = 0,2916
  • P (X = 4) = 4! 4! 0! × 0,9 4 0,1 0 = 1 × 0,6561 × 1 = 0,6561

Резюме: «для следующих 4 велосипедов есть крошечный 0.Вероятность отсутствия передач 01%, вероятность отсутствия передач 0,36%, вероятность 2 передач 5%, вероятность 3 передач 29% и колоссальная вероятность 66%, что все они пройдут проверку «.

Среднее значение, дисперсия и стандартное отклонение

Давайте рассчитаем среднее значение, дисперсию и стандартное отклонение для проверок спортивного велосипеда.

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

Среднее или «ожидаемое значение»:

мк = np

Для спортивных мотоциклов:

μ = 4 × 0.9 = 3,6

Итак, можно ожидать, что 3,6 мотоцикла (из 4) пройдут техосмотр.
На самом деле имеет смысл … 0,9 шанс для каждого велосипеда умножить на 4 велосипеда равняется 3,6

Формула дисперсии:

Отклонение: σ 2 = np (1-p)

Стандартное отклонение — это квадратный корень из дисперсии:

σ = √ (np (1-p))

Для спортивных мотоциклов:

Разница: σ 2 = 4 × 0,9 × 0,1 = 0,36

Стандартное отклонение:

σ = √ (0.36) = 0,6

Примечание: мы также можем вычислить их вручную, составив такую ​​таблицу:

X П (Х) X × P (X) X 2 × P (X)
0 0,0001 0 0
1 0.0036 0,0036 0,0036
2 0,0486 0,0972 0,1944
3 0,2916 0,8748 2,6244
4 0,6561 2,6244 10,4976
СУММА: 3.6 13,32

Среднее значение — это Сумма (X × P (X)) :

мк = 3,6

Дисперсия равна сумме (X 2 × P (X)) минус Среднее 2 :

Разница: σ 2 = 13,32 — 3,6 2 = 0,36

Стандартное отклонение:

σ = √ (0,36) = 0,6

И мы получили те же результаты, что и раньше (ура!)

Сводка

перестановок и комбинаций (алгебра 2, дискретная математика и вероятность) — Mathplanet

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

Если порядок не имеет значения, то у нас есть комбинация, если порядок имеет значение, то у нас есть перестановка. Можно сказать, что перестановка — это упорядоченная комбинация.

Количество перестановок n объектов, взятых r за раз, определяется по следующей формуле:

$$ P (n, r) = \ frac {n!} {(N-r)!} $$


Пример

Код состоит из 4 цифр в определенном порядке, цифры от 0 до 9.Сколько существует различных перестановок, если одну цифру можно использовать только один раз?

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

$$ P (n, r) = \ frac {10!} {(10-4)!} = \ Frac {10 \ cdot9 \ cdot8 \ cdot 7 \ cdot 6 \ cdot 5 \ cdot 4 \ cdot 3 \ cdot 2 \ cdot 1} {6 \ cdot5 \ cdot 4 \ cdot 3 \ cdot 2 \ cdot 1} = 5040 $$

В нашем примере порядок цифр был важен, если бы порядок не имел значения, у нас было бы определение комбинации.Количество комбинаций из n объектов, взятых r за раз, определяется по следующей формуле:

$$ C (n, r) = \ frac {n!} {(N-r)! R!} $$


Видеоурок

Четверо друзей сядут за стол с 6 стульями. Какими способами могли сесть друзья?

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

Введение

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

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

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

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

Факториалы

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

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

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

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

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

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

Чтобы найти простую формулу, подобную приведенной выше, мы можем думать о ней очень похожим образом.
«Есть ученики« + V.CombC1 + », которые могут сесть на первый стул. ‘+
(((Math.min (V.CombC1, V.CombC2)) == 2 || (Math.min (V.CombC1, V.CombC2)) == 3 || (Math.min (V.CombC1, V .CombC2)) == 4)? ‘Тогда есть’ + (V.CombC1-1) + ‘ученики, которые могли бы сесть на второй стул.’: ») +
(((Math.min (V.CombC1, V.CombC2)) == 3 || (Math.min (V.CombC1, V.CombC2)) == 4)? ‘Тогда есть’ + (V.CombC1 -2) + ‘ученики, которые могли бы сесть на третий стул.’: ») +
(((Math.min (V.CombC1, V.CombC2)) == 4)? ‘Наконец, остался один ученик, который сядет на последний стул.’:’ ‘) +
((V.CombC1- (Math.min (V.CombC1, V.CombC2)) == 1 || V.CombC1- (Math.min (V.CombC1, V.CombC2)) == 2 || V. CombC1- (Math.min (V.CombC1, V.CombC2)) == 3)? ‘Нас не волнуют оставшиеся’ + (V.CombC1-V.CombC2) + ‘дети, оставшиеся стоять.’: ‘ ‘)

Всего

возможностей. Мы снова должны подумать об обобщении этого. Мы начинаем, как и делали бы с факториалами, но останавливаемся, не дойдя до 1. Фактически мы останавливаемся, как только достигаем числа студентов без стула. При размещении 7 студентов на 3 стульях их

7 × 6 × 5 = 7 × 6 × 5 × 4 × 3 × 2 × 17 × 6 × 5 × 4 × 3 × 2 × 1 = 7 ! 4! = 7 ! ( 7 3 )!

возможностей, поскольку 4 × 3 × 2 × 1 компенсируют друг друга.Опять же, для этого есть более простое обозначение: 7 P 3 . Если мы хотим разместить n объектов на m позиций, то будет

n P m = n ! ( n m )!

возможностей. P означает « p ermutations», поскольку мы подсчитываем количество перестановок (порядков) объектов. Если m и n такие же, как и в задаче в начале этой статьи, мы имеем

n P n = n ! ( n n )! = n ! 0 !.

Чтобы понять это, мы определяем 0! = 1. Теперь n P n = n ! как и следовало ожидать от нашего решения первой проблемы.

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

Имеется 10 цифр (0, 1,…, 9), каждая из которых встречается не более одного раза.Число порядков этих цифр составляет 10 P 4 = 5040. Проверка такого количества комбинаций займет очень много времени, поэтому 4-значные блокировки очень безопасны.

Комбинации

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

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

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

, итого их 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 ! r ! ( 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)
знак равно
( + 1 + 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 столбик (деление n разных фруктов).Это составляет 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 предположений, сколько времени в среднем вам понадобится, чтобы выиграть?

(а) Всего 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 годам. Урок, который нужно усвоить: не играйте в лото!

формул комбинаторики | Суперпроф

Комбинаторика — Введение

Комбинаторика или комбинаторная математика — это раздел математики, который занимается счетом вещей. Задачи, связанные с комбинаторикой, изначально изучались математиками из Индии, Аравии и Греции.Некоторые из выдающихся математиков, изучавших эти проблемы, — это Блез Паскаль, Леонард Эйлер и Якоб Бернулли. Хотя комбинаторика полезна во многих других областях математики, однако наиболее известными из них являются кодирование, криптография, теория графов и вероятность.

Можно сказать, что комбинаторика — это математика расстановки и подсчета элементов множества. Мы знаем, что подсчет объектов прост, однако комбинаторика полезна для подсчета количества или расположения, которые слишком сложны, если они подсчитываются традиционным способом.

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

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

Лучшие доступные репетиторы по математике

Первый урок бесплатно

Факториалы

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

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

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

Количество расположений = n!

Читается как факториал n. Поскольку в приведенном выше примере упоминается, что в комнате 5 человек, а у нас 5 стульев, мы найдем такое количество расстановок:

Количество расстановок = 5!

Таким образом, в комнате может быть 120 различных вариантов размещения 5 человек на 5 разных стульях.

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

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

  • Когда разрешено повторение
  • Когда повторение запрещено

Когда разрешено повторение

Предположим, что вам дается задача, в которой вам нужно выбрать 3 цифры из набора из 6 цифры (0,1,2,3,4,5), чтобы получилось число. В этом случае вы будете использовать следующую формулу для вычисления количества перестановок:

Здесь n — количество элементов в наборе

m — количество элементов, которые мы выберем из набора

У нас есть Предполагается, что повторение разрешено, потому что вы можете выбрать одну цифру дважды, например, числа могут быть 100, 202, 203 и т. д.

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

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

= 216

Следовательно, возможны 216 различных перестановок.

Когда повторение не разрешено

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

Здесь n = общее количество элементов для выбора из

r = количество объектов, которые мы хотим для выбора

Например, рассмотрим следующий сценарий:

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

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

=

=

Следовательно, возможны 30240 перестановок.

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

Круговые перестановки

Круговые перестановки — это количество расположений вокруг фиксированного круга.Это также известно как циклическая перестановка.

Существует два типа циклических или круговых перестановок:

  • Когда порядок по часовой стрелке и против часовой стрелки различаются
  • Когда порядок по часовой стрелке и против часовой стрелки одинаковы

Формула для циклической перестановки, когда порядок по часовой стрелке и против часовой стрелки различаются, приведена ниже :

Формула для циклических перестановок при одинаковом порядке по часовой стрелке и против часовой стрелки приведена ниже:

Комбинации

В отличие от перестановок, порядок выбора в комбинациях не важен.Есть два типа комбинаций:

  • Комбинации без повторов
  • Комбинации с повторением

Комбинации без повторов

Ниже приведена формула для определения количества комбинаций без повторов:

Здесь:

n = общее количество предметов на выбор

r = количество предметов, которые мы хотим выбрать

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

В магазине есть 4 шара ваших любимых цветов.У вас есть деньги, чтобы купить только 2 из них. Как вы выберете 2 из них?

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

Таким образом, вы можете выбрать 2 шара 6 способами.

Комбинации с повторением

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

Здесь:

n = количество объектов на выбор

k = количество элементов мы хотим выбрать

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

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

Порядок не важен при выборе вкуса.Следовательно, это показывает, что это проблема комбинации. У вас может быть один аромат дважды, потому что вам разрешено две мерные ложки. Это показывает, что это проблема комбинации с повторением. Подставьте значения в приведенную выше формулу, чтобы получить количество вариантов:

Следовательно, возможно 10 вариантов.

Сводка формул

Перестановка, когда повторение разрешено:

Здесь n — количество элементов в наборе

m — количество элементов, которые мы выберем из набора

Перестановка, когда повторение запрещено:

Здесь n = общее количество элементов для выбора из

r = количество объектов, которые мы хотим выбрать

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

Круговой перестановка при одинаковом порядке по часовой стрелке и против часовой стрелки:

Комбинация без повторения:

Здесь: 9000 8

n = количество объектов на выбор

k = количество элементов, которые мы хотим выбрать

.

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

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