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

Оглавление:

Неудивительно, что она включена в программу 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.
• Возьмем тот же самый случай, но при условии, что один фрукт возвращается в коробку.
• В этом случае:

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

1. Под этим определением понимают набор m элементов из множества n элементов.
2. Задача №8.

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

Ответ прост:

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

• Задача №9.
• Из 12 букв латинского алфавита и 10 цифр натурального ряда надо найти все варианты составления автомобильного кода региона.
• Решение:

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

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

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

• Решения, согласно вышеприведенной формуле, следующие:
• 5! = 120;
• 6! = 720;

7! = 5040.

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

Задача №11.

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

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

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

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

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

Заключение

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

Комбинаторика. Основные формулы

Перестановкой называется конечное множество, в котором установлен порядок элементов.

Формула количества перестановок (Сколькими способами можно переставить n объектов?)

Пример 1. Дано:

Сколько существует способов переставить ягоды местами?

Решение: P3 = 3! = 1 ⋅ 2 ⋅ 3 = 6 (см. рисунок «Перестановки»)

Ответ: 6

Пример 2. В команде 6 человек. Сколькими способами они могут выстроиться для приветствия?

Решение: P6 = 6! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ⋅ 6 = 720 вариантов приветствия

Ответ: 720

Пример 3. Имеется 10 различных книг, среди которых есть трёхтомник одного автора. Сколькими способами можно расставить эти книги на полке, если книги трёхтомника должны находиться вместе, но в любом прядке?

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

P8 ⋅ P3 = 8! ⋅ 3!= 241920  вариантов перестановок книг.

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

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

Формула количества перестановок с повторениями (Количество способов, которыми можно переставить n объектов, среди которых 1-й объект повторяется n1 раз, 2-й объект повторяется n2 раз, 3-й объект – n3 раз,…, k -й объект – nk раз, n = n1 + n2 + … + nk)

Если имеются неповторяющиеся объекты, в этом случае соответствующие значения n равны единице.

Пример 1. Алексей занимается спортом. 4 раза в неделю — легкой атлетикой, 2 раза в неделю силовыми упражнениями и один день отдыхает. Сколькими способами он может составить себе расписание на неделю?

Решение: Имеем набор {л л л л с с о}. Имеем набор семиэлементного множества 7!, но мы не должны учитывать перестановки, в которых одинаковые элементы меняются местами, поэтому должны поделить на 4! ⋅ 2!

Р7= 7! / (4! ⋅ 2!) = 105. 

Ответ: 105

Пример 2. Сколько слов можно составить, переставив буквы в слове «экзамен», в слове «математика», в слове «колобок»?

Решение:

«Экзамен» – 7 букв ( без повторений), поэтому Р7 = 7! = 5040

«Математика» — 10 букв (м-2, а-3, т-2, е-1, и-1, к-1), перестановки с повторениями Р10= 10! / (2! ⋅ 3! ⋅ 2! ⋅ 1! ⋅ 1! ⋅ 1! ) = 151200

«Колобок» — 7 букв (к-2, о-3, л-1, б-1) , перестановки с повторениями Р7= 7! / (2! ⋅ 3!) = 420

Ответ: 5040; 151200; 420

Сочетания

Подмножества, составленные из n элементов данного множества и содержащие k элементов в каждом подмножестве, называют сочетаниями из n элементов по k. (Сочетания различаются только элементами, порядок их не важен: ab и ba – это одно и тоже сочетание).  

Формула количества сочетаний (Сколькими способами можно выбрать k объектов из n ?)

Пример 1. Дано:

Сколько существует способов выбрать из трех ягод по две?

Решение: С32= 3! /( 1! ⋅ 2!)  = 3 (см. рисунок «Сочетания»)

Ответ: 3

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

Решение: С72 =7! /(2! ⋅ (7 — 2)!) = 7! /(2! ⋅ 5!) = (6 ⋅ 7)/2 = 21

Ответ:  21

Пример 3. На тренировках занимаются 12 баскетболистов. Сколько может быть организовано тренером разных стартовых пятерок?

Решение: С125 =12! /(5! ⋅ (12 — 5)!) = 12! /(5! ⋅ 7!) = (12 ⋅ 11 ⋅ 10⋅ 9⋅ 8 ⋅ 7!)/(5! ⋅ 7!) = (12 ⋅ 11 ⋅ 10 ⋅ 9 ⋅ 8) /120  = 11⋅ 9⋅ 8 = 792

Ответ: 792

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

Решение: Т.к. двое мальчиков войдут в команду, то остается отобрать 3 из 8. Для выборки важен только состав (по условию все члены команды не различаются по ролям).

С83 = 8! /(3! ⋅ (8 — 3)!) = 8! /(3! ⋅ 5!) = (8 ⋅ 7 ⋅ 6 ⋅ 5!)/(3! ⋅ 5!) = (8 ⋅ 7 ⋅ 6) / 6  = 56

Ответ:  56.

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

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

С152 = 15! /(2! ⋅ (15 — 2)!) = 15! /(2! ⋅ 13!) = (15 ⋅ 14 ⋅ 13!)/(2! ⋅ 13!) = (15 ⋅ 14) / 2  = 105

Ответ: 105. 

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

Формула количества сочетаний с повторениями (Сколькими способами можно выбрать k объектов в  множестве, состоящем из n элементов, причем элементы возвращаются обратно?)

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

Пример 1. Дано:

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

Решение: С3(повт)2=  С42= 4! /( 1! ⋅ 2!)  = 6 (см. рисунок «Сочетания с повторениями»)

Ответ: 6

Пример 2. В кошельке находится достаточно большое 1 -рублевых, 2-х, 5-ти и 10-и рублёвых монет. Сколькими способами можно извлечь три монеты из кошелька?

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

С4(повт)3 = С63 = 6! /(3! ⋅ (4 — 1)!) = 6! /(3! ⋅ 3!) = (6 ⋅ 5 ⋅ 4 ⋅ 3!)/(3! ⋅ 3!) = (6 ⋅ 5 ⋅ 4) / 6  = 20 способами можно выбрать 3 монеты из кошелька.

Ответ: 20.

 

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

Решение: С10(повт)12 = С2112 = 21! /(12! ⋅ (21 — 12)!) = 21! /(12! ⋅ 9!) = (21 ⋅ 20 ⋅ 19 ⋅ 18  ⋅ 17 ⋅ 16 ⋅ 15  ⋅ 14 ⋅ 13  ⋅ 12!)/(12! ⋅ 9!) =(21 ⋅ 20 ⋅ 19 ⋅ 18  ⋅ 17 ⋅ 16 ⋅ 15  ⋅ 14 ⋅ 13)/(3 ⋅ 18 ⋅ 21 ⋅ 20 ⋅ 16) = 19 ⋅ 17 ⋅ 5  ⋅ 14 ⋅ 13 = 293930

Ответ: 293930.

Размещения 

Размещением  из n элементов по k (k≤n) называется любое множество, состоящее из k элементов, взятых в определённом порядке из данных n элементов. 

Формула количества размещений (Сколькими способами можно выбрать k объектов из n и в каждой выборке переставить их местами, либо распределить между ними какие-нибудь уникальные атрибуты?)

Пример 1. Дано:

Сколько существует размещений из трех ягод по две?

Решение: А32= 3! / 1! = 6 (см. рисунок «Размещения»)

 Ответ: 6

Пример 2. Сколько трехзначных чисел можно составить из цифр 2, 4, 6, 7, 9?

Решение:  А53 = 5! /(5 — 3)! = 5! /2! = 120/2 = 60

Ответ: 60.

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

Решение: А183 = 18! /(18 — 3)! = 18! /15! = 18 ⋅ 17 ⋅ 16 = 4896

Ответ: 4896.

 

Пример 4. Даниэль составляет коды из букв слова ДАНИЭЛЬ . Код должен состоять из 10 букв, он не может начинаться с буквы Ь и должен содержать все гласные буквы ровно по одному разу. Сколько различных кодов может составить Даниэль?

Решение: 1) Сначала найдем все возможные варианты таких слов, не ограничивая и считая мягкий знак согласной:

Найдем количество размещений гласных букв в 10-и позициях: А103 = 10! /(10 — 3)! = 10! /7! = 10 ⋅ 9 ⋅ 8 = 720

Умножим размещения гласных на остальные варианты семи позиций согласных букв:  А103 ⋅ 47 = 11 796 480 

2) Из всех вариантов вычтем слова, начинающиеся с Ь: 

Гласные в этом случае будут размещаться на 3-х из 9-и позиций: А93 = 9! /(9 — 3)! = 9! /6! = 9 ⋅ 8 ⋅ 7 = 504 

• Умножим размещения гласных на остальные варианты шести позиций четырех согласных букв: А93 ⋅ 46 = 2 064 384
• 3) Из 1) Вычтем слова найденные в пункте 2):
• 11 796 480 — 2 064 384 = 9 732 096
• Ответ: 9 732 096

Пример 5. Николай составляет коды из букв слова НИКОЛАЙ. Код должен состоять из 11 букв, он не может начинаться с буквы Й и должен содержать все гласные буквы ровно по одному разу. Сколько различных кодов может составить Николай?

Решение: 1) Сначала найдем все возможные варианты таких слов, не ограничивая и считая Й:

Найдем количество размещений гласных букв в 11-и позициях: А113 = 11! /(11 — 3)! = 11! /8! = 11 ⋅ 10 ⋅ 9 = 990

Умножим размещения гласных на остальные варианты восьми позиций четырех согласных букв:  А113 ⋅ 48 = 990 ⋅ 65 536 = 64 880 640

2) Из всех вариантов вычтем слова, начинающиеся с Й: 

Гласные в этом случае будут размещаться на 3-х из 10-и позиций: А103 = 10! /(10 — 3)! = 10! /7! = 10 ⋅ 9 ⋅ 8 = 720 

1. Умножим размещения гласных на остальные варианты семи позиций четырех согласных букв: А103 ⋅ 47 = 720 ⋅ 16 384= 11 796 480
2. 3) Из 1) Вычтем слова найденные в пункте 2):
3. 64 880 640 — 11 796 480 = 53 084 160
4. Ответ: 53 084 160

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

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

 Формула количества размещений с повторениями (Сколькими способами можно выбрать k объектов, если важен порядок их расположения в выборке?)

Пример 1. Дано:

Сколько существует способов разместить с повторениями из трех ягод по две?

Решение: А3(повт)2 = 32= 9

Ответ: 9

Пример 2. Согласно государственному стандарту, автомобильный номерной знак состоит из 3 цифр и 3 букв. При этом недопустим номер с тремя нулями, а буквы выбираются из набора А, В, Е, К, М, Н, О, Р, С, Т, У, Х  (используются только те буквы кириллицы, написание которых совпадает с латинскими буквами). Сколько различных номерных знаков можно составить для региона?

• Решение:
• А10(повт)3 = 103 = 1000 –способами можно составить цифровую комбинацию автомобильного номера, при этом одну из них (000) следует исключить А10(повт)3   — 1 = 999
• А12(повт)3 = 123 = 1728 – способами можно составить буквенную комбинацию автомобильного номера.
• По правилу умножения комбинаций, всего можно составить: А10(повт)3  ⋅  А12(повт)3 = 999 ⋅ 1728 =   1 726 272 автомобильных номера для региона. 
• Ответ: 1 726 272.

Пример 3. Человек, пришедший в гости, забыл код, открывающий дверь подъезда, но помнил, что он составлен из нулей и единиц и всего имеет четыре цифры. Сколько вариантов кода в худшем случае ему придётся перебрать, чтобы открыть дверь?

Решение: А2(повт)4 = 24 = 16

Ответ: 16.

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

Решение: Подсчитаем количество чисел от 1 до 999999 в записи которых нет единиц. Каждую цифру можно выбрать 9 способами (любая цифра кроме 1), поэтому все 6 цифр можно выбрать 96 способами.

При этом один вариант (000000) нужно убрать, так как число 0 не рассматривается. Получаем всего 96 − 1 = 531 440 чисел.

Так как всего чисел 1 000 000, то видно, что чисел без единицы среди чисел от 1 до 1 000 000 больше, чем тех, в записи которых единица есть.

Ответ: чисел без единицы больше.

Комбинаторика: основные правила и формулы

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

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

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

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

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

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

Пример 1.

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

Решение

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

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

Правило произведения.  Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n1 способами, второе действие n2 способами, третье – n3 способами и так до k-го действия, которое можно выполнить nk  способами, то все k действий вместе могут быть выполнены:

способами.

Пример 2.

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

Решение

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

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

• По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.
•  Сочетания без повторений. Сочетания с повторениями
• Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов?
• 
• Пример 3.

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

Решение

Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:

1. Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?
2. .
3. Пример 4.

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

Решение

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

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

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

Решение.

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

1. Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.
2. Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?
4. Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?

• Решение
• Можно  считать,  что  опыт  состоит  в 5-кратном выборе  с возращением одной из 3 цифр (1, 3, 7). Таким образом,  число  пятизначных  номеров  определяется  числом  размещений с повторениями из 3 элементов по 5:
• .
•  Перестановки без повторений. Перестановки с повторениями
• Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?
• Пример 7.
• Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?
• Решение

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

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

1. Пример 8.
2. Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?
3. Решение
4. Здесь 1 буква  «м», 4 буквы «и», 3 буквы «c» и 1 буква  «п», всего 9 букв. Следовательно, число перестановок с повторениями равно
5. ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ «КОМБИНАТОРИКА»

Лекция по теме "Основы комбинаторики"

Дисциплина
«Теория вероятностей и математической статистики»

Раздел 1. Элементы комбинаторики

                          
Тема 2.  Основы комбинаторики

• 1.    
  Основные понятия
• 2.    
  Перестановки
• 3.    
  Размещения
• 4.    
  Сочетания
• 5.    
  Правило сложения комбинаций
• 6.    
  Правило умножения комбинаций
• 7.    
  Перестановки
  с повторениями
• 8.    
  Сочетания
  с повторениями
• 9.    
  Размещения
  с повторениями
• Основные понятия
• Определение:Комбинаторика – это
  раздел математики, в котором изучаются вопросы о том, сколько различных
  комбинаций, подчиненных тем или иным условиям, можно составить из заданных
  объектов.

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

1. Термин
   «комбинаторика» был введён знаменитым Готфридом Вильгельмом
   Лейбницем, — всемирно известным немецким учёным.
2. Комбинаторные задачи 
   делятся на:задачи на перестановки, задачи на размещение, задачи на
   сочетание
3. Определение:Факториал – это
   произведение всех натуральных  чисел от 1 до n.

Обозначение: n! = 1 · 2 · 3 · … ·
n.Читается: «эн факториал».

Пример:  4! = 1 · 2 · 3 ·
4 = 24.

Кроме того: 0! = 1.

• Перестановки
• Определение: Перестановками из n элементов называются
  комбинации из n элементов,
  отличающиеся друг от друга только порядком расположения в них элементов.
• Формула
• Типичная смысловая
  нагрузка: «Сколькими способами можно переставить n объектов?»
• Сколькими способами можно
  расставить 3 различные книги на книжной полке?

Решение: Выбираем одну из
3-х книг и ставим на первое место. Это можно сделать 3-мя способами.

1. Вторую книгу мы можем
   выбрать из 2-х оставшихся двумя способами, получаем 3·2 способов.
2. Третью книгу мы можем
   выбрать 1 способом.
3. Получится 3·2·1=6
   способов.
4. Ответ: 6.

Пример 1. Сколькими
способами можно расставить  8 участников  финального забега  на  восьми беговых
дорожках?

Решение: P8= 8!=1 ∙ 2 ∙ 3 ∙
4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 = 40320.

Ответ:  40320.

Пример 2. Сколькими
способами можно составить расписание на один день, если в этот день
предусмотрено 6 уроков по 6 разным предметам?

Решение: P6= 6!=1 ∙2 ∙ 3 ∙ 4
∙ 5 ∙ 6 = 720.

Ответ:  720.

Пример 3. Сколькими
различными способами можно разместить на скамейке 10 человек?

Решение: P8= 8!=1 ∙ 2 ∙ 3 ∙
4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 ∙ 9 ∙ 10 = 3628800.

Ответ: 3628800.

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

Решение: P4= 4!=1 ∙2 ∙ 3 ∙ 4
= 24.

Ответ: 24.

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

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

P5= 5!=1 ∙ 2 ∙ 3 ∙
4 ∙ 5 = 120.

• Ответ: 120.
• Размещения
• Определение: Размещением  из n элементов по k (k≤n) называется любое
  множество, состоящее из k элементов, взятых в определённом порядке из данных n элементов.
• Формула:
• Типичная смысловая
  нагрузка: «Сколькими способами можно выбрать k объектов и в
  каждой выборке переставить их местами?»
• Имеется  5 книг и одна
  полка, такая  что на ней вмещается лишь 3 книги.
• Сколькими способами можно
  расставить на полке 3 книги?
• Это задача на размещение.

Решение: Выбираем одну из
5-ти книг и ставим на первое место на полке. Это можно сделать 5-ю способами.

1. Вторую книгу мы можем
   выбрать 4-мя способами и поставить рядом с одной из 5-ти возможных первых.
2. Таких пар может быть 5·4.
3. Третью книгу мы можем
   выбрать 3-мя способами.

Получится 5·4·3
разнообразных троек. Значит всего способов разместить 3 книги из 5-ти 5·4·3 =
60.

Ответ: 60.

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

Решение: 

Ответ: 3024.

Пример 2. Сколько
трехзначных чисел можно составить из цифр 2, 4, 6, 7, 9?

Решение:

Ответ: 60.

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

Решение:

Ответ: 4896.

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

Решение:

Ответ:55440.

Пример 5. Боря, Дима и
Володя сели играть в карты. Сколькими способами им можно сдать по одной
карте? (колода содержит 36 карт)

• Решение:
• – способами можно раздать 3 карты игрокам.
• Ответ: 42840.

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

1. Решение:
2. – способами можно рассадить в поезде 4 человека.
3. Ответ: 3024.
4. Сочетания
5. Определение: Сочетанием из n
   элементов по k (k

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

• Комбинаторика — это раздел математики,
  в котором изучаются вопросы о том,
  сколько различных комбинаций, подчиненных
  тем или иным условиям, можно составить
  из элементов, принадлежащих данному
  множеству.
• Решение многих комбинаторных задач
  основывается на двух фундаментальных
  правилах, называемых правилом суммы
  иправилом произведения.
• Правило суммы
• Если некоторый объект А может быть
  выбран из совокупности объектов nспособами, а другой объект В может быть
  выбранmспособами,
  то выбрать либо объект А, либо объект В
  можноспособами.
• Правило произведения
• Если объект А может быть выбран из
  совокупности объектов nспособами и посла каждого такого выбора
  объект В может быть выбранmспособами, то пара объектов (А,В) в
  указанном порядке может быть выбранаспособами.
• Примеры.

1. В первом ящике 8 шаров, во втором -10 шаров. Сколькими способами можно выбрать один шар из двух ящиков?

► Событие А – выбор шара из первого
ящика, он может быть осуществлен 8-ю
способами, событие В – выбор шара из
второго ящика, он может быть осуществлен
10-ю способами, т.е. n=8,m=10. Событие А+В – выбор
одного шара либо из первого ящика, либо
из второго. По правилу суммы
находим:=8+10=18.

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

1.5. Основные формулы комбинаторики

Пусть дано конечное множество X,
состоящее изnэлементов.

Размещениемизnэлементов поmмножестваXназывают любые
наборы, которые отличаются либо составом
элементов, либо их порядком:

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

n!. (5)

1. Сочетаниемизnэлементов поmмножестваXназывают любые
   неупорядоченные наборы, которые
   отличаются хотя бы одним элементом:
2. . (6)
3. Отсюда может быть выведена формула размещения, более удобная для счета:
4. . (7)

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

=. (8)

Примеры.

1. Сколько различных двузначных чисел можно составить из чисел 1,2,3,4?

1. Сколько различных четырехзначных чисел можно составить из чисел 1,2,3,4?

1. Сколькими способами можно выбрать две детали из ящика с десятью деталями?

1. Сколько различных шестизначных чисел можно составить из трех единиц, одной двойки и двух троек?

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

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

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

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

Пусть X– множество
изnэлементов. Достаем
один элемент, фиксируем, кладем элемент
обратно. Выборку производимтраз.
Число таких наборов изnэлементов множестваXпоmравно

Пример 13. Сколько существует
трехзначных телефонных номеров?

►.

XII Международный конкурс научно-исследовательских и творческих работ учащихся Старт в науке

Шухратбеков А.Ш. 1Тоштемиров А.Ф. 11Академический лицей Международного Вестминстерского университета в Ташкенте

Текст работы размещён без изображений и формул.

Полная версия работы доступна во вкладке «Файлы работы» в формате PDF

• Введение
• «Число, положение и комбинация —
• три взаимно пересекающиеся, но
• различные сферы мысли, к которым
• можно отнести все математические
• идеи».

Дж. Сильвестр (1844 г.)

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

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

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

Комбинаторика возникла в XVI веке. В жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры. Широко были распространены всевозможные лотереи.

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

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

Одним из первых занялся подсчетом числа различных комбинаций при игре в кости итальянский математик Тарталья. Он составил таблицу, показывавшую, сколькими способами могут выпасть r костей. Однако при этом не учитывалось, что одна и та же сумма очков может быть получена разными способами (например, 1+3+4=4+2+2)

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

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

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

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

1. Основные формулы комбинаторики
2. На самом начальном этапе нужно изучить основные формулы комбинаторики: сочетания, размещения, перестановки и научиться их применять для решения задач.
3. Комбинаторика перестановки
4. «Сколькими способами можно переставить n объектов?»

Пусть имеется n различных объектов. Будем переставлять их всеми возможными способами (число объектов остается неизменными, меняется только их порядок). Получившиеся комбинации называются перестановками, а их число равно

Pn=n!=1⋅2⋅3⋅…⋅(n−1)⋅n

Символ n! называется факториалом и обозначает произведение всех целых чисел от 1 до n

Пример всех перестановок из n=3 объектов (различных фигур) — на картинке справа. Согласно формуле, их должно быть ровно P3=3!=1⋅2⋅3=6так и получается.

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

=n!(n−m)!=n⋅(n−1)⋅…⋅(n−m+1)

Пример всех размещений из n=3 объектов (различных фигур) по m=2m=2 — на картинке справа. Согласно формуле, их должно быть ровно A23=3⋅(3−2+1)=3⋅2=6A32=3⋅(3−2+1)=3⋅2=6. Комбинаторика сочетания

Пусть имеется n различных объектов.

Будем выбирать из них m объектов все возможными способами (то есть меняется состав выбранных объектов, но порядок не важен). Получившиеся комбинации называются сочетаниями из n объектов по m, а их число равно

=n!(n−m)!⋅m!

Пример всех сочетаний из n=3 объектов (различных фигур) по m=2 — на картинке справа. Согласно формуле, их должно быть ровно =3!(3−2)!⋅2!=3. Ясно, что сочетаний всегда меньше чем размещений (так как при размещениях порядок важен, а для сочетаний — нет), причем именно в m! раз, то есть верна формула связи:

=⋅Pm

Основные комбинаторные объекты и методы

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

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

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

1. Есть несколько основных типов комбинаторных задач:
2. — существование объекта с заданными свойствами;
3. — подсчет или оценка количества искомых комбинаций или их описание;
4. — поиск оптимальной комбинации по какому-то параметру.

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

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

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

Морской семафор

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

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

Так как у нас два флажка, то общее число комбинаций основных положений равно А — 5^2— 25. При этом еще надо отбросить положение, когда оба флажка направлены вниз — оно служит для разделения слов. Всего получаем 24 комбинации, а этого недостаточно для передачи всех букв русского алфавита.

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

Генетический код

Замечательным открытием биологии XX века была разгадка генетического кода. Удалось выяснить, каким образом наследственная информация передается потомству. Оказалось, что эта информация записана в гигантских молекулах дезоксирибонуклеиновой кислоты (ДНК).

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

Ведь с помощью комбинаций двух оснований можно зашифровать лишь 4^2=16 аминокислот, а этого недостаточно. Если же брать по 3 основания, то получим 4^3=64 комбинации. А этого с избытком хватит, чтобы зашифровать два десятка.

Было бы весьма интересно узнать, как используется в природе избыточность информации-ведь число комбинаций равно 64, а число аминокислот втрое меньше. В одной хромосоме содержится несколько десятков миллионов азотистых оснований. Число различных комбинаций, в которых они могут идти друг за другом, невообразимо велико).

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

Заключение

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

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

Усиление интереса к комбинаторике в последнее время обуславливается бурным развитием кибернетики.

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

Литература

Н.Я. Виленкин “Комбинаторика”, 1969

М. А. Иванов, Ю. В. Якубович “Введение в комбинаторику. Теория и задачи”. 2018