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

Содержание

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

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

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

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

  • алгоритм выбора формулы (сочетания, перестановки, размещения с повторениями и без),
  • рекомендации по изучению комбинаторики,
  • 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 букв. Следовательно, число перестановок с повторениями равно

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

Math.ru


Наум Яковлевич Виленкин

М.: Наука, 1969. 328 с.

Тираж 100000 экз.



Загрузить (Mb)
djvu (2.58)pdf (-)ps (-)html (-)tex (-)

Область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов, называется комбинаторикой . В данной книге о комбинаторных проблемах рассказывается в занимательной, популярной форме. Тем не менее в ней разбираются и некоторые довольно сложные задачи, дается понятие о методах рекуррентных соотношений и производящих функций.
Первая глава книги посвящена общим правилам комбинаторики — правилам суммы и произведения. Во второй главе изучаются размещения, перестановки и сочетания. В главе 3 изучаются задачи, в которых на рассматриваемые комбинации налагаются те или иные ограничения. В главе 4 рассмотрены задачи на разбиения чисел и рассказано о геометрических методах в комбинаторике. Глава 5 посвящена задачам о случайных блужданиях и различным модификациям арифметического треугольника. В главе 6 рассказано о рекуррентных соотношениях, а в главе 7 — о производящих функциях, и в частности о биномиальной формуле.


Содержание

Предисловие

Глава I. Общие правила комбинаторики

    Суеверные велосипедисты

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

    Системы счисления

    Секретный замок

    Код Морзе

    Морской семафор

    Электронная цифровая вычислительная машина

    Генетический код

    Общие правила комбинаторики

    Задача о домино

    Команда космического корабля

    Задача о шашках

    Сколько человек не знают иностранных языков?

    Формула включений и исключений

    В чем ошибка?

    Решето Эратосфена

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

    Футбольное первенство

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

    Научное общество

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

    Задача о ладьях

    Лингвистические проблемы

    Хоровод

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

    Анаграммы

    Сочетания

    Генуэзская лотерея

    Покупка пирожных

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

    Снова футбольное первенство

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

    Частный случай формулы включений и исключений

    Знакопеременные суммы сочетаний

Глава III. Комбинаторные задачи с ограничениями

    Львы и тигры

    Постройка лестницы

    Книжная полка

    Рыцари короля Артура

    Девушка спешит на свидание

    Сеанс телепатии

    Общая задача о смещении

    Субфакториалы

    Караван в пустыне

    Катание на карусели

    Очередь в кассу

    Задача о двух шеренгах

    Новые свойства сочетаний

Глава IV. Комбинаторика разбиений

    Игра в домино

    Раскладка по ящикам

    Букет цветов

    Задача о числе делителей

    Сбор яблок

    Сбор грибов

    Посылка фотографий

    Флаги на мачтах

    Полное число сигналов

    Разные статистики

    Разбиения чисел

    Отправка бандероли

    Общая задача о наклейке марок

    Комбинаторные задачи теории информации

    Проблема абитуриента

    Уплата денег

    Покупка конфет

    Как разменять гривенник?

    Разбиение чисел на слагаемые

    Диаграммная техника

    Двойственные диаграммы

    Формула Эйлера

Глава V. Комбинаторика на шахматной доске

    Человек бродит по городу

    Арифметический квадрат

    Фигурные числа

    Арифметический треугольник

    Расширенный арифметический треугольник

    Шахматный король

    Обобщенный арифметический треугольник

    Обобщенные арифметические треугольники и m-ичная система счисления

    Некоторые свойства чисел Cm(k,n)

    Шашка в углу

    Арифметический пятиугольник

    Геометрический способ доказательства свойств сочетаний

    Случайные блуждания

    Броуновское движение

    У Шемаханской царицы

    Поглощающая стенка

    Блуждания по бесконечной плоскости

    Общая задача о ладьях

    Симметричные расстановки

    Два коня

Глава VI. Рекуррентные соотношения

    Числа Фибоначчи

    Другой метод доказательства

    Процесс последовательных разбиений

    Умножение и деление чисел

    Задачи о многоугольниках

    Затруднение мажордома

    Счастливые троллейбусные билеты

    Рекуррентные таблицы

    Другое решение проблемы мажордома

    Решение рекуррентных соотношений

    Линейные рекуррентные соотношения с постоянными коэффициентами

    Случай равных корней характеристического уравнения

    Третье решение задачи мажордома

Глава VII. Комбинаторика и ряды

    Деление многочленов

    Алгебраические дроби и степенные ряды

    Действия над степенными рядами

    Применение степенных рядов для доказательства тождеств

    Производящие функции

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

    Полиномиальная формула

    Ряд Ньютона

    Извлечение квадратных корней

    Производящие функции и рекуррентные соотношения

    Разложение на элементарные дроби

    Об едином нелинейном рекуррентном соотношении

    Производящие функции и разбиения чисел

    Сводка результатов по комбинаторике разбиений

Задачи по комбинаторике

Решения и ответы




Загрузить (Mb)
djvu (2.58)pdf (-)ps (-)html (-)tex (-)

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

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

Размещения

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

      Задача.   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

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

Решение

Первая монета имеет

 альтернативы – либо орел, либо решка. Для
второй монеты также есть

 альтернативы
и т.д., т.е.

.

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



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

Если любые две группы

 и

 не имеют общих элементов, то выбор одного
элемента или из

,
или из

,
…или из

 можно осуществить

 способами.


Пример 2

На полке 30 книг, из них 20 математических, 6 технических и 4
экономических. Сколько существует способов 
выбора одной математической или одной экономической книги.

Решение

Математическая книга может быть выбрана  

 способами, экономическая —

 способами.

По правилу суммы существует

 способа выбора математической или
экономической книги.


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


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

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

 элементов по

.

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

 элементов из генеральной совокупности объема

,
равно:



Пример 3

Расписание дня состоит из 5 различных уроков. Определите число
вариантов расписания при выборе из 11 дисциплин.

Решение

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


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

 элементов равно


Пример 4

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

Решение

Каждый вариант рассадки отличается только порядком участников, то
есть является перестановкой из 4 элементов:



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

 элементов по

.

Общее число различных способов, которыми можно произвести выбор с
возвращением

 элементов из генеральной совокупности объема

,
равно


Если вам сейчас не требуется платная помощь с решением задач, контрольных работ и типовых расчетов, но может потребоваться в дальнейшем, то, чтобы не потерять контакт
вступайте в группу ВК
сохраните контакт WhatsApp (+79688494598)
сохраните контакт Телеграм (@helptask) .

Пример 5

Лифт останавливается на 7
этажах. Сколькими способами могут выйти на этих этажах 6 пассажиров,
находящихся в кабине лифта?

Решение

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



 


Сочетания


Сочетаниями

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

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

 элементов из генеральной совокупности объема

 получаются комбинации, которые называются сочетаниями без повторений из

 элементов по

.

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

 элементов по

 равно:



Пример 6

В ящике 9 яблок. Сколькими
способами можно выбрать 3 яблока из ящика?

Решение

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

Количество способов,
которыми можно выбрать 3 яблока из 9:



Пусть из генеральной совокупности объема

 выбирается

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

 элементов по

.

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

 элементов по

:



Если вам сейчас не требуется платная помощь с решением задач, контрольных работ и типовых расчетов, но может потребоваться в дальнейшем, то, чтобы не потерять контакт
вступайте в группу ВК
сохраните контакт WhatsApp (+79688494598)
сохраните контакт Телеграм (@helptask) .

Пример 7

На почте продают открытки 3 видов. Сколькими способами можно купить
6 открыток?

Решение

Это задача на отыскание числа сочетаний с повторениями из 3 по 6:



Разбиение множества на группы


Пусть множество из

 различных элементов разбивается на

 групп так, то в первую группу попадают

 элементов, во вторую —

 элементов, в


группу —

 элементов, причем

.
Такую ситуацию называют разбиением множества на группы.

Число разбиений на

 групп, когда в первую попадают

 элементов, во вторую —

 элементов, в k-ю группу —

 элементов, равно:



Пример 8

Группу из 16 человек
требуется разбить на три подгруппы, в первой из которых должно быть 5 человек,
во второй – 7 человек, в третьей – 4 человека. Сколькими способами это можно
сделать?

Решение

Здесь

Число разбиений на 3 подгруппы:


Задачи контрольных и самостоятельных работ


Задача 1

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


Задача 2

Доступ к
файлу открывается, только если введен правильный пароль – определенный
трехзначный номер из нечетных цифр. Какова максимальное число возможных попыток
угадать пароль?


Задача 3

Группу из
10 человек требуется разбить на две непустые подгруппы

 и

. Сколькими способами можно
это сделать?


Задача 4

Два
наборщика должны набрать 16 текстов. Сколькими способами они могут распределить
эту работу между собой.


Задача 5

Шесть
студентов-переводников нужно распределить по трем группам. Сколькими способами
это можно сделать?


Если вам сейчас не требуется платная помощь с решением задач, контрольных работ и типовых расчетов, но может потребоваться в дальнейшем, то, чтобы не потерять контакт
вступайте в группу ВК
сохраните контакт WhatsApp (+79688494598)
сохраните контакт Телеграм (@helptask) .

Задача 6

Лифт
останавливается на 7 этажах. Сколькими способами могут выйти на этих этажах 6
пассажиров, находящихся в кабине лифта?


Задача 7

В ящике 5
красных и 4 зеленых яблока. Сколькими способами можно выбрать 3 яблока из
ящика?


Задача 8

Из ящика,
в котором лежат 10 красных и 5 зеленых яблок, выбирают одно красное и два
зеленых яблока. Сколькими способами можно это сделать.


Задача 9

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


Задача 10

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


Задача 11

В
телевизионной студии работают 3 режиссера, 4 звукорежиссера, 5 операторов, 7
корреспондентов и 2 музыкальных редактора. Сколькими способами можно составить съемочную
группу, состоящую из одного режиссера, двух операторов, одного звукорежиссера и
двух корреспондентов.


Задача 12

На группу
из 25 человек выделены 3 пригласительных билета на вечер. Сколькими способами
они могут быть распределены (не более одного билета в руки).


Задача 13

Имеются 7
билетов: 3 в один театр и 4 – в другой. Сколькими способами они могут быть
распределены между студентами группы из 25 человек?


Задача 14

Группу из
16 человек требуется разбить на три подгруппы, в первой из которых должно быть
5 человек, во второй – 7 человек, в третьей – 4 человека. Сколькими способами
это можно сделать?

Если вам сейчас не требуется платная помощь с решением задач, контрольных работ и типовых расчетов, но может потребоваться в дальнейшем, то, чтобы не потерять контакт
вступайте в группу ВК
сохраните контакт WhatsApp (+79688494598)
сохраните контакт Телеграм (@helptask) .

На цену сильно влияет срочность решения (от суток до нескольких часов). Онлайн-помощь на экзамене/зачете (срок решения 1,5 часа и меньше) осуществляется по предварительной записи.

Заявку можно оставить прямо в чате ВКонтакте, WhatsApp или Telegram, предварительно сообщив необходимые вам сроки решения и скинув условие задач.

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

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

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

Число перестановок из 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. Сочетания: АВ, АС, СВ

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

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

Алгебра – 9 класс. Комбинаторика

Дата публикации: .

Комбинаторика — знакомство

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

Так что же такое комбинаторика? И какими задачами она занимается? Комбинаторика и слово комбинация очень похожи и имеют прямое отношение друг к другу. В комбинаторике изучают различные комбинации элементов множества и отношения на этих множествах. Впервые термин «комбинаторика» ввел Лейбниц, который в 1666 году опубликовал большой труд «Рассуждения о комбинаторном искусстве».

Примеры использовании комбинаторики

Давайте рассмотрим пример. Сколько чисел можно составить из цифр: 1,2,3?
Нужно найти количество комбинаций из трех чисел. Давайте найдем их. Напрямую переберем все цифры и возможные получающиеся числа. Подойдем к этой задаче осознано и последовательно составим числа от наименьшего к наибольшему.
Очевидно, что наименьшее число будет начинаться с единицы, тогда у нас два варианта: 123, 132. Теперь поставим на первое место цифру два и у нас также два варианта: 213, 231. У нас осталась цифра три: 312, 321. Мы получили шесть комбинаций: 123, 132, 213, 231, 312, 321. Метод, которым мы воспользовались, называется методом перебора, причем перебор организованный: мы брали числа не произвольно, а придумали правило, по которому будем составлять числа.

Пример. Из цифр 1,4,6 составить трехзначные числа, в которых одна цифра не может повторяться более двух раз.
а) Найти наименьшее число.
б) Найти наибольшее число.
в) Сколько чисел, начинающихся с 6, можно составить?
г) Сколько всего чисел можно составить?
Решение.
а) Чтобы получить наименьшее число, нам нужно на первое место поставить наименьшую цифру, потом на второе и третье — соответственно тоже. Наименьшим числом будет 114 так, как самая маленькая цифра у нас единица, и мы ее можем повторить два раза. А из цифр 4 и 6, которые нам надо поставить на третью позицию, очевидно, что 4 меньше 6.
б) Чтобы получить наибольшее число, нам нужно на первое место поставить наибольшую цифру, потом на второе и третье — соответственно тоже. Наибольшим числом будет 664 так, как самая большая цифра у нас 6, и мы ее можем повторить два раза. 4 больше 1, тогда на последнее место и выберем 4.
в) Назовем числа без повторяющихся цифр. Помним, что все числа должны начинаться с 6. 614 и 641 – без повторяющихся цифр. Теперь рассмотрим числа, в которых повторяется шестерка. 661, 664, 616, 646. Повторяется четверка: 644. Повторяется единица: 611. Всего у нас получилось 8 чисел.
г) Для того, чтобы подсчитать общее количество чисел, которые можно составить, применим тот же способ, что и в пункте в). На первое место поставим цифры 1 и 4, тогда у нас получится еще 16 комбинаций. Учтем, числа начинающиеся с шести, и того 24 комбинации.
Также для решения задачи под пунктом в) можно нарисовать дерево вариантов. Давайте так и поступим.

Поместим цифру шесть в верхний прямоугольник, это будет первый уровень дерева. Тогда у нас существует три варианта, куда можно двигаться, соответственно записать — 66, 61 и 62. Таким образом, мы спустились вниз (на один уровень дерева). Далее для каждого из вариантов второго уровня составим возможные комбинации и запишем их в свои ячейки. На третьем уровне у нас получилось восемь ячеек, что и соответствует ответу.

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

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

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

Правила в комбинаторике

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

  • купив билет на остановке,
  • купив билет у кондуктора,
  • воспользоваться проездным.

Сколько существует всего комбинаций проезда и оплаты у Пети?
Решение.
Возможностей проезда у нас — четыре, способов оплаты — три. Тогда по правилу умножения у нас $4*3=12$ комбинаций. Давайте проверим с помощью таблицы все возможные комбинации.

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

Правило умножения приводит к важному понятию факториала. Давайте на примере разберем это понятие.
Пример. Сколько существует комбинаций из шести букв: А, Б, В, Г, Д, Е. Буквы не повторяются.
Решение.
На первое место мы можем поставить шесть букв, на второе место — уже пять, так как буквы не повторяются, на третье — соответственно четыре, на четвертое — три, на пятое — две, и на шестое — букву.
Используем правило умножения: 6*5*4*3*2*1=720.
Ответ: 720 способов расстановки букв без повторения.

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

Заметим важное свойство факториала: $n!=(n-1)!*n$.
Данное свойство значительно упрощает решение задач, где присутствует факториал.
Например, для вычисления задач вот такого типа: $\frac{4!*10!}{8!*3!}$.
Совсем необязательно вычислять все факториалы.
Можно все переписать вот в таком виде: $\frac{3!*4*8!*9*10}{8!*3!}$.
Сократив нашу дробь, получим гораздо более простое выражение: $4*9*10=360$.

Пример.
а) Сколько существует способов развесить на указанные места на елке пять различных шаров?
б) Вове надо выполнить четыре домашних задания: по математике, физике, русскому языку и истории. Сколько существует способов очередности выполнения домашнего задания?
Решение.
а) В нашей задаче шары не повторяются. Тогда на первое место претендуют пять шаров, на второе — уже четыре, на третье — соответственно три, на четвертое — два и на последнее — один.
$5*4*3*2*1=5!=120$.
б) Существует четыре варианта: с какого задания начать. Выполнив первое задание, Вове останется выбрать, что делать дальше из трех заданий, после — из двух и в конце останется только одно задание.
$4*3*2*1=4!=24$.

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

В математике принято называть наше утверждение, как количество перестановок из N элементов без повторений. Обозначают как: $P_{n}=n!$.

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

1. Из цифр 2,7,9 составить двухзначные числа, в которых цифры не повторяются.
а) Найти наименьшее число.
б) Найти наибольшее число.
в) Сколько чисел, начинающихся с 2, можно составить?
г) Сколько всего чисел можно составить?

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

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

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

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

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

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

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

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

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

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

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

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

Пример: № 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 лет.
  • Сколько денег вы сэкономите, не играя? Что можно купить за эти деньги?

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

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

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

  • Получили ли мы головы (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

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

Сводка

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

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

Чтобы построить треугольник, начните с «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 16120  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.

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

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

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

Введение

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

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

Первые комбинаторные задачи изучали математики Древней Индии, Арабских стран и Греции. Интерес к этому предмету возрос в XIX и XX веках, вместе с развитием теории графов и таких проблем, как теорема о четырех цветах. Среди ведущих математиков — Блез Паскаль (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 = количество элементов, которые мы хотим выбрать

Комбинаторика | Безграничная алгебра

Правила и методы подсчета

Комбинаторика — это раздел математики, изучающий конечные или счетные дискретные структуры.

Цели обучения

Описать различные правила и свойства комбинаторики

Основные выводы

Ключевые моменты
  • Правило суммы (правило сложения), правило произведения (правило умножения) и принцип включения-исключения часто используются для целей перечисления.
  • Биективные доказательства используются, чтобы продемонстрировать, что два набора имеют одинаковое количество элементов.
  • Двойной счет — это метод, используемый для демонстрации равенства двух выражений.Принцип ячейки часто устанавливает существование чего-либо или используется для определения минимального или максимального количества чего-либо в дискретном контексте.
  • Генерирующие функции и рекуррентные отношения — мощные инструменты, которые можно использовать для управления последовательностями, и они могут описывать, если не разрешать многие комбинаторные ситуации.
  • Двойной счет — это метод, используемый для демонстрации равенства двух выражений.
Ключевые термины
  • полином : выражение, состоящее из суммы конечного числа членов: каждый член является произведением постоянного коэффициента и одной или нескольких переменных, возведенных в неотрицательную целую степень.
  • комбинаторика : Раздел математики, изучающий (обычно конечные) совокупности объектов, удовлетворяющих указанным критериям.

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

Аспекты комбинаторики включают: подсчет структур данного вида и размера, решение, когда могут быть соблюдены определенные критерии, а также создание и анализ объектов, соответствующих критериям. Аспекты также включают поиск «наибольших», «наименьших» или «оптимальных» объектов, изучение комбинаторных структур, возникающих в алгебраическом контексте, или применение алгебраических методов к комбинаторным задачам.

Комбинаторные правила и методы

Общепризнано и используется несколько полезных комбинаторных правил или комбинаторных принципов.Каждый из этих принципов используется для определенной цели. Правило суммы (правило сложения), правило произведения (правило умножения) и принцип включения-исключения часто используются для целей перечисления. Биективные доказательства используются, чтобы продемонстрировать, что два набора имеют одинаковое количество элементов. Двойной счет — это способ показать, что два выражения равны. Принцип ячейки часто устанавливает существование чего-либо или используется для определения минимального или максимального количества чего-либо в дискретном контексте.Формирующие функции и рекуррентные отношения — мощные инструменты, которые можно использовать для управления последовательностями, и они могут описывать, если не разрешать многие комбинаторные ситуации. Каждый из этих методов более подробно описан ниже.

Правило суммы

Правило суммы — это интуитивный принцип, гласящий, что если есть [латекс] а [/ латекс] возможные способы сделать что-то, и [латекс] b [/ латекс] возможные способы сделать что-то еще, и эти две вещи могут » Если и то и другое будет сделано, то есть [latex] a + b [/ latex] все возможные способы сделать что-то одно.Более формально сумма размеров двух непересекающихся множеств равна размеру объединения этих множеств.

Правило продукта

Правило продукта — это еще один интуитивный принцип, гласящий, что если есть [latex] a [/ latex] способы сделать что-то и [latex] b [/ latex] способы сделать что-то другое, то есть [latex] a \ cdot b [/ latex] способов сделать и то, и другое.

Принцип включения-исключения

Принцип включения-исключения — это метод подсчета, который используется для получения количества элементов в объединении нескольких наборов.Этот метод подсчета гарантирует, что элементы, которые присутствуют более чем в одном наборе в объединении, не будут подсчитаны более одного раза. Он учитывает размер каждого набора и размер пересечения наборов. Самый маленький пример — когда есть два набора: количество элементов в объединении [latex] A [/ latex] и [latex] B [/ latex] равно сумме количества элементов в [latex] A [/ latex] и [latex] B [/ latex], за вычетом количества элементов на их пересечении. См. Схему ниже для примера с тремя наборами.

Биективное доказательство

Биективное доказательство — это метод доказательства, который находит биективную функцию [латекс] f: A \ rightarrow B [/ latex] между двумя конечными наборами [latex] A [/ latex] и [latex] B [/ latex], что доказывает что у них одинаковое количество элементов, [латекс] | A | = | B | [/ латекс]. Биективная функция — это функция, в которой существует взаимно однозначное соответствие между элементами двух множеств. Другими словами, каждый элемент в наборе [latex] B [/ latex] связан ровно с одним элементом в наборе [latex] A [/ latex].Этот метод полезен, если мы хотим узнать размер [латекса] A [/ latex], но не можем найти прямого способа подсчета его элементов. Если [латекс] B [/ латекс] более легко подсчитать, установление биекции от [латекса] A [/ латекса] к [латексу] B [/ latex] решает проблему.

Двойной счет

Двойной счет — это комбинаторный метод доказательства равенства двух выражений. Это делается путем демонстрации того, что два выражения представляют собой два разных способа подсчета размера одного набора.В этой технике конечный набор [latex] X [/ latex] описывается с двух точек зрения, что приводит к двум различным выражениям для размера набора. Поскольку оба выражения равны размеру одного и того же набора, они равны друг другу.

Принцип голубятни

Принцип «ящика» гласит, что если каждый предмет [latex] a [/ latex] помещается в одну из коробок [latex] b [/ latex], где [latex] a> b [/ latex], то по крайней мере один из коробки содержат более одного предмета. Этот принцип позволяет продемонстрировать наличие некоторого элемента в наборе с некоторыми специфическими свойствами.Например, рассмотрим комплект из трех перчаток. {n} [/ latex]

, коэффициенты которого дают последовательность [латекс] \ left \ {a_ {0}, a_ {1}, a_ {2},… \ right \} [/ latex].

Отношение повторения

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

Последовательность Фибоначчи — один из примеров рекуррентного отношения. Каждый член последовательности Фибоначчи определяется как [латекс] F_ {n} = F_ {n-1} + F_ {n-2} [/ latex] с начальными значениями [латекс] F_ {0} = 0 [/ latex ] и [латекс] F_ {1} = 1 [/ латекс].Таким образом, начинается последовательность чисел Фибоначчи:

[латекс] \ displaystyle 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,… [/ latex]

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

Перестановка набора объектов — это расположение этих объектов в определенном порядке; количество перестановок можно подсчитать.

Цели обучения

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

Основные выводы

Ключевые моменты
  • Неформально перестановка набора объектов — это расположение этих объектов в определенном порядке.Например, существует шесть вариантов набора [latex] {1,2,3} [/ latex], а именно [latex] (1,2,3) [/ latex], [latex] (1,3,2 ) [/ латекс], [латекс] (2,1,3) [/ латекс], [латекс] (2,3,1) [/ латекс], [латекс] (3,1,2) [/ латекс] , и [латекс] (3,2,1) [/ латекс].
  • Количество перестановок [latex] n [/ latex] различных объектов равно [latex] n \ cdot (n — 1) \ cdot (n — 2) \ cdots 2 \ cdot 1 [/ latex]. Это называется [латекс] п [/ латекс] факториал и пишется [латекс] п! [/ Латекс].
  • При принятии решения о перестановках подмножества из большего набора часто бывает полезно разделить один факториал на другой, чтобы определить количество возможных перестановок.Например, первые шесть карт из колоды карт будут иметь [латекс] \ frac {52!} {46! } [/ latex] возможных перестановок, или около 14,7 миллиарда.
Ключевые термины
  • факториал : результат умножения заданного количества последовательных целых чисел из [latex] 1 [/ latex] на заданное число. В уравнениях он обозначается восклицательным знаком ([латекс]! [/ Латекс]). Например, [латекс] 5! = 1 \ cdot 2 \ cdot 3 \ cdot 4 \ cdot 5 = 120 [/ латекс].
  • перестановка : упорядочение конечного набора различных элементов.

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

Перестановка набора объектов — это расположение этих объектов в определенном порядке. Например, существует шесть вариантов набора [латекс] {1,2,3} [/ латекс]: [латекс] (1,2,3) [/ латекс], [латекс] (1,3,2) [/ латекс], [латекс] (2,1,3) [/ латекс], [латекс] (2,3,1) [/ латекс], [латекс] (3,1,2) [/ латекс], и [латекс] (3,2,1) [/ латекс]. Можно определить анаграмму слова как перестановку его букв.

6 перестановок 3 шаров: Если у одного есть три шара разного цвета, есть шесть различных способов их упорядочить, как показано.Эти шесть различных порядков следующие: красный-зеленый-синий, красный-синий-зеленый, зеленый-красный-синий, зеленый-синий-красный, синий-красный-зеленый и сине-зеленый-красный.

Количество перестановок [latex] n [/ latex] различных объектов определяется по формуле:

[латекс] \ displaystyle n \ cdot (n — 1) \ cdot (n — 2) \ cdots 2 \ cdot 1 [/ латекс]

Это называется факториалом [латекс] п [/ латекс] и записывается как [латекс] п! [/ Латекс].

Другими словами, факториал — это умножение всех чисел от [latex] 1 [/ latex] до этого числа.Итак, [латекс] 5! [/ Латекс] означает [латекс] 1 \ cdot 2 \ cdot 3 \ cdot 4 \ cdot 5 = 120 [/ latex]. Таким образом, [latex] 120 [/ latex] — это количество перестановок, возможных для набора из пяти различных объектов.

Пример

В игре «Пасьянс» вначале раздаются семь карт: одна лицом вверх, а остальные шесть рубашкой вверх. Полная колода карт состоит из [латексных] 52 [/ латексных] карт. Если предположить, что единственная видимая карта — это [латекс] 7 [/ латекс] пик, сколько возможных «рук» (остальные шесть карт) может быть внизу? Что делает эту проблему перестановкой, так это то, что порядок имеет значение: если туз прячется где-то в этих шести картах, имеет значение, находится ли туз на первой позиции, на второй и т. Д.Проблемы перестановки всегда можно рассматривать как пример правила умножения с одним небольшим поворотом.

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

Сколько карточек может быть на первой позиции, прямо под показом [latex] 7 [/ latex]? Ответ — 51. Эта карта может быть чем угодно, кроме [латекса] 7 [/ латекса] пик.

Если какая-либо карта находится на первой позиции, сколько карт может быть на второй позиции? Ответ [латекс] 50 [/ латекс]. Сданы семерка пик и следующая карта. Так что для второй позиции остались возможные карты.

Итак, сколько возможностей существует для первых двух позиций вместе? Ответ [латекс] 51 \ cdot 50 [/ латекс].

Сколько возможностей существует для всех шести позиций? Ответ: [латекс] 51 \ cdot 50 \ cdot 49 \ cdot 48 \ cdot 47 \ cdot 46 [/ latex], или приблизительно [латекс] 1.{10} [/ латекс]; о [латексе] 13 [/ латексе] миллиардов возможностей!

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

Обратите внимание, что [латекс] \ frac {7!} {5! } [/ latex] также можно записать как [latex] \ frac {1 \ cdot 2 \ cdot 3 \ cdot 4 \ cdot 5 \ cdot 6 \ cdot 7} {1 \ cdot 2 \ cdot 3 \ cdot 4 \ cdot 5 }[/латекс]. Большинство условий отменяют, оставляя только [латекс] 6 × 7 = 42 [/ латекс].

Рассмотрим другой пример, [латекс] \ frac {51!} {45! }[/латекс]. Если все термины выписаны, первые [latex] 45 [/ latex] термины отменяются, оставляя [latex] 46 \ cdot 47 \ cdot 48 \ cdot 49 \ cdot 50 \ cdot 51 [/ latex] в числителе.Вместо того, чтобы вводить в калькулятор шесть чисел для умножения или шестьдесят чисел или шестьсот в зависимости от задачи, ответ на проблему перестановки можно найти, разделив два факториала. По этой причине во многих калькуляторах факториал находится в меню «вероятность».

Общие положения

В математике понятие перестановки используется в нескольких немного разных значениях, и все они связаны с актом перестановки (перестановки) объектов или значений.Неформально перестановка набора объектов — это
расположения этих объектов в определенном порядке. Изучение перестановок обычно относится к области комбинаторики.

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

Перестановки различимых объектов

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

Цели обучения

Подсчитайте количество перестановок [латекс] n [/ латекс] объектов, взятых [латекс] k [/ латекс] за раз

Основные выводы

Ключевые моменты
  • Если все рассматриваемые объекты различны, они могут быть расположены в перестановках [latex] n! [/ Latex], где [latex] n [/ latex] представляет количество объектов.
  • Если не все объекты в наборе уникальных элементов [latex] n [/ latex] выбраны, приведенная выше формула может быть изменена на: [latex] \ displaystyle \ frac {n!} {(N-k)! } [/ latex], где [latex] k [/ latex] представляет количество выбранных элементов.
  • При вычислении частных факториалов члены знаменателя могут сокращаться с членами числителя, таким образом устраняя, возможно, большинство членов, подлежащих умножению.
Ключевые термины
  • факториал : результат умножения заданного количества последовательных целых чисел из [latex] 1 [/ latex] на заданное число.В уравнениях он обозначается восклицательным знаком ([латекс]! [/ Латекс]). Например, [латекс] 5! = 1 \ cdot 2 \ cdot 3 \ cdot 4 \ cdot 5 = 120 [/ латекс].
  • перестановка : упорядочение конечного набора различных элементов.

Напомним, что если все объекты в наборе различны, то они могут быть расположены в [latex] n! [/ Latex] возможных перестановках, где [latex] n [/ latex] представляет количество объектов. Количество [латекс] n! [/ Латекс] определяется по формуле:

[латекс] \ Displaystyle п \ cdot (n-1) \ cdot (n-2) \ cdots 2 \ cdot 1 [/ латекс]

Эту формулу достаточно легко использовать для подсчета числа возможных перестановок набора различных объектов; например, количество перестановок трех разноцветных шаров.Однако рассмотрим ситуацию, когда не все элементы в наборе отдельных объектов используются в каждой перестановке. Например, что, если карты [latex] 7 [/ latex] выбраны из полной колоды [latex] 52 [/ latex]? В этом случае не все карты из колоды выбираются для каждой возможной перестановки. Существует формула для решения проблемы перестановки, подобной этой, которую иначе было бы почти невозможно определить.

Перестановки частичного множества

Если выбраны не все объекты в наборе уникальных элементов, используется следующая формула.Эта формула определяет количество возможных перестановок элементов [latex] k [/ latex], выбранных из набора элементов [latex] n [/ latex]:

[латекс] \ displaystyle \ frac {n!} {(N-k)! } [/ латекс]

Чтобы понять применение этой концепции, рассмотрим гонку, в которой [латекс] 3 [/ латекс] различных призов награждаются лучшими [латексными] 3 [/ латексными] спортсменами. Если в гонке участвуют участники [latex] 25 [/ latex], в каком количестве различных порядков могут быть присуждены призы [latex] 3 [/ latex]?

Чтобы решить эту проблему, мы хотим оценить количество возможных перестановок элементов [latex] 3 [/ latex] из набора элементов [latex] 25 [/ latex]; другими словами, [латекс] k = 3 [/ латекс] и [латекс] n = 25 [/ латекс].Подставляя эти значения в формулу, получаем:

[латекс] \ displaystyle \ frac {25!} {(25–3)! } = \ frac {25!} {22!} [/ latex]

Помните, что и [латекс] 25! [/ Латекс], и [латекс] 22! [/ Латекс] содержат термины [латекс] 22 \ cdot 21 \ cdots 2 \ cdot 1 [/ latex]. Таким образом, эти значения исключаются из числителя и знаменателя, и уравнение можно упростить:

[латекс] [/ латекс]
[латекс] \ displaystyle \ begin {align} \ frac {25!} {22!} & = \ Frac {25 \ cdot 24 \ cdot 23 \ cdot 22 \ cdot 21 \ cdots 2 \ cdot 1} {22 \ cdot 21 \ cdots 2 \ cdot 1} \\ & = 25 \ cdot 24 \ cdot 23 \\ & = 13,800 \ end {align} [/ latex]

Существует 13 800 [/ latex] возможных перестановок, в которых главные призы [latex] 3 [/ latex] могут быть присуждены участникам гонки [latex] 25 [/ latex].

Общие положения

Стоит отметить, что эта формула не исключает того, что мы могли бы назвать «повторяющимися» перестановками. Другими словами, порядок выбранных элементов имеет значение. Рассмотрим [латексные] 3 [/ латексные] карты, взятые из колоды: туз пик, [латекс] 10 [/ латекс] бубен и [латекс] 3 [/ латекс] треф. Рука точно такая же, как следующая: [латекс] 10 [/ латекс] бубен, туз пробелов и [латекс] 3 [/ латекс] треф. Если вы играете в игру, в которой порядок ваших карт не имеет значения , , вам нужно будет подсчитывать каждую перестановку карт только один раз.Представленная здесь формула не применима к таким ситуациям.

[латекс] [/ латекс]

Перестановки неотличимых объектов

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

Цели обучения

Вычислить количество перестановок данного набора объектов, некоторые из которых неразличимы

Основные выводы

Ключевые моменты
  • Некоторые наборы включают повторения определенных элементов.В этих случаях количество возможных перестановок элементов не может быть выражено с помощью [latex] n! [/ Latex], где [latex] n [/ latex] представляет количество элементов, потому что это вычисление будет включать в себя множество возможных состояния.
  • Чтобы исправить множественность определенных перестановок, разделите факториал общего количества элементов на произведение факториалов количества каждого повторяющегося элемента.
  • Выражение для количества перестановок с повторяющимися элементами: [latex] \ frac {n!} {N_1! N_2! N_3!…} [/ Latex], где [latex] n [/ latex] — общее количество терминов в последовательность, а [латекс] n_1 [/ латекс], [латекс] n_2 [/ латекс] и [латекс] n_3 [/ латекс] — это количество повторений различных элементов.
Ключевые термины
  • кратность : количество значений, для которых выполняется данное условие.
  • перестановка : упорядочение конечного набора различных элементов.

Напомним, что количество возможных перестановок набора из [latex] n [/ latex] различных элементов определяется как [latex] n! [/ Latex]:

[латекс] \ Displaystyle п \ cdot (n-1) \ cdot (n-2) \ cdots 2 \ cdot 1 [/ латекс]

Это легко проверить.Число [латекс] 1 [/ латекс] можно расположить всего одним способом [латекс] 1! [/ Латекс]. Номера [latex] 1 [/ latex] и [latex] 2 [/ latex] можно расположить двумя способами [latex] 2! [/ Latex]: [latex] (1,2) [/ latex] и [latex] ] (2,1) [/ латекс]. Номера [латекс] 1 [/ латекс], [латекс] 2 [/ латекс] и [латекс] 3 [/ латекс] могут быть расположены [латекс] 3! [/ Латекс] способами: [латекс] (1, 2,3) [/ латекс], [латекс] (1,3,2) [/ латекс], [латекс] (2,1,3) [/ латекс], [латекс] (2,3,1) [ / латекс], [латекс] (3,1,2) [/ латекс] и [латекс] (3,2,1) [/ латекс]. Это правило справедливо для наборов любого размера, пока все элементы различны.Но что, если некоторые элементы повторяются?

Повторение некоторых элементов усложняет вычисление перестановок, поскольку позволяет использовать несколько способов упорядочивания элементов в определенном порядке. Например, учитывая номера [латекс] 1 [/ латекс], [латекс] 3 [/ латекс] и [латекс] 3 [/ латекс] в наборе, есть 2 способа получить заказ [латекс] (3 , 1,3) [/ латекс].

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

[латекс] \ displaystyle \ frac {n!} {N_1! N_2! N_3!…} [/ Латекс]

Где [latex] n [/ latex] — общее количество терминов в последовательности, а [latex] n_1 [/ latex], [latex] n_2 [/ latex] и [latex] n_3 [/ latex] представляют количество повторений разных элементов.

Чтобы понять, почему мы должны разделить на количество повторов, примите во внимание, что элементы [latex] 2 [/ latex] могут быть расположены в общей сложности [latex] 2! [/ Latex] различными способами, [latex] 3 [/ latex ] элементы могут быть скомпонованы [латексными] 3! [/ латексными] различными способами и так далее.Когда мы сталкиваемся с множественностью в перестановке, мы должны учесть ее, разделив эти возможные расстановки из общего числа перестановок, которые были бы возможны, если бы все элементы были различными.

Пример: Рассмотрим набор чисел:

[латекс] \ displaystyle (15, 17, 24, 24, 28) [/ латекс]

Есть пять терминов, поэтому [латекс] n = 5 [/ латекс]. Однако два термина одинаковы; их стоимость [латекс] 24 [/ латекс]. Таким образом, количество возможных различных перестановок в наборе составляет:

[латекс] \ displaystyle {\ frac {5!} {2! } = 60} [/ latex]

Та же логика применима к более сложным системам.

Пример: Рассмотрим набор:

[латекс] \ displaystyle (0, 0, 0, 2, 4, 4, 7, 7, 7, 7, 7, 8, 8) [/ латекс]

Всего [latex] 13 [/ latex] элементов. Они включают в себя множество повторов: [латекс] 0 [/ латекс] встречается 3 раза, [латекс] 4 [/ латекс] и [латекс] 8 [/ латекс] наблюдается дважды, и есть [латекс] 5 [/ латекс ] экземпляры числа [латекс] 7 [/ латекс]. Таким образом, количество возможных различных перестановок можно рассчитать по формуле:

[латекс] \ displaystyle \ frac {13! } {2! \ Cdot 2! \ Cdot 3! \ Cdot 5! } = 2 162 160 [/ латекс]

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

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

Слово водопад состоит всего из [латексных] 9 [/ латексных] букв, поэтому [латекс] n = 9 [/ латекс]. Буква «а» появляется дважды, что дает значение [латекс] 2 [/ латекс] для [латекс] n_ {1} [/ латекс]. Точно так же буква «l» появляется дважды, что дает [латекс] n_ {2} = 2 [/ latex]. Таким образом, количество различных перестановок букв в «водопаде» можно рассчитать как:

[латекс] \ displaystyle \ frac {9! } {2! \ Cdot 2!} = 90,720 [/ латекс]

Комбинации

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

Цели обучения

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

Основные выводы

Ключевые моменты
  • Комбинация — это математическая концепция, при которой подсчитывается количество способов, которыми можно выбрать несколько элементов из большей группы.
  • В отличие от перестановки, при определении количества комбинаций порядок не имеет значения.
  • Формально, [latex] k [/ latex] -комбинация набора [latex] S [/ latex] является подмножеством [latex] k [/ latex] отдельных элементов [latex] S [/ latex].Если в наборе есть [latex] n [/ latex] элементов, то количество [latex] k [/ latex]-комбинаций равно биномиальному коэффициенту: [latex] \ begin {pmatrix} n \\ k \ end {pmatrix} = \ frac {n (n-1)… (n-k + 1)} {k (k-1)… 1} [/ latex], который можно записать с использованием факториалов как [latex] \ frac {n!} {к! (нк)! } [/ latex] всякий раз, когда [latex] k \ le n [/ latex] и который равен нулю, когда [latex] k> n [/ latex].
Ключевые термины
  • комбинация : способ выбора элементов из набора, где порядок не имеет значения.п [/ латекс].

В математике комбинация — это способ выбора нескольких вещей из большей группы, где (в отличие от перестановок) порядок не имеет значения. В меньших случаях можно подсчитать количество комбинаций. Например, даны [latex] 3 [/ latex] кусочка фруктов: яблоко, апельсин и груша. Из этого набора можно извлечь [latex] 3 [/ latex] комбинации [latex] 2 [/ latex]: яблоко и грушу, яблоко и апельсин или грушу и апельсин.

Комбинации могут относиться к комбинации [латекс] n [/ латекс] вещей, взятых [латекс] k [/ латекс] за один раз с повторением или без него.В приведенном выше примере повторение было запрещено. Если бы, однако, было возможно иметь [латекс] 2 [/ латекс] любого вида [латекс] 1 [/ латекс] фруктов, то было бы [латекс] 3 [/ латекс] больше комбинаций: [латекс] 2 [/ латексные] яблоки, [латексные] 2 [/ латексные] апельсины и [латексные] 2 [/ латексные] груши.

Чтобы понять разницу между перестановкой и комбинацией, рассмотрим колоду из [латексных] 52 [/ латексных] карт, из которой раздается покерная рука ([латексные] 5 [/ латексные] карты). Сколько существует возможных покерных комбинаций?

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

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

Вспомните формулу перестановки: [latex] \ displaystyle {\ frac {n!} {(Nk)!}} [/ Latex], где [latex] n [/ latex] — количество различных объектов в наборе, а [latex] k [/ latex] — количество выбранных объектов.В этом случае мы можем рассчитать количество перестановок как:

[латекс] [/ латекс] [латекс] \ displaystyle \ begin {align} \ frac {52!} {(52-5)!} & = \ Frac {52!} {47!} \\ & = 52 \ cdot 51 \ cdot 50 \ cdot 49 \ cdot 48 \ end {align} [/ latex]

Это дает приблизительно [латекс] 311,9 [/ латекс] миллиона возможных покерных рук. Однако в этом подсчете нужно много раз пересчитывать все возможные руки. Сколько раз подсчитывается каждая отдельная рука?

Ключевым моментом является ответ на второй вопрос: «Сколько раз можно считать каждую отдельную руку?» сам по себе вопрос перестановки.Это то же самое, что и вопрос «Сколько разных способов переставить эти пять карт в руке?» Возможности [latex] 5 [/ latex] для первой карты, [latex] 4 [/ latex] для второй и так далее. Ответ — [латекс] 5! [/ Латекс], то есть [латекс] 120 [/ латекс]. Итак, поскольку каждая возможная рука была подсчитана [латекс] 120 [/ латекс] раз, разделите наш предыдущий результат на [латекс] 120 [/ латекс], чтобы найти [латекс] \ frac {52!} {(47! ) (5!)} [/ Latex], или примерно [latex] 2,6 [/ latex] миллиона возможных покерных комбинаций.

У комбинаций

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

  • Школа предлагает 50 классов [/ латекса]. Каждый ученик должен выбрать [латекс] 6 [/ латекс] из них, чтобы заполнить расписание. Сколько возможных графиков можно составить?
  • В баскетбольной команде есть [латекс] 12 [/ латекс] игроков, но только [латекс] 5 [/ латекс] будут стартовать. Сколько возможных стартовых команд они могут выставить?
  • На вашем компьютере есть [latex] 300 [/ latex] видео, но вы можете разместить на телефоне только [latex] 10 [/ latex] из них.Сколько возможных способов загрузить свой телефон?

Каждый из этих вопросов представляет собой комбинацию вопросов, на которые можно ответить точно так же, как в карточном сценарии. Поскольку этот тип вопросов возникает в очень разных контекстах, ему дается особое имя и символ. Последний вопрос будет называться «[латекс] 300 [/ латекс] выбрать [латекс] 10 [/ латекс]» и писать [латекс] \ begin {pmatrix} 300 \\ 10 \ end {pmatrix} [/ latex] .

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

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