![]()
| ||||||
Математические формулы, Высшая математика для чайников, или с чего начать? Аналитическая геометрия:
Векторы для чайников
Элементы высшей алгебры:
Множества и действия над ними
Пределы:
Пределы. Примеры решений
Производные функций:
Как найти производную?
Функции и графики:
Графики и свойства ФНП:
Область определения функции Интегралы:
Неопределенный интеграл.
Дифференциальные уравнения:
Дифференциальные уравнения первого порядка
Числовые ряды:
Ряды для чайников
Функциональные ряды:
Степенные ряды
Кратные интегралы:
Двойные интегралы
Элементы векторного анализа:
Основы теории поля
Комплексный анализ:
Примеры решений типовых Теория вероятностей:
Основы теории вероятностей
Математическая статистика:
Математическая статистика
Не нашлось нужной задачи? Не получается пример? Промокод –15% (показать)5530-hihi5
Часто задаваемые вопросы Если Вы заметили опечатку, пожалуйста, сообщите мне об этом |
Задачи по комбинаторике. Примеры решенийНа данном уроке мы коснёмся элементов комбинаторики, которые потребуются для дальнейшего изучения теории вероятностей. Следует отметить, что комбинаторика является самостоятельным разделом высшей математики (а не частью тервера) и по данной дисциплине написаны увесистые учебники, содержание которых, порой, ничуть не легче абстрактной алгебры. Однако нам будет достаточно небольшой доли теоретических знаний, и в данной статье я постараюсь в доступной форме разобрать основы темы с типовыми комбинаторными задачами. А многие из вас мне помогут ;-) Чем будем заниматься? В узком смысле комбинаторика – это подсчёт различных комбинаций, которые можно составить из некоторого множества дискретных объектов. Под объектами понимаются какие-либо обособленные предметы или живые существа – люди, звери, грибы, растения, насекомые и т.д. При этом комбинаторику совершенно не волнует, что множество состоит из тарелки манной каши, паяльника и болотной лягушки. Принципиально важно, что эти объекты поддаются перечислению – их три (дискретность) и существенно то, что среди них нет одинаковых. С множеством разобрались, теперь о комбинациях. Самыми распространёнными видами комбинаций являются перестановки объектов, их выборка из множества (сочетание) и распределение (размещение). Давайте прямо сейчас посмотрим, как это происходит: Перестановки, сочетания и размещения без повторенийНе пугайтесь малопонятных терминов, тем более, некоторые из них действительно не очень удачны. Начнём с хвоста заголовка – что значит «без повторений»? Это значит, что в данном параграфе будут рассматриваться множества, которые состоят из различных объектов. Например, … нет, кашу с паяльником и лягушкой предлагать не буду, лучше что-нибудь повкуснее =) Представьте, что перед вами на столе материализовалось яблоко, груша и банан (при наличии таковых ситуацию можно смоделировать и реально). Выкладываем фрукты слева направо в следующем порядке: яблоко / груша / банан Вопрос первый: сколькими способами их можно переставить? Одна комбинация уже записана выше и с остальными проблем не возникает: яблоко / банан / груша Итого: 6 комбинаций или 6 перестановок. Хорошо, здесь не составило особого труда перечислить все возможные случаи, но как быть, если предметов больше? Уже с четырьмя различными фруктами количество комбинаций значительно возрастёт! Пожалуйста, откройте справочный материал Основные формулы комбинаторики (методичку удобно распечатать) и в пункте № 2 найдите формулу количества перестановок. Никаких мучений – 3 объекта можно переставить Вопрос второй: сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт? Зачем выбирать? Так нагуляли же аппетит в предыдущем пункте – для того, чтобы съесть! =) а) Один фрукт можно выбрать, очевидно, тремя способами – взять либо яблоко, либо грушу, либо банан. Формальный подсчёт проводится по формуле количества сочетаний: Запись б) Перечислим все возможные сочетания двух фруктов: яблоко и груша; Количество комбинаций легко проверить по той же формуле: Запись в) И, наконец, три фрукта можно выбрать единственным способом: Кстати, формула количества сочетаний сохраняет смысл и для пустой выборки: г) Сколькими способами можно взять хотя бы один фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта или все 3 фрукта: Читатели, внимательно изучившие вводный урок по теории вероятностей, уже кое о чём догадались. Но о смысле знака «плюс» позже. Для ответа на следующий вопрос мне требуется два добровольца… …Ну что же, раз никто не хочет, тогда буду вызывать к доске =) Вопрос третий: сколькими способами можно раздать по одному фрукту Даше и Наташе? Для того чтобы раздать два фрукта, сначала нужно их выбрать. Согласно пункту «бэ» предыдущего вопроса, сделать это можно яблоко и груша; Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов: И такая перестановка возможна для каждой пары фруктов. В данном случае работает формула количества размещений: Она отличается от формулы Пожалуйста, внимательно прочитайте пункт № 2 методички Основные формулы комбинаторики и постарайтесь хорошо уяснить разницу между перестановками, сочетаниями и размещениями. В простейших случаях можно пересчитать все возможные комбинации вручную, но чаще всего это становится неподъемной задачей, именно поэтому и нужно понимать смысл формул. Также напоминаю, что сейчас речь идёт о множестве с различными объектами, и если яблоко/грушу/банан заменить на 3 яблока или даже на 3 очень похожих яблока, то в контексте рассмотренной задачи они всё равно будут считаться различными. Остановимся на каждом виде комбинаций подробнее: ПерестановкиПерестановками называют комбинации, состоящие из одних и тех же Отличительной особенностью перестановок является то, что в каждой из них участвует ВСЁ множество, то есть, все Задача 1 Сколькими способами можно рассадить 5 человек за столом? Решение: используем формулу количества перестановок: Ответ: 120 способами Невероятно, но факт. Обратите внимание, что здесь не имеет значения круглый ли стол, квадратный, или вообще все люди сели Задача 2 Сколько четырёхзначных чисел можно составить из четырёх карточек с цифрами 0, 5, 7, 9? Для того чтобы составить четырёхзначное число нужно задействовать все четыре карточки (цифры на которых различны!), и это очень важная предпосылка для применения формулы Хорошенько подумайте над задачей! Вообще, это характерная черта комбинаторных и вероятностных задач – в них НУЖНО ДУМАТЬ. И зачастую думать по-житейски, как, например, в разборе вступительного примера с фруктами. Нет, конечно, я не призываю тупо прорабатывать другие разделы математики, однако должен заметить, что те же интегралы можно научиться решать чисто механически. Решение и ответ в конце урока. Увеличиваем обороты: СочетанияВ учебниках обычно даётся лаконичное и не очень понятное определение сочетаний, поэтому, в моих устах формулировка будет не особо рациональной, но, надеюсь, доходчивой: Сочетаниями называют различные комбинации из Задача 3 В ящике находится 15 деталей. Сколькими способами можно взять 4 детали? Решение: прежде всего, снова обращаю внимание на то, что по логике условия, детали считаются различными – даже если они на самом деле однотипны и визуально одинаковы В задаче речь идёт о выборке из 4 деталей, в которой не имеет значения их «дальнейшая судьба» – грубо говоря, «просто выбрали 4 штуки и всё». Таким образом, у нас имеют место сочетания деталей. Считаем их количество: Здесь, конечно же, не нужно ворочать огромные числа
Ещё раз: что это значит? Это значит, что из набора 15 различных деталей можно составить одну тысячу триста шестьдесят пять уникальных сочетания 4 деталей. То есть, каждая такая комбинация из четырёх деталей будет отличаться от других комбинаций хотя бы одной деталью. Ответ: 1365 способами Формуле
Рекомендую внимательно ознакомиться с биномом Ньютона и треугольником Паскаля, по которому, к слову, очень удобно выполнять проверку вычислений Задача 4 Сколькими способами из колоды в 36 карт можно выбрать 3 карты? Это пример для самостоятельного решения. Чем приятны многие комбинаторные задачи, так это краткостью – главное, разобраться в сути. И суть, бывает, открывается с различных сторон. Разберём весьма поучительный пример: Задача 4* В шахматном турнире участвует Поскольку я сам играю в шахматы и неоднократно принимал участие в круговых турнирах, то сразу же сориентировался по турнирной таблице размером Однако один из посетителей сайта заметил, что на самом деле здесь можно руководствоваться самыми что ни на есть банальными сочетаниями: Эквивалентной является задача о рукопожатиях: в отделе работает Ну а вывода тут два: Большое спасибо за ваши письма, они помогают улучшить качество учебных материалов! РазмещенияИли «продвинутые» сочетания. Размещениями называют различные комбинации из Что наша жизнь? Игра: Задача 5 Боря, Дима и Володя сели играть в «очко». Сколькими способами им можно сдать по одной карте? (колода содержит 36 карт) Решение: ситуация похожа на Задачу 4, но отличается тем, что здесь важно не только то, какие три карты будут извлечены из колоды, но и то, КАК они будут распределены между игроками. По формуле размещений:
Есть и другая схема решения, которая, с моей точки зрения, даже понятнее:
Теперь давайте рассмотрим, какую-нибудь одну из семи тысяч ста сорока комбинаций, например: король пик, 9 червей , 7 червей. Выражаясь комбинаторной терминологией, эти 3 карты можно «переставить» между Борей, Димой и Володей КП, 9Ч, 7Ч; И аналогичный факт справедлив для любого уникального набора из трёх карт. А таких наборов, не забываем, мы насчитали
По существу, получилась наглядная проверка формулы Ответ: 42840 Возможно, у вас остался вопрос, а кто же раздавал карты? …Наверное, преподаватель =) Задача 6 В студенческой группе 23 человека. Сколькими способами можно выбрать старосту и его заместителя? Задача о «размещении» должностей в коллективе встречается очень часто и является самым настоящим баяном. Краткое решение и ответ в конце урока. Правило сложения и правило умножения комбинацийДанные правила весьма напоминают алгебру событий, и многие читатели уже ознакомились с пунктом № 4 справочного материала Основные формулы комбинаторики, где они изложены в общем виде. Постараюсь повторить принципы максимально кратко: 1) Знак «плюс» следует понимать и читать как союз ИЛИ. Вспоминаем демонстрационную задачу с яблоком, грушей и бананом: То есть, можно взять 1 фрукт (любой из трёх) ИЛИ какое-нибудь сочетание двух фруктов ИЛИ все три фрукта. Заметьте, что сложение комбинаций предполагает безразличие выбора (без разницы будет ли выбран один, два или 3 фрукта). Рассмотрим более основательный пример: Задача 7 Студенческая группа состоит из 23 человек, среди которых 10 юношей и 13 девушек. Сколькими способами можно выбрать двух человек одного пола? Решение: в данном случае подсчёт Условие «выбрать двух человек одного пола» подразумевает, что необходимо выбрать двух юношей или двух девушек, и уже сама словесная формулировка указывает на верный путь решения:
Таким образом, двух человек одного пола (без разницы – юношей или девушек) можно выбрать: Ответ: 123 Правило умножения комбинаций: 2) Знак «умножить» следует понимать и читать как союз И. Рассмотрим ту же студенческую группу, которая пошла на танцы. Сколькими способами можно составить пару из юноши и девушки?
Таким образом, одного юношу и одну девушку можно выбрать: Когда из каждого множества выбирается по 1 объекту, то справедлив следующий принцип подсчёта комбинаций: «каждый объект из одного множества может составить пару с каждым объектом другого множества». То есть, Олег может пригласить на танец любую из 13 девушек, Евгений – тоже любую из тринадцати, и аналогичный выбор есть у остальных молодых людей. Итого: Следует отметить, что в данном примере не имеет значения «история» образования пары; однако если принять во внимание инициативу, то количество комбинаций нужно удвоить, поскольку каждая из 13 девушек тоже может пригласить на танец любого юношу. Всё зависит от условия той или иной задачи! Похожий принцип справедлив и для более сложных комбинаций, например: сколькими способами можно выбрать двух юношей и двух девушек для участия в сценке КВН? Союз И недвусмысленно намекает, что комбинации необходимо перемножить:
Иными словами, каждая пара юношей (45 уникальных пар) может выступать с любой парой девушек (78 уникальных пар). А если рассмотреть распределение ролей между участниками, то комбинаций будет ещё больше. …Очень хочется, но всё-таки воздержусь от продолжения, чтобы не привить вам отвращение к студенческой жизни =). Правило умножения комбинаций распространяется и на бОльшее количество множителей: Задача 8 Сколько существует трёхзначных чисел, которые делятся на 5? Решение: для наглядности обозначим данное число тремя звёздочками: *** Комбинации будем считать по разрядам – слева направо: В разряд сотен можно записать любую из А вот в разряд десятков («посерединке») можно выбрать любую из 10 цифр: По условию, число должно делиться на 5. Число делится на 5, если оно заканчивается на 5 либо на 0. Таким образом, в младшем разряде нас устраивают 2 цифры. Итого, существует: При этом произведение Или ещё проще: «каждая из 9 цифр в разряде сотен комбинируется с каждой из 10 цифр разряда десятков и с каждой из двух цифр в разряде единиц». Ответ: 180 А теперь… Да, чуть не забыл об обещанном комментарии к задаче № 5, в которой Боре, Диме и Володе можно сдать по одной карте А теперь задача для самостоятельного решения… сейчас придумаю что-нибудь поинтереснее, …пусть будет про ту же русскую версию блэкджека: Задача 9 Сколько существует выигрышных комбинаций из 2 карт при игре в «очко»? Для тех, кто не знает: выигрывает комбинация 10 + ТУЗ (11 очков) = 21 очко и, давайте будем считать выигрышной комбинацию из двух тузов. (порядок карт в любой паре не имеет значения) Краткое решение и ответ в конце урока. Кстати, не надо считать пример примитивным. Блэкджек – это чуть ли не единственная игра, для которой существует математически обоснованный алгоритм, позволяющий выигрывать у казино. Желающие могут легко найти массу информации об оптимальной стратегии и тактике. Правда, такие мастера довольно быстро попадают в чёрный список всех заведений =) Пришло время закрепить пройденный материал парой солидных задач: Задача 10 У Васи дома живут 4 кота. а) сколькими способами можно рассадить котов по углам комнаты? Решаем: во-первых, вновь следует обратить внимание на то, что в задаче речь идёт о разных объектах (даже если коты – однояйцовые близнецы). Это очень важное условие! а) Повторюсь, что при перестановках имеет значение лишь количество различных объектов и их взаимное расположение. В зависимости от настроения Вася может рассаживать животных полукругом на диване, в ряд на подоконнике и т.д. – перестановок во всех случаях будет 24. Желающие могут для удобства представить, что коты разноцветные (например, белый, чёрный, рыжий и полосатый) и перечислить все возможные комбинации. б) Сколькими способами можно отпустить гулять котов? Предполагается, что коты ходят гулять только через дверь, при этом вопрос подразумевает безразличие по поводу количества животных – на прогулку могут выйти 1, 2, 3 или все 4 кота. Считаем все возможные комбинации:
Наверное, вы догадались, что полученные значения следует просуммировать: Энтузиастам предлагаю усложнённую версию задачи – когда любой кот в любой выборке случайным образом может выйти на улицу, как через дверь, так и через окно в) Сколькими способами Вася может взять на руки двух котов? Ситуация предполагает не только выбор 2 животных, но и их размещение по рукам: Второй вариант решения: Ответ: а) 24, б) 15, в) 12 Ну и для очистки совести что-нибудь поконкретнее на умножение комбинаций…. Пусть у Васи дополнительно живёт 5 кошек =) Сколькими способами можно отпустить гулять 2 котов и 1 кошку? То есть, с каждой парой котов можно выпустить каждую кошку. Ещё один баян для самостоятельного решения: Задача 11 В лифт 12-этажного дома сели 3 пассажира. Каждый независимо от других с одинаковой вероятностью может выйти на любом (начиная со 2-го) этаже. Сколькими способами: 1) пассажиры могут выйти на одном и том же этаже (порядок выхода не имеет значения); И тут часто переспрашивают, уточняю: если 2 или 3 человека выходят на одном этаже, то очерёдность выхода не имеет значения. ДУМАЙТЕ, используйте формулы и правила сложения/умножения комбинаций. В случае затруднений пассажирам полезно дать имена и порассуждать, в каких комбинациях они могут выйти из лифта. Не нужно огорчаться, если что-то не получится, так, например, пункт № 2 достаточно коварен, впрочем, один из читателей отыскал простое решение, и я в очередной раз выражаю благодарность за ваши письма! Полное решение с подробными комментариями в конце урока. Заключительный параграф посвящён комбинациям, которые тоже встречаются достаточно часто – по моей субъективной оценке, примерно в 20-30% комбинаторных задач: Перестановки, сочетания и размещения с повторениямиПеречисленные виды комбинаций законспектированы в пункте № 5 справочного материала Основные формулы комбинаторики, однако некоторые из них по первому прочтению могут быть не очень понятными. В этом случае сначала целесообразно ознакомиться с практическими примерами, и только потом осмысливать общую формулировку. Поехали: Перестановки с повторениямиВ перестановках с повторениями, как и в «обычных» перестановках, участвует сразу всё множество объектов, но есть одно но: в данном множестве один или бОльшее количество элементов (объектов) повторяются. Встречайте очередной стандарт: Задача 12 Сколько различных буквосочетаний можно получить перестановкой карточек со следующими буквами: К, О, Л, О, К, О, Л, Ь, Ч, И, К? Решение: в том случае, если бы все буквы были различны, то следовало бы применить тривиальную формулу Всё предельно просто – всего: 11 карточек, среди которых буква: К – повторяется 3 раза; Проверка: 3 + 3 + 2 + 1 + 1 + 1 = 11, что и требовалось проверить. По формуле количества перестановок с повторениями: Для быстрого расчёта большого факториального значения удобно использовать стандартную функцию Экселя: забиваем в любую ячейку =ФАКТР(11) и жмём Enter. На практике вполне допустимо не записывать общую формулу и, кроме того, опускать единичные факториалы: Ответ: 554400 Другой типовой пример перестановок с повторениями встречается в задаче о расстановке шахматных фигур, которую можно найти на складе готовых решений в соответствующей pdf-ке. А для самостоятельного решения я придумал менее шаблонное задание: Задача 13 Алексей занимается спортом, причём 4 дня в неделю – лёгкой атлетикой, 2 дня – силовыми упражнениями и 1 день отдыхает. Сколькими способами он может составить себе расписание занятий на неделю? Формула Двухстрочное решение и ответ в конце урока. Сочетания с повторениямиХарактерная особенность этого вида комбинаций состоит в том, что выборка проводится из нескольких групп, каждая из которых состоит из одинаковых объектов. Сегодня все хорошо потрудились, поэтому настало время подкрепиться: Задача 14 В студенческой столовой продают сосиски в тесте, ватрушки и пончики. Сколькими способами можно приобрести пять пирожков? Решение: сразу обратите внимание на типичный критерий сочетаний с повторениями – по условию на выбор предложено не множество объектов как таковое, а различные виды объектов; при этом предполагается, что в продаже есть не менее пяти хот-догов, 5 ватрушек и 5 пончиков. Пирожки в каждой группе, разумеется, отличаются – ибо абсолютно идентичные пончики можно смоделировать разве что на компьютере =) Однако физические характеристики пирожков по смыслу задачи не существенны, и хот-доги / ватрушки / пончики в своих группах считаются одинаковыми. Что может быть в выборке? Прежде всего, следует отметить, что в выборке обязательно будут одинаковые пирожки (т.к. выбираем 5 штук, а на выбор предложено 3 вида). Варианты тут на любой вкус: 5 хот-догов, 5 ватрушек, 5 пончиков, 3 хот-дога + 2 ватрушки, 1 хот-дог + 2 + ватрушки + 2 пончика и т.д. Как и при «обычных» сочетаниях, порядок выбора и размещение пирожков в выборке не имеет значения – просто выбрали 5 штук и всё. Используем формулу Приятного аппетита! Ответ: 21 Какой вывод можно сделать из многих комбинаторных задач? Порой, самое трудное – это разобраться в условии. Аналогичный пример для самостоятельного решения: Задача 15 В кошельке находится достаточно большое количество 1-, 2-, 5- и 10-рублёвых монет. Сколькими способами можно извлечь три монеты из кошелька? В целях самоконтроля ответьте на пару простых вопросов: 1) Могут ли в выборке все монеты быть разными? Решение и ответы в конце урока. Из моего личного опыта, могу сказать, что сочетания с повторениями – наиболее редкий гость на практике, чего не скажешь о следующем виде комбинаций: Размещения с повторениямиИз множества, состоящего из Когда так бывает? Типовым примером является кодовый замок с несколькими дисками, но по причине развития технологий актуальнее рассмотреть его цифрового потомка: Задача 16 Сколько существует четырёхзначных пин-кодов? Решение: на самом деле для разруливания задачи достаточно знаний правил комбинаторики: А теперь с помощью формулы. По условию нам предложен набор из Ответ: 10000 Что тут приходит на ум… …если банкомат «съедает» карточку после третьей неудачной попытки ввода пин-кода, то шансы подобрать его наугад весьма призрачны. И кто сказал, что в комбинаторике нет никакого практического смысла? Познавательная задача для всех читателей mathprofi.ru: Задача 17 Согласно государственному стандарту, автомобильный номерной знак состоит из 3 цифр и 3 букв. При этом недопустим номер с тремя нулями, а буквы выбираются из набора А, В, Е, К, М, Н, О, Р, С, Т, У, Х (используются только те буквы кириллицы, написание которых совпадает с латинскими буквами). Сколько различных номерных знаков можно составить для региона? Не так их, кстати, и много. В крупных регионах такого количества не хватает, и поэтому для них существуют по несколько кодов к надписи RUS. Решение и ответ в конце урока. Не забываем использовать правила комбинаторики ;-) …Хотел похвастаться эксклюзивом, да оказалось не эксклюзивом =) Заглянул в Википедию – там есть расчёты, правда, без комментариев. Хотя в учебных целях, наверное, мало кто прорешивал. Наше увлекательное занятие подошло к концу, и напоследок я хочу сказать, что вы не зря потратили время – по той причине, что формулы комбинаторики находят ещё одно насущное практическое применение: они встречаются в различных задачах по теории вероятностей, Всем спасибо за активное участие и до скорых встреч! Решения и ответы: Задача 2: Решение: найдём количество всех возможных перестановок 4 карточек: Примечание: т.к. карточек немного, то здесь несложно перечислить все такие варианты: Таким образом, из предложенного набора можно составить: З.Ы. Никогда не думал, что эти задачи будут предлагать первоклассникам, один из которых заметил, что карточку «9» можно использовать как «6», и поэтому количество комбинаций нужно удвоить. Но в условии всё же заявлена конкретная цифра и от удвоения лучше воздержаться. Задача 4: Решение: Задача 6: Решение: Задача 9: Решение: Задача 11: Решение: 2) Способ первый: Способ второй, который нашёл один из читателей сайта: 3) Третий вариант решения, нашёл другой читатель сайта. Через комбинаторное произведение: 4) Способ первый: суммируем комбинации первых трёх пунктов: Способ второй: в общем случае он более рационален, более того, позволяет обойтись без результатов предыдущих пунктов. Рассуждения таковы: Ответ: 1) 11; 2) 330; 3) 990; 4) 1331 Задача 13: Решение: по формуле количества перестановок с повторениями: Задача 15: Решение: используем формулу Задача 17: Решение: Автор: Емелин Александр Высшая математика для заочников и не только >>> (Переход на главную страницу) Как можно отблагодарить автора?
|
© Copyright mathprofi.ru, Александр Емелин, 2010-2021. Копирование материалов сайта запрещено |