Презентация по математике "Введение в комбинаторику"

Цель урока:
1) понятие комбинаторных задач
2)основные методы решения комбинаторных задач

.

Комбинаторика – это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.
Выбором объектов и расположением их в том или ином порядке приходится заниматься чуть ли не во всех областях человеческой деятельности, например конструктору, разрабатывающему новую модель механизма, ученому-агроному, планирующему распределение с/х культур на нескольких полях, химику, изучающему строение органических молекул, имеющих данный атомный состав.
С комбинаторными задачами люди столкнулись в глубокой древности. В Древнем Китае увлекались составлением магических квадратов. В Древней Греции занимались теорией фигурных чисел.

Комбинаторные задачи возникли и в связи с такими играми, как шашки, шахматы, домино, карты, кости и т.д. Комбинаторика становится наукой лишь в 18 в. – в период, когда возникла теория вероятности.
После первых работ, выполненных в 16в. Итальянскими учеными Дж.Кардано, Н.Тартальей и Г.Галилеем, такие задачи изучали французские математики Б.паскаль и П.Ферма. Первым рассмотрел комбинаторику как самостоятельная ветвь науки немецкий философ и математик Г.Лейбниц, опубликовавший в 1666г. Работу «Об искусстве комбинаторики». Замечательные достижения в области комбинаторики принадлежат Л.Эймеру.

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

Квадратное число находится по формуле:
Nкв.=п х п
Треугольное число находится по формуле:
Nтр.=п(п-1):2
Пятиугольные числа находятся по формуле:
Nпят.=п+3п(п-1):2

Все составные числа древние математики представляли в виде прямоугольников.

«Число , место и комбинация – три взаимно перекрещивающиеся, но отличные сферы мышления, к которым можно отнести все математические идеи».
Дж. Сильвестр

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

Правило суммы

Если элемент А может быть выбран К1 способами, а элемент В – К2 способами, причем выборы А и В являются взаимно исключающими, то выбор «либо А, либо В» может быть осуществлен К1+К2 способами.
Задача 1. Сколько существует способов выбрать кратное двум или трем число из множества чисел : 2,3,4,15,16,20,21, 75,28 ?
Решение: К1=5 –кратное 2 (2,4,16,20,28),
К2=4 – кратное 3 (3,15,21,75)
К1+К2 = 5+4 = 9

Если элемент А может быть выбран К1 способами, а элемент В – К2 способами, то выбор «А и В» может быть осуществлен К1*К2 способами
Задача2. а) Сколько различных двузначных чисел можно составить из цифр 1,3,5,7,9?
Решение: N= 5х5 = 25 ( Если не сказано, что элемент не повторяется, то выборка с повторениями)
б) Сколько среди них чисел, кратных 5?
Решение: Число кратно 5, если оканчивается цифрой 5 или 0. В нашем случае – 5.
На первой позиции фиксируем одну из пяти цифр, на второй – 5.
N= 5х1 =5

в) Сколько среди чисел 1,3,5,7,9, кратных 11?
Решение: Двузначное число кратно 11, если обе его цифры одинаковы.
N= 5
г) Сколько среди чисел 1,3,5,7,9 кратных 3?
Решение: Число кратно 3, если сумма его цифр делится на 3. Составим всевозможные пары:
1 -1 3 -3 5 – 5 7 – 7 9 -9
1 -3 3 -5 5 – 7 7 – 9
1 -5 3 -7 5 -9
1 -7 3 – 9
1 – 9
Таких пар 15. Среди них 5 пар, сумма которых делится на 3, причем три пары допускают перестановку, т.е. могут образовать по два разных числа. Всего 5+3=8 различных двузначных чисел.

Задача 3. Сколько существует способов занять 1-ое, 2-ое и 3-е места на чемпионате по футболу, в котором участвуюта) 10 команд, б) 11 команд?
Решение: N=10х9х8=720
N=11х10х9=990

Задача 4. Сколько различных трехзначных чисел можно составить из цифр 0, 1,2,3,4, если
а) цифры не повторяются? б) цифры могут повторяться
Решение: а)На первом месте одна из 4-х цифр ( 0 не может быть), на 2-ом – одна из оставшихся 4-х:
N=4х4х3= 48
б)На 1-ом месте может быть одна из 4-х цифр, на 2-ом – одна из 5 (0 входит):
N=4х5х5= 100

Задача 5. Несколько стран в качестве символа своего государства решили использовать флаг в виде четырех горизонтальных полос, одинаковых по ширине, но разных по цвету: белый, синий, красный, зеленый. У каждой страны свой, отличный от других, флаг.

а)Сколько всего стран могут использовать такую символику?
б) Сколько стран могут использовать такую символику с верхней белой полосой?
в) Сколько всего стран могут использовать такую символику с нижней белой полосой?
г) Сколько стран могут использовать такую символику с синей и красной полосами, расположенными рядом?

а)Решение: Цвет верхней полосы можно выбрать одним из 4 способов, второй полосы – одним из трех оставшихся, цвет 3 полосы – одним из 2 оставшихся, а 4 – одним способом. По правилу произведения N=4х3х2х1=24
б)Решение: Если фиксировать цвет белой полосы, то цвета следующих полос можно выбрать 3х2х1 = 6 способами.
в)Решение: Если фиксировать цвет нижней полосы, то цвета трех расположенных над ней полос можно выбрать 3х2х1 = 6 способами.
г)Решение: Две полосы, всегда расположенные рядом, можно рассматривать как одну полосу, тогда полос останется 3, из них можно составить 3х2х1=6 разных флагов. Но две полосы (синюю и красную) можно «склеить» по-разному: синяя, а под ней красная, или красная, а под ней синяя. Поэтому общее количество вариантов по правилу суммы равно 6+6=12

Задача 6. В клетки квадратной таблицы 2х2 произвольно ставят крестики и нолики.
а) Сколькими способами можно заполнить эту таблицу?
Решение: Для заполнения первой клетки есть 2 способа
( крестик или нолик); для заполнения каждой последующей – тоже 2 способа; общее количество способов заполнить таблицу по правилу произведения равно 2х2х2х2=16.
б) В скольких случаях в левой нижней клетке будет стоять крестик?
Решение: Если в левой нижней клетке фиксируем крестик, то остальные 3 клетки можно заполнить 2х2х2=8 различными способами.
в) В скольких случаях в верхней левой и нижней правой будут разные значки?
Решение: Если в верхней клетке – крестик, а нижней – нолик, то остальные клетки можно заполнить 2х2=4 способами. Если в верхней клетке – нолик, в нижней – крестик, то еще 4 способа заполнения. Всего 4+4=8 способов.

Задача 7. Из цифр 1,2,3,5 составили все возможные четырехзначные числа (без повторения цифр). Сколько среди них таких чисел, которые больше 2000, но меньше 5000?
Решение: Выбор 1-ой цифры – 2 способа (3,4), 2-ой цифры – 3 способа, третьей – 2 способа, четвертой -1. По правилу произведения N=2х3х2х1=12 чисел.

Задача 8. На входной двери дома установлен домофон, на котором нанесены цифры 0,1,2,…9.Каждая квартира получает кодовый замок из двух цифр типа 0-2, 3-7 и т.п. Хватит ли кодовых замков для всех квартир, если в доме 96 квартир? (код 0-0 не существует)
Решение: Выбор 1-й цифры – 10 вариантов, 2-й –10 вариантов.
Всего 10х10 – 1 = 99 вариантов
Ответ: хватит.

Задача 9. В контрольной работе будет 5 задач – по одной из каждой пройденной темы. Задачи будут взяты из общего списка по 10 задач в каждой теме, а всего было пройдено 5 тем. При подготовке к контрольной работе Вова решил только по 8 задач в каждой теме. Найдите:
а) общее число всех возможных вариантов контрольной работы
Решение: Каждая задача может быть выбрана 10 способами. По правилу произведения N=10х10х10х10х10=100000
б)число тех вариантов, в которых Вова умеет решать все 5 задач
Решение: N=8х8х8х8х8=32768
в) число тех вариантов, в которых Вова не сможет решить ни одной задачи
Решение: N=2х2х2х2х2=32
г) число тех вариантов, в которых Вова умеет решать все задачи, кроме первой.
Решение: N=2х8х8х8х8=8192

Таблицы вариантов

Задача 10. Составляя расписание уроков на понедельник для 7а класса, завуч хочет первым уроком поставить либо физику, либо алгебру, а вторым – либо русский язык, либо литературу, либо историю. Сколько существует вариантов составления расписания на первые два урока?
Решение: Составим таблицу вариантов:
Всего существует 2х3 = 6 вариантов

Задача 11. Сколько двузначных чисел, кратных 3, можно получить из цифр 1,3,5,7,9?
а) цифры не повторяются -
6 вариантов (15,39,57,51,75,93)
б) цифры могут повторяться –
8 вариантов (еще 33,99)

Подсчет вариантов с помощью графов

Задача 12. При встрече каждый из друзей пожал другому руку. Сколько было рукопожатий, если друзей:
а) трое б) четверо в) пятеро
N=3 N=6 N=10

3

2

1

1

3

2

4

1

2

3

5

4

Построение графов

Задача 16. По окончании деловой встречи специалисты обменялись визитными карточками. Сколько всего визитных карточек было роздано, если во встрече участвовали:
А) 3 человека б) 4 человека в) 5 человек







3 ребра, 6 стрелок 6 ребер, 12 стрелок 10 ребер, 20стрелок
N=6 N=12 N=20

1

3

2

4

3

2

1

5

4

3

2

1

Виды выборок

Перестановки
Размещения
Сочетания
Размещения с повторениями (строки)
Перестановки с повторениями
Сочетания с повторениями
Разбиения
Подмножества

Формулы комбинаторики