Элементы комбинаторики. Комбинаторика - основные понятия и формулы. Перестановки, размещения, сочетания Комбинаторика примеры

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

Неудивительно, что она включена в программу 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 цифр?

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

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

Если А можно выбрать 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 цифр?

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

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

Задача №11.

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

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

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

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

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

Заключение

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

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

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

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

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В - n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.

Пример 1.

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

Решение

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n 1 способами, второе действие n 2 способами, третье - n 3 способами и так до k-го действия, которое можно выполнить n k способами, то все 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. Он решил с помощью этих штампов нанести на все книги пятизначные номера- составить каталог. Сколько различных пятизначных номеров может составить мальчик?

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

Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?

Пример 7.

Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?

Решение

Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.

Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k < n), т. е. есть одинаковые предметы.

Пример 8.

Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?

Решение

Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно

ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ "КОМБИНАТОРИКА"

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

Определение 1: Порядок во множестве изэлементов – это нумерация его элементов натуральными числами, т.е. отображение множества
на множество
.

Определение 2: Множество с заданным на нем порядком называется упорядоченным множеством.

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

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

и
.

Три буквы ,иможно расположить в виде последовательности шестью способами:

,
,
,
,
,
.

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

Упорядоченные последовательности элементов некоторого множества можно рассматривать как распределения или расстановки этих элементов в последовательности.

Определение 3: Пусть дано конечное множество
изэлементов. Всякий набор изэлементов данного множества (при этом элементы в наборе могут и повторяться) будем называть-расстановками .

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

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

Определение 4: Пусть
- конечное множество изэлементов.Перестановками из различных элементов множества
называются все расположенияэлементов в определенном порядке. Обозначается:(от французского словаpermutation - перестановка).

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

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

Последнее определение сформулировано с позиции теории множеств.

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

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

Теорема 1: Число перестановок из различных элементов вычисляется по формуле:

Доказательство. Рассмотрим произвольное множество из элементов. Построим всевозможные расстановки из этихэлементов. На первое место расстановки можно поставить любой из элементов (способов выбора первого элемента). После того, как первый элемент выбран и независимо как он выбран, второй элемент можно выбрать
способом. Для выбора третьего элемента остается
способа и т.д. Последний элемент выбирается соответственно одним способом. Тогда, в силу комбинаторного принципа умножения, количество таких расстановок будет равно:

Теорема доказана.

Пример 1: Сколькими способами трое друзей могут занять в кинотеатре места с номерами 1, 2 и 3.

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

Перестановки букв некоторого слова называют анаграммами . Открытые еще в ІІІ веке до нашей эры греческим грамматиком Ликофроном анаграммы до сих пор привлекают внимание языковедов, поэтов и любителей словесности. Мастера словесных игр помимо эрудиции и большого запаса слов знают много секретов, связанных с комбинаторными навыками, один из которых – анаграммы. Часто требуется среди всех перестановок выбрать те, которые обладают определенным свойством. Например, среди анаграмм слова «крот» , которых всего
, только одна, не считая самого слова«крот» , имеет смысл в русском языке – «корт».

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

Теорема 2: Число круговых перестановок из различных элементов равно

Пример 2: Сколькими способами 7 детей могут стать в хоровод?

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

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

Определение 7: Пусть имеется различных предметов. Расстановки изэлементов поэлементов (
) называютсяразмещениями без повторений . Обозначают: . Здесь имеется в виду, что элементы в расстановках не повторяются.

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

Приведем еще одно определение размещений, эквивалентное исходному, более простое для понимания.

Определение 8: Конечные упорядоченные множества называются размещениями.

Теорема 3: Количество всех размещений из элементов поэлементов без повторений вычисляется по формуле:

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

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

По определению, такие расстановки являются размещениями. Что и требовалось доказать.

Пример 3: Собрание из 25 человек выбирает президиум из 3 человек: 1) председатель, 2) заместитель, 3) секретарь. Сколько возможно вариантов выбора президиума?

Решение. Выбирая трех человек из 25, замечаем, что важен порядок выбора, поэтому количество президиумов будет равно:

Замечание: Число размещений без повторений можно также находить по формуле:

. (3)

Если в знаменателе дроби из формулы (3)
, то принято считать
.

Замечание: Формула (3) отличается компактностью, но при решении задач удобнее использовать формулу (2). Дробь, стоящая в правой части формулы (3), может быть сокращена до целого числа. Это число равно числу из правой части формулы (2).

Пример 4: Сколько можно составить двухбуквенных слов (буквы не повторяются) из 33 букв русского алфавита?

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

Тогда количество различных комбинаций из 2 букв, выбранных из 33 букв алфавита, будет равно:

.

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

Замечание: Перестановка без повторений – это частный случай размещений без повторений при
. Можно сказать, что перестановка изэлементов – это размещение изэлементов поэлементов:

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

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

Определение 9: Сочетания без повторений из элементов некоторого множества поэлементов (
) – это расстановки, отличающиеся друг от другасоставом , но не порядком элементов. Обозначают: (от французского словаcombinaison – сочетание).

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

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

Определение 10: Конечные неупорядоченные множества называются сочетаниями.

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

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

Теорема 4: Число сочетаний находится по следующей формуле:

. (4)

Доказательство. Если из произвольного -элементного множества выбраныэлементов, то их можно пронумеровать номерами
числом способов, равным. Оставшиеся
элементов можно занумеровать номерами
,
, …,всего
способами. Кроме того, сам отборэлементов изэлементов можно осуществитьспособами. Таким образом, мы получили
вариантов нумерации полного множества из элементов, которых всего. Поэтому имеем
, откуда получаем:

.

Теорема доказана.

Замечание: Дробь, стоящая в правой части (4), может быть сокращена до целого числа.

Из формулы числа сочетаний следует:

,
,
.

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

Пример 5: Сколькими способами можно выбрать 3 различные краски из имеющихся пяти.

Решение. Порядок выбора красок не важен. Важно только какие краски выбраны. Поэтому количество вариантов равно:
.

Пример 6: Сколькими способами можно пошить трехцветные полосатые флаги, если имеется материал пяти различных цветов.

Решение. Порядок выбора полос важен, поэтому количество таких флагов равно:
.

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

1. Сколько анаграмм имеет слово КЛАСС?

Трудность в том, что в этом слове две одинаковые буквы С. Будем временно считать их разными и обозначим С 1 и С 2 . Тогда число анаграмм окажется равным 5! = 120. Но те слова, которые отличаются друг из друга лишь перестановкой букв С 1 и С 2 , на самом-то деле являются одной и той же анаграммой! Поэтому 120 анаграмм разбиваются на пары одинаковых, т.е. искомое число анаграмм равно 120/2 = 60.

2. Сколько анаграмм имеет слово ШАРАДА?

Считая три буквы А различными буквами А 1 , А 2 , А 3 , получим 6! анаграмм. Но слова, которые получаются друг из друга только перестановкой букв А 1 , А 2 , А 3 , на самом деле являются одной и той же анаграммой. Поскольку имеется 3! перестановок букв А 1 , А 2 , А 3 , полученные изначально 6! анаграмм разбиваются на группы по 3! одинаковых, и число различных анаграмм оказывается равным 6!/3! = 120.

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

Найдем количество «ненужных» четырехзначных чисел, в записи которых присутствуют только нечетные цифры. Таких чисел 5 4 = 625. Но всего четырехзначных чисел 9000, поэтому искомое количество «нужных» чисел равно 9000 – 625 = 8375.

1. Найти число анаграмм у слов ВЕРЕСК, БАЛАГАН, ГОРОДОВОЙ.
2. Найти число анаграмм у слов БАОБАБ, БАЛЛАДА, ПЕРЕПОЛОХ, АНАГРАММА, МАТЕМАТИКА, КОМБИНАТОРИКА, ОБОРОНОСПОСОБНОСТЬ.
3. Сколькими способами можно поселить 7 приезжих в три гостиничных номера: одноместный, двухместный и четырехместный?
4. В холодильнике лежат два яблока, три груши и четыре апельсина. Каждый день в течение девяти дней подряд Пете дают один какой-то фрукт. Сколькими способами это может быть сделано?
5. Из семи лучших лыжников школы нужно отобрать команду из трех человек для участия в городских соревнованиях. Сколькими способами это можно сделать?
6. Перед экзаменом профессор пообещал поставить двойки половине экзаменуемых. На экзамен пришло 20 студентов. Сколькими способами он может выполнить обещание?
7. Сколько слов можно составить из пяти букв А и не более чем из трех букв Б?
8. В продаже есть шоколадное, клубничное и молочное мороженое. Сколькими способами можно купить три мороженых?
9. При приготовлении пиццы к сыру добавляются разные компоненты, обеспечивающие тот или иной вкус. В распоряжении Билла имеются лук, грибы, помидоры, перец и анчоусы, причем все это, по его мнению, можно добавлять к сыру. Сколько видов пиццы может приготовить Билл?
10. Свидетель криминальной разборки запомнил, что преступники скрылись на «мерседесе», номер которого содержал буквы Т, З, У и цифры 3 и 7 (номером является строка, в которой сначала идут три буквы, а затем - три цифры). Сколько существует таких номеров?
11. Сколько диагоналей в выпуклом n -угольнике?
12. Сколько всего существует n -значных чисел?
13. Сколько существует десятизначных чисел, в записи которых есть хотя бы две одинаковые цифры?
14. Кубик бросают трижды. Среди всевозможных последовательностей результатов есть такие, в которых хотя бы один раз выпала шестерка. Сколько их?
15. Сколько пятизначных чисел имеют в своей записи цифру 1?
16. Сколькими способами можно расставить на шахматной доске белого и черного короля так, чтобы они не били друг друга?
17. Сколько делителей у числа 10800?

Реферат на тему:

Выполнил ученик 10 класса «В»

средней школы №53

Глухов Михаил Александрович

г. Набережные Челны

2002 г.
Содержание

Из истории комбинаторики_________________________________________	3
Правило суммы___________________________________________________	4
	-
Правило произведения_____________________________________________	4
Примеры задач____________________________________________________	-
Пересекающиеся множества________________________________________	5
Примеры задач____________________________________________________	-
Круги Эйлера_____________________________________________________	-
Размещения без повторений________________________________________	6
Примеры задач____________________________________________________	-
Перестановки без повторений_______________________________________	7
Примеры задач____________________________________________________	-
Сочетания без повторений__________________________________________	8
Примеры задач____________________________________________________	-
Размещения и сочетания без повторений______________________________	9
Примеры задач____________________________________________________	-
Перестановки с повторениями_______________________________________	9
Примеры задач____________________________________________________	-
Задачи для самостоятельного решения________________________________	10
Список используемой литературы___________________________________	11

Из истории комбинаторики

Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. Нидийцы умели вычислять числа, которые сейчас называют "сочетания". В XII в. Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские ученые изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Например, в связи с подсчетом возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из n слогов. Как научная дисциплина, комбинаторика сформировалась в XVII в. В книге "Теория и практика арифметики" (1656 г.) французский автор А. Также посвящает сочетаниям и перестановкам целую главу.
Б. Паскаль в "Трактате об арифметическом треугольнике" и в "Трактате о числовых порядках" (1665 г.) изложил учение о биномиальных коэффициентах. П. Ферма знал о связях математических квадратов и фигурных чисел с теорией соединений. Термин "комбинаторика" стал употребляться после опубликования Лейбницем в 1665 г. работы "Рассуждение о комбинаторном искусстве", в которой впервые дано научное обоснование теории сочетаний и перестановок. Изучением размещений впервые занимался Я. Бернулли во второй части своей книги "Ars conjectandi" (искусство предугадывания) в 1713 г. Современная символика сочетаний была предложена разными авторами учебных руководств только в XIX в.

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

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

Если конечные множества не пересекаются, то число элементов X U Y {или} равно сумме числа элементов множества X и числа элементов множества Y.

То есть, если на первой полке стоит X книг, а на второй Y, то выбрать книгу из первой или второй полки, можно X+Y способами.

Примеры задач

Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы?

Решение: X=17, Y=13

По правилу суммы X U Y=17+13=30 тем.

Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10 билетов автомотолотереи. Сколькими способами можно выбрать один билет из спортлото или автомотолотереи?

Решение: Так как денежно-вещевая лотерея в выборе не участвует, то всего 6+10=16 вариантов.

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

Если элемент X можно выбрать k способами, а элемент Y-m способами то пару (X,Y) можно выбрать k*m способами.

То есть, если на первой полке стоит 5 книг, а на второй 10, то выбрать одну книгу с первой полки и одну со второй можно 5*10=50 способами.

Примеры задач

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

Решение: Имеется 12 книг и 3 цвета, значит по правилу произведения возможно 12*3=36 вариантов переплета.

Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

Решение: В таких числах последняя цифра будет такая же, как и первая, а предпоследняя - как и вторая. Третья цифра будет любой. Это можно представить в виде XYZYX , где Y и Z -любые цифры, а X - не ноль. Значит по правилу произведения количество цифр одинаково читающихся как слева направо, так и справа налево равно 9*10*10=900 вариантов.

Пересекающиеся множества

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

, где X и Y - множества, а - область пересечения. Примеры задач

20 человекзнаютанглийскийи 10 - немецкий, изних 5 знаютианглийский, инемецкий. СколькоЧеловеквсего?

Ответ: 10+20-5=25 человек.

Также часто для наглядного решения задачи применяются круги Эйлера. Например:

Из 100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют 30 человек, английским - 28, французским - 42. Английским и немецким одновременно владеют 8 человек, английским и французским - 10, немецким и французским - 5, всеми тремя языками - 3. Сколько туристов не владеют ни одним языком?

Решение: Выразим условие этой задачи графически. Обозначим кругом тех, кто знает английский, другим кругом - тех, кто знает французский, и третьим кругом - тех, кто знают немецкий.

Всеми тремя языками владеют три туриста, значит, в общей части кругов вписываем число 3. Английским и французским языком владеют 10 человек, а 3 из них владеют еще и немецким. Следовательно, только английским и французским владеют 10-3=7 человек.

Аналогично получаем, что только английским и немецким владеют 8-3=5 человек, а немецким и французским 5-3=2 туриста. Вносим эти данные в соответствующие части.

Определим теперь, сколько человек владеют только одним из перечисленных языков. Немецкий знают 30 человек, но 5+3+2=10 из них владеют и другими языками, следовательно, только немецкий знают 20 человек. Аналогично получаем, что одним английским владеют 13 человек, а одним французским - 30 человек.

По условию задачи всего 100 туристов. 20+13+30+5+7+2+3=80 туристов знают хотя бы один язык, следовательно, 20 человек не владеют ни одним из данных языков.

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

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

Это пример задачи на размещение без повторений. Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые цифры стоят в разном порядке считаются разными.

Если X-множество, состоящие из n элементов, m≤n, то размещением без повторений из n элементов множества X по m называется упорядоченное множество X, содержащее m элементов называется упорядоченное множество X, содержащее m элементов.

Количество всех размещений из n элементов по m обозначают

n! - n-факториал (factorial анг. сомножитель) произведение чисел натурального ряда от 1 до какого либо числа nЗадача

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

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

Возможно 360 вариантов.

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

В случае n=m (см. размещения без повторений) из n элементов по m называется перестановкой множества x.

Количество всех перестановок из n элементов обозначают P n.

Действительно при n=m:

Примеры задач

Сколько различных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, если цифры в числе не повторяются?

1) Найдем количество всех перестановок из этих цифр: P 6 =6!=720

2) 0 не может стоять впереди числа, поэтому от этого числа необходимо отнять количество перестановок, при котором 0 стоит впереди. А это P 5 =5!=120.

P 6 -P 5 =720-120=600

Проказница Мартышка

Да косолапый Мишка

Затеяли играть квартет

Стой, братцы стой! –

Кричит Мартышка, - погодите!

Как музыке идти?

Ведь вы не так сидите…

И так, и этак пересаживались – опять музыка на лад не идет.