Правило суммыправило произведения

Правило суммыправило произведения

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

Правило суммы. Если некоторый объект можно выбрать способами, а другой объект можно выбрать способами, то выбор «либо , либо » можно осуществить способами.

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

Пусть = <, , . >, = <, , . > и А — число элементов множества . Составим декартово произведение множеств и , т.е. множество пар (, .

Тогда правило произведения записывается следующим образом:

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

Решение. Поскольку в двузначном числе цифра, обозначающая число десятков, должна быть отлична от нуля, то = <1, 2, . 9>, = <0, 1, 2, . 9>и

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

Число размещений из элементов по обозначим Используя основное правило комбинаторики, получаем

Если , то — число таких размещений, которые отличаются только порядком расположения элементов. Такие размещения называются перестановками. Их число находится по формуле

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

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

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

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

Решение. При проведении турнира по круговой системе каждый участник встречался с каждым и порядок их вхождения в пару не важен. Следовательно, по круговой системе потребуется провести встреч, а по олимпийской только — 7 (четыре встречи в финала, две — в полуфинале и одна в финале).

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

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

Число перестановок , в которых 1-й элемент повторяется раз, 2-й — раз, а -й — раз, находится следующим образом:

Пример 9. Сколько «слов» можно получить, переставляя буквы в слове МАТЕМАТИКА?

Решение. Заметим, что если бы все буквы были различны, то получили бы новых «слов», но буква «М» употребляется в «слове» 2 раза, «А» — 3 раза, «Т» — 2 раза, оставшиеся три буквы — по разу. Следовательно, искомое число будет в раз меньше, чем , и равно

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

Пример 10. В кафе в продаже имеются 5 сортов пирожных. Сколькими способами 8 студенток могут заказать себе по одному пирожному?

Решение. Зашифруем каждую покупку 8 пирожных единицами по 5 сортам, разделяя сорта нулями. Тогда каждой покупке будет соответствовать упорядоченный набор из 8 единиц и 4 (= 5 — 1) разделительных нулей, а общее число покупок будет соответствовать числу перестановок этих нулей и единиц . Таким образом,

Вопросы для самоконтроля

  1. Основные правила комбинаторики и их иллюстрация на графе.
  2. Порядок решения комбинаторных задач.
  3. Приведите примеры размещений и перестановок без повторений.
  4. Свойства сочетаний без повторений.
  5. Как получить треугольник Паскаля, и где он применяется?
  6. Приведите примеры выборок с повторениями.
  7. Каких выборок больше: с повторениями или без повторений?
  8. Что понимают под словом длины над алфавитом ?

I 11. В чемпионате России по футболу участвуют 16 команд. Сколькими способами может определиться тройка призеров?

12. Из колоды, содержащей 36 карт, вынули 10 карт. Сколькими различными способами это можно сделать? В скольких случаях среди этих карт окажется хотя бы один туз? В скольких случаях окажется ровно один туз?

13. Сколькими способами 8 человек могут встать в очередь друг за другом?

14. Сколькими способами можно расставить на книжной полке 5 учебников по комбинаторике, 4 — по алгебре и 3 — по математическому анализу, если учебники по каждому предмету одинаковые?

15. На физмате работают 76 преподавателей. Из них 49 знают английский язык, 32 — немецкий и 15 — оба языка. Сколько преподавателей на физмате не знает ни английского, ни немецкого языков?

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

II 17. В азбуке Морзе буквы представляются последовательностями тире и точек. Сколько символов потребуется, чтобы закодировать буквы русского алфавита?

18. Какова вероятность выиграть хотя бы один из призов в спортлото?

III 19. Доказать с помощью комбинаторных рассуждений тождество

cito-web.yspu.org

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

Правило суммы заключается в следующем. Если объект A можно выбрать m способами, а другой объект B можно выбрать n способами, тогда выбор «Объект А или объект В» можно выполнить m+n способами. Аналогично в теории множеств количество элементов объединения непересекающихся множеств равно сумме количеств элементов в каждом из множеств. Правило суммы очевидным способом обобщается на несколько типов объектов.

Пример. Мы можем добраться до центра города одной из 5 маршруток, одним из 3 автобусов, или одним троллейбусом. Сколько есть способов добраться? Ответ: 5 + 3 + 1 = 9.

Замечание. Требуется следить за тем, чтобы выбор A и выбор B был взаимоисключающим. Допустим, пусть в студенческой группе 5 человек шарят в английском, 4 в немецком, шарящих в других иностранных языках нет. Сколько человек в группе шарят в английском или немецком? Ответ: не более 9: некоторые могут шарить в обоих языках. Здесь нельзя применить правило суммы.

Правило произведения: если объект A можно выбрать способами, а другой объект B можно выбрать n способами, тогда пару (объект А, объект В) можно выбрать mn способами. Аналог в теории множеств: количество элементов декартова произведения множеств равно произведению количеств элементов «умножаемых» множеств. Правило легко обобщается на несколько типов объектов.

Пример. Секретный код имеет следующий вид: сначала любая строчная буква английского алфавита, далее две цифры. Сколько существует кодовых комбинаций? Ответ: 26 * 10 * 10 = 2600.

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

Пример 1. Сколько существует трехзначных чисел, у которых есть хотя бы один нуль? I. Определим, сколько всего есть трехзначных чисел. Первая цифра может быть от 1 до 9, остальные — от 0 до 9, то есть всего 9 * 10 * 10 = 900 трехзначных чисел по правилу произведения. II. По правилу произведения всего 9 * 9 * 9 = 729 трехзначных чисел без нуля вообще (по 9 вариантов каждой цифры). III. По правилу суммы количество трехзначных чисел равно сумме количества трехзначных чисел без нулей и сумме количества трехзначных чисел с одним и более нулем. Следовательно, ответ: 900 — 729 = 171.

Пример 2. Сколько есть возможных позиций на шахматной доске, когда обе стороны сделали первый ход? Каждая стороны может сделать ход либо пешкой, либо конем. Каждой пешкой можно сделать первый ход 2 способами, всего 8 пешек. По правилу произведения у одной стороны есть 2 * 8 = 16 способов хода пешкой. Каждым конем можно сделать ход 2 способами, всего 2 коня. По правилу произведения у одной стороный есть 2 * 2 = 4 способа хода конем. По правилу суммы получаем, что у каждой стороны есть 16 + 4 = 20 способов хода. Заметим, что первый ход белых не исключает никакого хода черных: никакое поле, куда могут пойти черные, не будет занято. Следовательно, по правилу произведения есть 20 * 20 = 400 возможных позиций. Это можно было определить и перебором, но что быстрее?

crypto.hut2.ru

Правило суммы произведения

Обозначим число элементов конечного множества А символом n(A). Если множества А и В не пересекаются, то nВ)=n(A)+n(B). Если множества А и В пересекаются, то nВ)=n(A)+n(B) – n(AB).

Например. На тарелке лежат 11 груш и 5 лимонов. Сколькими способами можно выбрать один плод?

Речь идет о выборе «яблоко или груша» из множества плодов. Поэтому используем правило суммы: 11+5=16. Значит, один плод можно выбрать 16 способами.

Правило подсчета числа элементов объединения непересекающихся конечных множеств носит название в комбинаторике правила суммы: если элемент х можно выбрать k способами, а элемент y – m способами, причем ни один из способов выбора элемента х не совпадает со способом выбора элемента y, то выбор «х или y» можно осуществить k+m способами.

Правило суммы распространяется не только на два множества. Так, например, пусть даны непересекающиеся множества А, В, С. Тогда

n(ABC)=n(A)+n(B)+n(C)-n(AB)-n(BC)-n(AC)+n(ABC).

Число элементов декартова произведения множеств А и В подсчитывается по формуле n(AB)=n(A)n(B).

Найдем сколько элементов содержит декартово произведение АА, если А=<a, b, c, d, e>?

Так как множество А содержит 5 элементов (n(A)=5)), то декартово произведение АА содержит 55 элементов: n(АА) = 55= 25 пар. Значит, декартово произведение АА содержит 25 элементов.

Правило подсчета числа элементов декартова произведения конечных множеств носит название в комбинаторике правила произведения: если элемент х можно выбрать k способами, а элемент y – m способами, то пару (x, y) можно выбрать km способами.

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

Приведем решения некоторых комбинаторных задач:

Задача 2. В группе 30 студентов. 20 изучают немецкий язык по скайпу, 15 – изучают английский язык по скайпу. Каким может быть число студентов, изучающих оба языка; изучающих хотя бы один язык?

Решение: обозначим множество студентов, изучающих немецкий язык через N, а множество студентов, изучающих английский – через А, множество всех студентов – через С. Тогда n(N)=20, n(A)=15, n(С)=50.

Вопрос о числе студентов, изучающих оба языка, сводится к определению числа элементов в пересечении множеств N и А, вопрос о числе студентов, изучающих хотя бы один язык, – к определению числа элементов в объединении этих множеств.

а) n( NA)=0, n(NA)=n(N)+N(A)=20+15=35;

b) n( NA)=?, n(NA)=?;

c) n( NA)=n(A)=15, n(NA)=n(N)=20.

Таким образом, число студентов, изучающих оба языка (обозначим через х): 0 х 15, а число студентов, изучающих хотя бы один из языков (обозначим через y): 20 y 35.

Задача 3. В классе 30 человек. Из них 26 человек занимается баскетболом, 25 – плаванием, 27 – лыжами, 15 занимаются баскетболом и плаванием, 18 – плаванием и лыжами, 16 посещают секции по баскетболу и лыжам. Один ученик освобожден от физкультурных занятий. Сколько человек занимается всеми указанными видами спорта? Сколько человек занимается только одним видом спорта?

Решение: В задаче рассматриваются три множества: множество А – учащихся, играющих в баскетбол, множество В – занимающихся плаванием и множество С – посещающих лыжную секцию. По условию эти множества попарно пересекаются и в объединении дают 40-1=39.

Обозначим n(ABC)= x. Определим число учащихся в каждой непересекающейся области (рис. 44). Так как n(A)=26, n(B)=25, n(C)=27, n(AB)=15, n(BC)=18, n(AC)=16, то число детей, посещающих только баскетбол и плавание, равно (15-х), только плавание и лыжи – (18-х), баскетбол и плавание – (16-х), только баскетболом занимаются 26-(15-х)-(16-х)-х=х-5
детей, только плавание посещает 25-(15-х)-(18-х)-х=х-8 человек и, наконец, только лыжами – 27-(16-х)-(18х)-х=х-7 учащихся.

Задача 4. Пусть число дождливых дней равно 12, ветреных – 8, холодных – 4, дождливых и ветреных – 5, дождливых и холодных – 3, ветреных и холодных – 2 . Наконец, дождливых, ветреных и холодных – 1.

Тогда общее число плохих дней можно вычислить так: n(AAA)=n(A)+n(A)+n(A)-n(AA)-n(AA)-n(AA)-n(AAA)=12+8+4-5-3-2+1=15.

Задача 5. Сколько трехзначных чисел можно составить, используя цифры 1, 3, 5?

Решение: Цифры в записи числа могут повторяться и не повторяться. Рассмотрим первый случай. Тогда первую цифру в записи числа можно выбрать тремя способами (это может быть любая из данных цифр), вторую – также тремя и третью – тремя способами. Используя правило произведения, получаем: 333=27 чисел. Во втором случае – первую цифру можно выбрать тремя способами, вторую двумя (так как цифры не должны повторяться) и третью – одним способом. В этом случае таких чисел будет равно 321=6.

Задача 6. Из деревни А в деревню В ведут три дороги, а из В в С ведут две дороги. Сколькими способами можно пройти из А в С через В?

Чтобы решить данную задачу, обозначим дороги из А в В числами 1,2,3, а из В в С – буквами a, b. Тогда каждый вариант пути из А в С задается парой, состоящей из числа и буквы. Например, (2; a). Но число пар такого вида по правилу произведения равно 3 2 = 6. Вот эти варианты: (1;a), (2;a),(3;a), (1;b), (2;b), (3;b).

kto.guru

2. Правила суммы и произведения

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

Если объект а можно выбрать т способами, а объект b k способами (не такими, как а), то выбор «либо а, либо в» можно осуществить т + k способами.

Задача 1. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?

Решение. По условию задачи яблоко можно выбрать пятью способами, апельсин – четырьмя. Так как в задаче речь идет о выборе «либо яблоко, либо апельсин», то его, согласно правилу суммы, можно осуществить 5 + 4 = 9 способами.

Правило нахождения числа элементов декартова произведения двух множеств называют в комбинаторике правилом произведения и формулируют в таком виде:

Если объект а можно выбрать т способами, а объект b k способами, то пару (а, b) можно выбрать m k способами.

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

Задача 2. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать пару плодов, состоящую из яблока и апельсина?

Решение. По условию задачи яблоко можно выбрать пятью способами, апельсин – четырьмя. Так как в задаче речь идет о выборе пары (яблоко, апельсин), то ее, согласно правилу произведения, можно выбрать 5  4 = 20 способами.

Задача 3. Сколько всего двузначных чисел можно составить из цифр 7, 4 и 5 при условии, что они в записи числа не повторяются?

Решение. Чтобы записать двузначное число, надо выбрать цифру десятков и цифру единиц. Согласно условию на месте десятков в записи числа может быть любая из цифр 7, 4 и 5. Другими словами, выбрать цифру десятков можно тремя способами. После того, как цифра десятков определена для выбора цифры единиц остаются две возможности, поскольку цифры в записи числа не должны повторятся. Так как любое двузначное число – это упорядоченная пара, состоящая из цифры десятков и цифры единиц, то ее выбор, согласно правилу произведения, можно осуществить 3  2 = 6 способами.

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

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

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

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

Итак, цифру тысяч можно выбрать одним способом, цифру сотен – двумя, цифру единиц двумя. Чтобы узнать сколько всего четырехзначных чисел можно составить из цифр 0 и 3, согласно правилу произведения, способы выбора каждой цифры надо перемножить: 1 2  2  2 = 8.

Таким образом, имеем 8 четырехзначных чисел.

Задача 6. Сколько трехзначных чисел можно записать, используя цифры 0, 1, 3, 6, 7 и 9, если каждая из них может быть использована в записи только один раз?

Решение. Так как запись числа не может начинаться с нуля, то цифру сотен можно выбрать пятью способами; выбор цифры десятков можно осуществить также пятью способами, поскольку цифры в записи числа не должны повторятся, а одна из шести данных цифр будет уже использована для записи сотен; после выбора двух цифр (для записи сотен и десятков) выбрать цифру единиц из данных шести можно четырьмя способами. Отсюда, по правилу произведения, получаем, что всего трехзначных чисел (из данных шести цифр) можно образовать 100: 5  5  4 = 100.

studfiles.net

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

  • Собственные полномочия субъекта Единоличный исполнительный орган юридического лица: функции и полномочия Устав ООО, образец которого считается типовым для всех организаций, содержит ключевые положения, касающиеся […]
  • Налог на капитальный ремонт жилья 2018 москва официальный сайт Плата за капитальный ремонт многоквартирного дома в 2018 году Налог, целью которого, по словам чиновников, стала оплата капремонта жилых зданий, является очередной регулярной пошлиной. […]
  • Что делать с решением суда на алименты Исполнительный лист на алименты: особенности получения Исполнительный лист – это официальный документ. Он выдается судом на основании вынесенного им решения, приговора, другого судебного […]
  • Договор дарения земельного участка между родственниками налоги Дарственная на земельный участок: порядок оформления Составление дарственных в отношении земель, является наиболее простым и выгодным способом передачи прав одного владельца другому. Чаще […]
  • Приказ 185 гибдд 10 причин остановки Обзор 185 приказа ГИБДД Внимание! С 23 августа 2017 года 185 приказ ГИБДД утратил силу. Вместо него сейчас действует: Приказ МВД России от 23 августа 2017 г. N 664 «Об утверждении […]
  • Штраф браконьерство Рыба рыбец: описание, развитие, интересные факты и среда обитания Флора и фауна нашего земного шара поражает красотой и уникальностью. В водоемах проживает большое количество рыб, о […]