Комбинаторика лекции. Размещение без повторений. Сочетания c повторениями

ТЕМА: Основные понятия комбинаторики.

Ответьте на вопросы письменно: (20-25 мин)

Что называют факториалом? (примеры вычисления)

Комбинаторика-это…

Что такое соединения? виды соединений?

Решить задачу 1 и задачу 2 методом подбора!

Часто в математике нужно вычислить произведение натуральных чисел по порядку, начиная с 1. Например, 1*2*3*4*5*6*7 и т.д. Чтобы запись была короче используют знак «!»

Произведением всех натуральных чисел от 1 до n называется факториалом числа n и записывается n!(читается как эн факториал)

n!=1 ⋅ 2 ⋅ 3 ⋅ ... ⋅ (n−2) ⋅ (n−1) ⋅ n

Чему, к примеру, равны 2!, 3!, 4!, 5!, 6! ? Посчитайте в тетради!

2!= … 3!=… 4!=… 5!=… 6!=…

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

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

Группы, составленные из каких-либо элементов, называются соединениями .

Различают три вида соединений: размещения , перестановки и сочетания .

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

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

Задача 1. В некотором учреждении имеются две различные вакантные должности, на каждую из которых претендуют три сотрудника: A, B, C. Сколькими способами из этих трех кандидатов можно выбрать два лица на эти должности?

Задача 2. Для участия в соревнованиях требуется выбрать двоих спортсменов из трех кандидатов: A, B, C. Сколькими способами можно осуществить этот выбор?

1) Размещения.

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

Число размещений из m элементов по n обозначают (от французского «arrangement» - «размещение») и вычисляют по формуле:

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

Определение. Перестановкой из n элементов называют размещение из n элементов по n.

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

3) Сочетания.

Определение.

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

Число сочетаний из n элементов по m обозначают (от французского «combination» - «сочетание») и вычисляют по формуле:

Решение комбинаторных задач.

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

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

а) судья хоккейного матча и его помощник;

б) «Шесть человек останутся убирать класс!»

в) две серии для просмотра из многосерийного фильма.

Задача 1. Сколькими способами могут занять I, II, III места 8 участниц финального забега на дистанции 100 м?

Задача 2. Из 30 обучающихся группы надо выбрать старосту и помощника старосты. Сколькими способами это можно сделать?

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

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

Домашнее задание Подготовка сообщений по темам: «Истории комбинаторики», «Комбинаторика и ее применение в реальной жизни».

Проверь себя!

1 .Определите вид соединений:

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

б) Соединения из m элементов по n , отличающихся друг от друга только составом элементов, называются _______________

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

2 .Восстановите соответствие типов соединений и формул для их подсчёта

	А.сочетания
	В. размещения
	С. перестановки

3. Сколькими способами из класса, где учатся 24 ученика, можно выбрать: а)двух дежурных; б)старосту и помощника старосты?

4. «Проказница Мартышка, Осёл, Козёл да косолапый Мишка задумали сыграть квартет». Сколькими способами они могут выбрать каждый для себя по одному инструменту из 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.

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

Решение. Действием в данном случае является составление набора из ручки, карандаша и линейки; действие распадается на три этапа (части): выбрать ручку, выбрать линейку и выбрать карандаш. Первую часть действия – выбрать ручку – можно выполнить пятью способами, вторую часть действия – выбрать карандаш – можно выполнить семью способами, третью часть действия – выбрать линейку – можно выполнить десятью способами. Тогда все действие можно выполнить 5*7*10 =350 Число способов. Т.е. возможно 350 вариантов такого набора.

Пример. В столовой предлагают два различных первых блюда а1 и а2, три различных вторых блюда b1, b2, b3 и два вида десерта с1 и с2. Сколько различных обедов из трех блюд может предложить столовая? Решение. Пусть А – множество первых блюд, В – множество вторых блюд, а С – множество третьих блюд. По условию известно, что

Пример. "Команда космического корабля" Рассмотрим задачу о формировании команды космического корабля. Известно, что возникнет вопрос психологической совместимости. Предположим, надо составить команду из 3-х человек: командира, инженера и врача. На место командира есть четыре кандидата: a1, a2, a3, a4, на место инженера три - b1, b2, b3, на место врача три – c1, c2, c3. Проведенная проверка показала, что a1 совместим с b1, b2, c2,c3; a2 совместим с b1, b2,c1,c2,c3; a3 совместим с b1 и b2, c1, c3; a4 совместим с b1, b2, b3, c2 ; b1 не совместим с c3 ; b2 не совместим с c1 ; b3 не совместим с c2.

Расположение n различных элементов в определенном порядке называется перестановкой без повторений из n элементов. Например, на множестве из трех элементов {a,b,c} возможны следующие перестановки: abc, acb, bca, bac, cab, cba. Число различных перестановок без повторений из элементов обозначается P n и равно n!, т.е.

Таблица вариантов КБСКСБ БСКБКС СБКСКБ Дерево вариантов Правило умножения 1 полоса 3 способа 2 полоса 2 способа 3 полоса 1 способ = 6 Ответ: 6 способов Подсчет перестановок

Сочетанием без повторений из n элементов по k называется неупорядоченное k-элементное подмножество n-элементного множества. Число сочетаний без повторений из элементов по равно: Например, требуется подсчитать, сколькими способами можно составить бригаду из трех человек для дежурства в группе из 30 человек. Поскольку порядок расположения людей в бригаде не фиксируется и люди не повторяются, то мы имеем случай сочетаний из 30 элементов по 3 без повторений: Таким образом, бригаду дежурных из трех человек в группе из 30 человек можно выбрать 4060 различными способами.

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

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

Пример. Сколько перестановок можно получить из букв слова КОЛОКОЛА? Решение. Требуется найти число перестановок с повторениями на множестве из 8 букв, среди которых: буква К повторяется 2 раза; буква О повторяется 3 раза; буква Л повторяется 2 раза буква А повторяется 1 раз. Таким образом,

Пример. Сколькими способами можно составить набор из 5 шоколадок, если имеются шоколадки трех сортов в количестве по 10 штук каждого вида? Решение. Поскольку при составлении шоколадного набора порядок расположения шоколадок не важен, то используем для подсчета формулу сочетаний с повторениями:

Очевидно, что количество всех возможных комбинаций из 10 цифр по 4 равно Число всех возможных комбинаций из 30 букв по две равно Если учесть возможность того, что буквы могут повторяться, то число повторяющихся комбинаций равно 30 (одна возможность повтора для каждой буквы). Итого, полное количество комбинаций по две буквы равно 900. Если к номеру добавляется еще одна буква из алфавита в 30 букв, то количество комбинаций увеличивается в 30 раз, т.е. достигает комбинаций. Окончательно, т.к. каждой буквенной комбинации можно поставить в соответствие числовую комбинацию, то полное количество автомобильных номеров равно Пример. Номер автомобиля состоит из трех букв и трех цифр. Сколько различных номеров можно составить, используя 10 цифр и алфавит в 30 букв.

Транскрипт

1 Лекция 1. Тема: «Элементы комбинаторики» Определение. Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиально возможное количество различных вариантов развития событий. Основные правила комбинаторики Большинство комбинаторных задач решается с помощью двух основных правил - правила суммы и правила произведения. Правило суммы. Если некоторый объект можно выбрать способами, а другой объект можно выбрать способами, то выбор "либо, либо " можно осуществить способами. Правило произведения. Если объект можно выбрать способами, а после каждого такого выбора другой объект можно выбрать (независимо от выбора объекта) способами, то пары объектов и можно выбрать способами. Пример 1. Сколько существует двузначных чисел? Решение. Поскольку в двузначном числе цифра, обозначающая число десятков, должна быть отлична от нуля, то = {1, 2,..., 9}, = {0, 1, 2,..., 9} и Основные формулы комбинаторики 1. Выборки элементов без повторений Определение. Размещениями из элементов по называются такие выборки, которые, имея по элементов, выбранных из числа данных элементов, отличаются одна от другой либо составом элементов, либо порядком их расположения. Число размещений из элементов по обозначим Используя основное правило комбинаторики, получаем 1

2 Пример 2. Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различные и нечетные? Решение. Т.к. нечетных цифр пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет: Пример 3. Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из пяти языков: русского, английского, немецкого, французского, испанского - на любой другой из этих пяти языков? Решение. Поскольку важен порядок, с какого языка задается перевод на другой, то для ответа на вопрос необходимо найти число размещений из пяти по два. Определение. Если, то - число таких размещений, которые отличаются только порядком расположения элементов. Такие размещения называются перестановками. Их число находится по формуле Пример 4. Сколькими способами семь книг разных авторов можно расставить на полке в один ряд? Решение. Эта задача о числе перестановок семи разных книг. Имеется P 7 =7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг. Определение. Выборки из элементов, взятых из данных, отличающихся только составом элементов, называются сочетаниями из элементов по. Число таких сочетаний находится Пример 5. В соревнованиях на первенство университета по волейболу участвуют 8 команд. Насколько более продолжительным будет турнир, организованный по круговой системе, чем по олимпийской? Решение. При проведении турнира по круговой системе каждый участник встречался с каждым и порядок их вхождения в пару не важен. Следовательно, по круговой системе потребуется провести встреч, а по олимпийской только - 7 (четыре встречи в полуфинале и одна в финале). финала, две - в 2

3 Пример 6. Сколькими способами читатель может выбрать две книжки из шести имеющихся? Решение. Число способов равно числу сочетаний из шести книжек по две, т.е. равно: Обсуждение. Мы видим, что число возможных комбинаций можно посчитать по разным правилам (перестановки, сочетания, размещения) причем результат получится различный, т.к. принцип подсчета и сами формулы отличаются. Внимательно посмотрев на определения, можно заметить, что результат зависит от нескольких факторов одновременно. Во-первых, от того, из какого количества элементов мы можем комбинировать их наборы (насколько велика генеральная совокупность элементов). Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны. И последнее, важно знать, является ли для нас существенным порядок элементов в наборе. Поясним последний фактор на следующем примере. Пример 7. На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек? Решение. В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5. Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантов перестановок, которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5. Пусть имеется k групп элементов, причем i-я группа состоит из n i элементов. Выберем по одному элементу из каждой группы. Тогда общее число N способов, которыми можно произвести такой выбор, определяется соотношением N=n 1 *n 2 *n 3 *...*n k. Пример 8. Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из n 1 элементов, а вторая - из n 2 элементов. Сколько различных пар элементов можно составить из этих двух 3

4 групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить n 2. Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет n 2. Так как в первой группе всего n 1 элемент, всего возможных вариантов будет n 1 *n 2. Пример 9. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться? Решение. n 1 =6 (т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6), n 2 =7 (т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5, 6), n 3 =4 (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4, 6). Итак, N=n 1 *n 2 *n 3 =6*7*4= Выборки элементов с повторениями В том случае, когда все группы состоят из одинакового числа элементов, т.е. n 1 =n 2 =...n k =n можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно n k. Такой способ выбора в комбинаторики носит название выборки с возвращением. В данных выборках допускается повторение элементов, что является достаточно естественным (например, в телефонных и автомобильных номерах возможно использование одной цифры несколько раз). Пример 10. Сколько всех четырехзначных чисел можно составить из цифр 1, 5, 6, 7, 8? Решение. Для каждого разряда четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=5 4 =625. Число размещений из элементов по с повторениями обозначается и находится каким образом Число перестановок, в которых 1-й элемент повторяется раз, 2-й - раз, а -й - раз, находится следующим образом: Пример 11. Сколько "слов" можно получить, переставляя буквы в слове МАТЕМАТИКА? Решение. Заметим, что если бы все буквы были различны, то получили бы новых "слов", но буква "М" употребляется в "слове" 2 раза, "А" - 3 раза, 4

5 "Т" - 2 раза, оставшиеся три буквы - по разу. Следовательно, искомое число будет в раз меньше, чем, и равно Число сочетаний с повторениями из элементов по выражается через число сочетаний без повторений: Пример 12. В кафе в продаже имеются 5 сортов пирожных. Сколькими способами 8 студенток могут заказать себе по одному пирожному? Решение. Зашифруем каждую покупку 8 пирожных единицами по 5 сортам, разделяя сорта нулями. Тогда каждой покупке будет соответствовать упорядоченный набор из 8 единиц и 4 (= 5-1) разделительных нулей, а общее число покупок будет соответствовать числу перестановок этих нулей и единиц. Таким образом, Задачи для самопроверки 1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться? 2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево? 3. В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день? 4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек? 5. Сколькими способами можно разложить восемь различных писем по восьми различным конвертам, если в каждый конверт кладется только одно письмо? 6. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать? 5

6 Задачи 1. В чемпионате России по футболу участвуют 16 команд. Сколькими способами может определиться тройка призеров? 2. Из колоды, содержащей 36 карт, вынули 10 карт. Сколькими различными способами это можно сделать? В скольких случаях среди этих карт окажется хотя бы один туз? В скольких случаях окажется ровно один туз? 3. Сколькими способами 8 человек могут встать в очередь друг за другом? 4. Сколькими способами можно расставить на книжной полке 5 учебников по комбинаторике, 4 - по алгебре и 3 - по математическому анализу, если учебники по каждому предмету одинаковые? 5. На физмате работают 76 преподавателей. Из них 49 знают английский язык, 32 - немецкий и 15 - оба языка. Сколько преподавателей на физмате не знает ни английского, ни немецкого языков? 6. В цветочном магазине продаются цветы 4 сортов. Сколько можно составить различных букетов из пяти цветов в каждом? 7. В азбуке Морзе буквы представляются последовательностями тире и точек. Сколько символов потребуется, чтобы закодировать буквы русского алфавита? 8. Какова вероятность выиграть хотя бы один из призов в спортлото? 6

КОМБИНАТОРИКА 1. Общие правила комбинаторики На практике часто приходиться выбирать из некоторого множества объектов подмножество элементов, обладающих теми или иными свойствами, располагать элементы одного

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» ЛЕКЦИЯ ПО ТЕОРИИ

Практическая работа 15 Расчет количества выборок Цель работы: научиться определять количество выборок, используя правила комбинаторики и основные формулы. Содержание работы. Основные понятия. 1 Правило

С О Д Е Р Ж А Н И Е 1 ТЕМА II. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ... 2 1. СПРАВОЧНЫЕ МАТЕРИАЛЫ И ПРИМЕРЫ... 2 1.1. ПРИМЕРЫ... 2 2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ, ОБОЗНАЧЕНИЯ И ФОРМУЛЫ... 3 3. ПРАВИЛА КОМБИНАТОРИКИ... 4 4.

Тема 48 «Поочередный и одновременный выбор» Наука, изучающая способы составления и количество множеств и их подмножеств, называется комбинаторикой. Каждое конкретное подмножество, составленное из элементов

КОМБИНАТОРНЫЕ ЗАДАЧИ Вендина Алла Анатольевна Доцент кафедры математики и информатики Ставропольского государственного педагогического института Вендина А.А. Комбинаторные задачи. Задачи на выбор элементов

1) Имеется слово из 12 [неповторяющихся] букв. Сколькими способами можно переставить буквы в этом слове, чтобы получились всевозможные различные наборы букв? Поскольку все буквы различны, то n P12 12!

Урок 2.Размещения и сочетания Цели урока: образовательные: научить учащихся решать задачи с помощью формул сочетаний и размещений; различать комбинаторные соединения; научить решать задачи из жизни; воспитательные:

Комбинаторика Методы решения задач Румянцева ЛС Правило суммы Если конечные множества не пересекаются, то число элементов X U Y {или} равно сумме числа элементов множества X и числа элементов множества

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

Кафедра математики и информатики Математика Учебно-методический комплекс для студентов СПО, обучающихся с применением дистанционных технологий Модуль 6 Элементы теории вероятностей и математической статистики

Министерство образования Московской области Государственное бюджетное образовательное учреждение среднего профессионального образования Московской области «Балашихинский промышленно-экономический колледж»

И. В. Яковлев Материалы по математике MathUs.ru Комбинаторика. Правило произведения При решении комбинаторных задач часто приходится умножать число способов выбора одного объекта на число способов выбора

Теория вероятностей и математическая статистика Доктор физ.-мат. наук профессор Михаил Павлович Харламов «Страница» с методическими материалами http://inter.vags.ru/hmp Волгоградский филиал РАНХиГС (ФГОУ

С А Лавренченко ТЕОРИЯ ВЕРОЯТНОСТЕЙ «Три карты три карты три карты!» (Опера «Пиковая дама») Практическое занятие 1 11 Классическое определение вероятности 111 Простейшие задачи на классическое определение

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

Теория множеств и основы комбинаторики План лекции П.. Определение множества и подмножества... П.. Множества и отношения... П.. Операции над множествами... П. 4. Свойства операций над множествами... 4

Примеры комбинаторных задач и общие принципы комбинаторики Пример, навеянный сказкой Андерсена «Снежная королева». Помните, когда Герда нашла Кая в чертогах Снежной королевы, тот безуспешно складывал

ЗАНЯТИЕ 1 ЭЛЕМЕНТЫ КОМБИНАТОРИКИ МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО МАТЕМАТИКЕ МИСИС 2013 УТВЕРЖДАЮ: Д.Е. Капуткин Председатель Учебно-методической комиссии по реализации Соглашения с Департаментом образования

Лекция 1 Элементы комбинаторики Комбинаторика это раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами

РЕШЕНИЕ ЗАДАЧ ПО ТЕОРИИ ВЕРОЯТНОСТЕЙ 1 В теории вероятностей часто приходится иметь дело с задачами, в которых необходимо подсчитывать число возможных способов совершения каких-либо действий. Задачи такого

4 Комбинаторика Перестановка это упорядоченный набор чисел 1 обычно трактуемый как биекция на множестве { 1 } которая числу i ставит в соответствие i-й элемент из набора Число при этом называется порядком

Пособие для учителей учреждений общего среднего образования Рекомендовано Научно-методическим учреждением «Национальный институт образования» Министерства образования Республики Беларусь М о з ы р ь «Белый

Тема 53 «Комбинированные задачи». Задачи, рассмотренные в данном разделе, обобщают сведения комбинаторики, статистики и теории вероятностей. Основные формулы комбинаторики. Без повторений С повторениями

Разработчик курса доцент кафедры высшей математики кандидат технических наук Некряч Е.Н. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ МНОЖЕСТВА И ОПЕРАЦИИ НАД НИМИ Такое понятие, как множество, вообще говоря, не определяется,

Теория вероятностей и математическая статистика Доктор физ.-мат. наук профессор Михаил Павлович Харламов Интернет-ресурс с методическими материалами http://www.vlgr.ranepa.ru/pp/hmp Волгоградский филиал

009-00 уч. год. 6, 0 кл. Математика. Элементы комбинаторики. Комбинаторикой (от латинского combinare соединять, сочетать) называют раздел математики, в котором изучаются задачи следующего типа: сколько

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ. Правило произведения. Если существует n вариантов выбора первого элемента и для каждого из них имеется m вариантов выбора второго элемента, то всего существует n m различных пар

Представляю разбор контрольных работ из сборника «Л.А. Александрова. Алгебра 9 класс. Контрольные работы» Иногда трудно самостоятельно разобраться со всеми заданиями, предлагаемыми на контрольных, особенно

НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им Н И ЛОБАЧЕВСКОГО Факультет вычислительной математики и кибернетики Кафедра математической логики и высшей алгебры ЭЛЕМЕНТЫ КОМБИНАТОРИКИ (Пособие для студентов

1 Основные понятия комбинаторики 1 Приложение Определение Произведение всех натуральных чисел от 1 до n включительно называют n-факториалом и пишут Пример Вычислить 4! 3! n! 1 3 n 4!-3!= 1 3 4 1 3 4 18

Задачи по теории вероятностей Н.М. Ефимова, учитель математики МБОУ «Гимназия» Теория вероятностей и математическая статистика занимаются построением и исследованием моделей различных ситуаций, связанных

Тема 49 «Формулы числа сочетаний. Бином Ньютона». Основные формулы комбинаторики. Без повторений С повторениями A = n! n k! A = n Порядок важен P = A = n! P = A = n Pk, k, k = (k + k + + k)! k! k! k!

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

И. В. Яковлев Материалы по математике MathUs.ru Содержание Десятичная запись 1 Всероссийская олимпиада школьников по математике................ 1 2 Московская математическая олимпиада........................

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение дополнительного образования детей «Заочная физико-техническая школа Московского физико-технического

III ОСНОВЫ КОМБИНАТОРИКИ Общие правила комбинаторики Комбинаторика это раздел дискретной математики, который изучает способы подсчета числа элементов различных конечных множеств Многие правила комбинаторики

Математика (БкПл-100) М.П. Харламов 2011/2012 учебный год, 1-й семестр Лекция 5. Тема: Комбинаторика, введение в теорию вероятностей 1 Тема: Комбинаторика Комбинаторика это раздел математики, изучающий

Лекция 2: перечслительная комбинаторика Дискретная математика, ВШЭ, факультет компьютерных наук (Осень 2014 весна 2015) Задачи перечислительной кмбинаторики имеют типовой вид: «сколько способов сделать

ВЕРОЯТНОСТЬ СЛУЧАЙНОГО СОБЫТИЯ Аксиомы Колмогорова В 1933 г. А. Н. Колмогоров в книге «Основные понятия теории вероятностей» дал аксиоматическое обоснование теории вероятностей. «Это означает, что, после

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

Задачи и головоломки 1. Десятичная система счисления Десятичная система счисления является позиционной. В позиционных системах счисления вклад цифры в число зависит от положения этой цифры в записи числа.

Муниципальное автономное общеобразовательное учреждение «Лицей 38» города Белгорода Учебное занятие по теме: «Комбинаторное правило умножения» Учитель математики МАОУ «Лицей 38» г.белгорода Реуцкая Людмила

Достоверное событие. Событие называется достоверным, если оно обязательно произойдет при осуществлении определенной совокупности условий. Обозначение: Ω (истина). Невозможное событие. Событие, которое

ЛЕКЦИЯ 1 ТЕМА: ВИДЫ КОМБИНАТОРНЫХ ЗАДАЧ. ОСНОВНЫЕ ПРИНЦИПЫ КОМБИНАТОРИКИ. План 1. История комбинаторики 2. Некоторые задачи комбинаторики 3. Структура и методы 4. Примеры решения задач 1. История комбинаторики

В лекции использовались материалы из книги И.А. Лаврова ѕматематическая логикаї и из сборника Т.В. Андреевой ѕдискретная математика для социологовї. 1 Размещения n предметов по k ящикам, перестановки.

Лекция 1. Тема: ОСНОВНЫЕ ПОДХОДЫ К ОПРЕДЕЛЕНИЮ ВЕРОЯТНОСТИ Предмет теории вероятностей. Историческая справка Предметом теории вероятностей является изучение закономерностей, возникающих при массовых, однородных

Элементы комбинаторики профессор кафедры физико-математического образования ИПК и ПРО, дфмн Мищенко С.П. џ1. Декартово произведение множеств Элементарная комбинаторика связана с одним простым результатом

Заочный физико-математический лицей «Авангард» Е. Н. Филатов АЛГЕБРА 8 Экспериментальный учебник Часть 1 МОСКВА 2016 СОДЕРЖАНИЕ 1. Делимость. 2. Чёт нечет 3. Множества. 4. Забавные задачи. 5. Комбинаторика

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ им. Р.Е. Алексеева

1 Классическое определение вероятности 1 Колода из 3-х карт тщательно перетасована Найти вероятность того, что все четыре туза лежат в колоде один за другим, не перемежаясь другими картами Решение Число

Югорский физико-математический лицей В.П. Чуваков Делимость целых чисел в задачах Сборник задач Ханты-Мансийск 05 Делимость целых чисел в задачах: Сборник задач, - Ханты-Мансийск, Югорский физико-математический

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Ухтинский государственный технический университет (УГТУ) КОМБИНАТОРИКА Методические

Воробьев В.В. «Лицей» г.калачинска Омской области Практикум по решению задач по теории вероятностей и математической статистике Большую роль при изучении тем по теории вероятностей и статистики играют

ПРКТИКУМ Основные формулы комбинаторики Виды событий Действия над событиями Классическая вероятность Геометрическая вероятность Основные формулы комбинаторики Комбинаторика изучает количества комбинаций,

Комбинаторика ДИСКРЕТНАЯ МАТЕМАТИКА C. Элементы комбинаторики (в рамках теории множеств) Tallinn University of Technology Комбинаторика раздел математики, посвящённый решению задач выбора и расположения

Математика 6 класс Множества и комбинаторика блок содержания знать уметь п/п 1 Понятие множества. Понятие множества, описывать совокупности Виды множеств. подмножества, предметов или объектов, конечного,

Двоичное кодирование 1.3 Двоичное кодирование Ключевые слова: дискретизация алфавит мощность алфавита двоичный алфавит двоичное кодирование разрядность двоичного кода 1.3.1. Преобразование информации из

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

Комбинаторика – раздел математики, посвященный подсчету
количеств разных комбинаций элементов некоторого, обычно
конечного, множества
Го́тфрид Ви́льгельм Ле́йбниц
(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