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

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

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

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

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

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

Презентация к уроку

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

Цели урока:

  • Образовательные: создать организационные и содержательные условия для формирования умений решения комбинаторных задач методом перебора возможных вариантов решения геометрическим способом (дерево решений), с применением правила умножения;
  • Развивающие: развитие логического мышления, умений анализировать, сравнивать, сопоставлять, делать выводы;
  • Воспитательные:
    • Владение интеллектуальными умениями и мыслительными операциями.
    • Воспитание трудолюбия, целеустремленности, положительного отношения к предмету.
    • Используемые технологии: технология коллективного взаимодействия, информационно-коммуникационные технологии, проблемное обучение.

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

      Формы работы: фронтальная, самостоятельная, работа в группе.

      Прогнозируемый результат (формируемые УУД)

      Предметные:

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

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

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

            • Уметь вести диалог на основе взаимного уважения. Уметь высказывать и обосновывать своё мнение, учитывать мнение других при поиске решения.
            • Личностные:

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

                • ПК, интерактивная доска, презентация к уроку.
                • Пакеты с индивидуальными и групповыми заданиями.
                • Элементы комбинаторики. Правила умножения и сложения (стр. 1 из 5)

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

                  Комбинаторика – раздел математики, в котором изучаются задачи выбора элементов из заданного множества и расположения их в группы по заданным правилам, в частности задачи о подсчете числа комбинаций (выборок), получаемых их элементов заданного множества. В каждой из них требуется подсчитать число возможных вариантов осуществления некоторого действия, ответить на вопрос: «Сколькими способами?» Многие комбинаторные задачи могут быть решены с помощью следующих 2х важных правил, называемых соответственно правилами умножения и сложения.

                  Если из нек множ первый объект (элемент х) можно выбрать n1 способами и после каждого такого выбора второй объект (элем у) можно выбр n2 способами, то оба объекта (х и у) в указ порядке можно выбрать n1*n2 способами.

                  Это правило распр-ся на случай трех и более объектов.

                  Пример : сколько трехзначных чисел можно составить из цифр 1,2,3,4,5, если: а) числа не повт; б) числа могут повтор.

                  Решение: а) 1ую цифру выбираем 5мя способами, 2ую – 4мя, 3 – 3мя 5*4*3=60 способов

                  б) 5*5*5=125 сособов

                  Если некот объект х можно выбр n1 способами, а объект у можно выбр n2 способами, причем первые и вторые выборы таковы, что они взаимно искл друг друга и не могут быть получены одновременно, то объект хUу (х или у) можно выбр n1+n2 способами.

                  Пример : Четыре города M,N,P,K соединены дорогами так, что из Mв Nведут 5дорог, из N в K– 6 дорог, из M в P ведут 4 дороги, из P в К – 3 дороги.

                  Сколькими способами можно проехать из М в К?

                  Решение: Из М в К через N ведут 5*6=30 дорог, Из М в К через P ведут 4*3=12 дорог

                  Из М в К ведут 30+12=42 дороги.

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

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

                  Если элементы комбинации не повторяются.

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

                  Размещения с повторениями обозначаются Ã и вычисляются по формуле:

                  Примеры в 1ом вопросе!

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

                  Пример: Имеется 5 равных геом фигур: 3 желтых и 2 белых круга. Сколько различных узоров можно составить из этих кругов, располагая их в ряд?

                  Решение: Желтые круги будут повт 2! раз

                  Число разл узоров будет равно 5!/2!*3!=10

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

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

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

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

                  Обозначается – Č и вычисл по форм:

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

                  Бином Ньютона – это формула, представляющая выражение

                  Её можно записать иначе:

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

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

                  Любой элемент треугольника паскаля, распол в n-ой строке на k-ом месте выражает

                  Где отчет nведется от 1, а отчет k ведется от 0.

                  Пример : Представить в виде многочлена

                  4. Булевы функции. Определение. Примеры.

                  Алгебра логики, выстроенная в XIX веке, долго существовала как абстрактная, хотя и очень красивая наука. Но в середине XX века оказалось, что она имеет конкретное и очень важное применение в современной жизни. Булева алгебра в настоящее время служит основой для описания логики работы аппаратных и программных средств ЭВМ. Она ис­пользует логические переменные, которые принимают лишь два значения 0 и 1. Аналогично и ЭВМ использует лишь сигналы 0 и 1, воспринимая их как логические переменные.

                  Рассмотрим множество В = <0;1>.

                  Каждому элементу множества В n поставим в соответствие единст­венный элемент множества В — <0; 1>. Полученное соответствие наз булевой функцией . Элементы множества В n являются значениями аргумента булевой функции. Они представляют собой наборы, состоящие из нулей и единиц, и называются кортежами. Длиной кортежа назы­вается число цифр, образующих кортеж. Множество В n — область определения функции

                  Множества значений булевой функции, вообще говоря это значение функции В = <0;1>.

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

                  Геометрическая интерпретация отражает геометрический способ задания булевых функций.

                  Область определения D ( f ) булевой функции n = 1 это совокупность двух точек 0 и 1 числовой прямой, т.е. одномерного куба

                  Если п = 2, то D ( f ) = <00,01,10,11>— это множество вершин квадрата, т. е. двухмерного куба

                  множество вершин трёхмерного куба в декартовой системе координат.

                  На кортежах длины n можно составить

                  Если n=1, то число простейших булевых функций равно 4, если n=2, то их 16, если n=3, то их 256

                  Если n=1, то существует 4 простейших булевых функций:

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

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

                  Правило умножения (принцип умножения, правило «и»):

                  пусть имеется две группы элементов,

                  если элемент из первой группы можно выбрать k1 способами,

                  после чего элемент из второй группы – k2 способами,

                  то общее число комбинаций N из двух элементов будет

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

                  Решение: Очевидно, число групп равно двум, (т.к. составляем пары)

                  k 1=14 ( т.к. для выбора элемента первой группы имеется 14 вариантов),

                  k 2=10 (т.к. для выбора элемента второй группы имеется 10 вариантов ),

                  Согласно правила умножения, получаем общее количество различных вариантов:

                  N = k 1 k 2 = 14*10 = 140 пар.

                  Замечание. Если в качестве первого элемента взять девушку, то ответ не изменится: от перестановки множителей произведение не меняется!

                  Покажем, что правило умножения допускает обобщение на случай n групп элементов:

                  N = k n

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

                  Решение: Определяем число групп — очевидно число групп равно трем, т.к. число призовых мест равно трем.

                  k 1=24 ( т.к. для выбора лучшей работы имеется 24 варианта),

                  k 2=23 (т.к. для выбора второй работы имеется 23 варианта ),

                  k 3=22 (т.к. для выбора третьей работы имеется 22 варианта).

                  N = k 1 k 2 k 3= 24*23*22 = 12144

                  Пример 3. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?

                  Решение: Определяем число групп — очевидно число групп равно трем, т.к. числа трехзначные.

                  k 1=6 (т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6),

                  k 2=7 (т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5, 6),

                  k 3=4 (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4, 6).

                  Согласно правила умножения, получаем ответ: N = k 1 k 2 k 3= 6*7*4 = 168

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

                  1.1 0 .Имеется 5 видов конвертов без марок и 4 вида марки. Сколькими способами можно выбрать конверт и марку для посылки письма?

                  1.2 0 .При составлении одного варианта письменной контрольной работы по математике преподаватель располагает 4 задачами по геометрии, 8 – по алгебре и 3 – по тригонометрии. Сколькими способами можно составить этот вариант, если в него должно войти по одной задаче из перечисленных разделов?

                  1.3 0 .Из двух полуфинальных групп, каждая их которых содержит по 6 команд, в финал выходит по одной команде. Сколько может быть различных вариантов участников финального матча?

                  1.4 0 .В забеге участвуют 5 спортсменов. Сколькими способами могут распределиться места в результате забега?

                  1.5 0 .В книге из 20 страниц на каких-либо трех страницах надо поместить по одно иллюстрации. Сколькими способами это можно сделать?

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

                  1.7.Имеется 9 белых, 12 красных и 11 синих шаров. Скольким способами можно разложить эти шары по двум урнам так, чтобы каждая урна содержала не менее четырех шаров каждого цвета?

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

                  Разделы: Математика

                  Образовательные: К концу урока учащиеся должны:

                  • Иметь представление о переборе всех возможных вариантов, о простейших комбинаторных задачах, о дереве возможных вариантов, о правиле умножения;
                  • Уметь решать простейшие комбинаторные задачи, используя правило умножения и правило деления для комбинаторных задач;
                  • Знать о переборе всех возможных вариантов, о комбинаторных задачах, о дереве возможных вариантов, о правиле умножения.
                  • формированию познавательного интереса к предмету;
                  • воспитанию чувства патриотизма.
                • развитию речи; творческого мышления;
                • развитию умения излагать информацию, интерпретируя факты, разъясняя значение и смысл теории.

                I. Актуализация знаний

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

                В пятом классе мы с вами уже познакомились с достоверными, невозможными и случайными событиями. Познакомились с простейшими комбинаторными задачами, т.е. задачами в которых приходилось осуществлять перебор всех возможных вариантов, или как говорят в таких случаях, всех возможных комбинаций. Слово «комбинаторика» происходит от латинского combino – соединяю. Давайте вспомним основные теоретические положения:

                1. Какие задачи называются комбинаторными? (задачи в которых осуществляют перебор всех возможных вариантов);
                2. Как называется раздел математики, занимающийся поисками ответов на вопросы: сколько всего есть комбинаций в том или ином случае, как из всех этих комбинаций выбрать наилучшую? (комбинаторика);
                3. Может ли комбинаторика помочь в реальной жизни?
                4. Как часто вы комбинируете в реальной жизни?
                5. Каким способом вы умеете решать комбинаторные задачи?
                  («дерево» вариантов);
                6. В чем заключается метод решения задач по «дереву » вариантов?

                II. Изучение нового материала

                Давайте вспомним один из способов решения комбинаторных задач.

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

                Какой способ вы использовали в 5-м классе для решения такой задачи?

                (построение «дерева» возможных вариантов).

                Построим «дерево» вариантов и ответим на вопрос задачи. (Учащиеся работают в группах, затем правильность выполнения работы проверяется на слайде 1)

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

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

                Вопрос на который вы должны знать ответ: какой из представленных на рисунке флагов является Государственным флагом России? (Российский флаг «триколор» выделен на этой схеме).

                Что означает каждый цвет флага? Белый цвет означает мир, чистоту, совершенство; синий – цвет веры и верности; красный – энергию, силу, кровь, пролитую за Отечество.

                «Дерево» вариантов можно считать геометрической моделью рассматриваемой ситуации.

                Рассмотрим вторую задачу: Сколько двузначных чисел можно составить из цифр 0, 1, 2, 3, 4?

                (Учащиеся работают в группах несколько минут).

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

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

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

              • Какая цифра у интересующих нас двузначных чисел на первом месте (цифра десятков) может находиться?
              • Ответ: Любая из заданных цифр кроме цифры 0. Не существует двузначного числа, начинающегося с цифры 0.

                Слово учителя: Значит, цифрой десятков может служить одна из цифр 1, 2, 3 или 4. Поэтому в первой группе только 4 «ветви».

              • Сколько вариантов для цифры единиц возможно для каждого из этих случаев?
              • Ответ: Возможны пять вариантов – 0, 1, 2, 3, 4.

                Всего получаем 4•5 = 20 вариантов.

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

                Слово учителя: Сформулируем правило умножения.

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

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

                У Насти 3 брюк и 5 блузок, удачно сочетающихся по цвету. Сколько различных комбинаций одежды она может составить? (3*5=15)

                В 5-м классе в субботу 4 урока: математика, русский язык, информатика и музыка. Сколько можно составить вариантов расписания в субботу? (4*3*2*1=24).

                III. Выполнение упражнений

                В списке учеников 6-го класса 15 девочек и 13 мальчиков. Нужно выбрать двух дежурных по классу. Сколькими способами это можно сделать: а) при условии, что пару дежурных обязательно должны составить мальчик и девочка, б) без указанного условия?

                А) Для выбора девочки в качестве дежурного есть 15 вариантов. Если девочка дежурной назначена, то имеется 13 вариантов выбора мальчика в качестве второго дежурного.

                Всего: 15*13= 195 способов.

                Ответ: 195 способов.

                Б) Для выбора первого дежурного имеется 28 способов. Для каждого из них существует 27 способов выбора второго дежурного.

                Всего 28*27 = 756 способов.

                Но среди этих 756 пар есть одинаковые пары. Для простоты рассуждений перенумеруем учеников (в списке каждому ученику присваивается номер). Тогда ясно, что например, пара «ученик №1, ученик №2» и пара «ученик №2 , ученик №1» это одна и та же пара. Таким образом, мы каждую пару посчитали дважды. Значит, полученный результат надо уменьшить вдвое: 756:2= 378

                Ответ: 378 способов.

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

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

                Давайте сравним известные вам способы решения комбинаторных задач.

                Рубрикатор

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

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

                Комбинато́рика (Комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике).Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».Сформулируем несколько простых и очевидных правил комбинаторики.Правило сложенияПусть в множестве А имеется m элементов, а в множестве В – n элементов. Если у множеств А и В нет общих элементов, то в их объединении число элементов равно Можно сказать так, что если в двух мешках лежат разные предметы, и мы ссыпаем их вместе, то, чтобы найти их общее количество, надо сложить количества предметов в каждом из мешков.Если для конечного множества Х мы через |Х| обозначим количество его элементов, то правило сложения можно записать так:Если то Это правило несложно обобщается на случай, когда у множеств А и В есть общая часть.Правило умноженияЧисло пар, составленных из элементов множеств А и В, равно произведению количеств элементов этих множеств.Множество пар элементов двух множеств часто обозначают с помощью знака произведения. Тогда правило умножения можно записать так: Правило умножения легко пояснить с помощью таблицы. Если мы составим прямоугольную таблицу и занумеруем (обозначим) ее строчки элементами множества А, а столбцы – элементами множества В, то клетки таблицы будут соответствовать парам где Число клеток таблицы очевидно равно произведению числа строк и числа столбцов.Примеры.1. Рассмотрим произведение Сколько одночленов (до приведения подобных) получится при умножении «скобки на скобку»?Этот же вопрос можно переформулировать так: сколько пар можно составить из одночленов первой и второй скобок? В первой скобке выберем любой из трех одночленов, во второй – любой из шести. Число пар равно В этом примере используется правило умножения.

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

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

                Основная формула комбинаторики

                Пусть имеется k групп элементов, причем i-я группа состоит из ni элементов. Выберем по одному элементу из каждой группы. Тогда общее число N способов, которыми можно произвести такой выбор, определяется соотношением N=n1*n2*n3*. *nk.

                Пример. Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из n1 элементов, а вторая — из n2 элементов. Сколько различных пар элементов можно составить из этих двух групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить n2. Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет n2. Так как в первой группе всего n1 элемент, всего возможных вариантов будет n1*n2.

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

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

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

                Пример. Различными размещениями из трех элементов <1, 2, 3>по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком.

                Число размещений в комбинаторике обозначается Anm и вычисляется по формуле:

                Замечание: n!=1*2*3*. *n (читается: «эн факториал»), кроме того полагают, что 0!=1.

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

                Решение: т.к. нечетных цифр пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:

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

                Пример . Для множества <1, 2, 3>сочетаниями являются <1, 2>, <1, 3>, <2, 3>.

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

                Число сочетаний обозначается Cnm и вычисляется по формуле:

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

                Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:

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

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

                Пример. Всевозможными перестановками множества, состоящего из трех элементов <1, 2, 3>являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).Число различных перестановок из n элементов обозначается Pn и вычисляется по формуле Pn=n!.

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

                Решение: эта задача о числе перестановок семи разных книг. Имеется P7=7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.

                Основные понятия алгебры случайных событий: «случайный эксперимент», «случайное событие», «элементарное событие», «пространство элементарных событий», «достоверное событие», «невозможное событие»

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

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

                Множество всех подмножеств на множестве исходов формирует множество (алгебру) событий.

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

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

                Событие, которое нельзя разбить на элементы называется элементарным.

                Событие, которое в данных условиях всегда происходит называется достоверным

                Событие, которое в данных условиях никогда не происходит называется невозможным

                Все элементарные события, в сумме составляющие достоверное образуют пространство элементарных событий. При однократном бросании одной кости пространство элементарных событий содержит 6 элементов, при одновременном бросании двух костей — 36 элементов (всевозможные сочетания числа очков на первой и второй кости), при попадании стрелы в мишень пространство элементарных событий содержит бесконечное множество точек мишени. На рисунках 1 и 2 пространство элементарных событий (достоверное событие) условно обозначено прямоугольником, ограниченным тонкой черной линией и, следовательно содержит все точки этого прямоугольника.

                Основные операции алгебры случайных событий. Аксиомы и теоремы алгебры событий

                Определение 1.1. Суммой А+В двух событий А и В называют событие, состоящее в том, что произошло хотя бы одно из событий А и В. Суммой нескольких событий, соответ-ственно, называется событие, заключающееся в том, что произошло хотя бы одно из этих событий.

                Пример 1. Два стрелка делают по одному выстрелу по мишени. Если событие А – попадание первого стрелка, а событие В – второго, то сумма А+В – это хотя бы одно попадание при двух выстрелах.

                Пример 2. Если при броске игральной кости событием Аi назвать выпадение i очков, то выпадение нечетного числа очков является суммой событий А1+А2+А3.

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

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

                Пример 3. В примере 1 ( два выстрела по мишени) событием АВ будет попадание обоих стрелков.

                Пример 4. Если событие А состоит в том, что из колоды карт извлечена карта пиковой масти, а событие В – в том, что из колоды вынута дама, то событием АВ будет извлечение из колоды дамы пик.

                Определение 1.3. Разностью А\B событий А и В называется событие, состоящее в том, что А произошло, а В – нет.

                Пример 5. Вернемся к примеру 1, где А\ В – попадание первого стрелка при промахе второго.

                Пример 6. В примере 4 А\В – извлечение из колоды любой карты пиковой масти, кроме дамы. Наоборот, В \А – извлечение дамы любой масти, кроме пик.

                Аксиома 1. Каждому событию соответствует неотрицательное число — вероятность этого события P(A).

                Аксиома 2. Вероятность достоверного события равна 1.

                Аксиома 3. Вероятность объединения несовместных событий равна сумме их вероятностей, т. е.

                Это верно как для конечного числа событий , так и для бесконечного (счетного) множества событий.

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

                Вероятность события A Î T есть, как уже говорилось, число. Поэтому вероятность можно трактовать как функцию, ставящую в соответствие некоторому событию определенное число P(A). Функцию P(A), удовлетворяющую Аксиоме 3, называют аддитивной, или счетно-аддитивной, если множество событий бесконечно (часто пишут также «s-аддитивна»). Счетно-аддитивная функция множества называется мерой. В силу Аксиомы 1 и Аксиомы 3 вероятность P(A) представляет собой неотрицательную s-аддитивную функцию множества, т. е. неотрицательную меру.

                Пространство элементарных событий W с заданной на нем алгеброй или s-алгеброй множеств T и определенной на T вероятностью — неотрицательной мерой P(A), , называется вероятностным пространством и обозначается (W, T, P). Можно говорить, что математической моделью любого случайного явления в современной теории вероятностей служит вероятностное пространство.

                Теорема сложения вероятностей.

                Теорема 2.1 (теорема сложения). Вероятность р(А + В) суммы событий А и В равна

                Р (А + В ) = р (А) + р (В) – р (АВ).

                Докажем теорему сложения для схемы случаев. Пусть п – число возможных исходов опыта, тА – число исходов, благоприятных событию А, тВ – число исходов, благопри-ятных событию В, а тАВ – число исходов опыта, при которых происходят оба события (то есть исходов, благоприятных произведению АВ). Тогда число исходов, при которых имеет место событие А + В, равно тА + тВ – тАВ (так как в сумме (тА + тВ) тАВ учтено дважды: как исходы, благоприятные А, и исходы, благоприятные В). Следовательно, вероятность суммы можно определить по формуле (1.1):

                что и требовалось доказать.

                Следствие 1. Теорему 2.1 можно распространить на случай суммы любого числа событий. Например, для суммы трех событий А, В и С

                Р(А + В + С) = р(А) + р(В) + р(С) – р(АВ) – р(АС) – р(ВС) + р(АВС)

                Следствие 2. Если события А и В несовместны, то тАВ = 0, и, следовательно, вероятность суммы несовместных событий равна сумме их вероятностей:

                Определение 2.1. Противоположными событиями называют два несовместных события, образующих полную группу. Если одно из них назвать А, то второе принято обозначать .

                Замечание. Таким образом, заключается в том, что событие А не произошло.

                Теорема 2.2. Сумма вероятностей противоположных событий равна 1:

                Так как А и образуют полную группу, то одно из них обязательно произойдет в результате опыта, то есть событие А + является достоверным. Следовательно,

                Р( А +) = 1. Но, так как А и несовместны, из (2.4) следует, что Р(А +) = р(А) + р(). Значит, р(А) + р() = 1, что и требовалось доказать.

                Теорема умножения вероятностей.

                Определение 2.2. Назовем условной вероятностью р(В/А) события В вероятность события В при условии, что событие А произошло.

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

                р (АВ) = р (А) · р (В/А).

                Воспользуемся обозначениями теоремы 2.1. Тогда для вычисления р(В/А) множеством возможных исходов нужно считать тА (так как А произошло), а множеством благоприятных исходов – те, при которых произошли и А, и В ( тАВ ). Следовательно,

                откуда следует утверждение теоремы.

                Пример. Для поражения цели необходимо попасть в нее дважды. Вероятность первого попадания равна 0,2, затем она не меняется при промахах, но после первого попадания увеличивается вдвое. Найти вероятность того, что цель будет поражена первыми двумя выстрелами.

                Решение. Пусть событие А – попадание при первом выстреле, а событие В – попадание при втором. Тогда р (А) = 0,2, р (В/А) = 0,4, р (АВ) = 0,2·0,4 = 0,08.

                Следствие. Если подобным образом вычислить вероятность события ВА, совпадающего с событием АВ, то получим, что р (ВА) = р (В) · р (А/В). Следовательно,

                р (А) · р (В/А) = р (В) · р (А/В).

                Классическое определение вероятности. Свойства вероятности.

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

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

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

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

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

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

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

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

                Свойство 3. Вероятность наступления событий, образующих полную группу, равна единице.

                Свойство 4. Вероятность наступления противоположного события определяется так же, как и вероятность наступления, события :

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

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

                Пример 1. Набирая номер телефона, абонент забыл одну цифру и набрал ее наудачу. Найти вероятность того, что набрана нужная цифра.

                Решение. Обозначим событие, состоящее в том, что набрана нужная цифра. Абонент мог набрать любую из 10 цифр, поэтому общее число возможных исходов равно 10. Эти исходы единственно возможны (одна из цифр набрана обязательно) и равновозможны (цифра набрана наудачу). Благоприятствует событию лишь один исход (нужная цифра лишь одна). Искомая вероятность равна отношению числа исходов, благоприятствующих событию, к числу всех исходов:

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

                Правило умножения, иначе называемое правилом «и» — одно из основных правил комбинаторики. Согласно ему, если элемент A можно выбрать n способами и, при любом выборе A (то есть независимо), элемент B можно выбрать m способами, то пару (A, B) можно выбрать n*m способами. Естественным образом обобщается на произвольную длину последовательности.

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

                Содержание

                Выбрать книгу и диск из 10 книг и 12 дисков можно способами. Правило сложения

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

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

                Пусть требуется найти количество слов, составленных не более, чем из 3 букв алфавита . Количество n-буквенных слов равно количеству размещений из 4 букв на n мест с повторениями — оно равно 4 n . Количество всех слов (так как нужно учитывать любое из слов) будет складываться из количеств одно-, двух- и трёхбуквенных слов. Тогда ответ на первоначальный вопрос будет 4 1 + 4 2 + 4 3 = 84 .

                Wikimedia Foundation . 2010 .

                Смотреть что такое «Правило умножения (комбинаторика)» в других словарях:

                Правило сложения (комбинаторика) — Правило сложения (правило «или») одно из основных правил комбинаторики, утверждающее, что, если элемент A можно выбрать n способами, а элемент B можно выбрать m способами, то выбрать A или B можно n + m способами. Содержание 1 Примеры 1.1 Пример… … Википедия

                Правило умножения — (правило «и») одно из основных правил комбинаторики. Согласно ему, если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару (A, B) можно выбрать n·m способами. Естественным образом… … Википедия

                История арифметики — Арифметика. Роспись Пинтуриккьо. Апартаменты Борджиа. 1492 1495. Рим, Ватиканские дворцы … Википедия

                Арифметика — Ганс Себальд Бехам. Арифметика. XVI век Арифметика (др. греч. ἀ … Википедия

                Дифференциальная алгебра — Дифференциальными кольцами, полями и алгебрами называются кольца, поля и алгебры, снабжённые дифференцированием унарной операцией, удовлетворяющей правилу произведения. Естественный пример дифференциального поля поле рациональных… … Википедия

                Математика в Древнем Египте — Данная статья часть обзора История математики. Статья посвящена состоянию и развитию математики в Древнем Египте в период примерно с XXX по III век до н. э. Древнейшие древнеегипетские математические тексты относятся к началу II… … Википедия

                Вавилонская математика — Данная статья часть обзора История математики. Вавилонская табличка с вычислением = 1.41421296. Вавилоняне писали … Википедия

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

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

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

                Смотрите так же:

                • Документы на оформление детских пособий от 3 лет Ежемесячные пособия на ребенка после трех лет Порядок начисления и ежемесячной выплаты пособий на ребенка старше 3-х лет определяется требованиями ст. 16 Федерального закона от 19 мая 1995 года № 81-ФЗ «О государственных пособиях гражданам, имеющим детей». […]
                • Штраф за неуплату единого налога 2018 Налоговая ответственность за неуплату налогов в 2017–2018 годах Налоговая ответственность включает совокупность наказаний, предусмотренных НК РФ. Подборка материалов данной рубрики расскажет вам о налоговой ответственности плательщиков и налоговых агентов и […]
                • Акт проверки по транспортному налогу 29 января 2018 года организация подала декларацию по транспортному налогу. 16 февраля 2018 года налоговый орган выслал требование о предоставлении пояснений: при заполнении декларации по транспортному налогу применена ставка для легкового автомобиля, а […]
                • Кто определяет размер госпошлины Госпошлина при вступлении в наследство «Какие расходы придется понести при оформлении наследства?» — интересуются наследники. Вот уже 10 лет, как с наследников снята обязанность по оплате налога за унаследованное имущество. В 2005 году Госдумой РФ был […]
                • В каких числах перечисляют пособия в москве В каких числах перечисляют ежемесячные детские пособия? В каких числах перечисляют детские пособия? Этот и другие вопросы, касающиеся сроков и графика перечислений, процедуры и нюансов платежей, интересуют не только родителей, но и работников бухгалтерии, […]
                • Постановление конституционного суда рф о толковании отдельных положений российской конституции Конституционный Суд Российской Федерации о Конституционных (Уставных) судах субъектов Российской Федерации Постановления Конституционного Суда Российской Федерации "По делу о проверке конституционности отдельных положений Федерального закона "Об общих […]
                • Санитарные положения в приказе Приказ 493 Об утверждении Положения о Департаменте охраны здоровья и санитарно-эпидемиологического благополучия человека Министерства здравоохранения и социального развития Российской Федерации Приказ Министерства здравоохранения и социального развития РФ от […]
                • Заявление об увольнении в связи с призывом в армию Увольнение в связи с призывом Актуально на: 10 октября 2016 г. Иногда случается так, что и работодателя полностью устраивает работник, и сам сотрудник доволен своей работой, но им все же приходится расстаться. В трудовом законодательстве это называется […]