Тема: основные понятия комбинаторики. Решение комбинаторных задач

План:

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

2. Общие правила комбинаторики.

4. Применение графов (схем) при решении комбинаторных задач.

1. Комбинаторика и ее возникновение.

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

Комбинаторика возникла в XVI веке. В жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры (карты, кости). Широко были распространены лотереи. Первоначально комбинаторные задачи касались в основном азартных игр: сколькими способами можно получить данное число очков, бросая 2 или 3 кости или сколькими способами можно получить 2-ух королей в некоторой карточной игре. Эти и другие проблемы азартных игр являлись движущей силой в развитии комбинаторики и далее в развитии теории вероятностей.

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

Теоретическое исследование вопросов комбинаторики предприняли в XVII веке французские математики Блез Паскаль и Ферма. Исходным пунктом их исследований были так же проблемы азартных игр.

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

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

2. Общие правила комбинаторики.

Правило суммы: Если некоторый объект А может быть выбран m способами, а объект В- k способами, то объект «либо А, либо В» можно выбрать m +k способами.

Примеры:

1. Допустим, что в ящике находится n разноцветных шаров. Произвольным образом вынимается 1 шарик. Сколькими способами это можно сделать?

Ответ: n способами.

Распределим эти n шариков по двум ящикам: в первый- m шариков, во второй- k шариков. Произвольным образом из произвольно выбранного ящика вынимается 1 шарик. Сколькими способами это можно сделать?

Решение: Из первого ящика шарик можно вынуть m способами, из второго- k способами. Тогда всего способов m+k=n .

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

В морском семафоре каждой букве алфавита соответствует определенное положение относительно тела сигнальщика двух флажков. Сколько таких сигналов может быть?

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

Правило произведения: Если объект А можно выбрать m способами, а после каждого такого выбора другой объект В можно выбрать (независимо от выбора объекта А) k способами, то пары объектов «А и В» можно выбрать m *k способами.

Примеры:

1. Сколько двузначных чисел существует?

Решение: Число десятков может быть обозначено любой цифрой от 1 до 9. Число единиц может быть обозначено любой цифрой от 0 до 9. Если число десятков равно 1, то число единиц может быть любым (от 0 до 9). Таким образом, существует 10 двузначных чисел, с числом десятков- 1.Аналогично рассуждаем и для любого другого числа десятков. Тогда можно посчитать, что существует 9 *10 = 90 двузначных чисел.

2. Имеется 2 ящика. В одном лежит m разноцветных кубиков, а в другом- k разноцветных шариков. Сколькими способами можно выбрать пару «Кубик-шарик»?

Решение: Выбор шарика не зависит от выбора кубика, и наоборот. Поэтому, число способов, которыми можно выбрать данную пару равно m *k .

3. Генеральная совокупность без повторений и выборки без повторений.

Генеральная совокупность без повторений - это набор некоторого конечного числа различных элементов a 1 , a 2 , a 3 , ..., a n .

Пример: Набор из n разноцветных лоскутков.

Выборкой объема k (k n ) называется группа из m элементов данной генеральной совокупности.

Пример: Пестрая лента, сшитая из m разноцветных лоскутков, выбранных из данных n .

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

- число размещений из n по k .

Число размещений из n по k можно определить следующим способом: первый объект выборки можно выбрать n способами, далее второй объект можно выбрать n -1 способом и т.д.

Преобразовав данную формулу, имеем:

Следует помнить, что 0!=1.

Примеры:

1. В первой группе класса А первенства по футболу участвует 17 команд. Разыгрываются медали: золото, серебро и бронза. Сколькими способами они могут быть разыграны?

Решение: Комбинации команд-победителей отличаются друг от друга составом и порядком следования элементов, т.е. являются размещениями из 17 по 3.

2. Научное общество состоит из 25-ти человек. Необходимо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами это можно сделать?

Решение: Комбинации руководящего состава общества отличаются друг от друга составом и порядком следования элементов, т.е. являются размещениями из 25 по 4.

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

Число перестановок.

Примеры:

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

Решение: Имеем перестановки из 5 элементов. 2. Сколькими способами можно собрать 6 разноцветных лоскутков в пеструю ленту?
Решение: Имеем перестановки из 6 элементов.

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

- число сочетаний из n по k

Элементы каждого из сочетаний можно расставить способами. Тогда Примеры:

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

Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки, вышедшие в финал, являются сочетаниями из 20 по 3.

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

Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки делегатов являются сочетаниями из 10 по 3.

Конспект:

4.Применение графов (схем) при решении комбинаторных задач.

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

Задача:

При составлении команд космического корабля учитывается вопрос и психологической совместимости участников путешествия. Необходимо составить команду космического корабля из 3 человек: командира, инженера и врача. На место командира есть 4 кандидата: a 1 , a 2 , a 3 , a 4 .На место инженера- 3: b 1 , b 2 , b 3 . На место врача- 3: c 1 , c 2 , c 3 . Проведенная проверка показала, что командир a 1 психологически совместим с инженерами b 1 и b 3 и врачами c 1 и c 3 . Командир a 2 - с инженерами b 1 и b 2 . и всеми врачами. Командир a 3 - с инженерами b 1 и b 2 и врачами c 1 и c 3 . Командир a 4 -со всеми инженерами и врачом c 2 . Кроме того, инженер b 1 не совместим с врачом c 3 , b 2 - с врачом c 1 и b 3 - с врачом c 2 . Сколькими способами при этих условиях может быть составлена команда корабля?

Решение:

Составим соответствующее «дерево».

Ответ: 10 комбинаций.

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

Лекция 9: Комбинаторика-2.

Практически вся эта лекция будет посвящена разнообразным свойствам особых чисел, называемых попросту "цэшками", а по-научному числами сочетаний. Эти числа, обозначаемые стандартно Сnk , уже появлялись в первой лекции "Комбинаторика". Напомним их определение основную формулу:
Сnk - это число способов выбрать k различных (т. е. без повторений) предметов из n различных (0<=k<=n), без учета порядка выбора. Они могут быть вычислены по следующим формулам:
Сnk=Ank/k!
Cnk=(n*(n-1)*(n-2)*...*(n-k+1))/k!
Cnk=n!/(k!*(n-k)!)
Доказательства всех этих формул и определение чисел Ank вы можете прочитать в лекции "Комбинаторика".

Из формул видно, что: Cn0=1, Cn1=n, Cn2=n*(n-1)/2=(n2-n)/2, Cn3=n*(n-1)*(n-2)/6 ... Cnn-1=n, Cnn=1.

Свойство 1. Cnk=Cnn-k (при всех n>=0 и всех k от 0 до n; обычно говорят кратко - "при всех n и k").
Доказательство: Их у этого свойства будет два: первое - из формулы, второе - комбинаторное рассуждение.
1.) Cnk=n!/(k!*(n-k)!), а Cnn-k=n!/((n-k)!*(n-(n-k))!)=n!/((n-k)!*k!) - то же самое, что и Cnk, ч. т.д.
2.) Когда мы выбираем k предметов из n, то n-k предметов мы оставляем. Если мы, наоборот, выбранные k предметов оставим, а оставленные n-k - выберем, то получим способ выбора n-k предметов из n. Заметим, что мы получили взаимно-однозначное соответствие способов выбора k и n-k предметов из n. Значит, тех и других способов поровну. Но одних а Cnk, а других а Cnn-k, поэтому они равны, ч. т.д.

Свойство 2. Cn+1k+1=Cnk+Cnk+1, "при всех n и k".
Доказательство: Их опять будет два, различных по тому же принципу.
1.) Cnk=n!/(k!*(n-k)!), Cnk+1=n!/((k+1)!*(n-k-1)!), а Cn+1k+1=(n+1)!/((k+1)!*(n-k)!). Теперь приведем первые два равенства к общему знаменателю и сложит: Cnk+Cnk+1 = n!*(k+1)/((k+1)!*(n-k)!)+n!*(n-k)/((k+1)!*(n-k)!) = n!*(k+1+n-k)/((k+1)!*(n-k)!) = (n+1)!/((k+1)!*(n-k)!) = Cn+1k+1, ч. т.д.
2.) Cn+1k+1 - это кол-во способов выбрать k+1 предметов из n+1. Посчитаем его, зафискировав один предмет (назовем его "крапленым"). Если мы не берем крапленый предмет, то нам надо выбрать k+1 предмет из n оставшихся, а если мы его берем, то надо выбрать из n оставшихся еще k предметов. Первое можно сделать Cnk+1 способами, второе - Cnk способами. Всего как раз Cnk+Cnk+1, ч. т.д.

(!) Мы только что познакомились со специфическим комбинаторным способом доказательства равенств. Он заключается в том, чтобы посчитать одно и то же количество двумя способами и получить при этом формулы, стоящие в разных частях доказываемого равенства. Раз мы считали одно и то же, то эти формулы равны (см., напр. док-во 2 св-ва 2). Иногда мы считаем два разных количества, а потом замечаем, что они одинаковы, приводя взаимно-однозначное соответствие между объектами, посчитанными в первый и во второй раз (см., напр. док-во 2 св-ва 1) - соответствие способов выбрать k и n-k предметов.

Примеры комбинаторных задач с "цэшками":

Задача 1. Сколькими способами можно из семи банок с краской разных цветов выбрать четыре?
Решение: Число способов выбора - это C74. Давайте его посчитаем: C74=C73 по св-ву 1. C73 = 7*6*5/3! = 7*6*5/6 = 7*5 = 35.

Задача 2. У одного меломана есть 6 дисков известной поп-группы, у другого 8. Сколькими способами они могут обменяться тремя дисками?
Решение: Каждый меломан должен выбрать из своих дисков три, которые он будет менять. Первый может сделать это C63 способами, а второй C83 способами. Так как выбор независим, то все вариантов C63*C83. Посчитаем: C63 = 6*5*4/3! = 6*5*4/6 = 5*4 = 20. C83 = 8*7*6/3! = 8*7*6/6 = 8*7 = 56. Ответ: 20*56=1120.

Задача 3. В кружке занимаются 2 девочки и 7 мальчиков. Сколько есть способов послать на конкурс команду из 4-х человек, если в ней обязательно должна быть хоть одна девочка?
Решение: В команду входит либо одна девочка, либо обе. В первом случае эту девочку можно выбрать C21 способами, а также C73 способами выбрать в команду еще трех мальчиков. Во втором случае в команду надо выбрать еще 2-х мальчиков C72 разными способами. Всего C21*C73+C72 способов. Посчитаем: C21=2, C73=35 (уже считали в зад.1), C72=7*6/2!=42/2=21. Ответ: 2*35+21=91.

Задача 4. Сколькими способами можно разбить 10 человек на 2 команды по 5 человек в каждой? А 15 человек на 3 команды по 5 человек в каждой?
Решение: Число способов выбрать одну команду (5 человек) - C105. Тогда ясен и состав второй команды - другие 5 человек. Но: каждый вариант выбора мы посчитали дважды , один раз считая первой одну команду, другой раз - другую. Поэтому в ответе будет C105/2 (желающие могут посчитать сами, что это будет 126).
Для трех команд давайте считать, что мы на время зафискировали порядок их выбора: первую, вторую и третью команды. Тогда число способов выбрать первую команду - C155, вторую (при выбранной первой) - C105, а третью автоматически образуют оставшиеся 5 человек. Сколько мы насчитали лишнего? Ясно, что способы выбора одних и тех же трех команд в разном порядке мы посчитали как разные. А одни и те же 3 команды можно поставить в разном порядке 3!=6 способами (см. лекцию "Комбинаторика"). Поэтому мы насчитали в 6 раз больше, чем нужно. Ответ: C155*C105/6 (это будет, на самом деле, 126126).
(!) Обратите внимание: мы сделали здесь примерно то же, что и в док-ве формулы Сnk=Ank/k! в лекции "Комбинаторика": представили, что мы выбираем объекты не просто так, а в определенном порядке. То, что в исходной задаче было одним способом выбора, теперь может быть посчитано как разные способы много раз. А именно: факториал кол-ва объектов, к которым применена эта процедура, т. к. именно столькими способами можно эти объекты переставить. На этот факториал и надо будет поделить полученный ответ.
Вопрос на понимание: А почему из 15 человек можно выбрать 2 команды по 5 ровно C155*C105/2 способами?

"Цэшки", треугольник Паскаля и Бином Ньютона:
В предыдущих примерах мы вычисляли числа Cnk непосредственно по формуле, делая много умножений и делений. Оказывается, есть метод вычислять сразу много разных "цэшек", используя только сложение. Особенно важно это при программной реализации, поскольку компьютер складывает числа гораздо быстрее, чем умножает и тем более делит. Он основан на доказанном выше "свойстве 2": Cn+1k+1=Cnk+Cnk+1.

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

Утверждение. Если строчки треугольника Паскаля и позиции в них нумеровать, начиная с нуля, то на k-м месте в n-й строке будет стоять значение Cnk (основное свойство треугольника Паскаля).
Доказательство: Индукция по n (см. лекцию "Индукция", если вы еще не знакомы с этим методом).
База: n=0 - действительно, C00=1 - как раз то, что стоит на верхушке треугольника Паскаля.
Переход: от n к n+1. Пусть в n-й строчке все числа уже равны значениям "цэшек" из n по соответствующим k. Рассмотрим n+1-ю строчку. На ее краях (нулевое и n+1-е места) стоят две единицы - и значения Cn+10 и Cn+1n+1 как раз равны 1. Далее, при всех k от 1 до n число, стоящее на k-м месте в n+1-й строке, равно сумме чисел, стоящих в n-й строке на k-1-м и k-м местах соответственно (т. е. как раз двух стоящих над ним - по принципу построения треугольника Паскаля). По предположению индукции, они равны Cnk-1 и Cnk, а их сумма тогда будет Cnk-1+Cnk, что как раз равно Cn+1k (по свойству 2 "цэшек"), ч. т.д.

Для справки мы приводим здесь первые 11 строчек (с нулевой по 10-ю) треугольника Паскаля - их можно посчитать и вручную. На компьютере, с помощью простой программы, можно вычислить значительно больше "цэшек", и более быстрого алгоритма, чем треугольник Паскаля, пока не существует.

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

(a+b)0=
(a+b)1=
(a+b)2=
(a+b)3=

1
a+b
a2+2ab+b2
a3+3a2b+3ab2+b3

Коэффициенты в этих формулах (и это лучше видно, когда выписаны еще нулевая и первая степень) - это числа из треугольника Паскаля, то есть "цэшки". На самом деле, такая закономерность будет продолжаться и дальше, и называется она бином Ньютона . Точнее: (a+b)n=an+Cn1an-1b+Cn2an-2b2+...+Cnn-1a1bn-1+bn.
Можно доказать эту формулу по индукции, как и основное свойство треугольника Паскаля. Но это будет упражнением для желающих попрактиковаться в индукции. Приведем более простое объяснение:
(a+b)n=(a+b)(a+b)...(a+b) (n скобок). Раскрывая скобки, получаем в отдельных слагаемых произведения n букв, каждая из которых - a или b, т. е. an-kbk при каком-то k от 0 до n. Докажем, что для каждого такого k число таких слагаемых - ровно Cnk, откуда, приведя подобные, и получаем формулу бинома. Но это правда: an-kbk получается путем взятия a из k скобок и b из n-k оставшихся; разные такие слагаемые получаются путем разного выбора этих самых k скобок, а k скобок из n можно выбрать как раз Cnk способами, ч. т.д.
(!) Именно из-за бинома Ньютона числа Cnk часто называют биномиальными коэффициентами .

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

Утверждение 1. Сумма Cn0+Cn1+Cn2+...+Cnn-1+Cnn (т. е. чисел в n-й строке треугольника Паскаля) равна 2n.
Доказательство №1: (комбинаторное). Поскольку Cnk - число способов выбрать k предметов из n, то сумма всех таких чисел при фиксированном n и разных k (т. е. сумма из условия) - число способов выбрать несколько предметов (возможно, 0, 1 или все) из n. Почему же несколько предметов из n можно выбрать именно 2n способами? Мы можем выбрать первый предмет или не выбрать - 2 случая. В каждом из этих случаев мы можем выбрать или не выбрать второй предмет - имеет по 2 подслучая, т. е. 22=4 варианта. В каждом из них образуется по 2 подслучая, смотря, выбран ли третий предмет - всего 23=8 вариантов и т. д. В конце, после n ветвления на подслучаи, получаем 2n вариантов, ч. т.д.
Доказательство №2: (индукция с использованием свойства Cn+1k+1=Cnk+Cnk+1).
База: n=0 и Cn0+Cn1+Cn2+...+Cnn-1+Cnn=C00=1=20, ч. т.д.
Переход: (от n к n+1). Cn+10+Cn+11+Cn+12+...+Cn+1n+Cn+1n+1 = Cn+10+Cn0+Cn1+Cn1+Cn2+...+Cnn-1+Cnn+Cn+1n+1 по указанному свойству. Заметим, что Cn+10=1=Cn0 и Cn+1n+1=1=Cnn, откуда это выражение равно 2Cn0+2Cn1+2Cn2+...+2Cnn-1+2Cnn = 2*(Cn0+Cn1+Cn2+...+Cnn-1+Cnn). Это, по предположению индукции, равно 2*2n=2n+1, ч. т.д.
Доказательство №3: (бином Ньютона). Заметим, что 2n=(1+1)n и раскроем по формуле бинома Ньютона (при a=b=1). Получим 1+Cn1+Cn2+...+Cnn-1+1 - с учетом того, что Cn0=Cnn=1, это как раз сумма из условия, ч. т.д.
(!) Обратите внимания: три разных рассуждения, использующие совершенно разный взгляд на природу "цэшек", приводят к одному и тому же результату. На самом деле, тот или иной взгляд может оказаться более удобным в зависимости от конкретной задачи и, конечно, конкретного решающего.

Утверждение 2. Сумма Cn0-Cn1+Cn2-...+(-1)n-1Cnn-1+(-1)nCnn равна 0.
Доказательство №1: (комбинаторное). Заметим, что сумма всех слагаемых со знаком "+" - это число способов выбрать четное число предметов из n, а со знаком "-" - соответственно, нечетное. Докажем, что тех и других способов поровну, например, поставив их во взаимно-однозначное соответствие. Объединим способы выбора предметов в пары так: в одном способе первый предмет выбран, а в другом не выбран, но остальные предметы в обоих способах выбираются одинаково. Ясно, что в двух способах из пары кол-ва выбранных предметов различаются на 1, поэтому в каком-то из способов выбрано четное число предметов, а в другом - нечетное. Поскольку мы разбили на пары все способы, то тех и других поровну, ч. т.д.
Упражнение: Придумать еще два доказательства, по индукции и через бином Ньютона.
(!) Заметим, что четное (и нечетное тоже) число предметов из n можно выбрать 2n-1 способами: число способов выбрать четное и нечетное число предметов одинаковы, а в сумме они дают 2n, значит, оба по 2n-1.

Утверждение 3. Сумма (Cn0)2+(Cn1)2+...+ (Cnn)2 равна C2nn.
Замечание: Это редкостное свойство, напротив, ни по индукции, ни через бином не доказывается:-(
План доказательства: Вспомнив про "свойство 1", сделаем в сумме замену: Cn0*Cnn+Cn1*Cnn-1+...+Cnn*Cn0. Возьмем такой объект: 2n шариков, n белых и n черных. Число способов выбрать из них какие-то n шариков - конечно, C2nn. А если мы сгруппируем эти способы по количеству белых и черных шариков среди выбранных, то получим как раз написанную выше сумму (упражнение: убедиться в этом).

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

Задача 5. Есть k ящиков и n>=k однаковых шаров. Сколькими способами можно разложить шары по ящикам так, чтобы ни один ящик не оказался пустым?
Решение: Давайте определять раскладку так: выложим шары в ряд и поставим между ними k-1 перегородку. То, что слева от первой перегородки, положим в первый ящик, между первой и второй - во второй... то, что справа от последней - в последний, k-й ящик. Ящик будет пустым, только если две перегородки стоят рядом не разделенные шарами, либо перегородка стоит с краю, левее или правее всех шаров. Так давайте это запретим! Пусть на каждое из n-1 мест между n шарами можно поставить не более одной из k-1 перегородок. То есть, из n-1 мест надо будет выбрать k-1, куда мы ставим перегородки. Отсюда получаем ответ: Cn-1k-1 .

Задача 6. А сколько способов разложить шары, если могут быть пустые ящики?
Решение: Если определять раскладку так же, ставя между шарами k-1 перегородку, то ограничений уже не будет: шары и перегородки можно ставить в произвольном порядке. Давайте считать, что у нас расставлено в ряд n+k-1 объектов: n из них шары, а остальные - перегородки. Тогда раскладка будет определяться тем, на каких местах какие объекты стоят. Из n+k-1 мест можно выбрать n мест для шаров Cn+k-1n способами, или: k-1 место для перегородок Cn+k-1k-1 способами. Эти числа равны и оба являются ответом.

Выбор с повторениями, без учета порядка (с помощью новой теории).
Найдем, наконец, то, что мы не нашли в первой лекции по комбинаторике (но проанонсировали ответ Cn+k-1k): число способов выбрать k предметов из n с повторениями без учета порядка.
Общая формулировка задачи: есть предметы n различных сортов. Сколько способов выбрать k предметов, если учитывается только число предметов того или иного сорта?
Давайте считать, что k предметов - это "шары", а n сортов - "ящики", по которым мы их раскладываем. Тогда получаем ситуацию, аналогичную задаче 6, только n и k надо поменять местами. В ответе будет Cn+k-1k или, что то же самое, Cn+k-1n-1 .

Задача 7. Сколько способов переплести 12 одинаковых книг в красные, зеленые или синие переплеты?
Решение: Опять нас выручает теория "шаров и перегородок": пусть 12 книг - это "шары", а 3 цвета переплетов - "ящики", по которым мы их раскладываем. Приходим к задаче 6 при n=12, k=3. В ответе будет C142=C1412.

Задача 8. Сколько способов разложить 7 белых и 2 черных шара по 9 различным ящикам?
Решение: Давайте посчитаем отдельно число раскладки белых и черных шаров. Для белых получаем C158=C157 (опять задача 6: n=7, k=9), а для черных C108=C102 (та же задача 6 при n=2, k=9). Так как одна раскладка от другой не зависит, то число вариантов надо перемножить. Ответ: C157*C102.

Задача 9. Общество из n человек выбирает председателя из своего состава. Сколько есть разных распределений голосов за различных кандидатов?
Решение: Пусть n голосов - это "шары", а n кандидатов - "ящики". Получаем ту же всенародно любимую:-) задачу 6 (на самом деле, задача 5 тоже нередко применяется), при k=n. А ответ тогда C2n-1n.

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

1. Правила суммы и произведения.

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

Теорема 13.1. Пусть даны непересекающиеся конечные множества . Тогда мощность объединения этих множеств равна сумме мощностей данных множеств:

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

Если некоторый элемент можно выбрать способами, а элемент - способами, причём любой способ выбора элемента отличается от любого способа выбора элемента , то выбор “ или ” можно сделать способами. Это правило называется правилом суммы .

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

Теорема 13.2. Число элементов в декартовом произведении множеств равно произведению мощностей этих множеств:

Как и в предыдущем случае, сформулируем данную теорему упрощённым образом для двух множеств. Если элемент можно выбрать способами, а элемент - способами, причём любой способ выбора элемента отличается от любого способа выбора элемента , то выбор “ и ” (то есть, пары ) можно сделать способами. Это правило называется правилом произведения, или умножения .

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

Пример 1.

а) В некоторой средней школе имеется три пятых класса, в которых обучаются соответственно 28, 31 и 26 учащихся. Требуется одного из них выбрать для участия в совете школы. Сколькими способами можно сделать выбор?

По правилу суммы получаем .

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

По правилу произведения получаем .

2. Размещения.

Определение. размещением без повторений по элементов из . Число всех размещений без повторений по элементов из обозначается и равно .

Пример 2. Куплено различных 12 книг. На полке можно поставить в ряд ровно 6 книг. Сколькими различными способами можно это сделать?

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

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

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

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

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

3. Перестановки.

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

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

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

Здесь, в отличие от примера 2, значение имеет только порядок расставляемых книг. Поэтому речь идёт о перестановках из 10 элементов. Получаем: .

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

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

Пример 5. Сколько различных шестизначных чисел могут быть записано с помощью цифр 1, 2, 2, 2, 3, 3?

Имеется набор из шести цифр, в котором цифра 2 повторяется трижды и цифра 3 – дважды. Полученные числа будут представлять собой перестановки с повторениями из 6 элементов. Получаем: .

4. Сочетания. Бином Ньютона.

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

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

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

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

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

Пример 6.

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

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

б) В цветочном магазине имеются в продаже 5 различных видов цветов. Покупателю требуется составить букет из 7 цветов. Сколькими способами можно это сделать?

Будем считать различными те букеты, которые отличаются друг от друга по подбору цветов. Поскольку цветы в букете могут повторяться, то речь идёт о сочетаниях с повторениями по 7 элементов из 5. Тогда получим .

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

С частными случаями применения этой формулы (для случаев и ) сталкиваются ещё в школе при изучении формул сокращённого умножения:

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

…………………..

Назад, в начало конспекта.

Комбинаторика

Комбинаторика – раздел математики, посвященный подсчету
количеств разных комбинаций элементов некоторого, обычно
конечного, множества
Го́тфрид Ви́льгельм Ле́йбниц
(21июня1646-14 ноября 1716) -
немецкий философ, математик,
логик, физик, юрист, языковед,
историк, дипломат
Блез Паска́ль
(19 июня 1623 - 19 августа 1662) -
французский математик, механик, физик,
литератор и философ
2

Задачи

1) Сколькими способами 6 разных папок с документами можно
расставить на полке?
2) При расследовании хищения установлено, что у преступника
шестизначный номер телефона, в котором все цифры различны
и нет нулей. Следователь, полагая, что перебор этих номеров
достаточно будет одного - двух часов, доложил о раскрытии
преступления. Прав ли он?
3) На иномарке, скрывшейся с места ДТП, был трехзначный
номер, в котором первая цифра 2. Сколько номеров
необходимо проверить по картотеке ГИБДД, чтобы найти
нарушителя?
3

Принципы комбинаторики Принцип сложения

Основные принципы комбинаторики:
Принцип сложения.
Принцип умножения.
Принцип сложения
Задача 1: В группе 7 девушек и 8 юношей. Сколькими
способами можно выбрать 1 человека для работы у доски?
Решение: 7+8=15
Задача 2: В группе 7 человек имеют «5» по математике, 9
человек – «5» по философии. В сессии 2 экзамена. Известно,
что 4 человека сдали сессию отлично. Сколько человек
имеют хотя бы одну пятерку в сессии?
Решение: 7+9-4=12
4

Принцип сложения

Принцип сложения: Если объект a можно получить n
способами, объект b можно получить m способами,
то объект «a или b» можно получить n+m-k
способами, где k – это количество повторяющихся
способов.
Теоретико-множественная формулировка
A B A B A B
5

Принцип умножения

Задача: На вершину горы ведут 5 дорог.
Сколькими способами можно подняться на гору и
спуститься с нее?
Решение: 5∙5=25.
Принцип умножения: если объект a можно получить
n способами, объект b можно получить m
способами, то объект «a и b» можно получить m∙n
способами.
Теоретико-множественная формулировка
A B A B
6

Задачи

Из 3 экземпляров учебника алгебры, 5
экземпляров учебника геометрии и 7
экземпляров учебника истории нужно выбрать
по одному экземпляру каждого учебника.
Сколькими способами это можно сделать?

3 5 7 105
7

Задачи

От дома до школы существует 6 маршрутов.
Сколькими способами можно дойти до школы
и вернуться, если дорога «туда» и «обратно»
идет по разных маршрутам?
Решение. По принципу умножения
6 5 30
8

Задачи

В корзине лежат 7 различных яблок и 5 апельсинов.
Яша выбирает из нее яблоко или апельсин, после чего
Полина берет яблоко и апельсин. В каком случае
Полина имеет большую свободу выбора: если Яша взял
яблоко или если он взял апельсин?
Решение. Если Яша взял яблоко, то по принципу
умножения Полина может осуществить свой выбор
6 5 30
способами. Если Яша взял апельсин,
то способами.
7 4 28
В первом случае у Полины свобода выбора большая.
9

Задачи

В классе 24 человека. Из них 15 человек изучают
английский язык, 12 – немецкий язык, 7 – оба языка.
сколько человек не изучают ни одного языка?
Решение. По принципу сложения 2 получим
количество людей, изучающих английский или
немецкий 15+12-7=20. Из общего числа учеников
класса вычтем полученное количество людей.
24-20=4. 4 человека не изучает ни одного языка.
15
7
12
10

Замечание

n!
читается «n факториал» и вычисляется по формуле
Например,
n! 1 2 3 ... n.
3! 1 2 3 6,
5! 1 2 3 4 5 120.
Считают, что 0!=1
11

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

Определение 1
Перестановкой n элементного множества называется
упорядоченный набор неповторяющихся элементов этого
множества длины n.
А а; b; с;
Пример:
перестановки: a; b; c ; b; a; c ; a; c; b ; b; c; a ; c; a; b ; c; b; a
Число размещений n – элементного множества обозначают Pn и
вычисляется по формуле:
Pn n!
Задача: В команде 6 человек. Сколькими способами можно
осуществить построение?
P6 6! 720
12

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

Определение 2
Число перестановок n – элементов, в котором
типа (i 1, k) вычисляется по формуле
Pn (n1 , n2 ,..., nk)
ni элементов i –того
(n1 n2 ... nk)!
n1!n2 !.... nk !
Задача: Сколько слов можно составить, переставив буквы в слове
«экзамен», а в слове «математика»?
Решение:
7! 5040
10!
151200
2! 3! 2! 1! 1! 1!
13

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

Определение 3
k -размещением без повторений n–элементного множества
называется упорядоченный набор длины k попарно различных
элементов данного множества.
A a; b; c - 2 размещения: a; b ; a; c ; b; c ; b; a ; c; a ; c; b
Число k- размещений n элементного множества обозначается
Ank
и вычисляется по формуле:
Пример:
n!
A
n k !
k
n
Задача: В соревновании участвуют 12 команд, сколькими
способами они могут занять призовые места?
А123
12!
12 11 10 1320
9!
14

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

Определение 4
k – размещением с повторениями n–элементного множества называется
упорядоченный набор длины k элементов данного множества.
А а; b; с
Пример
2- размещения с повторениями:
a; b ; b; a ; a; c ; c; a ; b; c ; c; b ; a; a ; b; b ; c; c
Число k – размещений с повторениями вычисляется по формуле:
Аnk n k
Задача: Сколько существует номеров машин?
А103 А123 123 103
15

Решение задач

Задачи

1)Сколькими способами можно составить список из
8 студентов, если нет полного совпадения ФИО?
Решение
P8 8! 40320
17

Задачи

2)Сколькими способами можно составить список 8
студентов, так, чтобы два указанных студента
располагались рядом?
Решение
Можно считать двоих указанных студентов за один
объект и считать число перестановок уже 7
объектов, т.е.
P7 7! 5040
Так как этих двоих можно переставлять местами друг
с другом, необходимо умножить результат на 2!
P7 2! 7! 2! 5040 2 10080
18

Задачи

3) Сколькими способами можно разделить 11 спортсменов
на 3 группы по 4, 5 и 2 человека соответственно?
Решение. Сделаем карточки: четыре карточки с номером 1,
пять карточек с номером 2 и две карточки с номером 3.
Будем раздавать эти карточки с номерами групп
спортсменам, и каждый способ раздачи будет
соответствовать разбиению спортсменов на группы. Таким
образом нам необходимо посчитать число перестановок 11
карточек, среди которых четыре карточки с одинаковым
номером 1, пять карточек с номером 2 и две карточки с
номером 3.
P(4,5,2)
11!
6 7 8 9 10 11
6930
4!5!2! 1 2 3 4 1 2
19

Задачи

4) Сколькими способами можно
вызвать по очереди к доске 4
учеников из 7?
Решение. Задача сводится к
подсчету числа размещений из 7
элементов по 4
7!
7!
A
4 5 6 7 840
(7 4)! 3!
4
7
20

Задачи

5)Сколько существует четырехзначных чисел, у которых
все цифры различны?
Решение. В разряде единиц тысяч не может быть нуля, т.е
возможны 9 вариантов цифры.
В остальных трех разрядах не может быть цифры,
стоящей в разряде единиц тысяч (так как все цифры
должны быть различны), поэтому число вариантов
вычислим по формуле размещений без повторений из 9 по
3
A93 9 8 7 504
По правилу умножения получим
9 A93 4536
21

Задачи

6)Сколько существует двоичных чисел, длина
которых не превосходит 10?
Решение. Задача сводится к подсчету числа
размещений с повторениями из двух элементов
по 10
10
2
A 2 1024
10
22

Задачи

7)В лифт 9 этажного дома зашли 7 человек. Сколькими
способами они могут распределиться по этажам дома?
Решение. Очевидно, что на первом этаже никому не надо
выходить. Каждый из 7 человек может выбрать любой из 8
этажей, поэтому по правилу умножения получим
8
8
...
8 87 2097152
7
Можно так же применить формулу для числа размещений с
повторениями из 8 (этажей) по 7(на каждого человека по
одному этажу)
7
8
A 87
23

Задачи

8)Сколько чисел, меньше 10000 можно написать с
помощью цифр 2,7,0?
Решение. Так как среди цифр есть 0, то, например
запись 0227 соответствует числу 227, запись 0072
соответствует числу 72, а запись 0007
соответствует числу 7. Таким образом, задачу
можно решить, используя формулу числа
размещений с повторениями
4
3
A 34 81

1. ДИСКРЕТНАЯ МАТЕМАТИКА Курс лекций Московский государственный университет имени М.В.Ломоносова Экономический факультет 1
2. Лекция 4 Комбинаторика 2
3. Комбинаторика 3 В этой лекции мы узнаем, как подсчитывать элементы конечных множеств, удовлетворяющих определенным свойствам. Мы познакомимся с типичными ситуациями, в каждой из которых можно для упрощения расчетов использовать определенную свою формулу. Мы познакомимся также с главной областью приложения комбинаторики - расчетом вероятностей, полная теория которых изучается на втором курсе.
4. Основная задача комбинаторики 4 С элементами конечных множеств можно производить различные действия: упорядочивать их, объединять в группы, отбирать подмножества по дополнительным признакам и свойствам, и т.д. При этом возникают новые, более сложные (комбинированные) множества, элементы которых тоже нужно уметь пересчитывать. . Иногда комбинаторику определяют также как науку о подсчете числа подмножеств, удовлетворяющих определенным свойствам. Предмет комбинаторики: подсчет числа способов выполнить определенные действия.
5. Основные принципы комбинаторики. 5 Большинство задач комбинаторики можно решить, используя один из двух простых принципов, интуитивно очевидных, легко проверяемых на примерах, и используемых в качестве аксиом. Практически гораздо чаще применяется принцип умножения, поскольку очень часто сложные действия приходится разлагать на последовательность простых. Принцип сложения применим к ситуациям, когда есть выбор между двумя альтернативными действиями (когда два действия исключают друг друга). Принцип умножения, напротив, применяется к действиям, которые выполняются совместно (последовательно или одновременно)
6. Принцип сложения 6 Принцип сложения: если действие 1 можно выполнить n способами, а действие 2 можно выполнить m способами, то сложное действие, состоящее в выполнении одного из действий 1 или 2 (но не обоих), можно выполнить n+m способами. Пример: как провести вечер: куда пойти? В кино В гости «Она» «Помпеи 3D» Миша Маша Леша Всего 2 + 3 = 5 способов провести вечер.
7. Принцип умножения 7 Принцип умножения: если действие A можно выполнить n способами, а действие B можно выполнить m способами, то сложное действие, состоящее в выполнении обоих действий A и B (одновременно или последовательно) можно выполнить nm способами. В кино!!! (но с кем?) Наташа Таня Оля «Академия вампиров» «В спорте только девушки» Всего: 2*3=6 способов сходить в кино.
8. Вероятность 8 Вероятность - мера уверенности в том, что некоторое событие произойдет (измеряется числом от 0 до 1). В простейшем случае вероятность вычисляется комбинаторно. Практически, вычисление всегда начинают со знаменателя, разбираются с тем, что считать действием, какие действия считать различными, вычисляют общее количество таких действий, и только после этого переходят к числителю. Разбивают сложный благоприятный исход на простейшие или стандартные, и используют принципы комбинаторики. Определение вероятности для простейшего случая равновероятных исходов – отношение числа благоприятных действий (или их исходов) к общему числу действий (их исходов): n m p 
9. 9 Один из студентов каждую минуту задумывает одну из цифр (от 0 до 9), и записывает ее, а другой, находящийся в другом месте, пытается ее «принять телепатически», и также записывает (часы синхронизированы). В предположении, что телепатии не существует, какова вероятность, что задуманная цифра будет угадана правильно? Какова вероятность, что три задуманные подряд цифры будут угаданы правильно? Телепатия. Потусторонняя задача…
10. Применение принципа умножения 10 ПРИМЕР: камера хранения. Для того, чтобы открыть камеру хранения, используется комбинация из 4 цифр (от 0 до 9), набираемая на 4 колесиках. а) Найти вероятность наугад открыть камеру хранения. РЕШЕНИЕ: Устанавливаем цифры на каждом из колесиков по очереди; каждый раз у нас есть 10 вариантов (цифры от 0 до 9), по принципу умножения они перемножаются: 10101010 = 10000 вариантов. Открывает дверцу из них только один, так что вероятность наудачу открыть ее равна 1/10000 = 0,0001. Довольно безнадежное занятие. Даже в простейших случаях удобно раскладывать сложные действия на простейшие, например, представляя себе, что они выполняются поочередно.
11. Ценность информации 11 В результате использования дополнительной информации в сообщении перебор сократился вдвое, отсюда можно в принципе подсчитать, сколько стоит сообщенная информация, если ее можно было бы купить. Продолжение: б) Найти вероятность наугад открыть камеру хранения, если дополнительно стало известно, что все цифры на правильном номере разные. РЕШЕНИЕ: Теперь на втором колесике нужно не повторить цифру, набранную на первом, так что число вариантов сокращается до 9, далее уже две цифры становятся запрещенными, так что всего вариантов остается 8, а на последнем – уже 7 вариантов: 10987 = 5040 вариантов. Открывает дверцу по-прежнему только один, откуда вероятность открыть дверцу становится 1/5040  0,0002.
12. Задачка на дом 12 1. N человек становятся случайным образом в очередь на концерт известной группы. Какова вероятность того, что два определенных человека (назовем их A и B) будут стоять рядом (и будут иметь шанс как бы случайно познакомиться). 2. N человек приглашены в гости и располагаются за круглым столом. Какова вероятность того, что те же A и B случайно окажутся на соседних местах. А и B сидели …и стояли.
13. Задачка на дом 13 В ночной электричке, состоящей из 8 вагонов, едут 6 человек. При посадке каждый человек выбирает свой вагон наугад и далее в другой вагон не переходит. Найти вероятность того, что: 1. все едут в разных вагонах 2. не менее двух человек оказываются в одном вагоне. 3. все набьются в один вагон и будут дрожать вместе. Последняя электричка
14. Стандартные действия комбинаторики 14 Основных правил для решения комбинаторных задач в принципе достаточно. Но практически их используют только в нестандартных задачах. Большинство же решаемых в комбинаторике задач являются типовыми, стандартными. Для них удобнее прямо использовать готовые формулы, каждая из которых ассоциируется с определенным стандартным действием. Стандартные действия комбинаторики: Перестановки Размещения Выборки Разбиения (на группы)
15. Перестановки 15 Две перестановки отличаются друг от друга только порядком элеметов, все элементы у них общие. Первый элемент можно поставить на любое из n мест, следующий – на любое из (n-1) мест, и так далее. Последний элемент занимает единственное оставшееся место. Это приводит к формуле n!=n(n-1)(n-2)...1 (n-факториал). ПРИМЕР: Число перестановок 5 книг на полке равно 5!.
16. Размещения 16 Два размещения отличаются друг от друга составом и порядком элементов. k nA – число размещений k элементов по n местам. Для первого элемента есть n мест, далее– (n-1) мест, и так далее. Для последнего k-го элемента остается (n–k+1) мест. Это приводит к формуле)1)...(2)(1( knnnnAk n . ("недоделанный факториал"). По сути это перестановка k элементов на n местах k
17. Задачка на дом 17 Студентка садится в лифт вместе с другими 6 студентами (до этого момента они не были знакомы). Лифт идет на любой из 7 этажей (не считая нижнего). Выйдя из лифта на своем этаже, девушка заметила, что вместе с ней вышел юноша. Следует ли ей рассматривать это как нечто большее, чем случайность? А может это… .
18. Задачка на дом 18 Будем считать, что день рождения наугад выбранного человека может прийтись на любой день из 365 дней в году. Какова вероятность того, что в группе из 23 человек у двух или более человек день рождения придется на один и тот же день? Гулянка по крупному.
19. 19 Один человек придумал, как ему кажется, способ наверняка выиграть в рулетку. Он рассуждает так: шарик может остановиться на любом из 36 чисел: 1, 2, …36 (для простоты будем игнорировать 0). Если я буду ставить на определенное число 36 раз, я наверняка выиграю хотя бы раз. Прав ли он? Какова на самом деле вероятность хотя бы одного выигрыша? Найдите способ оценить ее приближенно без калькулятора). Утешительный приз Задачка на дом
20. Выбор 20 Две выборки отличаются друг от друга только составом элементов, их порядок безразличен (поэтому в знаменателе появляется факториал числа элементов). Число способов выбора k элементов из имеющихся n элементов ввиду стандартности и широкой распространенности задачи выбора носит специальное название – число сочетаний из n элементов по k. ПРИМЕР: Число способов распределить 5 флаеров на дискотеку в компании из 7 человек равно 21 12345 345675 7    C . Число выборок, обозначаемое k nC , равно!)1)...(2)(1(k knnnn Ck n  
21. Вывод формулы для числа сочетаний 21 Для получения формулы для числа выборок сводим задачу к уже изученному случаю (размещение с учетом порядка). Таким образом, мы исходим из числа размещений, но которое теперь (поскольку порядок k элементов безразличен) требуется разделить на число перестановок k элементов: !)1)...(2)(1(! k knnnn k A C k nk n   . Обратите внимание, что в числителе всего k сомножителей, столько же, сколько и в знаменателе.
22. Свойство симметрии сочетаний 22 Выбранные и оставшиеся с точки зрения разбиения на группы равноправны, поэтому число способов выбрать k элементов равно числу способов оставить невыбранными n-k элементов kn n k n CC   ПРИМЕР: В задаче о распределении флаеров получаем гораздо более удобную формулу 21 12 672 7 5 7     CC .
23. Вероятность для учебы 23 Каждый студент получает на экзамене 3 вопроса, случайно выбранных из 25 вопросов программы. Студент получит «5», если ответит правильно на все вопросы, «4» – только на два, «3» – только на один, и «2» - ни на один. Каковы вероятности получения пятерки, четверки, тройки и двойки? Экзаменационная ловушка.
24. Математика риска 24 Лет двадцать назад в России была популярна лотерея «Спортлото», где нужно было, купив билет, зачеркнуть 6 названий видов спорта из 45. В еженедельном тираже объявлялись 6 выигрышных видов. Призовой фонд делился между угадавшими. Какова вероятность угадать три вида спорта? Все шесть? Счастливый билетик
25. Выбор как разбиение на две группы 25 Можно придать формуле для сочетаний удобный для запоминания симметричный вид. Умножим числитель и знаменатель на (n-k)!, дополняющий числитель до полного факториала.)!(! ! 123)...(! 123)...()1)...(2)(1(knk n knk knknnnn     Итак,)!(! ! knk n Ck n   Симметрия поученной формулы позволяет рассматривать выбор как ситуацию разбиения на две группы (выбранные – оставшиеся) Итак, число способов),(knkPn  разбить множество, состоящее из n элементов, на две группы, первая из которых содержит k элементов, а вторая – n-k элементов, равно)!(! !),(knk n knkPn  
26. Сложная выборка из двух типов элементов 26 Сложная выборка – это выборка из неоднородной совокупности, которая включает элементы двух или более типов. Чтобы составить сложную выборку, нужно сначала выбрать m элементов из M, обладающих нужным свойством, а затем отдельно выбрать n-m элементов из N-M не обладающих нужным свойством: mn MN m M CC   Вероятность такого факта равна n N mn MN m M C CC p   Пусть совокупность содержит N элементов, из которых только M обладают некоторым свойством (а значит N-M им не обладают).
27. Приложение сложной выборки 27 Практически удобно представлять себе, что действия по формированию составляющих частей сложной выборки производятся отдельно, например, различными людьми В курсе теории вероятностей эта формула получит гордое имя гипергеометрического распределения. ПРИМЕР: Покупка телевизора на Митинском рынке. В ларьке имеется 10 телевизоров, из которых только 6 работают. За день продано 7 телевизоров. Найти вероятность того, что из них 4 работают. Рассчитываем по формуле сложной выборки 2 1 123 8910 4 21 56 7 10 3 4 4 6        C CC p
28. Сложная выборка. Общий случай. 28 Рассмотрим теперь случай k различных типов элементов. Пусть совокупность содержит n элементов, из которых только n1 обладают свойством 1, n2 обладают свойством 2, …, nk обладают свойством k. Действуя по аналогии с случаем двух групп, и набирая в выборке элементы разных типов по отдельности, получаем k k n nnn n nnn n nn n n CCCC 11 3 21 2 1 1 ......  Прямым подсчетом можно убедиться, что это равно!!...! ! 21 knnn n 
29. Разбиения на группы 29 Два разбиения отличаются друг от друга составом элементов групп, порядок элементов в группах безразличен, порядок групп существенен. Для вывода формулы для числа разбиений на группы можно пойти и другим путем: обобщить на случай k групп симметричную формулу для сочетаний. Количество способов)...,(21 kn nnnP , которыми можно разбить множество из n предметов на k различимых групп, содержащих соответственно 1n , 2n , …, kn предметов, равно!!...! ! 21 knnn n  ПРИМЕР: руководитель отдела, состоящего из 10 сотрудников, составляет график дежурств по пяти дням недели (каждый день должны дежурить два сотрудника, каждый сотрудник дежурит один день). У нас пять групп. По стандартной формуле числа разбиений получаем 10!/(2!2!2!2!2!)=1134000.
30. Задачка на дом 30 На карточках складной азбуки написаны буквы: две «М», три «А», две «Т», и по одной «Е», «И» и «К». Маленький ребенок играет с карточками, прикладывая их друг к другу. Какова вероятность того, что случайно с первого раза он получит слово «МАТЕМАТИКА»? . Юный математический гений
31. Задачка на дом 31 Найти вероятность того, что при вытаскивании трех карт из колоды из 52 карт получатся тройка, семерка и туз. Бедный Германн.
32. Основные формулы комбинаторики. 32 Подведем итог, соберем вместе полученные результаты. Перестановки различаются только порядком элементов. Число перестановок n элементов равно n!=n(n-1)(n-2)...1 Размещения различаются составом и порядком элементов. Число размещений k элементов по n местам равно)1)...(2)(1( knnnnAk n . Выборки отличаются друг от друга составом элементов, порядок безразличен. Число выборок по k элементов из n элементов равно!)1)...(2)(1(k knnnn Ck n   Число разбиений множества из n предметов на k групп, содержащих 1n , 2n , …, kn элементов, равно k k n nnn n nn n n k kn CCC nnn n nnnP 11 2 1 1 ... 21 21 ... !!...! !),...,(  
33. Конец лекции