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

Содержание
  1. Правила комбинаторики в задаче B6
  2. Число сочетаний и факториалы
  3. Закон умножения
  4. Закон сложения
  5. Дополнительные условия и ограничения
  6. Комбинаторные задачи
  7. Метод перебора
  8. Дерево возможных вариантов
  9. Метод отрезков
  10. Правило встречается в следующих упражнениях:
  11. Элементы комбинаторики: размещение, сочетание, перестановки и комбинации с повторением
  12. Размещение элементов комбинаторики
  13. Перестановка элементов комбинаторики
  14. Комбинации или сочетание элементов комбинаторики
  15. Перестановки и комбинации с повторениями
  16. Примеры решения задач с элементами комбинаторики
  17. Комбинаторная задача. Простейшие комбинаторные задачи. Комбинаторные задачи: примеры
  18. Как решить комбинаторную задачу?
  19. Решение комбинаторных задач
  20. Способ 1. Перебор
  21. Способ 2. Дерево из вариантов
  22. Способ 3. Формирование таблиц
  23. Способ 4. Умножение
  24. Комбинаторика и ее виды
  25. Методика преподавания комбинаторных задач
  26. Комбинаторные задачи: зачем они нужны?
  27. Как решить комбинаторную задачу быстро?
  28. Где найти примеры?
  29. Что делать, если нужно составить комбинаторную задачу?
  30. Комбинаторика – наука будущего?
  31. Комбинаторика основные понятия и формулы, задачи с решением для начинающих, основы комбинаторики для чайников, свойства сочетания с повторениями
  32. Что такое комбинаторика в математике
  33. Основные понятия
  34. Правило произведения
  35. Правило суммы
  36. Сочетания с повторениями и без повторений
  37. Размещения с повторениями и без повторений
  38. Перестановки с повторениями и без повторений
  39. Комбинаторные задачи с решениями
  40. Заключение

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

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

29 декабря 2011

Решая задачи по теории вероятностей, мы постоянно используем одну и ту же формулу, которая одновременно является классическим определением вероятности:

где k — число благоприятных исходов, n — общее число исходов (см. «Тест по теории вероятностей»).

И эта формула прекрасно работает до тех пор, пока задачи были легкими, а числа, стоящие в числителе и знаменателе — очевидными.

Однако последние пробные экзамены показали, что в настоящем ЕГЭ по математике могут встречаться значительно более сложные конструкции. Отыскание значений n и k становится проблематичным. В таком случае на помощь приходит комбинаторика. Ее законы работают там, где искомые значения не выводятся непосредственно из текста задачи.

В сегодняшнем уроке не будет строгих формулировок и длинных теорем — они слишком сложны и, к тому же, совершенно бесполезны для решения настоящих задач B6. Вместо этого мы рассмотрим простые правила и разберем конкретные задачи, которые действительно встречаются на ЕГЭ. Итак, поехали!

Число сочетаний и факториалы

Пусть имеется n объектов (карандашей, конфет, бутылок водки — чего угодно), из которых требуется выбрать ровно k различных объектов. Тогда количество вариантов такого выбора называется числом сочетаний из n элементов по k. Это число обозначается Cnk и считается по специальной формуле.

Обозначение:

Выражение n! читается как «эн-факториал» и обозначает произведение всех натуральных чисел от 1 до n включительно: n! = 1 · 2 · 3 · … · n.

Кроме того, в математике по определению считают, что 0! = 1 — подобный бред редко, но все же встречается в задачах по теории вероятностей.

Что дает нам эта формула? На самом деле, без нее не решается практически ни одна серьезная задача.

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

Для лучшего понимания разберем несколько простейших комбинаторных задач:

Задача. У бармена есть 6 сортов зеленого чая. Для проведения чайной церемонии требуется подать зеленый чай ровно 3 различных сортов. Сколькими способами бармен может выполнить заказ?

Тут все просто: есть n = 6 сортов, из которых надо выбрать k = 3 сорта. Число сочетаний можно найти по формуле:

Задача. В группе из 20 студентов надо выбрать 2 представителей для выступления на конференции. Сколькими способами можно это сделать?

Опять же, всего у нас есть n = 20 студентов, а выбрать надо k = 2 студента. Находим число сочетаний:

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

Задача. На склад завезли 17 серверов с различными дефектами, которые стоят в 2 раза дешевле нормальных серверов. Директор купил в школу 14 таких серверов, а сэкономленные деньги своровал и купил дочке шубу из меха соболя за 200 000 рублей. Сколькими способами директор может выбрать бракованные серверы?

В задаче довольно много лишних данных, которые могут сбить с толку. Наиболее важные факты: всего есть n = 17 серверов, а директору надо k = 14 серверов. Считаем число сочетаний:

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

Как видите, число сочетаний из n по k считается достаточно просто. Проблема в том, что многие школьники никогда не работали с факториалами. Для них это новый и незнакомый математический объект, и для его освоения требуется некоторая тренировка.

Хорошая новость состоит в том, что во многих задачах формулы Cnk оказывается вполне достаточно для нахождения ответа. Но есть и плохая новость: в тех редких случаях, когда нужны дополнительные правила, решение задачи резко усложняется. Эти правила мы сейчас и рассмотрим.

Закон умножения

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

Другими словами, пусть имеется A способов выполнить одно действие и B способов выполнить другое действие. Путь также эти действия независимы, т.е. никак не связаны между собой. Тогда можно найти число способов выполнить первое и второе действие по формуле: C = A · B.

Задача. У Пети есть 4 монеты по 1 рублю и 2 монеты по 10 рублей. Петя, не глядя, достал из кармана 1 монету номиналом 1 рубль и еще 1 монету номиналом 10 рублей, чтобы купить сигарету за 11 рублей у бабули в подземном переходе. Сколькими способами он может выбрать эти монеты?

Итак, сначала Петя достает k = 1 монету из n = 4 имеющихся монет номиналом 1 рубль. Число способов сделать это равно C41 = … = 4.

Затем Петя снова лезет в карман и достает k = 1 монету из n = 2 имеющихся монет номиналом 10 рублей. Здесь число сочетаний равно C21 = … = 2.

Поскольку эти действия независимы, общее число вариантов равно C = 4 · 2 = 8.

Задача. В корзине лежат 8 белых шаров и 12 черных. Сколькими способами можно достать из этой корзины 2 белых шара и 2 черных?

Всего в корзине n = 8 белых шаров, из которых надо выбрать k = 2 шара. Это можно сделать C82 = … = 28 различными способами.

Кроме того, в корзине имеется n = 12 черных шаров, из которых надо выбрать опять же k = 2 шара. Число способов сделать это равно C122 = … = 66.

Поскольку выбор белого шара и выбор черного — события независимые, общее число комбинаций считается по закону умножения: C = 28 · 66 = 1848. Как видим, вариантов может быть довольно много.

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

Именно этой формулы многим не хватило для решения задачи B6 на пробном ЕГЭ по математике. Разумеется, существуют и другие методы решения, в которых комбинаторика не используется — и мы обязательно рассмотрим их ближе к настоящему экзамену. Однако ни один из них не сравнится по надежности и лаконичности с теми приемами, которые мы сейчас изучаем.

Закон сложения

Если закон умножения оперирует «изолированными» событиями, которые не зависят друг от друга, то в законе сложения все наоборот. Здесь рассматриваются взаимоисключающие события, которые никогда не случаются одновременно.

Например, «Петя вынул из кармана 1 монету» и «Петя не вынул из кармана ни одной монеты» — это взаимоисключающие события, поскольку вынуть одну монету и при этом не вынуть ни одной невозможно.

Аналогично, события «Выбранный наугад шар — белый» и «Выбранный наугад шар — черный» также являются взаимоисключающими.

Закон сложения в комбинаторике: если два взаимоисключающих действия можно выполнить A и B способами соответственно, то эти события можно объединить. При этом возникнет новое событие, которое можно выполнить X = A + B способами.

Другими словами, при объединении взаимоисключающих действий (событий, вариантов) число их комбинаций складывается.

Можно сказать, что закон сложения — это логическое «ИЛИ» в комбинаторике, когда нас устраивает любой из взаимоисключающих вариантов. И наоборот, закон умножения — это логическое «И», при котором нас интересует одновременное выполнение и первого, и второго действия.

Задача. В корзине лежат 9 черных шаров и 7 красных. Мальчик достает 2 шара одинакового цвета. Сколькими способами он может это сделать?

Если шары одинакового цвета, то вариантов немного: оба они либо черные, либо красные. Очевидно, что эти варианты — взаимоисключающие.

В первом случае мальчику предстоит выбирать k = 2 черных шара из n = 9 имеющихся. Число способов сделать это равно C92 = … = 36.

Аналогично, во втором случае выбираем k = 2 красных шара из n = 7 возможных. Число способов равно C72 = … = 21.

Осталось найти общее количество способов. Поскольку варианты с черными и красными шарами — взаимоисключающие, по закону сложения имеем: X = 36 + 21 = 57.

Задача. В ларьке продаются 15 роз и 18 тюльпанов. Ученик 9-го класса хочет купить 3 цветка для своей одноклассницы, причем все цветы должны быть одинаковыми. Сколькими способами он может составить такой букет?

По условию, все цветы должны быть одинаковыми. Значит, будем покупать либо 3 розы, либо 3 тюльпана. В любом случае, k = 3.

В случае с розами придется выбирать из n = 15 вариантов, поэтому число сочетаний равно C153 = … = 455. Для тюльпанов же n = 18, а число сочетаний — C183 = … = 816.

Поскольку розы и тюльпаны — это взаимоисключающие варианты, работаем по закону сложения. Получаем общее число вариантов X = 455 + 816 = 1271. Это и есть ответ.

Дополнительные условия и ограничения

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

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

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

Очевидно, что любые ограничения резко сокращают итоговое количество вариантов. Ну и как в этом случае найти число сочетаний? Просто запомните следующее правило:

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

Другими словами, если из 5 ручек надо выбрать 3, при этом одна из них должна быть красной, то выбирать придется из n = 5 − 1 = 4 элементов по k = 3 − 1 = 2 элемента. Таким образом, вместо C53 надо считать C42.

Теперь посмотрим, как это правило работает на конкретных примерах:

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

Итак, есть группа из n = 20 студентов. Но выбрать надо лишь k = 4 из них. Если бы не было дополнительных ограничений, то количество вариантов равнялось числу сочетаний C204.

Однако нам поставили дополнительное условие: 2 отличника должны быть среди этих четырех. Таким образом, согласно приведенному выше правилу, мы уменьшаем числа n и k на 2. Имеем:

Задача. У Пети в кармане есть 8 монет, из которых 6 монет по рублю и 2 монеты по 10 рублей. Петя перекладывает какие-то три монеты в другой карман. Сколькими способами Петя может это сделать, если известно, что обе монеты по 10 рублей оказались в другом кармане?

Итак, есть n = 8 монет. Петя перекладывает k = 3 монеты, из которых 2 — десятирублевые. Получается, что из 3 монет, которые будут переложены, 2 уже зафиксированы, поэтому числа n и k надо уменьшить на 2. Имеем:

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

В заключение отмечу, что в первой задаче мы получили 153 варианта — это намного меньше, чем исходные C204 = … = 4845 вариантов. Аналогично, 3 монеты из 8 можно переложить C83 = … = 56 способами, что значительно больше 6 способов, которые мы получили в последней задаче.

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

Источник: https://www.berdov.com/ege/teorver/combinatorics/

Комбинаторные задачи

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

Комбинаторика (от латинского слова combinare, означающего №соединять», «сочетать») — это область математики, которая изучает способы выбора, расположения, сочетания различных объектов.

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

?» или «Сколько вариантов..?«

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

Метод перебора

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

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

Теперь в основании положим овал, тогда возможны варианты построения: овал — прямоугольник  — треугольник и овал — треугольник — прямоугольник.

Теперь в основании положим треугольник, тогда возможны варианты построения: треугольник — прямоугольник — овал и треугольник — овал — прямоугольник.

Итак, мы получили шесть возможных вариантов:

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

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

Т  О  Т  П  О  П

О  Т  П  Т  П  О

П  П  О  О Т   Т

Дерево возможных вариантов

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

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

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

Метод отрезков

Данный метод используется только для составления всевозможных пар. Например, рассмотрим прямую, на которой обозначены точки A, B, C, D, F:

Необходимо ответить  на вопрос: » Сколько отрезков изображено на рисунке?». Мы знаем, что отрезок обозначается двумя буквами, значит, для ответа на вопрос необходимо перебрать всевозможные пары букв. Это можно сделать при помощи следующей схемы: Отметим точки так, чтобы никакие 3 не лежали на одной прямой:

Соединим  данные точки отрезками между собой. Число отрезков будет числом вариантов, то есть числом отрезков, изображенных на рисунке:

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

Ответ: На рисунке 10 отрезков.

Поделись с друзьями в социальных сетях:

Правило встречается в следующих упражнениях:

5 класс

Задание 283, Виленкин, Жохов, Чесноков, Шварцбург, Учебник

Задание 356, Виленкин, Жохов, Чесноков, Шварцбург, Учебник

Задание 694, Виленкин, Жохов, Чесноков, Шварцбург, Учебник

Задание 733, Виленкин, Жохов, Чесноков, Шварцбург, Учебник

Задание 807, Виленкин, Жохов, Чесноков, Шварцбург, Учебник

Задание 922, Виленкин, Жохов, Чесноков, Шварцбург, Учебник

Упражнение 1, Мерзляк, Полонский, Якир, Учебник

Упражнение 647, Мерзляк, Полонский, Якир, Учебник

Упражнение 841, Мерзляк, Полонский, Якир, Учебник

Упражнение 5, Мерзляк, Полонский, Якир, Учебник

6 класс

Задание 24, Виленкин, Жохов, Чесноков, Шварцбург, Учебник

Задание 53, Виленкин, Жохов, Чесноков, Шварцбург, Учебник

Задание 160, Виленкин, Жохов, Чесноков, Шварцбург, Учебник

Задание 232, Виленкин, Жохов, Чесноков, Шварцбург, Учебник

Задание 355, Виленкин, Жохов, Чесноков, Шварцбург, Учебник

Задание 410, Виленкин, Жохов, Чесноков, Шварцбург, Учебник

© budu5.com, 2020

Пользовательское соглашение

Copyright

Нашли ошибку?

Связаться с нами

Источник: https://budu5.com/manual/chapter/1227

Элементы комбинаторики: размещение, сочетание, перестановки и комбинации с повторением

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

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

Размещение элементов комбинаторики

Пусть даны три элемента . Из них можно создать такие соединения:

1) по одному элементу: ;

2) по два элемента: ;

3) по три элемента: .

Если, например, рассматривать соединения по два элемента, тогда некоторые из них отличаются элементами ( и ), другие – порядком элементов и . Такие соединения называются размещением из 3 элементов по 2.

Число размещений обозначается . Из вышеописанного, мы видим, что , , .

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

.

(1)

Действительно, пусть нам дано элементов: .

Рассмотрим размещение по одному элементу. Понятно, что их будет , то есть .

Теперь рассмотрим, какие возможные размещения по 2 элемента. Чтобы их получить, мы допишем к каждому из данных элементов ещё по одному, которые брались из остальных  элементов. Так, к элементу  допишем последовательно остальные элементы: ; к элементу последовательно остальные элементы: и т. д.

Получим все размещения из элементов по 2:

Записано строк, а число всех размещений в каждом из этих строк . Общее количество всех размещений равняется произведению на , то есть:

.

Чтобы получить рзмещение по 3 элемента в каждом, нам нужно к каждой из записанных пар элементов приобщить ещё по одному элементу из элементов, что остались.

Например, к необходимо приобщить один из элементов . Тогда всех размещений по 3 элемента будет:

и т. д.

Иногда встречаются задачи на размещение с повторениями.

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

.

(2)

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

Согласно с определением:

.

Произведение всех натуральных чисел от до обозначается , а читается ( факториал).

Таким образом,

.

Тогда формула для вычисления количества перестановок запишется:

(3)

При этом имеется ввиду, что .

Обратите внимание! Иногда встречается обозначение . Принято считать, что .

Комбинации или сочетание элементов комбинаторики

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

(4)

Формулу (4) объясним на таком примере:

Пусть даны 4 элемента , комбинациями из этих элементов по будут:

.

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

Число таких размещений равняется .

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

,

откуда получается формула (4).

Посмотрите пример:

.

Умножим числитель и знаменатель в формуле (4) на . Тогда получим:

В итоге получаем:

(5)

По определению принимают . Это определение можно получить из формулы (5), если принять во внимание, что .

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

(6)

Действительно, если по формуле (5) записать , тогда получим:

(7)

Последнее выражение совпадает с правой частью в формуле (5).

Отметим ещё, что числа – это коэффициенты в биноме Ньютона:

(8)

причём согласно с равенством (6) коэффициенты, равноотдалённые от окончания в формуле (8), равные между собой, то есть:

, , и т. д.

Перестановки и комбинации с повторениями

 Иногда бывают перестановки с повторениями: , которые можно образовать из элементов, среди которых одинаковых элементов 1-го типа, одинаковых элементов 2-го типа, и т. д. одинаковых элементов к-го типа, причём находятся по формуле:

(9)

Теперь рассмотрим комбинации с повторениями.

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

(10)

где может быть .

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

Пример 1

Задача

Студенты группы изучают 9 дисциплин по 3 пары ежедневно. Сколько существует способов, чтобы распределить пары на один день?

Решение

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

.

Ответ

Существует 504 размещений.

Пример 2

Задача

Автомобильный номер состоит из 5 цифр (из такого набора: и двух букв. В соединении из букв для номеров автомобилей, какие зарегистрированы в Московской области, на первом месте стоит буква , а на втором месте одна из букв А, Б. В, И. К, Н. Сколько автомобильных номеров можно составить в области?

Решение

Числовая часть номера – один из размещений из по с повторениями. И количество:

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

.

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

.

Ответ

Автомобильных номеров в одной области можно составить по числам – 99 999, а по буквам – 599994.

Пример 3

Задача

Сколько пятизначных телефонных номеров можно составить используя цифры 3, 4, 5, 6, 7 (без повторений)?

Решение

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

.

Ответ

Всего можно составить 120 пятизначных номеров.

Пример 4

Задача

Сколько есть способов, чтобы заполнить карточку спортлото, в которой из 49 чисел необходимо выбрать 6?

Решение

Две заполненные карточки считаются разными, если среди выбранных 6 чисел они отличаются хотя бы одним числом, то есть это будут комбинации, и их количество равняется:

.

Ответ

Количество комбинаций =

Пример 5

Задача

Сколько есть способов, чтобы в данном тайме тренер смог бы выставить на поле 5 баскетболистов, если в команде 10 игроков, причём одного из ведущих игроков тренер планирует задействовать в игре не заменяя на другого игрока весь тайм?

Решение

Так как один из ведущих игроков должен находится на поле в игре весь тайм, тогда менять придётся только 4 игрока из оставшихся 9, то есть у нас получается:

Ответ

Есть 126 способов.

Пример 6

Задача

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

Решение

Всего 8 фигур, причём , , , , , тогда:

.

Ответ

На первой горизонтальной шахматной доске с перестановками фигур можно расставить 5 040 раз.

Пример 7

Задача

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

1. В слове “мама”;

Важно! Когда работу писать становится сложно, можно обратиться с вопросом к экспертам. Это поможет сделать работу быстро.

Подробнее

2. в слове параллелограмм.

Записать соединения букв.

Решение

1. В слове “мама” буквы, при этом две буквы “м”, и две буквы “а”. По формуле (9) всех перестановок будет:

.

А сами перестановки будут такими: “мама”, “маам”, амам”, “аамм”, “амма”.

2. В слове “параллелограмм” 12 букв, из них букв “а” – 3, “г” – 1, “е” – 1, “л” – 2, “м” – 1, “о” – 1, “п” – 1, “р” – 2. Всех перестановок будет:

.

Ответ

Всевозможных перестановок будет – .

Пример 8

Задача

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

Решение

.

Ответ

Для того, чтобы выбрать 5 деталей 3 цветов, мы нашли 21 способ.

Источник: https://NauchnieStati.ru/spravka/elementy-kombinatorik/

Комбинаторная задача. Простейшие комбинаторные задачи. Комбинаторные задачи: примеры

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

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

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

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

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

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

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

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

Решение комбинаторных задач

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

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

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

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

Способ 1. Перебор

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

Как правило, вопрос в такой задаче связан с возможными вариантами происхождения того или иного события, например: какие числа можно составить с помощью цифр 2, 4, 8, 9? Путем перебора всех вариантов составляется ответ, состоящий из возможных комбинаций. Такой способ прекрасно подходит, если количество возможных вариантов сравнительно невелико.

Способ 2. Дерево из вариантов

Некоторые комбинаторные задачи можно решить, только составляя схемы, в которых будет подробно указана информация о каждом элементе. Составление дерева возможных вариантов – еще один способ нахождения ответа. Он подходит для решения не слишком-то сложных задач, в которых имеется дополнительное условие.

Пример такой задачи:

  • Какие пятизначные числа можно составить из цифр 0, 1, 7, 8? Для решения понадобится построить дерево из всех возможных комбинаций, при этом имеется дополнительное условие – число не может начинаться с нуля. Таким образом, ответ будет состоять из всех чисел, которые будут начинаться с 1, 7 или 8.

Способ 3. Формирование таблиц

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

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

Способ 4. Умножение

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

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

  • 6 человек ожидают экзамена в коридоре. Сколько способов можно использовать, чтобы расположить их в общем списке? Для получения ответа необходимо уточнить, сколько их них может быть на первом месте, сколько на втором, на третьем и т. д. Ответом будет число 720.

Комбинаторика и ее виды

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

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

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

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

Согласно учебным планам, возраст учеников, который рассчитан на первичное знакомство с данным материалом и на решение комбинаторных задач, – 5 класс.

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

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

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

Комбинаторные задачи: зачем они нужны?

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

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

Как решить комбинаторную задачу быстро?

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

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

Где найти примеры?

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

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

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

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

Что делать, если нужно составить комбинаторную задачу?

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

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

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

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

Комбинаторика – наука будущего?

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

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

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

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

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

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

Источник: https://FB.ru/article/149409/kombinatornaya-zadacha-prosteyshie-kombinatornyie-zadachi-kombinatornyie-zadachi-primeryi

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

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

Комбинаторика — раздел математики. Основные понятия и формулы комбинаторики как науки применяются во всех сферах жизни.

Неудивительно, что она включена в программу 11 класса, а также во вступительные испытания во многих ВУЗах РФ. Ее основы лежат в прикладном искусстве многих сфер деятельности человека.

Ее история насчитывает более 6 веков. Первые комбинаторные задачи появились в трудах философов и математиков Средневековья.

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

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

Что такое комбинаторика в математике

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

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

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

Основные понятия

Их несколько:

  1. Элемент – любой объект или явление, входящий в искомое множество.
  2. Сочетание – подмножества, находящиеся в произвольном порядке в исходном множестве.
  3. Перестановка – элементы во множестве находятся в строго определенном порядке.
  4. Размещение – упорядоченные подмножества в исходном множестве.

Правило произведения

Является одним из основных правил при решении таких задач и звучит так:

При выборе элемента А из n способов и выборе элемента В из m способов верно утверждение, что выбрать пару А и В одновременно можно n*m способами.

Рассмотрим на конкретных примерах.

Задача №1.

В коробке лежит 2 мяча и 6 скакалок. Сколько существует способов достать 1 мяч и 1 скакалку?

Ответ прост: 2 * 6 = 12.

Задача №2.

Есть 1 кубик, 2 шарика, 3 цветка и 4 конфеты. Сколькими способами можно вытянуть кубик, шарик, цветок и конфету?

Решение аналогично: 1 * 2 * 3 * 4 = 24.

Причем левую часть можно записать гораздо проще: 4!

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

Задача №3.

Сколько двузначных чисел можно составить из 2 цифр?

Ответ: 2! = 2.

Задача №4.

Сколько десятизначных чисел можно составить из 10 цифр?

10! = 3628800.

Правило суммы

Тоже является базовым правилом комбинаторики.

Если А можно выбрать n раз, а В — m раз, то А или В можно выбрать (n + m) раз.

Задача №5.

В коробке лежат 5 красных, 3 желтых, 7 зеленых, 9 черных карандашей. Сколько есть способов вытащить 1 любой карандаш?

Ответ: 5 + 3 + 7 + 9 = 24.

Сочетания с повторениями и без повторений

Под этим термином понимают комбинации в произвольном порядке из множества n по m элементов.

Число сочетаний равно количеству таких комбинаций.

Задача №6.

В коробке находится 4 разных фрукта. Сколькими способами можно достать одновременно 2 разных фрукта?

Решение простое:

Где 4! – комбинация из 4 элементов.

С повторениями чуть сложней, комбинации считаются по такой формуле:

Задача №7.

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

В этом случае:

Размещения с повторениями и без повторений

Под этим определением понимают набор m элементов из множества n элементов.

Задача №8.

Из 3 цифр надо выбрать 2, чтобы получались разные двузначные числа. Сколько вариантов?

Ответ прост:

А как же быть с повторениями? Здесь каждый элемент может размещаться несколько раз! В таком случае общая формула будет выглядеть следующим образом:

Задача №9.

Из 12 букв латинского алфавита и 10 цифр натурального ряда надо найти все варианты составления автомобильного кода региона.

Решение:

Перестановки с повторениями и без повторений

Под этим термином понимают все возможные комбинации из n элементного множества.

Задача №10.

Сколько возможных пятизначных чисел можно составить из 5цифр? А шестизначных из 6 цифр? Семизначных из 7 цифр?

Решения, согласно вышеприведенной формуле, следующие:

5! = 120,

6! = 720,

7! = 5040.

А как же быть с повторениями? Если в таком множестве есть одинаковые по своей значимости элементы, то перестановок будет меньше!

Задача №11.

В коробке есть 3 одинаковых карандаша и одна ручка. Сколько перестановок можно сделать?

Ответ прост: 4! / (3! * 1!) = 4.

Комбинаторные задачи с решениями

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

Типы задачЧто требуется найтиМетоды решения
Магический квадратФигура, в которой сумма чисел в рядах и столбцах должна быть одинакова (его разновидность – латинский квадрат).Рекуррентные соотношения. Решается подобная же задача, но с гораздо меньшим множеством элементов по известным правилам и формулам.
Задача размещенияСтандартная производственная задача (например, в лоскутной технике) найти возможные способы разложения количества продуктов в ячейки в определенном порядке.Включения и исключения. Как правило, применяется при доказательстве различных выражений.
Задачи про торговцевСуть найти все возможные пути прохождения людей из пункта А в пункт В.Траектории. Для этого вида задач характерно геометрическое построение возможных способов решения.

Заключение

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

Источник: https://tvercult.ru/nauka/kombinatorika-osnovnyie-ponyatiya-i-formulyi-s-primerami

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

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: