Глава 10. Комбинаторика. Комбинаторные конфигурации
Во многих практических случаях возникает необходимость подсчитать количество возможных комбинаций объектов, удовлетворяющих определенным условиям. Такие задачи называются Комбинаторными. Разнообразие комбинаторных задач не поддается исчерпывающему описанию, но среди них есть целый ряд особенно часто встречающихся, для которых известны способы подсчета.
Число всех функций (при отсутствии ограничений), или число всех возможных способов разместить П Предметов по Т Ящикам называется, Числом размещений И обозначается U(M,N).
Каждый из N предметов можно разместить M способами.
При игре в кости бросаются две кости и выпавшие на верхних гранях очки складываются. Какова вероятность выбросить 12 очков? Каждый возможный исход соответствует функции F: <1,2>® <1,2,3,4,5,6>(аргумент — номер кости, результат — очки на верхней грани). Таким образом, всего возможно U(6,2) = 62 = 36 различных исходов. Из них только один (6 + 6) дает двенадцать очков. Вероятность 1/36.
Размещения без повторений
Число инъективных функций, или число всех возможных способов разместить П Предметов по M ящикам, не более чем по одному в ящик, называется Числом размещений без повторений И обозначается А(M, п) или [M]n, или (M)n.
ТЕОРЕМА 
Ящик для первого предмета можно выбрать M способами, для второго — M — 1 способами, и т. д. Таким образом,
По определению считают, что А(Т, N) = 0 при П > Т И А(Т, 0) = 1.
В некоторых видах спортивных соревнований исходом является определение участников, занявших первое, второе и третье места. Сколько возможно различных исходов, если в соревновании участвуют П Участников? Каждый возможный исход соответствует функции F: <1,2,3>® <1..N> (аргумент — номер призового места, результат — номер участника). Таким образом, всего возможно А(П,3) = П(П — 1)(N — 2) различных исходов.
Число взаимнооднозначных функций, или Число перестановок п Предметов, обозначается Р(П).
Последовательность E = (E1. Em) непустых подмножеств множества Е (E Ì 2E, Ei Ì Е, Ei ¹ Æ) называется Цепочкой В Е, Если
Цепочка E называется Полной Цепочкой в Е, Если |E| = |Е|. Сколько существует полных цепочек? Очевидно, что в полной цепочке каждое следующее подмножество Ei+1 получено из предыдущего подмножества Ei Добавлением ровно одного элемента из Е И, таким образом, |E1| = 1, |E2| = 2, . |Ет| = |Е| = т. Следовательно, полная цепочка определяется порядком, в котором элементы Е Добавляются для образования очередного элемента полной цепочки. Отсюда количество полных цепочек — это количество перестановок элементов множества Е, Равное M!.
Число строго монотонных функций, или число размещений П Неразличимых предметов по Т Ящикам, не более чем по одному в ящик, то есть число способов выбрать из m ящиков N ящиков с предметами, называется Числом сочетаний И обозначается С(Т, п) или 
или 
.
ТЕОРЕМА 
1. Число размещений без повторений нужно разделить на число перестановок, поскольку предметы неразличимы.
2. Число сочетаний является числом строго монотонных функций, потому что строго монотонная функция F: 1..п ® L..M определяется набором своих значений, причем 1£ F(1) M.
В начале игры в домино каждому играющему выдается 7 костей из имеющихся 28 различных костей. Сколько существует различных комбинаций костей, которые игрок может получить в начале игры? Очевидно, что искомое число равно числу 7-элементных подмножеств 28-элементного множества. Имеем:
Сочетания с повторениями
Число монотонных функций, или число размещений N неразличимых предметов по M ящикам, называется Числом сочетаний с повторениями И обозначается V(M, N).
Сколькими способами можно рассадить N Вновь прибывших гостей среди M Гостей, уже сидящих за круглым столом? Очевидно, что между то сидящими за круглым столом гостями имеется M Промежутков, в которые можно рассаживать вновь прибывших. Таким образом, это можно сделать
Источник
Сколькими способами можно разместить шары по ящикам без ограничений
Добрый день. Есть две задачи:
1) Есть N разных шаров и M одинаковых ящиков. Сколькими способами можно разместить шары по ящикам без ограничений, т.е. в одном ящике может быть от 0 до N шаров.
2) Есть N одинаковых шаров и M разных ящиков. Сколькими способами можно разместить шары по ящикам без ограничений, т.е. в одном ящике может быть от 0 до N шаров.
Я правильно понимаю, что для 2 задачи подойдет формула , т.е. это количество способов разместить M-1 перегородку по N+M-1 возможным местам?
Подскажите, как решать первую задачу, пожалуйста.
Сколькими способами можно разложить шары по ящикам?
Сколькими способами можно разложить 8 одинаковых шаров по 3 одинаковым ящикам?
Сколькими способами можно разложить все шары по ящикам?
Имеется 6 различных ящиков и 10 неразличимых шаров. Сколькими способами можно разложить все шары.
Сколькими способами можно разместить N шаров по N ящикам
Сколькими способами можно разместить N шаров по N ящикам, включая те случаи когда несколько ящиков.
Сколькими способами можно разместить шары по урнам?
Здравствуйте. Подскажите пожалуйста по решению данной задачи: сколькими способами можно разместить.
Спасибо большое за ответ.
Не могли бы вы чуть более детально объяснить решение и формулу? В чем именно заключается фишка «одинаковых» ящиков и «разных» шаров, и как это всё влияет на количество возможных вариантов?
И, например, как подсчитать ответ для 10 шаров и 4 ящиков? Не могу понять как именно всё подставить в формулу.
Возможно, у вас есть какие-то ссылки для меня, чтобы я мог ознакомиться. Искал в интернете задачи с «одинаковыми» ящиками и не нашел, к сожалению.
Вот ответ ваш достаточно понятен для меня. Но всё же сижу не могу сообразить как мне с помощью вашей формулы решить свою задачу с 10 шарами и 4 ящиками.
Шары различимы, т.е. важно какие именно попадают в ящики. Т.е. нужно для каждого варианта «вместимости» ящика подобрать разнообразные варианты выбора шаров из N (10) штук.
Получается, что нужно перебирать разнообразные варианты вместимости ящиков (0-10), и для каждого такого варианта перебирать выбор шаров для этих ящиков, начиная с первого ящика, где точно должно быть >1 шара. Я правильно мыслю?
Но вот всё никак не понимаю, как это решить с вашей формулой, эх.
Особенно предложение «Две части формулы связаны с тем, превышает ли количество групп шаров количество ящиков или не превышает.» вводит меня в ступор. Правильно я понимаю, что для каждой левой итерации от k до M мы умножаем всю эту часть на сумму ? Или это у нас идет умножение одной суммы на другую?
Добавлено через 57 минут
Сколькими способами можно разложить a одинаковых шаров по b различным ящикам?
Сколькими способами можно разложить a одинаковых шаров по b различным ящикам, так, чтобы в каждом.
Сколькими способами можно разложить красные и синие шары по урнам?
Имеется 5 урн. Сколькими способами можно разложить 50 красных и 30 синих шаров по 5 занумерованным.
Сколькими способами можно разместить
Сколькими способами можно разместить
Источник
Элементы дискретной математики (стр. 2 )
 | Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
2n – число всех размещений с повторениями из элементов двух типов. Разобьем эти размещения на классы, отнеся в k-ый класс те, в которые входят k элементов первого типа и n–k элементов второго типа. Размещения k-го типа — это ни что иное, как всевозможные перестановки из k элементов первого типа и n–k элементов второго типа. Число таких перестановок равно P(k, n–k)=C(n, k). По правилу суммы общее число размещений всех классов равно . С другой стороны, это же число равно 2n.
Выпишем все сочетания из n элементов а1, …,аn и сделаем следующее преобразование: к сочетанию, не содержащему элемент а1, допишем его, а из сочетаний, куда оно входит, вычеркнем. Легко проверить, что при этом снова получаются все сочетания, и притом по одному разу. Но при этом преобразовании все сочетания, имевшие четное число элементов, превратятся в сочетания, имеющие нечетное число элементов, и обратно. Значит сочетаний с четным и нечетным количеством элементов одинаковое количество (пустое сочетание тоже входит в рассмотрение). Это и выражает данная формула.
На окружности отмечено 11 точек. Сколько существует многоугольников с вершинами в отмеченных точках?
Первый способ. Существует 
треугольников с вершинами в отмеченных точках, 
– четырехугольников, 
– пятиугольников, … , 
– одиннадцатиугольников. Таким образом, по правилу суммы всего многоугольников +++…+. Из четвертого свойства следует, что это выражение равно 211-
—
=1 982.
Второй способ. Любая из одиннадцати точек либо является вершиной рассматриваемого многоугольника, либо не является. Всего вариантов 211. Но одна или две точки не могут составлять многоугольник. Остается 211-— вариантов многоугольников с вершинами в отмеченных точках.
Сочетания с повторениями.
В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?
Эта задача не является задачей на размещения с повторениями, так как порядок, в котором укладывают пирожные в коробку, несуществен. Поэтому она ближе к задачам на сочетания. Но от задач на сочетания она отличается тем, что в комбинации могут быть повторяющиеся элементы. Такие задачи называют задачами на сочетания с повторениями.
Чтобы решить задачу, поступим следующим образом. Зашифруем каждую покупку с помощью нулей и единиц. Сначала напишем столько единиц, сколько куплено наполеонов. Потом, чтобы отделить наполеоны от эклеров, напишем нуль, затем – столько единиц, сколько куплено эклеров, и т. д. Например, если куплено 3 наполеона, 1 эклер, 2 песочных и 1 слоеное пирожное, то получим такую запись: . Ясно, что разным покупкам соответствуют разные комбинации из 7 единиц и 3 нулей. Обратно, каждой комбинации 7 единиц и 3 нулей соответствует какая-то покупка.
Таким образом, число различных покупок равно числу перестановок с повторениями, которые можно составить из 7 единиц и 3 нулей. А это число равно P(7,3)=120.
К тому же самому результату можно было прийти и другим путем, а именно: расположим в каждой покупке пирожные в таком порядке: наполеоны, эклеры, песочные и слоеные, а потом перенумеруем их. Но при нумерации будем к номерам эклеров прибавлять 1, к номерам песочных – 2, к номерам слоеных – 3. К номерам наполеонов ничего прибавлять не будем. Например, пусть куплено 2 наполеона, 3 эклера, 1 песочное пирожное и 1 слоеное. Тогда эти пирожные нумеруются так: 1, 2, 4, 5, 6, 8, 10. Ясно, что самый большой номер может быть 10, самый маленький – 1, а кроме того, ни один из номеров не повторяется, причем они образуют возрастающую последовательность. Обратно, каждой возрастающей последовательности из 7 чисел соответствует некоторая покупка. Например, последовательность 2, 3, 4, 5, 7, 8, 9 соответствует покупке из 4 эклеров и 3 песочных пирожных. Чтобы убедиться в этом, надо отнять от заданных номеров числа 1, 2, 3, 4, 5, 6, 7. Мы получим числа 1, 1, 1, 1, 2, 2, 2. Но 1 мы прибавляли к номерам эклеров, а 2 – к номерам песочных.
Отсюда, общее число покупок равно числу возрастающих последовательностей из 7 чисел от 1 до 10. А число таких последовательностей равно C(10,7)=120.
Сочетаниями с повторениями из n элементов по k называют всевозможные комбинации, составленные из элементов n видов по k элементов в каждой. Комбинации считаются различными, если они отличаются составом, но не порядком входящих в них элементов. В комбинацию могут входить элементы одного вида.
Количество сочетаний с повторениями из n элементов по k обозначают 
. Общее правило вычисления количества сочетаний с повторениями:
Зашифуем каждую комбинацию с помощью нулей и единиц: для каждого типа напишем столько единиц, сколько предметов этого типа входит в комбинацию, а предметы различных типов отделить нулями. При этом число единиц будет k, а число нулей – n–1. Различным комбинациям будут соответствовать различные перестановки с повторениями из k элементов первого вида и n–1 элементов второго вида, а каждой перестановке с повторениями – своя комбинация. Итак, 
.
Встречаются задачи, в которых на сочетания с повторениями накладывается дополнительное условие, например, когда в комбинацию обязательно должны входить элементы r фиксированных типов, где r≤n. Эта задача легко сводится к уже решенной. Для того чтобы обеспечить присутствие заданных r типов, возьмем с самого начала по одному элементу каждого такого типа. Тем самым в k-сочетании окажутся заняты r мест. Поэтому ответом на задачу будет число 
. В частности, если требуется, чтобы в каждом сочетании был элемент каждого из типов (n≤k), то получится 
.
Задача.
Сколько существует различных бросаний двух одинаковых кубиков?
Решение.
Переформулируем задачу. Всего при подбрасывании одного кубика возможны шесть ситуаций – имеем предметы шести различных типов. Подбрасывают два кубика, следовательно, из данных шести типов предметов необходимо выбрать два, причем нас не интересует порядок выбора, и допускается выбор одинаковых предметов. Таким образом, это задача на сочетания с повторением. По формуле для вычисления количества сочетаний с повторением имеем 
различных бросаний двух одинаковых кубиков.
Многим комбинаторным задачам можно придать вид стандартной схемы. В этой схеме объекты (предметы) помещаются в ящики. Из-за наложения различных ограничений получаются различные задачи. Рассмотрим некоторые из них.
Имеется n1 предметов одного сорта, n2 – другого, . , nk – k-го сорта. Сколькими способами можно разложить их в два ящика?
Так как в каждый ящик может попасть от 0 до ni предметов i-го сорта (во второй все оставшиеся), по правилу произведения получаем (n1+1)∙(n2+1)∙. ∙(nk+1) способов раскладки.
Двое ребят собрали 10 ромашек, 15 васильков и 14 незабудок. Сколькими способами они могут разделить эти цветы?
Необходимо 10 предметов одного вида, 15 – второго и 14 – третьего разложить в два ящика. Применяя рассуждения, аналогичные приведенным выше, получаем 11×16×15=2460 способов раздела цветов.
Следствие 1. Если все предметы различны (n1=n2=. =nk=1), то их можно разложить 2k способами.
Следствие 2. Если в каждый ящик нужно положить не менее si предметов i-го сорта, то получим формулу: (n1-2s1+1) × (n2-2s2+1) ×. × (nk-2sk+1).
Даны n различных предметов и k ящиков. Надо положить в первый ящик n1 предметов, во второй – n2, . в k-ый – nk, где n1+. +nk=n. Сколькими способами можно сделать такое распределение, если не интересует порядок предметов в ящике?
Выложим все предметы в один ряд. Это можно сделать n! способами. Первые n1 предметов положим в первый ящик, вторые n2 предмета – во второй ящик, …, k-ые nk предметов – в к-ый ящик. Так как нас не интересует порядок предметов в ящике, то любая перестановка первых n1 предметов не меняет результат раздела. Точно так же его не меняет любая перестановка вторых n2 предметов, . k-ых nk предметов. По правилу произведения получаем n1! ×n2!×. ×nk! перестановок, не меняющих результата раздела. Таким образом, n! перестановок делятся на группы по n1! ×n2!×. ×nk! перестановок в каждой группе, причем перестановки из одной группы приводят к одинаковому распределению предметов. Следовательно, число раздела предметов равно 
=P(n1. nk).
При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать?
Переформулируем задачу: необходимо разложить 28 предметов в 4 ящика по 7 предметов в каждый, причем порядок предметов в ящике не важен. Получаем 
способов распределения костей домино.
Можно было рассуждать другим способом. Первый игрок выбирает себе 7 костей из 28, это можно сделать 
способами. Второму необходимо выбрать 7 костей из оставшихся 21, это можно сделать 
способами. Третьему 7 из 14 – 
способов. А четвертый заберет оставшиеся. По правилу произведения получаем 
.
Даны n различных предметов и k одинаковых ящика. Надо положить в каждый ящик n1 предметов, где n1=
. Сколькими способами можно сделать такое распределение, если не интересует порядок предметов в ящике, и все ящики одинаковы?
Задача отличается от предыдущей только тем, что ящики не пронумерованы. Так как k ящиков можно переставить k! способами, то полученный в предыдущей задаче результат необходимо разделить на k!. Всего 
способов распределения.
Сколькими различными способами можно разделить 8 книг на 4 бандероли по 2 книги в каждой?
Если бы интересовал порядок бандеролей, то существовало бы 
способов распределения книг. Так как не важно, в каком порядке будут отправлены бандероли, то полученное число необходимо поделить на 4!. Итого 
способов разделить 8 книг на 4 бандероли по 2 книги.
Сколькими способами можно разложить n одинаковых предметов в k ящиков?
Выложим все предметы в один ряд, добавим к ним k–1 одинаковых разделяющих предмета. Переставим всеми возможными способами n данных одинаковых предметов и k–1 разделяющих. Каждая такая перестановка определяет один из способов распределения. А именно предметы, расположенные до первого разделителя, положим в первый ящик, предметы, расположенные между первым и вторым разделителем, – во второй ящик и так далее, предметы расположенный после k–1 разделителя, – в k ящик. По формуле перестановок с повторениями число таких перестановок равно P(n, k-1)= 
. Значит, всего имеем способов разложить n одинаковых предметов в k ящиков.
Трое ребят собрали с яблони 40 яблок. Сколькими способами они могут их разделить, если все яблоки считаются одинаковыми (то есть нас интересует, сколько яблок получит каждый, а не какие именно)?
Добавим два разделяющих предмета, тогда получаем Р(40, 2)=780 способа разделить яблоки.
Следствие 1. Если в каждый ящик надо положить не менее r предметов, то получим: P(n-k×r, k-1) способов.
Следствие 2. Если в каждый ящик надо положить хотя бы один предмет, то r=1 и получим P(n-k, k-1)= 
способов распределения.
Сколько существует способов разложить n различных предметов в k ящиков, если нет никаких ограничений?
Каждый предмет можно положить в любой из k ящиков. Получаем kn способов распределения предметов по ящикам.
Сколькими способами можно разделить 8 различных пирожных между 5 детьми?
Необходимо разложить 8 предметов по 5 ящикам. Это можно сделать 58=способами.
Сколькими способами можно поместить n различных предметов в k ящиков, если не должно быть пустых ящиков?
Данные r ящиков остаются пустыми, если в k–r ящиков предметы кладутся без ограничений. r пустых ящиков можно выбрать Cnk способами. В оставшиеся k–r ящиков предметы можно разложить (k–r)n способами. По формуле включений и исключений число распределений, при которых хотя бы один ящик остается пустым, равно 
. Тогда количество распределений, при которых ни один ящик не окажется пустым, равно
kn-().
Сколькими способами можно послать по почте 8 различных фотографий, использовав 5 конвертов?
Переформулируем задачу: необходимо 8 предметов разложить в 5 ящиков. Посылать пустые конверты не рационально, поэтому накладывается запрет на пустые ящики.
Применяя полученную выше формулу, получаем
58-
×48+
×38-
×28+ 
×18=
Имеется n1 предметов одного сорта, n2 – другого, . , ns – s-го сорта. Сколькими способами их можно разложить по k ящикам, если не должно быть пустых ящиков?
Применяя рассуждения, аналогичные предыдущей задаче, получим следующую формулу
.
Сколькими способами можно разделить 8 яблок, 10 груш и 7 апельсинов между 4 детьми, если каждый должен получить хотя бы один фрукт?
Требуется 8 предметов одного сорта, 10 второго и 7 третьего разложить в 4 ящика так, чтобы ни один ящик не оказался пустым. По предыдущей формуле получаем
способов такого распределения.
Сколькими способами можно распределить n различных предметов по k различным ящикам с учетом порядка расположения предметов в ящиках, причем все n предметов должны быть использованы?
Добавим к n предметам k–1 одинаковых разделяющих предмета. Рассмотрим все возможные перестановки из n различных предметов и k–1 одинаковых. Каждая такая перестановка определяет один из способов распределения. Всего таких перестановок 
. Значит, n различных предметов можно разложить в k ящиков, с учетом расположения их в ящиках, = 
способами.
К тому же результату можно было прийти и другим путем. Переставим всеми возможными способами данные n предметов (n! способов). Теперь считаем предметы неразличимыми, их можно разложить в k ящиков Р(n, k–1) способами. Получаем n!∙Р(n, k–1)= способов распределения этих вещей по к различным ящикам с учетом порядка их расположения в ящиках.
Имеются 6 различных сигнальных флагов и 3 мачты, на которые их вывешивают. Значение сигнала зависит от того, в каком порядке вывешены флаги. Сколькими способами можно развесить флаги, если все флаги должны быть использованы, но некоторые из мачт могут оказаться пустыми?
Имеем 6 предметов, которые необходимо разложить в 3 ящика, причем порядок предметов в ящике важен. Это можно сделать 
способами.
Следствие. Если не должно быть пустых ящиков, то выберем k предметов и разложим по одному в каждый ящик. Это можно сделать 
способами. Оставшиеся n–k предметов разложим в k–1 ящик, причем теперь некоторые ящики могут оказаться пустыми. Это распределение можно осуществить 
способами. Всего имеем 
способов распределения.
Сколькими способами можно распределить n различных предметов по k различным ящикам с учетом порядка расположения предметов в ящиках, причем не все n предметов могут быть использованы и некоторые ящики могут оказаться пустыми?
Разобьем все возможные комбинации на классы. В s класс войдут комбинации, в которых использованы ровно s предметов. Из предыдущей задачи известно, что s предметов можно разложить по k ящикам 
способами. s предметов из данных n можно выбрать 
способами. Всего в s класс войдут × 
комбинаций. По правилу суммы имеем
способов распределения n различных предметов по k различным ящикам с учетом порядка их расположения в ящиках, если не все n предметов могут быть использованы.
Имеются 6 различных сигнальных флагов и 3 мачты, на которые их вывешивают. Значение сигнала зависит от того, в каком порядке вывешены флаги. Сколькими способами можно развесить флаги, если не все флаги могут быть использованы и некоторые из мачт могут оказаться пустыми?
Имеем 6 различных предметов, которые необходимо разложить в 3 ящика, причем порядок предметов в ящике важен и не все ящики и предметы могут быть использованы. По формуле получаем
Следствие. Если не должно быть пустых ящиков, то в этом случае имеем
способов распределения.
Частотой появления события в серии испытаний называется отношение числа наступления этого события в данной последовательности испытаний к общему числу испытаний.
Вероятностью случайного события называется отношение числа равновозможных элементарных событий, благоприятствующих этому событию, к числу всех равновозможных элементарных событий.
Равновозможными элементарными событиями будем считать такие события, любое из которых по отношению к другим событиям не обладает никаким преимуществом появляться чаще другого при многократных испытаниях, проводимых в одинаковых условиях.
Например, при бросании игральной кости возможны шесть различных результатов; из них лишь в одном случае выпадает шестёрка. Поэтому вероятность выпадения шестёрки равна 1/6.
Задача.
Для того чтобы открыть камеру хранения, используется комбинация из 4 цифр (от 0 до 9), набираемая на 4 колесиках.
а) Найти вероятность наугад открыть камеру хранения.
б) Найти вероятность наугад открыть камеру хранения, если дополнительно стало известно, что все цифры на правильном номере разные.
Решение.
а) Всего комбинаций из 10 цифр по 4 
=104 вариантов. Открывает дверцу только одна из них, так что вероятность наудачу открыть ее равна 1/10000 = 0,0001.
б) Всего комбинаций из 10 цифр по 4, если все цифры различны – 
=10×9×8×7=5 400 вариантов. Открывает дверцу по-прежнему только один, откуда вероятность открыть дверцу становится 1/5400 @ 0,0002.
Таким образом, вероятность в простейшем случае вычисляется комбинаторно.
Источник
