Комбинаторика
учебно-методическое пособие по теме

Министерство образования и науки РФ.

ГБОУ СПОМО Фрязинский государственный техникум электроники, управления и права.

КОМБИНАТОРИКА

Учебное пособие

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 красных

1. Сколько существует способов извлечь цветной шар?

Ответ:5+7=12, т.к. цветной – это зеленый или красный.

С помощью правил сложения и умножения можно составлять цепочки решения для еще более сложных вопросов.

1.  Сколько существует способов извлечь 3 шара разного цвета?

Ответ: 8∙5∙7=280

3. Сколько существует способов извлечь два шара разного цвета?

Ответ: 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+

=+3b+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 самостоятельно.

У биномиальных коэффициентов есть свойства:

1. Равностоящие от концов биномиальные коэффициенты равные между собой(это очевидно из треугольника Паскаля).
2. Сумма биноминальных коэффициентов равна .

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. Чему равна сумма коэффициентов в разложении ?
2. Чему равна сумма коэффициентов в разложении ?
3. Каков самый большой коэффициент в разложении ?
4. Чем размещения отличается от сочетаний?
5. Перестановки ближе размещениям или сочетаниям?
6. Чего всегда больше из одного и того же числа элементов – сочетаний, размещений или перестановок?
7. У сочетаний есть свойства: =1    =n   =1. Справедливы ли аналогичные свойства для размещений? Перестановок?
8. Перечислите свойства биномиальных коэффициентов.

15

Ответы к контрольным вопросам:

1. 512
2. 19683
3. 35

16

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ:

1. В высшей лиге чемпионата страны по футболу 16 команд. Борьба идет за золотые, серебряные и бронзовые медали. Сколькими способами медали могут быть распределены между командами?
2. В классе 10 предметов и 5 различных уроков в день. Сколькими способами эти уроки могут быть распределены на 1 день?
3. Сколькими способами можно рассадить 12 человек за длинным столом, на котором поставлено 12 предметов?
4. В секции занимается 12 баскетболистов. Сколько тренер может организовать различных стартовых  «пятерок»?
5. Из группы в 25 человек выбирают 3 для экскурсионной поездки. Сколькими способами это можно сделать?
6. Из группы в 20 человек выбирают старосту, физорга и ответственного за выпуск стенных газет. Сколькими способами это можно сделать?
7. В предыдущей задаче выбирают еще 4 человека редколлегии. Сколькими способами это можно сделать?

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

1. Коллектив, включающий, 4 женщин и 3 мужчин разыгрывает 4 билета в театр. Сколько существует способов размещения билетов с условием, что обладателями билетов окажутся 2 женщины и 2 мужчины?
2. Сколько существует способов выбора 6 номеров из 49 в лотереи «спортлото»
3. Для удобства сдачи экзаменов из учебной группы формируются команды по 4 студента на каждый час экзамена. Сколько существует способов подобного размещения, если в группе 24 студента.
4. В ящике 5 красных, 7 зеленых и белых шара. Сколько существует способов взять 3 шара одного цвета?

17

ЛИТЕРАТУРА

1. М.И. Башмаков. Математика – М.: Издательский центр «Академия», 2011
2. В.А. Гусев и др. Математика – М.: Издательский центр «Академия», 2010

19

ОТВЕТЫ К ЗАДАЧАМ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ:

1. 3360 способов.
2. 30240 способов.
3. 479001600 способов.
4. 792 пятерок.
5. 2300 способов.
6. 380 способов.
7. 2380 способов, 904400 способов.
8. 18 способов.
9. 1398816 способов
10. 966 способов.
11. 105 способов, 34 способа.

18

ОГЛАВЛЕНИЕ

Аннотация……………………………………………………………...……………….……. стр.4

Введение……………………………………………….…………………...……………........ стр.6

Комбинаторика, ее правила и виды………………………………………….….….стр.7-12 Бином Ньютона………………………………………………………………….…..… стр.13 - 14

Контрольные вопросы………...……………………………………………...………… стр.15-16

Задачи для самостоятельного решения……………….……………………………….стр.17 - 18

3

РЕЦЕНЗИЯ

На методическую разработку преподавателя ГБОУ СПО МО ФГТЭУП Морозовой Н.Е.

Тема методической разработки актуальна, ее форма – учебное пособие – наиболее рациональна в условиях дефицита учебной литературы по данной дисциплине. Материал адаптирован к учебному контингенту, т.к. преподаватель имеет опыт ведения этой темы в предыдущие годы.

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

Рекомендуется дополнить пособие теоретическими вопросами по изучаемому материалу, которые будут акцентировать внимание на основных этапах.

Рекомендуется иметь данное учебное пособие в библиотеке техникума.

Рецензент                                                Ивонин В.И., преподаватель ГБОУ СПО МО ФГТЭУП

5