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

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

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

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

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

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

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

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

Элементы комбинаторики: Правило Суммы, Правило Произведения

Задача 1Д-Т2.1. В русском языке 33 буквы 10 гласных, 21 согласная и две специальные буквы (Ь и Ъ). Два студента независимо друг от друга выбрали по одной букве русского алфавита. Какова вероятность того, что:

а) были выбраны различные буквы;

б) обе выбранные буквы – гласные;

в) среди выбранных букв имеются согласные?

г) это две соседние буквы алфавита.

Задача 2Д-Т2.1. Из пяти чисел 1, 2, 3, 4, 5 поочередно выбираются два. Найдите вероятность того, что:

а) первое из чисел меньше второго;

б) эти два числа – дины катетов прямоугольного треугольника с целочисленной гипотенузой;

в) произведение этих чисел оканчивается нулем;

г) первое из чисел делится на второе.

Задача 3Д-Т2.1. Случайно и поочередно нажимают три клавиши одной октавы. Найдите вероятность того, что:

а) не была нажата «фа»;

б) не были нажаты ни «до», ни «си»;

в) была нажата «ля»;

г) получилось до-мажорное трезвучие «до-ми-соль».

Задача 4Д-Т2.1. Двое независимо друг от друга записали по одному двузначному натуральному числу. Найдите вероятность того, что:

а) эти два числа различны;

б) сумма чисел равна 100;

в) сумма чисел не больше 25;

г) сумма чисел больше 190.

Задача 5Д-Т2.1. Набирая номер телефона, абонент забыл две последние цифры и набрал их наугад. Найти вероятность того, что были набраны нужные цифры.

Задача 6Д–Т2.1. Из колоды в 36 карт наугад вытянуто последовательно без возвращения две карты. Найти вероятность того, что обе они – тузы.

Задача 7Д-Т2.1. В студенческой группе 12 девушек и 16 юношей. Сколькими способами можно выбрать для вручения разных призов студентов одного пола?

Задача 8Д-Т2.1. Если подбросить одновременно три игральные кости, то сколько имеется различных комбинаций выброшенных очков?

Задача 9Д-Т2.1. В цветочном киоске 7 видов цветов. Сколькими способами можно составить букет из трех цветов?

Задача 10Д-Т2.1. Из пункта А в пункт В можно добраться самолетом, поездом, автобусом. Из пункта В в пункт С – пешком, на тракторе, на лошади, на лодке. Сколькими способами можно выбрать дорогу от пункта А до пункта С через В?

Задача 11Д-Т2.1. Сколькими способами можно выбрать один цветок из корзины, в которой находятся 12 гвоздик, 15 роз и 7 хризантем?

Задача 12Д-Т2.1. Сколько имеется пятизначных чисел, все цифры у которых различны?

Задача 13Д-Т2.1. Сколькими способами можно составить трехцветный полосатый флаг (три горизонтальные полосы), если имеется материя пяти различных цветов?

Задача 14Д-Т2.1. Из группы в 15 человек выбирают 4-х участников эстафеты 800х400х200х100. Сколькими способами можно расставить спортсменов на этапах?

Задача 15Д-Т2.1. Какова вероятность того, что произвольно взятое трехзначное число делится на 3?

Задача 16Д-Т2.1. Некто написал на листочке четырехзначное число. Какова вероятность отгадать его с первой попытки?

Задача 17Д-Т2.1. В урне находятся 10 белых, 15 черных и 20 красных шаров. Сколькими различными способами можно вытащить из урны 3 шара разных цветов?

Задача 18Д-Т2.1. Группа студентов изучает 10 различных дисциплин. Сколькими способами можно составить расписание занятий в понедельник, если в этот день должно быть 4 разных занятия?

Задача 19Д-Т2.1. Из 10 мальчиков и 10 девочек спортивного класса для участия в эстафете надо составить три команды, каждая из которых состоит из мальчика и девочки. Сколькими способами это можно сделать?

Задача 20Д-Т2.1. Сколько можно составить четырехзначных чисел так, чтобы любые две соседние цифры были различны?

Задача 21Д-Т2.1. Является ли выбор с помощью «считалки» случайным и справедливым? Пусть два брата считаются до числа, которое оказалось суммой «выброшенных» пальцев одной руки каждого. Тот, на котором остановился счет, выходит, а оставшийся убирает квартиру. Играет ли роль, с кого начинать счет?

Тема 3. Элементы комбинаторики. Понятие о «схеме выбора». Схема выбора без возвращения: Перестановки, Размещения, Сочетания. – 4 часа: 2 часа лекции, 2 часа семинарское занятие

Существуют две схемы выбора m элементов из множества, состоящего из n элементов:

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

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

studopedia.org

Учебник по теории вероятностей

1.1. Элементы комбинаторики

Размещения

Рассмотрим некоторое множество $Х$, состоящее из $n$ элементов $X = \< x_1, x_2, . x_n \>$. Будем выбирать из этого множества различные упорядоченные подмножества $Y$ из $k$ элементов.

Размещением из $n$ элементов множества $Х$ по $k$ элементам назовем любой упорядоченный набор $ \left( x_, x_, . x_ \right)$ элементов множества $Х$.

Если выбор элементов множества $Y$ из $Х$ происходит с возвращением, т.е. каждый элемент множества $Х$ может быть выбран несколько раз, то число размещений из $n$ по $k$ находится по формуле $n^k$ (размещения с повторениями).

Если же выбор делается без возвращения, т.е. каждый элемент множества $Х$ можно выбирать только один раз, то количество размещений из $n$ по $k$ обозначается $A_n^k$ и определяется равенством $$ A_n^k=n\cdot(n-1)\cdot . \cdot (n-k+1) = \frac<(n-k)!>. $$ (размещения без повторений).

Пример. Пусть даны шесть цифр: 1; 2; 3; 4; 5; 6. Определить сколько трехзначных чисел можно составить из этих цифр.

Решение. Если цифры могут повторяться, то количество трехзначных чисел будет $m=n^k=6^3=216$. Если цифры не повторяются, то $m=A_6^3 = 6 \cdot 5 \cdot 4= 120$.

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

Решение. Расписание на каждый день может отличаться либо предметами, либо порядком расположения этих предметов, поэтому имеем размещения: $A_<10>^3 = 10 \cdot 9 \cdot 8= 720$.

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

Частный случай размещения при $n=k$ называется перестановкой из $n$ элементов. Число всех перестановок из $n$ элементов равно $A_n^n=P_n=n!$.

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

Решение. Будем считать три книги одного автора за одну книгу, тогда число перестановок будет $P_<28>$. А три книги можно переставлять между собой $P_3$ способами, тогда по правилу произведения имеем, что искомое число способов равно: $N=P_3 \cdot P_ <28>= 3! \cdot 28!$.

Пусть теперь из множества $Х$ выбирается неупорядоченное подмножество $Y$ (порядок элементов в подмножестве не имеет значения). Сочетаниями из $n$ элементов по $k$ называются подмножества из $k$ элементов, отличающиеся друг от друга хотя бы одним элементом. Общее число всех сочетаний из $n$ по $k$ обозначается $C_n^k$ и равно $$ C_n^k = \frac = \frac <(n-k)!\cdot k!>= \frac. $$

Справедливы равенства: $$ C_n^0=1, \; C_n^n=1, \; C_n^k = C_n^. $$

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

Решение. Так как порядок студентов не важен, используем формулу для числа сочетаний: $$ C_<27>^3 = \frac<27!> <24!\cdot 3!>= \frac<27\cdot 26\cdot 25><1\cdot 2\cdot 3>=2925. $$

Подробности и онлайн калькуляторы для комбинаторики

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

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

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

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

Правило произведения. Если объект $А$ можно выбрать из совокупности объектов $m$ способами и после каждого такого выбора объект $В$ можно выбрать $n$ способами, то пара объектов $(А, В)$ в указанном порядке может быть выбрана $m \cdot n$ способами.

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

Решение. Пусть сначала студентка выбирает блузку. Этот выбор может быть совершен четырьмя способами, так как студентка имеет четыре блузки, затем пятью способами произойдет выбор юбки и тремя способами выбор туфель. По принципу умножения получается 4*5*3=60 нарядов (комбинаций).

www.matburo.ru

Факультативный курс по теме «Элементы комбинаторики» для 8 класса (стр. 1 из 8)

ГОУ СПО «Кунгурское педагогическое училище»

ПЦК преподавателей естественно-математических дисциплин

Допущена к защите

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

Разработка программы факультативного курса по теме «Элементы комбинаторики» для 8 класса

Выпускная квалификационная работа

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

Лузиной Татьяны Юрьевны

Глава 1. Использование комбинаторных задач на уроках математики

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

1.2 Методика обучения решению комбинаторных задач

Глава 2. Разработка программы факультативного курса по теме «Элементы комбинаторики» для 8 класса

2.1 Основные понятия о факультативном курсе

2.2 Программа факультативного курса

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

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

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

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

В ходе работы над темой был проведен анализ учебников математики на наличие в них комбинаторных задач и анализ программы по математике, а также анкетирование учителей школ г. Кунгура (приложение №1).

Анализ учебников показал, что только в учебниках Дорофеева Г. В. (6 класс) и Мордковича А. Г. (9 класс) имеются элементы комбинаторики. А, именно, разбираются два способа решения комбинаторных задач: перебор и дерево возможных вариантов, а также рассматриваются правила сложения и произведения.

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

В лицее №1 г. Кунгура элементы комбинаторики изучаются не достаточно, только один час в неделю, (так как нет программы), поэтому автору работы было предложено разработать программу факультативного курса по теме «Элементы комбинаторики» для 8 класса.

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

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

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

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

Цель: разработка программы факультативного курса по теме «Элементы комбинаторики» для 8 класса.

1) изучить методическую и научную литературу по теме исследования;

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

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

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

Предмет исследования: процесс решения комбинаторных задач учащимися 8 класса.

Контингент: учащиеся восьмого класса лицея №1 г. Кунгура.

В написании выпускной квалификационной работы помогла следующая литература:

— Виленкин Н. Я. Комбинаторика. – М.: Наука, 1969. В этой книге разбираются некоторые довольно сложные комбинаторные задачи, так же даются понятия о методах их решения.

— Журнал «Начальная школа», в котором были освещены следующие темы:

— «Способы решения комбинаторных задач»;

— «Методика обучения решению комбинаторных задач»;

— «Характеристика комбинаторных задач».

— Газета «Математика», которая включала в свое содержание комбинаторные задачи для школьников различных возрастов.

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

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

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

Во второй главе – основные понятия о факультативном курсе, а также программа факультативного курса по теме «Элементы комбинаторики».

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

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

Глава 1. Использование комбинаторных задач в обучении математике

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

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

Один из разделов теории вероятности – комбинаторика.

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

Задачи, в которых идет речь о тех или иных комбинациях объектов, называются комбинаторными. Область математики, в которой изучаются комбинаторные задачи, называется комбинаторикой [23, 28].

Раздел комбинаторики, в котором рассматривается лишь вопрос о подсчете числа решений комбинаторной задачи, называется теорией перечислений. Он тесно связан с теорией вероятностей. Во многих случаях при вычислении вероятности данного события надо найти число возможных вариантов и число благоприятных вариантов. Число вариантов отыскивается комбинаторными методами [23, 19].

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

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

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

Комбинаторика как наука стала развиваться в XIII веке параллельно с возникновением теории вероятностей, так как для решения вероятностных задач необходимо было подсчитать число различных комбинаций элементов. Первые научные исследования по комбинаторике принадлежат итальянским ученым Дж. Кардано, Н.Тарталье (1499-1557), Г.Галилею (1564-1642) и французским ученым Б.Паскалю (1623-1662) и П.Ферма.

Комбинаторику как самостоятельный раздел математики первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666 году. Он также впервые ввел термин «комбинаторика». Значительный вклад в развитие комбинаторики внес Л.Эйлер. В современном обществе с развитием вычислительной техники комбинаторика «добилась» новых успехов. В настоящее время в образовательный стандарт по математике включены основы комбинаторики, решение комбинаторных задач методом перебора, составлением дерева вариантов (еще его называют «дерево возможностей») с применением правила умножения.

mirznanii.com

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

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

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

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

Популярное:

  • Налог на капитальный ремонт кто не платит Что говорит закон об оплате за капитальный ремонт, есть ли льготы пенсионерам? Компенсация взносов - сколько должны платить пенсионеры? С начала 2016 года вступил в силу Федеральный Закон № 271 «О капитальном ремонте в […]
  • За сколько работодатель должен предупреждать об увольнении Увольнение по собственному желанию Увольнение по собственному желанию (другими словами, по инициативе работника) - одно из самых распространенных оснований расторжения трудового договора. Инициатива прекращения трудовых […]
  • Правило рядности это Правило рядности это Собственно, на курсы вождения меня записалПодробнее Самой распространенной ошибкой начинающего водителя является несоблюдение рядности движения. Сложность возникает особенно в тех местах, где […]
  • Новые штрафы на такси Какой будет в 2018 штраф, если на такси нет лицензии Как известно, именно на малый бизнес во всем мире возлагают функцию основного движителя экономики. Россия в данном случае не является исключением. Правительство и законодатели […]
  • Почему задерживают пенсию по потере кормильца На карточку не пришла пенсия: почему возникают проблемы Финансовый кризис больнее всего ударил по самой незащищенной категории граждан Российской Федерации – по пенсионерам. Выплаты от государства в подавляющем большинстве […]
  • Таблица штрафов гибдд 2018 страховка Новая таблица штрафов ПДД С начала 2018 года в российской дорожной системе появится множество корректировок, которые затронут и штрафы ПДД. Теперь всем участникам движения – автолюбителям и пешеходам – потребуется проявлять […]
  • Срок оплаты транспортного налога для физических лиц 2018 В какие сроки нужно оплатить транспортный налог? Законодательство РФ установило отдельные сроки уплаты транспортного налога физическими лицами в 2018 году до 1 декабря года, следующего за тем, за который налог […]
  • Повышение пенсий милиции Увеличение выслуги лет в МВД до 25 лет в 2018 году Пенсионная реформа за последние пару лет произвела немалый фурор. Мнения граждан разошлись: одни уверены, что пенсионная реформа лишь ухудшит положение российских пенсионеров, […]