Правило произведения в задачах комбинаторики

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

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

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

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

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

Пример 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

Примеры решений задач по комбинаторике

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

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

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

Калькуляторы онлайн и примеры

Задачи по комбинаторике с решениями онлайн

Задача 1. У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано?

Задача 2. Предприятие может предоставить работу по одной специальности 4 женщинами, по другой — 6 мужчинам, по третьей — 3 работникам независимо от пола. Сколькими способами можно заполнить вакантные места, если имеются 14 претендентов: 6 женщин и 8 мужчин?

Задача 3. В пассажирском поезде 9 вагонов. Сколькими способами можно рассадить в поезде 4 человека, при условии, что все они должны ехать в различных вагонах?

Задача 4. В группе 9 человек. Сколько можно образовать разных подгрупп при условии, что в подгруппу входит не менее 2 человек?

Задача 5. Группу из 20 студентов нужно разделить на 3 бригады, причем в первую бригаду должны входить 3 человека, во вторую — 5 и в третью — 12. Сколькими способами это можно сделать.

Задача 6. Для участия в команде тренер отбирает 5 мальчиков из 10. Сколькими способами он может сформировать команду, если 2 определенных мальчика должны войти в команду?

Задача 7. В шахматном турнире принимали участие 15 шахматистов, причем каждый из них сыграл только одну партию с каждым из остальных. Сколько всего партий было сыграно в этом турнире?

Задача 8. Сколько различных дробей можно составить из чисел 3, 5, 7, 11, 13, 17 так, чтобы в каждую дробь входили 2 различных числа? Сколько среди них будет правильных дробей?

Задача 9. Сколько слов можно получить, переставляя буквы в слове Гора и Институт?

Задача 10. Каких чисел от 1 до 1 000 000 больше: тех, в записи которых встречается единица, или тех, в которых она не встречается?

Готовые примеры

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

www.matburo.ru

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

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

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

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

ya-znau.ru

Как решать задачи по комбинаторике?

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

Возникновение комбинаторной теории

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

Истоки этой науки были положены знаменитым математиком и философом Готфридом Лейбницем.

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

Теория комбинаторики зиждется на двух основных принципах – это правило сложения и правило умножения. Рассмотрим их подробнее.

Правило сложения: Пусть объект А мы можем выбрать из множества $m$ способами, а объект В можно выбрать $n$ способами, то объект «А+В» можно выбрать $m+n$ способами.

Возможно, это правило покажется непосвященному человеку абракадаброй, но ничего сложного нет. Рассмотрим пример – пусть в одном ящике есть $m$ шариков, а во втором ящике – $n$ шариков. Сколькими способами можно вытащить шарик из одного этих ящиков. Очевидно, что ОДИН шарик можно достать $m+n$ способами.

Правило умножения: Пусть объект А выбирается $m$ способами, объект В выбирается $n$ способами, то оба объекта можно выбрать $mn$ способами.
Все очень просто – каждый из $m$ способов выбора объекта А комбинируется с каждым из $n$ способов выбора объекта В, то есть количество способов просто умножается друг на друга.

Рассмотрим простой пример: сколько чисел можно составить из цифр 0,1,2,3,4,5,6,7,8,9, если число должно быть двузначным?
Можно составить 90 чисел – первую цифру числа (объект А) можем выбрать 9 способами, так как число не может начинаться с нуля. Вторую цифру числа (объект В) можем выбрать 10 способами, так как у нас есть 10 цифр. Итого получается $9*10=90$ чисел.

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

Готовые решения задач по теории вероятностей, в том числе по комбинаторике — более 400 решений. Найди свою задачу:

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

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

Есть 5 книг. Сколькими способами их можно расположить на книжной полке?
Ответ – 120 способов. Первую книгу можем выбрать 5 способами, вторую книгу 4 способами и т.д. Перемножая числа с 5 до 1, получим 120.

С этой задачи начинается понятие факториала. N-факториал или N! – это количество перестановок из N объектов, вычисляемое по формуле $P_N =N!= 1*2*3*…*(N-1)*N$.

Следующий пример – в чемпионате мира участвуют 18 команд по футболу. Сколькими способами можно распределить золотые, серебряные и бронзовые комплекты?
Ясно, что золотые медали может получить любая из команд, значит золотого призера (объект А) можно выбрать 18 способами. Остается два комплекта и 17 команд. Серебряным медалистом может стать одна из 17 команд, а бронзовым – одна из 16 команд. Значит, серебряного и бронзового медалиста можно выбрать 17 и 16 способами.
Итого, три комплекта медалей могут распределиться 18*17*16 = 4896 способами.

www.matburo.ru

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

Понятие комбинаторной задачи

Лекция № 13,14

Элементы комбинаторики и теории вероятностей

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

studopedia.su

Еще по теме:

  • Спор овощей стихотворение тувим Сценка про овощи (на основе стихотворения Ю. Тувима «Овощи») Оксана Шмакова Сценка про овощи (на основе стихотворения Ю. Тувима «Овощи») СЦЕНКА ПРО ОВОЩИ (по Ю. Тувиму) Действующие лица: воспитатель, Хозяйка (в фартуке и с корзинкой, дети в масках […]
  • Справка общий стаж работы образец Зачем нужна справка о трудовом стаже, и как ее подготовить Пока действуют трудовые книжки, их нужно заполнять по инструкции. Если книжка потеряна или испорчена, заполняется дубликат. Но в него тоже нужно вписывать сведения о том, где и кем […]
  • Медиация налоговые споры Медиативный подход к налоговым спорам Цисана Шамликашвили, президент Национальной организации медиаторов, научный руководитель Центра медиации и права. 2 июля 2013 года был принят Федеральный закон № 153-ФЗ "О внесении изменений в часть первую […]
  • Увеличение пенсий мвд когда Последние изменения в вопросе предоставления пенсионного обеспечения бывшим сотрудникам МВД Начало нового года всегда таит в себе ожидание каких либо изменений. Многие граждане нашей страны, которые получают военные пенсии, интересуются последними […]
  • Как оформить депортацию Депортация из РФ в 2018 году Депортация из России может грозить только лишь иностранным подданным либо лицам без гражданства, которые грубым образом нарушили правила миграции. Депортация как форма административного наказания не может быть применена […]
  • Заявление от работника на уменьшение ндфл Иностранный работник: уменьшаем НДФЛ на фиксированный авансовый платеж Работодатель — налоговый агент имеет право на уменьшение НДФЛ иностранного работника на сумму фиксированных авансовых платежей, уплаченных им самостоятельно. Рассмотрим порядок […]