КОМБИНАТОРИКА
Комбинаторика – раздел математики, который изучает задачи выбора и расположения элементов из некоторого основного множества в соответствии с заданными правилами. Формулы и принципы комбинаторики используются в теории вероятностей для подсчета вероятности случайных событий и, соответственно, получения законов распределения случайных величин. Это, в свою очередь, позволяет исследовать закономерности массовых случайных явлений, что является весьма важным для правильного понимания статистических закономерностей, проявляющихся в природе и технике.
Правила сложения и умножения в комбинаторике
Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В – n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.
Пример 1.
В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?
Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.
По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.
Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n1 способами, второе действие n2 способами, третье – n3 способами и так до k-го действия, которое можно выполнить nk способами, то все k действий вместе могут быть выполнены:
Пример 2.
В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?
Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.
После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.
По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.
Сочетания без повторений. Сочетания с повторениями
Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?
Пример 3.
Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?
Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:
.
Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m (
) из этих (n*r) предметов?
.
Пример 4.
В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?
Т.к. среди 7 пирожных могут быть пирожные одного сорта, то число способов, которыми можно купить 7 пирожных, определяется числом сочетаний с повторениями из 7 по 4.
.
Размещения без повторений. Размещения с повторениями
Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?
Пример 5.
В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?
В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:
Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.
Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?
Пример 6.
У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?
Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр (1, 3, 7). Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:
.
Перестановки без повторений. Перестановки с повторениями
Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?
Пример 7.
Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?
Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.
Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k
Пример 8.
Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?
Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно
ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ «КОМБИНАТОРИКА»
Источник
Сколькими способами можно построить шеренгу
Сколькими способами можно построить их в одну шеренгу?
Приветствую, :friends: В классе 12 девочек и 10 мальчиков. Сколькими способами можно .
Сколькими способами можно построить 9 человек в колонну по 3 шеренги
Здравствуйте, не могу понять, как решить задачу. Понимаю, что через число сочетаний, но не могу.
сколькими способами можно поставить
Энциклопедия состоит из девяти томов — с первого по девятый.Сколькими способами её можно поставить.
Сколькими способами можно выбрать.?
Сколькими способами можно выбрать 4 набора по 5 карт из колоды, содержащей 52 карты?
Сколькими способами можно разменять
Сколькими способами можно разменять 100руб в 5,10,20 и 50 руб? решить рекурсией..помогите.
Сколькими способами можно разместить
Сколькими способами можно разместить
Сколькими способами можно распределить
В распоряжении ГУВД поступило 28 новых одинаковых машин, которые нужно распределить между 4.
Источник
Комбинаторика
В классе 17 мальчиков и 4 девочки. Сколькими способами Андрей Анатольевич может построить их в шеренгу так, чтобы никакие две девочки не стояли рядом?
задан 27 Апр ’15 1:45
587896
25 ● 4 ● 8
87% принятых
@587896, Если вам дан исчерпывающий ответ, отметьте его как верный (нажмите на галку рядом с выбранным ответом).
1 ответ
Сначала построим всех мальчиков в шеренгу. Это можно сделать $%17!$% способами (число перестановок). При этом образуется $%18$% различных мест для расположения девочек: перед первым мальчиком; между первым и вторым; . ; после 17-го мальчика. Разместить четырёх девочек на этих местах можно $%A_<18>^4$% способами (число размещений). Первую девочку ставим на одно из $%18$% мест, потом вторую на одно из $%17$% оставшихся, затем третью и четвёртую.
По правилу произведения, получается, что общее число способов равно $%17!\cdot A_<18>^4=17!\cdot18\cdot17\cdot16\cdot15$%. Можно выразить через одни факториалы: $%\frac<17!\,18!><14!>$%.
отвечен 27 Апр ’15 2:17
falcao
268k ● 6 ● 37 ● 51
falcao, в условии сказано, чтобы никакие две девочки не стояли рядом, а не чтобы все 4 девочки стояли рядом.
@587896: каждая из этих четырех девочек будет стоять на одном из 18 мест, которые РАЗДЕЛЕНЫ мальчиками.
Например, 1-я девочка стоит перед 1-м мальчиков, 2-я девочка перед 2-м, 3-я перед 3-м, 4-я перед 4-м. Вот такие способы нужны. Только как их посчитать, не знаю.
@587896: у нас все девочки стоят так, как сказано в условии. Не стоят рядом — означает, что между девочками есть мальчик. Именно это и требовалось.
Если ввести какие-то ещё ограничения, то это будет новая задача. У неё, скорее всего, будет какой-то другой ответ.
Вам их даже уже посчитали. Нарисуйте мальчиков как палочки. Между ними — 16 мест и два по краям — всего 18 мест куда можно ставить девочек. То есть у вас 18 мест и 4 девочки. Количество способов расставить сюда девочек — $%A_<18>^<4>$%. Дальше — читайте решение.
Источник
Элементы комбинаторики
Правило сложения
Правило сложения используется в том случае, если у нас есть два или более множеств, которые попарно не пересекаются, то есть не имеют общих элементов. И нам нужно найти сколько элементов содержится в объединении этих множеств. В этом случае мы складываем число элементов в каждом множестве. Простейший пример: если у нас есть две корзинки с фруктами: в одной 5 яблок, а в другой 7 груш. Если мы эти фрукты пересыпаем в одну корзинку (объединяем множества), тогда в новой корзинке окажется 5+7=12 фруктов.
Правило умножения
Правило умножения используется в том случае, если у нас есть два множества, и мы составляем всевозможные пары из элементов этих множеств. Например, если взять множество, состоящее из 5-ти яблок и множество, состоящее из 7-ми груш и составить всевозможные пары из этих фруктов, то мы получим 
всевозможных пар.
Действительно. Возьмем первое яблоко. Мы можем положить к нему любую из семи груш, то есть получаем 7 пар. Возьмем второе яблоко, и к нему мы также можем положить любую из 7-ми груш, получаем ещё 7 пар. И так далее. Всего получается пар.
Правило умножения легко понять, если попытаться ответить, например, на такой вопрос: «сколько существует двузначных чисел?«
Пусть двузначное чиcло имеет вид 
, где 
— число десятков, 
— число единиц. При этом цифра может принимать значения от 1 до 9 ( цифра 0 не может стоять на первом месте, так как в этом случаем мы получим однозначное число), цифра может принимать значения от 0 до 9.
Пусть 
, и у нас есть 10 вариантов цифр, которые могут стоять на втором месте. Тогда мы имеем 10 двузначных чисел, содержащих 1 десяток.
Затем мы берем 
и так же получаем 10 двузначных чисел, у которых теперь уже 2 десятка.
Так как цифра может принимать 9 различных значений, то получаем 
двузначных чисел.
Зная, что на первом месте может стоять 9 различных цифр, а на втором — 10, мы получаем комбинаций этих цифр, то есть все возможные двузначные числа. Здесь важно понимать, что любая цифра, стоящая на первом месте, может сочетаться с любой цифрой, стоящей на втором месте.
В общем случае правило умножения звучит так:
Если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару (A, B) можно выбрать n·m способами. Это правило распространяется на любое число независимо выбираемых элементов.
Если мы хотим ответить на вопрос, сколько существует трехзначных чисел, мы заметим, что в трехзначном числе 
первая цифра может принимать 9 значений, вторая — 10, и третья 
— 10 значений. И мы получаем 
трехзначных чисел.
Формула включений-исключений
используется в том случае, если нам нужно найти число элементов в объединении двух множеств, в том случае, если эти множества пересекаются.
Пусть множество А содержит n элементов, множество В содержит m элементов, и пересечение этих множеств 
содержит k элементов. То есть k элементов содержатся и в множестве А, и в множестве В. Тогда объединение множеств 
содержит m+n-k элементов.
Действительно, при объединении двух множеств мы k элементов посчитали два раза, и теперь один раз мы должны их вычесть.
Число элементов в множестве обозначается общепринятым значком #. Тогда формула для подсчета числа элементов в объединении трех множеств имеет вид:
# 
# 
# 
# 
# 
# 
# 
# 
Рассмотрим примеры задач.
1. Сколько трехзначных чисел содержит хотя бы одну цифру 3?
Если вопрос задачи содержит слова «хотя бы», то в большинстве случаев сначала надо ответить на противоположное утверждение.
Найдем, сколько трехзначных чисел НЕ содержит цифру 3. В этом случае на первом, втором и третьем месте в записи числа может стоять любая цифра кроме 3. То есть первая цифра может принимать 8 значений, вторая — 9, и третья — 9 значений. Тогда мы получаем 
трехзначных чисел, которые НЕ содержит цифру 3. Следовательно, остальные 
числа содержат хотя бы одну цифру 3.
2. Сколько четырехзначных чисел, кратных 5.
Мы знаем, что число делится на 5, если оно оканчивается на 0 или 5. Следовательно, в четырехзначном числе 
последняя цифра может принимать только два значения: 0 и 5.
Первая цифра может принимать 9 значений, вторая — 10, и третья — 10 значений, четвертая 
— 2 значения.
Тогда мы получаем 
четырехзначных чисел, которые делятся на 5.
Перестановки
Воспользуемся правилом умножения чтобы ответить на вопрос, «сколькими способами можно построить 7 человек в шеренгу?».
Человека, стоящего первым в шеренге можно выбрать семью способами, второго можно выбрать из оставшихся шести человек, то есть шестью способами. Третьего, соответственно, пятью. И так далее. Последнего можно выбрать единственным способом. Всего получаем 
способов построить 7 человек в шеренгу.
В общем случае, если мы имеем 
объектов, которые хотим расположить в определенном порядке (пронумеровать их), то мы получим
способов расположения этих объектов.
Факториалом натурального числа 
называется произведение всех натуральных чисел от 1 до : 
По определению 0!=1; 1!=1.
Перестановкой из предметов называется любой способ нумерации этих предметов (способ расположения их в ряд).
Число перестановок предметов равно .
3. Имеется 10 компьютерных дисков и 10 коробок от них. Найдите вероятность того, что случайным образом уложив диски в коробки, мы обнаружим, что
1. Каждый диск лежит в своей коробке.
2. Хотя бы один диск лежит не в своей коробке.
3. Два определенных диска перепутаны местами, а остальные в своих коробках.
4. Ровно один лежит не в своей коробке, а остальные — в своих коробках.
1. Пронумеруем диски и коробки. Расположим коробки в определенной последовательности. Нам нужно, чтобы при случайном расположении дисков в ряд, их номера тоже оказались расположены в той же последовательности.
Расположить 10 чисел в определенной последовательности можно единственным способом, то есть мы имеем 1 благоприятный исход.
Расположить 10 чисел в произвольном порядке можно 10! способами.
Следовательно, вероятность того, что каждый диск окажется в своей коробке равна
2. Событие «хотя бы один диск лежит не в свой коробке» противоположно событию «каждый диск лежит в своей коробке«, и его вероятность равна
3. Событие «два определенных диска перепутаны местами, а остальные в своих коробках», также как событие «каждый диск лежит в своей коробке«, имеет единственный благоприятный исход, поэтому вероятность этого события равна
4. Событие «ровно один лежит не в своей коробке, а остальные — в своих коробках» невозможно, так как если один диск лежит не своей коробке, то обязательно должен найтись ещё один, который так же лежит не в своей коробке. Поэтому вероятность этого события равна нулю.
4. Слово «МАТЕМАТИКА» написали на полоске картона и разрезали полоску на буквы. Найдите вероятность того, что составив все эти буквы случайным образом в ряд, мы снова получим слово «МАТЕМАТИКА».
Сколько буквосочетаний можно составить из букв слова «МАТЕМАТИКА»?
Вероятность того, что на первом месте будет стоять буква М равна 2/10 — у нас две буквы М, и всего 10 букв.
Вероятность того, что на втором месте будет стоять буква А равна 3/9 — у нас осталось 9 букв, из которых 3 буквы А.
Вероятность того, что на втором месте будет стоять буква Т равна 2/8 — у нас осталось 8 букв, из которых 2 буквы Т.
И так далее. В итоге получаем:
Пронумеруем все буквы в слове «МАТЕМАТИКА». Найдем, сколькими способами мы можем их расположить в определенном порядке. В слове 10 букв, и мы можем их расположить 10!=3628800 различными способами.
Поскольку в слове есть одинаковые буквы, то при перестановке этих букв мы получим то же слово:
в слове «МАТЕМАТИКА» 2 буквы «М»; 3 буквы «А»; 2 буквы «Т», следовательно по правилу произведения это дает нам 
способов перестановки этих букв с сохранением слова «МАТЕМАТИКА».
Таким образом, вероятность снова получить слово «МАТЕМАТИКА» равна:
Сколько буквосочетаний можно составить из букв слова «МАТЕМАТИКА»?
Из 10 букв слова «МАТЕМАТИКА» можно составить 10! буквосочетаний. Но некоторые из них будут одинаковыми, так как при перестановке одинаковых букв, мы будем получать те же буквосочетания. То есть в итоге мы получим
Размещения
В задачах по теории вероятностей часто возникает необходимость определить, сколькими способами можно выбрать определенное число предметов и расположить их в определенном порядке.
5. Сколько существует различных вариантов выбора 4-х кандидатур из 9-ти специалистов для поездки в 4 различных страны?
Воспользуемся правилом умножения.
В первую страну мы выбираем из 9 специалистов, то есть у нас 9 вариантов выбора. После того, как специалист для поездки в первую страну выбран, у нас осталось 8 специалистов, и для поездки во вторую страну у нас 8 вариантов выбора. И так далее. в четвертую страну мы можем выбрать кандидата из 6 специалистов.
Таким образом, мы получаем 
вариантов выбора 4-х кандидатур из 9-ти специалистов для поездки в 4 различных страны.
Обобщим эту задачу на случай выбора k кандидатур из n специалистов для поездки в k различных стран.
Рассуждая аналогичным образом, мы получаем
Если умножить и разделить это выражение на 
, то получим следующую формулу:
В этой задаче из множества, состоящего из элементов мы выбрали упорядоченные подмножества (для нас был важен порядок расположения элементов в подмножестве), состоящие из 
элементов. Задача сводилась к нахождению числа таких подмножеств.
Такие упорядоченные подмножества называются размещениями из n элементов по k.
Пусть у нас есть множество 
, состоящее из элементов. Размещением (из n по k) называется упорядоченное подмножество из различных элементов из некоторого множества , состоящего из различных элементов.
Число размещений из элементов по обозначается 
и находится по формуле:
Размещения с повторениями
6. Игральную кость бросают трижды. Сколько различных комбинаций выпавших очков при этом получится?
При бросании кости первый раз мы получим 6 различных вариантов: 1 очко, 2, 3. или 6. Аналогично при бросании кости во второй и в третий раз мы получим также по 6 различных вариантов. По правилу умножения получим число различных комбинаций трех чисел, принимающих значения от 1 до 6: 
Пусть у нас есть множество , состоящее из элементов.
Любой упорядоченный набор элементов множества, состоящего из элементов называется размещением с повторением из элементов по . Число различных размещений с повторениями равно
Действительно. Представим ящик с пронумерованными шарами. Мы вынимаем шар, записываем его номер и возвращаем обратно, и так раз. Сколько комбинаций из номеров мы можем получить?
Поскольку шары каждый раз возвращаются, каждый раз, вынимая шар из коробки, в которой шаров, мы можем получить различных чисел. По правилу умножения имеем
Сочетания
Рассмотрим задачу, аналогичную задаче 5, но с существенным отличием.
7. Сколько существует различных вариантов выбора 4-х кандидатур из 9-ти специалистов?
В этой задаче нам нужно выбрать 4 кандидатуры, но при этом не важно, в каком порядке мы их выбираем, нас интересует только состав выбранных элементов, но не порядок их расположения.
Если бы нас интересовал порядок расположения элементов, как в задаче 5, то мы могли применили бы формулу для нахождения числа размещений из 9 по 4:
4 различных элемента можно расположить в определенном порядке 4! различными способами. Поскольку нас не интересует порядок расположения элементов, число способов, которыми мы можем выбрать 4 элемента, не располагая их в определенном порядке, уменьшается в 4! раза по сравнению с предыдущей задачей (так как для данной задачи различное расположение данных элементов считается одним способом), и мы получаем
В этой задаче появляется понятие сочетания.
Сочетаниями из n элементов по k элементов называются подмножества, состоящие из k элементов множества (множества, состоящего из n элементов).
Внимание! Одно сочетание от другого отличается только составом выбранных элементов (но не порядком их расположения, как у размещений).
Число сочетаний из n элементов по k элементов обозначается
и находится по формуле:
Число сочетаний из n по k показывает, сколькими способами мы можем выбрать k элементов из n элементов, или сколькими способами мы можем расположить k объектов по n местам.
Легко заметить, что
8. В коробке лежат 8 красных карандашей и 4 синих. Из коробки наугад вынимают 4 карандаша. Какова вероятность того, что среди них окажется 2 красных и 2 синих?
Всего в коробке 12 карандашей. Найдем, сколькими способами способами можно извлечь из коробки 4 карандаша. Так как нас не интересует порядок, в котором карандаши извлекаются из коробки, а только состав карандашей, это число равно числу сочетаний из 12 по 4:
Из 8 красных карандашей можно извлечь два карандаша 
способами.
Из 4 синих карандашей можно извлечь два карандаша 
способами.
По правилу произведения получаем, что извлечь 2 синих и 2 красных карандаша можно 
способами.
Таким образом, искомая вероятность равна:
Метод шаров и перегородок
9. Сколькими способами можно разложить 10 шаров в 4 коробки? Предполагается, что некоторые коробки могут оказаться пустыми.
Рассмотрим 10 шаров:
Будем «раскладывать шары по коробкам», ставя перегородки.
В этом примере в первой коробке 3 шара, во второй — 2, в третьей — 4, и в четвертой — 2. Переставляя шары и перегородки, мы получаем различные комбинации шаров в коробках. Например, переставив последний шар в первой коробке и первую внутреннюю перегородку, мы получим такую комбинацию:
Таким образом, мы получаем различное число шаров в коробках, комбинируя позиции 10-ти шаров и 3-х внутренних перегородок. Чтобы определить, сколько различных комбинаций мы можем получить, нам нужно найти число сочетаний из 13 по 3. (Или, что то же самое, что число сочетаний из 13 по 10.) Столько способов выбрать 3 места для перегородок из 13 возможных позиций. Или, что то же самое, 10 мест для шаров.
10. Сколько решений имеет уравнение 
в целых неотрицательных числах?
Так как переменные 
могут принимать только целые неотрицательные значения, следовательно, у нас есть 10 переменных, и они могут принимать значения 0, 1, 2, 3 и 4. Представим, что у нас есть 10 коробок (это переменные), и мы должны разложить по этим коробкам 4 шара. Сколько шаров попадет в коробку, таково значение соответствующей переменной. Если у нас 10 коробок, следовательно, 10-1=9 внутренних перегородки. И 4 шара. Всего 13 мест. Нам надо расположить на этих 13 местах 4 шара. Число таких возможностей:
В общем случае, если нам нужно разложить шаров в коробок, мы получаем комбинации из шаров и 
внутренней перегородки. И число таких комбинаций равно числу сочетаний из 
по .
В этой задаче мы имели дело с сочетаниями с повторениями.
Сочетания с повторениями
Сочетаниями из элементов по элементов с повторениями называются группы, содержащие элементов, причем каждый элемент принадлежит к одному из типов.
Что такое сочетания из элементов по элементов с повторениями можно понять с помощью такого мысленного эксперимента. Представим ящик с пронумерованными шарами. Мы вынимаем шар, записываем его номер и возвращаем обратно, и так раз. В отличие от размещений с повторениями нас не интересует порядок записанных чисел, а только их состав. Например, группы чисел <1,1,2,1,3,1,2>и <1,1,1,1,2,2,3>считаются одинаковыми. Сколько таких групп из номеров мы можем получить?
В конечном итоге нас интересует сколько элементов каждого типа (всего n типов элементов) содержится в каждой группе (из k элементов), и сколько таких различных вариантов может быть. То есть мы находим, сколько в целых неотрицательных решений имеет уравнение уравнение 
— задача аналогична задаче по раскладыванию n шаров в k коробок.
Число сочетаний с повторениями находится по такой формуле:
Таким образом, число сочетаний с повторениями — это количество способов представить число k в виде суммы n слагаемых.
Источник
