Комбинаторика
учебно-методическое пособие по теме
Предварительный просмотр:
Министерство образования и науки РФ.
ГБОУ СПОМО Фрязинский государственный техникум электроники, управления и права.
КОМБИНАТОРИКА
Учебное пособие
I курс
Специальности 210912
030912
г. Фрязино
2012 год
Согласовано Утверждаю
предметно – цикловой комиссией Зам. директора по УВР
протокол № _______Морозова О.Н.
«___»________ 201___
Председатель ПЦК
________ Морозова Н.Е.
Рецензент:
__________Ивонин В.И.
Преподаватель:
__________Морозова Н.Е.
2
АННОТАЦИЯ
Данное методическое пособие содержит теоретический материал по теме «Комбинаторика», рекомендации по применению формул комбинаторики, разобранные с объяснениями решения задач, подборку задач для самостоятельного решения с ответами.
Предназначено для самостоятельной работы студентов и для аудиторной работы преподавателя.
4
ВВЕДЕНИЕ
Данная методическая разработка необходима, т.к. тема Комбинаторика опять включена в программу всех специальностей техникума. Представляет собой теоретический материал для одного занятия, пояснительные задачи к каждому эпизоду темы. Изложения полны, но доступны. Материал разработки можно использовать преподавателям для подготовки к занятию и студентам для самостоятельной работы, ознакомительной и для подготовки докладов и рефератов.
Т.к. на разных специальностях на эту тему отводится разное количество часов, то материал дан максимально полный и к уроку его можно отбирать или компоновать по разному. Изложение лекционное, поэтапное с закрепительными вопросами по каждому этапу, задачами для самостоятельной работы.
Начать надо с истории развития темы и основного определения.
Комбинаторикой называется область математики, где подсчитывается число различных комбинаций, подчиненных тем или иным условиям и которые можно составить из элементов данного множества.
Комбинации, которые возникали при бросании кости и в других играх всегда привлекали людей. Самая древняя кость была найдена при раскопках в северном Ираке. Её возраст около 5.000 лет.
Различные игры (например, кости, лото, домино) ставят вопросы о числе исходов, способов, вариантов, т.е. комбинаторных соединений, требующих применения серьезной математической техники. Со временем выяснилось, что аналогичные вопросы возникают не только в играх, но и в самых разнообразных и внешне далеких друг от друга сферах человеческой деятельности: экономике и планировании, лингвистике и криптографии, теории стрельбы и организации движения транспорта.
С помощью комбинаторики и тесно связанных с ней разделов математики, таких как статистика и теория вероятностей, найдены строгие закономерности там, где их не должно было бы быть по самому смыслу – в мире случайных явлений, среди хаоса и беспорядка.
Родоначальники комбинаторики и теории вероятности: Б. Паскаль
П.Ферма
Я. Бернулли
П. Лаплас
Л. Эйлер
По этим фамилиям видно, что комбинаторика не является древним разделом математики. Интерес к ней и ее включение в программу связанно с наступлением компьютерной эры, повышением роли дискретной математики, имеющей дело с множествами.
6
ОСНОВНАЯ ЧАСТЬ
КОМБИНАТОРИКА, ЕЁ ПРАВИЛА И ВИДЫ.
Если во множестве есть элементы, то их можно комбинировать друг с другом по различным свойствам и правилам. Это и есть комбинаторика – подсчет числа различных соединений элементов. Существует два основных правила: правило суммы и правило произведения.
Правила суммы: Если объект А можно выбрать К способами, а объект В – L способами, то объект А либо В можно выбрать К+L способами.
Пример: В первом ящике 8 шаров, во втором – 5. Сколько существует способов извлечь шар или из первого или из второго ящика. Ответ: 8+5=13 способов.
Правило произведения: Если объект А можно выбрать К способами, а после этого другой объект В – L способами, то пары объектов и А и В можно выбрать К∙L способами.
Пример: В первом ящике 8 шаров, во втором – 5. Сколько существует способов извлечь один шар из первого и один из второго ящика. Ответ: 8∙5=40 способов, т.к. на каждый из 8 способов достать шар из первого ящика, существует 5 способов достать шар из второго, что видно из рисунка 1.
⃝
⃝ ⃝
⃝ ⃝
⃝ ⃝
⃝ ⃝
⃝ ⃝
⃝
⃝
Рис.1.
Правила запоминаются лучше, если сопоставлять правило сложения с союзом «ИЛИ», а правило умножения с «И»
Пример: В ящике 8 прозрачных шаров, 5 зеленых, 7 красных
- Сколько существует способов извлечь цветной шар?
Ответ:5+7=12, т.к. цветной – это зеленый или красный.
С помощью правил сложения и умножения можно составлять цепочки решения для еще более сложных вопросов.
- Сколько существует способов извлечь 3 шара разного цвета?
Ответ: 8∙5∙7=280
- Сколько существует способов извлечь два шара разного цвета?
Ответ: 8∙5+5∙7+7∙8=40+35+56=131
Пояснение: В данном вопросе возможны варианты ответа. Или прозрачный и зеленый, или зеленый и красный или красный и прозрачный.
Обратите внимание как вместо «И» и «ИЛИ» встали знаки сложения и умножения. В дальнейшем можно будет число способов подсчитывать по формулам, которые имеют вид: =
;
=n!
7
Обозначение n! читается «n факториал».
В анекдоте профессор просит студента назвать эти формулы и студент их громко с выражением выкрикивает. «Что вы кричите?»- спрашивает профессор. «Ну, там же восклицательный знак»- отвечает студент. Так вот этот восклицательный знак и есть знак факториала. Этот знак задает очень быстрое наращивание значения числа стоящего под ним. Факториалом числа называется произведение всех натуральных чисел от 1 до n включительно. Причем 0!=1.
1!=1
2!=1∙2=2
3!=1∙2∙3=6
4!=1∙2∙3∙4=24
5!1∙2∙3∙4∙5=120
6!=1∙2∙3∙4∙5∙6=720 и т.д.
Например:10!= 1∙2∙3∙4∙5∙6∙7∙8∙9∙10=3628800. Это уже более трех миллионов, а мы только в первом десятке чисел.
Попробуем считать по формулам.
Пример: Вычислить
Решение: =
=
=
Начнем произведение не с 1, а с 8 в числителе и с 5 в знаменателе
И видим следующую закономерность:
- если начинать по убывающей писать сомножители с нижнего числа(в данном случае это 8), то сомножителей после сокращения столько же каково верхнее число(в данном случае 3)
Пример: Вычислить
Решение: Применим формулу
=
, где n=10, m=5 и получим
=
=
=
=10∙9∙8∙7∙6 – опять произведение m=5 сомножителей, начиная с n=10.
Можно было посчитать сразу
=10∙9∙8∙7∙6=30240
Ответ: =30240.
Пример: Вычислить =
=
=
=8∙7= 56
Есть общее в вычислении с предыдущим примером. Только надо еще все поделить на верхнее число с факториалом
=
=8∙7=56.
Ответ: =56.
8
Когда элементы во множестве не только комбинируются, но из всех n элементов определенным образом выбирают только m (где 0≤m≤n), то это называется выборкой.
Выборки из n элементов по m бывают упорядоченные и неупорядоченные. В чем разница? Каких больше? Как «на слух» можно отделить их друг от друга?
В упорядоченных множествах с изменением порядка расположения его элементов меняется само множество. Например: - рейтинговая таблица;
- расписание уроков
Размещениями называются упорядоченные выборки из n элементов по m. Обозначаются
Находятся по формуле =
(1)
=n∙ (n-1)(n-2)…(n(m-1) (*)
=
(**)
Если равны правые части равенств (*) и (**), то равны и левые.
Пример: Сколько существует, способов составит расписание из 3 пар на один день из 9 предметов?
Решение: В расписании порядок расположения предметов важен, хорошо, когда последняя география или физическое воспитание. Чудесный день, когда это II и III пара. Упорядоченная выборка – это размещение и их число находится по формуле(1):
=
=
=
=9∙8∙6=504
Этот результат надо понимать так:
- любой из 9 предметов на I паре
- и любой из оставшихся восьми на II
- и любой из оставшихся семи на III
Союз «И» говорит об умножении.
Ответ: 504 способа составить расписание.
Пример: В чемпионате по футболу участвует 16 команд. Сколькими способами (без учета способностей) могут распределиться золотая, серебряная и бронзовая медали?
Решение: =
=16∙15∙14=3360 способами.
расшифровывается так: число способов из 16 команд выбрать три призовые, считая, что золото может быть у каждой из трех по очереди, т.е. порядок золото-серебро-бронза или бронза-золото-серебро и т.д. важен.
Ответ: 3360 способами.
Пример: Сколько существует, способов составит, пятизначное число из цифр 1,2,3,4,5,6,7,8,9 не повторяя их.
Решение: =
=
=9∙8∙7∙6∙5=15120
Ответ: 15120 способов.
Перестановками называются упорядоченные выборки из n элементов по n , и обозначаются =
=
=
9
В перестановках движутся все элементы множества. Этим перестановки отличаются от всех остальных выборок.
Пример: Сколько существует способов жеребьевки семи команд?
Решение: =5040.
Ответ: 5040 способов.
Пример: Сколько существует способов составить пятизначные числа из пяти цифр, не повторяя их?
Решение:
Ответ: 120 способов.
Сочетаниями называются неупорядоченные выборки из n элементов по m. Обозначаются , вычисляются по формуле
=
(3)
В формуле (3) в знаменателе лишнее число по сравнению с формулой (1), следовательно, ответ в формуле (3) меньше при тех же n и m, что и в формуле (1).
Сочетаний всегда меньше чем размещений при одинаковых n и m.
Пример: Сколько существует способов достать 3 белых шара из ящика с 7 одинаковыми шарами?
Решение: =
=
=
=
=5∙7=35
Ответ: 35 способов.
Пример: Сколько существует способов в группе из 25 человек выбрать трех членов редколлегии?
Решение: =
=2300
Ответ: 2300 способов.
Выбираем сочетания т.к. порядок членов редколлегии не важен.
Пример: В драме А.С. Пушкина «Пиковая дама» Герман вынимает сразу три карты из колоды в 52 листа. Сколько существует таких способов?
Решение: =
=22100
Ответ: 22100 способов.
Пример: В ящике 15 красных, 9 синих и 6 зеленых шаров. Сколько существует способов вынуть 1 зеленый , 2 синих, 3 красных, если взять все эти шары сразу?
Решение: Из условия следует, что вынуто 6 шаров сразу. Попробуем сформулировать вопрос задачи, чтобы разобраться, где сумма, где произведение (умножение «И», сложение «ИЛИ»). Вынуть 1 зеленый и 2 синих, и 3 красных, чтобы было их шесть. Значит умножение трех отдельных эпизодов. Теперь просчитываем каждый.
- Сколько способов из 6 зеленых достать 1? Шесть.
- Сколько способов из 9 синих достать два? =
=
=9∙4=36
- Сколько способов из 15 красных достать три? =
=
=35∙13=455
Итого: 6∙36∙455=98280
Ответ: 98280 способов.
10
Пример: В партии из 10 деталей имеются 4 бракованных. Сколько существует способов выбрать комплект из 3 стандартных и 2 бракованных. Есть союз «И», значит, умножают два эпизода:
- Сколько способов из 6 стандартных взять 3? =
=
=5∙4=20
- Сколько способов из 4 бракованных взять 2? =
=
=6
- Итого способов 20∙6=120
Ответ: 120 способов.
Пример: Юноша забыл две последние цифры номера своей знакомой, помнит только, что они разные. Сколько способов «угадать» номер?
Решение: Цифр используется 10 от 0 до 9. Из них надо составить двузначные числа, причем 31 и 13 это разные числа, а значит и варианты, т.к. порядок расположения чисел важен, используем формулу числа размещений:
=
=
=9∙8=72
Ответ: 72 варианта для угадывания правильного номера.
Пример: На прямой взяли 8 точек. Сколько отрезков различной длины получится, если считать концами эти точки.
Решение: рисуем отрезки
1 2 3 4 5 6 7 8
Рис.2.
Из рисунка 2 видно, что каждые 2 отрезка 1 и 8 или 8 и 1 – это один и тот же отрезок, т.е. порядок расположения элементов не важен, значит надо считать число сочетаний по формуле:
=
=
=4∙7=28
Ответ: 28 отрезков.
Пример: Сколько можно составить трехзначных чисел из 6 цифр (без 0).
Решение: Множества составляются упорядоченные, т.к. 231≠312≠321 и т.д. Используем число размещений =
=
=6∙5∙4=120 чисел.
Ответ: 120 чисел.
Пример: Сколькими способами можно посадить в ряд 6 человек.
Решение: Т.к. движутся и перемещаются все 6 человек, то используем перестановки. Посчитаем их число по формуле =6!=6∙5∙4∙3∙2∙1=720
Ответ: 720 способов.
Пример: В текстовом задании 3 примера. На каждый пример предложено 5 ответов. Каким числом способов можно выбрать ответ на задание.
Решение: Т.к. заданий 3, а ответов 5, то перестановки отпадают. Остается выбрать сочетания, которые являются неупорядоченными множествами или размещениями, где порядок расположения элементов важен. Конечно важен, т.к.каждый неправильный вариант уже надо подсчитывать. Смотрим:
11
1 2 3 4 5
Пример №1 + v v 0
Пример №2 0 +
Пример №3 v + 0
Из схемы видно, что каждый вариант ответа не повторим, т.е. выбираем размещения
=
=
=5∙4∙3=60 способов
Ответ: 60 способов выбора ответа.
12
БИНОМ НЬЮТОНА
- На чем срезался?
- На биноме Ньютона.
Здесь пугает слово бином и то, что он такого известного, и, говоря сегодняшним языком, «крутого» математика как Ньютон, который, как всем известно, ерундой не занимался. От Ньютона никуда не деться, а вот слово бином означает двучлен, т. е (a+b) или (m+n). Когда говорят о биноме Ньютона, то имеют в виду n – ую степень этого двучлена и вот эта то формула обладает рядом интересных и неожиданных свойств. Бином Ньютона имеет вид: =
∙
+
∙
∙
+
∙
∙
+…+
∙
∙
+
∙
, где числа
называются биномиальными коэффициентами.
Глядя на эту формулу, любой скажет, что в жизни еще ничего подобного не видел, ан нет. При n=2 и n=3 получаются известные со школы формулы
+2ab+
=
+3
b+3a
+
Возник вопрос: «Как я так легко подсчитала биноминальные коэффициенты, где 2, где 3?» Оказывается, закон их образования прост и называется треугольником Паскаля. В нем каждое число равно сумме двух ближайших чисел из предыдущей строки.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Рис.3.
Она же совпадает со схемой, где расписаны биномиальные коэффициенты через число сочетаний.
1
.. .. .. .. .. .. .. .. .. .. ..
Рис.4.
Заполните последнюю строку Рис.4 самостоятельно.
У биномиальных коэффициентов есть свойства:
- Равностоящие от концов биномиальные коэффициенты равные между собой(это очевидно из треугольника Паскаля).
- Сумма биноминальных коэффициентов равна
.
13
Доказательство: Пусть в a=b=1, тогда
=
=
∙
∙
+
∙
∙
+
∙
∙
+…
∙
Т.к. единица в любой степени равна единице, остается только сумма биномиальных коэффициентов. Этот факт поначалу вызывает недоумение, т.к. никто не считает, что может быть большим числом. Проверим первые четыре строки треугольника Паскаля
1=
1+1=
1+2+1=4=
1+3+3+1=8=
1+4+6+4+1=16=
. . . . . . . . . . . . . .
Рис.5.
Сопоставьте и запишите самостоятельно треугольники рисунков 3,4 и 5.
14
КОНТРОЛЬНЫЕ ВОПРОСЫ:
- Чему равна сумма коэффициентов в разложении
?
- Чему равна сумма коэффициентов в разложении
?
- Каков самый большой коэффициент в разложении
?
- Чем размещения отличается от сочетаний?
- Перестановки ближе размещениям или сочетаниям?
- Чего всегда больше из одного и того же числа элементов – сочетаний, размещений или перестановок?
- У сочетаний есть свойства:
=1
=n
=1. Справедливы ли аналогичные свойства для размещений? Перестановок?
- Перечислите свойства биномиальных коэффициентов.
15
Ответы к контрольным вопросам:
- 512
- 19683
- 35
16
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ:
- В высшей лиге чемпионата страны по футболу 16 команд. Борьба идет за золотые, серебряные и бронзовые медали. Сколькими способами медали могут быть распределены между командами?
- В классе 10 предметов и 5 различных уроков в день. Сколькими способами эти уроки могут быть распределены на 1 день?
- Сколькими способами можно рассадить 12 человек за длинным столом, на котором поставлено 12 предметов?
- В секции занимается 12 баскетболистов. Сколько тренер может организовать различных стартовых «пятерок»?
- Из группы в 25 человек выбирают 3 для экскурсионной поездки. Сколькими способами это можно сделать?
- Из группы в 20 человек выбирают старосту, физорга и ответственного за выпуск стенных газет. Сколькими способами это можно сделать?
- В предыдущей задаче выбирают еще 4 человека редколлегии. Сколькими способами это можно сделать?
Сколькими способами выбирается вся команда из старосты, физорга, ответственного за выпуск стенгазет и четырех членов редколлегии?
- Коллектив, включающий, 4 женщин и 3 мужчин разыгрывает 4 билета в театр. Сколько существует способов размещения билетов с условием, что обладателями билетов окажутся 2 женщины и 2 мужчины?
- Сколько существует способов выбора 6 номеров из 49 в лотереи «спортлото»
- Для удобства сдачи экзаменов из учебной группы формируются команды по 4 студента на каждый час экзамена. Сколько существует способов подобного размещения, если в группе 24 студента.
- В ящике 5 красных, 7 зеленых и белых шара. Сколько существует способов взять 3 шара одного цвета?
17
ЛИТЕРАТУРА
- М.И. Башмаков. Математика – М.: Издательский центр «Академия», 2011
- В.А. Гусев и др. Математика – М.: Издательский центр «Академия», 2010
19
ОТВЕТЫ К ЗАДАЧАМ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ:
- 3360 способов.
- 30240 способов.
- 479001600 способов.
- 792 пятерок.
- 2300 способов.
- 380 способов.
- 2380 способов, 904400 способов.
- 18 способов.
- 1398816 способов
- 966 способов.
- 105 способов, 34 способа.
18
ОГЛАВЛЕНИЕ
Аннотация……………………………………………………………...……………….……. стр.4
Введение……………………………………………….…………………...……………........ стр.6
Комбинаторика, ее правила и виды………………………………………….….….стр.7-12 Бином Ньютона………………………………………………………………….…..… стр.13 - 14
Контрольные вопросы………...……………………………………………...………… стр.15-16
Задачи для самостоятельного решения……………….……………………………….стр.17 - 18
3
РЕЦЕНЗИЯ
На методическую разработку преподавателя ГБОУ СПО МО ФГТЭУП Морозовой Н.Е.
Тема методической разработки актуальна, ее форма – учебное пособие – наиболее рациональна в условиях дефицита учебной литературы по данной дисциплине. Материал адаптирован к учебному контингенту, т.к. преподаватель имеет опыт ведения этой темы в предыдущие годы.
Пособие может быть использовано для самостоятельной работы студентов, подготовки домашнего задания, подготовки к уроку.
Рекомендуется дополнить пособие теоретическими вопросами по изучаемому материалу, которые будут акцентировать внимание на основных этапах.
Рекомендуется иметь данное учебное пособие в библиотеке техникума.
Рецензент Ивонин В.И., преподаватель ГБОУ СПО МО ФГТЭУП
5
По теме: методические разработки, презентации и конспекты
Учебное пособие по теме "Элементы комбинаторики и теории вероятностей"
Учебное пособие предназначено для студентов техникумов, изучающих теорию вероятностей....
![](/sites/default/files/pictures/2014/12/06/picture-545575-1417872291.jpg)
Самостоятельные работы по теме "Элементы комбинаторики и теории вероятностей"
Самостоятельные работы содержат задания по темам "Правило умножения. Дерево вариантов", "Размещения, перестановки, сочетания", "Случайные события и их вероятности"...
Открытый урок по теме: "Комбинаторика"
Разработка открытого урока по математике по теме: "Комбинаторика" для студентов 1-ого курса специальности 21.02.01 Разработка и эксплуатация нефтяных и газовых месторождений....
Презентация к открытому уроку по теме: "Комбинаторика"
Презентация к открытому уроку по теме: "Комбинаторика" для студентов 1-ого специальности 21.02.01 Разработка и эксплуатация нефтяных и газовых месторождений....
Методические пособия по математике для изучения тем "Комбинаторика", "Проценты", "Решение уравнений"
Пособия предназначены для изучения тем "Комбинаторика", "Проценты", "Решение уравнений"...
![](/sites/default/files/pictures/2020/02/13/picture-1218729-1581598369.jpg)
комбинаторика
Конспект занятия это раз оценкаhttps://www.yaklass.ru/p/algebra/11-klass дальше проходите по этой ссылке, находите раздел комбинаторика, и там всё понятно, всё с решениями! Что сможете, сложные не бер...