Помощь по Теле2, тарифы, вопросы

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

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. Тогда получим .

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

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

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

…………………..

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

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

Ответьте на вопросы письменно: (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)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.

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

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

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

Содержание
Лекция 1. Введение в комбинаторику. Некоторые области применения задач комбинаторики. Прямое произведение множеств. Правило суммы и правило произведения для конечных множеств. Принцип Дирихле. Размещения без повторений, размещения с повторениями, сочетания без повторений, сочетания с повторениями, перестановки. Мультимножество
Введение в комбинаторику. Некоторые области применения задач комбинаторики
Прямое произведение множеств
Правило суммы и правило произведения
Принцип Дирихле
Размещения, сочетания, перестановки
Мультимножество
Лекция 2. Основные тождества, связанные с числом сочетаний. Бином Ньютона. Следствия из теоремы о биноме Ньютона. Свойства биномиальных коэффициентов
Основные тождества, связанные с числом сочетаний
Бином Ньютона
Следствия из теоремы о биноме Ньютона
Свойства биномиальных коэффициентов
Лекция 3. Треугольник Паскаля. Некоторые свойства треугольника Паскаля. Свойства шестиугольника для треугольника Паскаля. Разбиение множеств. Числа Стирлинга второго рода
Треугольник Паскаля
Некоторые свойства треугольника Паскаля
Свойства шестиугольника
Разбиения множества
Числа Стирлинга второго рода
Лекция 4. Числа Белла. Числа Стирлинга первого рода. Беззнаковое число Стирлинга первого рода
Число Белла
Числа Стирлинга первого рода
Беззнаковое число Стирлинга первого рода
Лекция 5. Формула включений и исключений. Задача о беспорядках
Формула включений и исключений
Задача о беспорядках
Лекция 6. Число элементов, обладающих ровно к свойствами. Задача о встречах. Число элементов, обладающих не менее чем к свойствами
Число элементов, обладающих ровно к свойствами
Задача о встречах
Лекция 7. Полиномиальная теорема. Методы в комбинаторном анализе. Метод производящих функций. Задача о взвешивании
Полиномиальная теорема
Методы в комбинаторном анализе. Метод производящих функций
Задача о взвешивании
Лекция 8. Производящие функции. Виды производящих функций. Свойства производящих функций. Таблица соответствий производящих функций и последовательностей
Производящие функции
Виды производящих функций
Свойства производящих функций
Таблица соответствий производящих функций и последовательностей
Лекция 9. Дифференцирование и интегрирование производящих функций. Некоторые элементарные производящие функции. Бесконечно убывающая геометрическая прогрессия и последовательность из единиц
Дифференцирование и интегрирование производящих функций. Примеры использования
Некоторые элементарные производящие функции
Бесконечно убывающая геометрическая прогрессия и последовательность из единиц
Лекция 10. Примеры нахождения производящих функций для заданной последовательности. Примеры нахождения для последовательности производящих функций
Примеры нахождения производящих функций для заданной последовательности
Примеры нахождения для последовательности производящих функций
Лекция 11. Решение однородных рекуррентных соотношений. Общий метод решения рекуррентного соотношения
Решение однородных рекуррентных соотношений
Общий метод решения рекуррентных соотношений
Лекция 12. Последовательность Фибоначчи. Примеры использования производящих функций. Вычисление корня числа через производящие функции
Последовательность Фибоначчи
Примеры использования производящих функций
Вычисление корня числа через производящие функции
Лекция 13. Числа Каталана. Последовательность Каталана и производящая функция Каталана. Алгоритм расстановки скобок
Числа Каталана
Последовательность Каталана и производящая функция Каталана
Алгоритм расстановки скобок
Лекция 14. Генерирование комбинаторных объектов. Перестановки. Сочетания. Разбиение чисел. Подмножества множеств
Перестановки
Сочетания
Разбиения чисел
Подмножества множества
Литература
Учебно-методический комплекс по дисциплине «Комбинаторные алгоритмы»
1. Место дисциплины в структуре ООП
2. Цели и задачи дисциплины
3. Требования к результатам освоения дисциплины
4. Объем дисциплины и виды учебной работы
5. Содержание дисциплины
5.2. Лабораторный практикум
5.3. Практические занятия (семинары) не предусмотрены
6. Балльно-рейтинговая система оценки знаний, шкала оценок
7. Примерная тематика курсовых проектов (работ)
8. Учебно-методическое и информационное обеспечение дисциплины
I. Информация о преподавателях (ссылка на страницу)
II. Литература
III. Базы данных, информационно-справочные и поисковые системы
9. Материально-техническое обеспечение дисциплины
10. Методические рекомендации по организации изучения дисциплины.

Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Лекции по дискретной математике, Часть I, Комбинаторика, Зарипова Э.Р., Кокотчикова М.Г., 2012 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.