Тема: Элементы теории комбинаторики

Определение: Соединение (выборка)– некоторый набор, составленный из элементов данного множества.

Основные правила комбинаторики

1. Правило суммы: если элемент А можно выбрать n способами, а элемент В можно выбрать m способами, то выбрать либо А, либо В можно (п+ т) способами.

2. Правило произведения (умножения): если элемент А можно выбрать n способами, а элемент В можно выбрать m способами, то два элемента (пару) А и В можно выбрать п·* т способами.

Типы соединений: 1) Перестановки; 2) Размещения; 3) Сочетания.

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

Вычисляют по формуле: Рn= n!; n! = 1 · 2 · 3 ·…· (n–2)(n–1) n

Задача №1. Вычислить: =6!=1*2*3*4*5*6=720

Задача №2. Сколькими способами можно посадить три дерева (дуб, березу, клен) в три подготовленные лунки?

Решение: Р₃=3!=6;

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

Вычисляют по формуле:

Задача №3. Вычислить:

Задача №4. Из ящика, где находится 15 шаров, нумерованных последовательно от 1 до 15 требуется вынуть 3 шара. Определить число возможных комбинаций при этом?

Решение: =2730

Определение: Сочетанием из n элементов по m (m£n) называется любое соединение, составленное из m элементов, выбранных из данных n элементов. Сочетания из n по m отличаются друг от друга хотя бы одним элементом, порядок элементов значения не имеет. Обозначают: (читается «С из n по m»)

Вычисляют по формуле:

Свойства сочетаний:

1. С = С

2. С = С =1

3.

Задача №5. Вычислить:

Задача №6: Сколькими различными способами можно избрать из 15 человек делегацию в составе 3 человек?

Решение:

Лекция №2

Тема: Треугольник Паскаля. Формула бинома Ньютона.

Треугольник Паскаля

Свойство №3 используют при построении треугольника Паскаля.

Определение: Эта таблица называется треугольником Паскаля, по имени известного французского математика Блеза Паскаля (1623-1662), исследовавшего его свойства.

С

С С

С С С

С С С С

С С С С С

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

Определение: Для каждого натурального числа n и произвольных чисел a и b имеет место равенств:

Равенство называется формулой бинома Ньютона, где и называют биномиальными коэффициентами.

Формула Ньютона обладает следующими свойствами:

1) В разложении двучлена(а+b)ⁿ в формуле содержится n+1 член.

2) Сумма степеней всех одночленов раны степени двучлена n.

3) Степень первого выражения одночлена в разложении убывает, начиная со степени двучлена и заканчивая нулевой.

4) Степень второго выражения одночлена в разложении возрастает, начиная с нулевой и заканчивая степенью двучлена.

5) Биноминальные коэффициенты совпадают с числом соответствующей строки треугольника Паскаля.

6) Сумма биноминальных коэффициентов разложения равна 2ⁿ

Задача №1: Представьте каждую степень двучлена в виде многочлена.

(a +b)² = а² +2аb + 2b²

(а +b)³ = а³ +3а²b+3аb² +b³

(с +а)⁴ = с⁴+ 4с³а +6с²а² + 4са³ +а⁴

(с +а)⁵ =

(с +а)⁶=

(с +а)⁴

Практические задания по комбинаторике

1. Вычислить:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

2 Представьте каждую степень двучлена в виде многочлена:

а) (х +2у)²,

б) (а- b)³,

в) (а+1)³,

г) (с+3а)⁴,

д) (1- 2а)⁴,

е) (х -2)⁵,

ж) (х+у)⁶

з) (х - 1)⁷

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

4. В вашей группе в среду пять уроков: русский язык, литератур, математика, информатика, ЧКР. Сколько вариантов расписания можно составить?

4 Изменяя порядок слов: руки, мою, я, составьте всевозможные предложения.

5 При встрече 5 человек обменялись рукопожатиями. Сколько сделано рукопожатий?

6 Сколько существует способов выбора трёх ребят из 4-х желающих дежурить в столовой?

7 Сколько экзаменационных комиссий, состоящих из 3 человек, можно создать из 5 преподавателей?

8 Сколько различных четных трехзначных чисел, в каждом из которых все цифры различны, можно составить из цифр 1, 2, 3, 0?

9. Сколькими способами можно составить расписание на день из 4 различных уроков, если изучается 10 предметов?

10. Бригадир должен отправить на работу бригаду из 4 человек. Сколько бригад по 4 человека в каждой можно составить из 13 человек?

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

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

Лекция №1