Сколькими способами можно расставить 7 бегунов на 7 дорожках?
I. КОМБИНАТОРИКА
Часто приходится иметь дело с задачами выбора элементов из некоторой совокупности и расположения этих элементов в определенном порядке. Поскольку в таких задачах речь идет о тех или иных комбинациях объектов, их называют комбинаторными задачами. Роль таких задач важна не только в математике, но и физике, химии, биологии, технике и экономике. Комбинаторные задачи приходится рассматривать при определении наиболее выгодных коммуникаций внутри города, при организации автоматической телефонной связи, при выявлении связей внутри сложных молекул, генетического кода, математической статистики и т. д.
Трудно переоценить значимость той роли, которую играет обучение методам решения комбинаторных задач в общеобразовательной школе. Освоение методов решения таких задач способствует развитию умственных способностей и математического кругозора ученика. Комбинаторные задачи несут широкие возможности для способов решения таких задач, которые могут служить как формы общих методов решения задач.
Правило суммы
Для ознакомления первого правила комбинаторики-правила суммы мы предлагаем разбор следующей задачи:
Задача 1. На столе лежат 3 черных и 5 красных карандашей. Сколькими способами можно выбрать карандаш любого цвета?
Решение: Выбрать карандаш любого цвета можно 5+3=8 способами.
Правило суммы в комбинаторике:
Если элемент а можно выбрать m способами, а элемент в-n способами, причем любой выбор элемента а отличен от любого выбора элементов в, то выбор «а или в» можно сделать m+n способами.
Задача 2. В классе 10 учащихся занимаются спортом, остальные 6 учащихся посещают танцевальный кружок. 1)Сколько пар учащихся можно выбрать так, чтобы один из пары был спортсменом, другой танцором? 2)Сколько возможностей выбора одного ученика?
Решение: 1)Возможность выбора спортсменов 10, а на каждого из 10 спортсменов выборов танцора 6. Значит, возможность выбора пар танцора и спортсмена 10·6=60.
2) Возможность выбора одного ученика 10+6=16.
Правило произведения
Рассмотрим решение задачи, через которое сформулируем новое правило – правило произведения, неоднократно используемое при изучении последующего материала.
Задача 1. Из города А в город В ведут 3 дороги. А из города В в город С ведут 4 дороги. Сколько путей, проходящих через В, ведут из А в С?
Решение: Можно рассуждать таким образом: для каждой из трех путей из А в В имеется четыре способа выбора дороги из В в С. Всего различных путей из А в С равно произведению 3·4, т.е. 12.
Правило произведения:
Пусть нужно выбрать к элементов. Если первый элемент можно выбрать n1 способами, второй – n2 способами и т. д., то число способов к элементов, равно произведению n1· n2·… nк.
Задача 2. В школьной столовой имеются 2 первых, 5 вторых и 4 третьих блюд. Сколькими способами ученик может выбрать обед, состоящий из первых, вторых и третьих блюд?
Решение: Первое блюдо можно выбрать 2 способами. Для каждого выбора первого блюда существует 5 вторых блюд. Первые два блюда можно выбрать 2·5=10 способами. И, наконец, для каждой 10 этих выборов имеются четыре возможности выбора третьего блюда, т. е. Существует 2·5·4 способов составления обеда из трех блюд. Итак, обед может быть составлен 40 способами.
Перестановки
Простейшими комбинациями, которые можно составить из элементов конечного множества, являются перестановки.
Рассмотрим на примере перестановку без повторений.
Задача: На полке лежат 3 книги. В каком порядке можно расставить эти книги?
Решение: Обозначим их буквами а, в, с. Эти книги можно расставить на полке по – разному:
авс, асв, вас, вса, сав, сва.
Каждое из этих расположений называют перестановкой из трех элементов. При решении этой задачи можно воспользоваться правилом умножения. Выбор первого места на полке три. Для каждого выбора первого места есть две возможности выбора второго места. Из трех книг один выбран для первого места. Остаются 2 остальные книги. Наконец, для каждого выбора первых, вторых мест только один выбор третьего места.
Опредление: Перестановкой из n элементов называется каждое расположение этих элементов в определенном порядке.
Число перестановок из n элементов обозначается символом Рn.
Пусть мы имеем n элементов. На первое место можно поставить любой из них всего п выборов. На второе место любой из оставшихся, т. е. n-1 выбор. На третьем месте любой из оставшихся после первых двух выборов, т. е. n-2 выбора и т. д. В результате получим: Рn = n·(n-1)·(n-2)…2·1.
Если произведение обозначим 1·2·3…(n-1)·n = n!, то число всевозможных перестановок из к элементов вычисляется по формуле:
Рп = n!
Задачи:
Размещения
Задача: Даны четыре различных шара: белый, зеленый, красный и синий. Их нужно поместить в 3 пустые ячейки. Сколько всего будет способов размещения шаров?
Решение: Сначала выпишем все варианты, которые начинаются с белого шара, затем – с зеленого и т. д.
бзк, бкз, бзс, бсз, бкс, бск.
збк, зкб, зсб, збс, зкс, зск.
кбз, кзб, ксб, кбс, кзс, ксз.
сбз, сзб, скб, сбк, скз, сзк.
Всего способов 24. В первую ячейку можно выбрать четырьмя способами. Во вторую – тремя, в третью – двумя. Всего способов 4·3·2=24. Каждую упорядоченную тройку, которую можно составить из четырех элементов, называют размещением из четырех элементов по три.
Определение: Размещением из n элементов по к (к≤n) называется любое множество, состоящее из любых к элементов, взятых в определенном порядке из данных n элементов.
Каждое множество при размещении отличается порядком элементов или их составом.
к
Число размещений из n элементов по к обозначают Аn.
Первый элемент можно выбрать n способами, второй n-1 и последний к-й элемент n-(к-1) способами.
к
Аn = n(n-1)(n-2)… (n-(k-1))
Задачи:
1. Учащиеся одного класса изучают 8 предметов. Сколькими способами можно составить расписание на один день, чтобы в нем было 4 различных предметов.
Решение: Расписание на один день отличаются либо порядком следования предметов, либо самими предметами. Значит, здесь речь идет о размещении
из 8 элементов по 4.
А8= 8·7·6·5=1680 Ответ: 1680 способов.
2. Сколькими способами тренер может распределить 10 спортсменов, на эстафете 4·100 на первом, во втором, третьем и четвертом этапах?
Решение: А10 = 10·9·8·7·=5040 Ответ: 50400 способов.
3. Сколько существует пятизначных телефонных номеров, в каждом из которых все цифры различны и первая цифра различна отнуля? 5
Решение:Число размещений из десяти элементов по пять – А10. Число размещений
начинающихся с цифры ноль – А9. Число телефонных номеров равно:
5 4
А10 – А9 =10·9·8·7·6 – 9·8·7·6 = 27216 Ответ: 27216 номеров.
Сочетания
Задача: На столе лежат 5 разноцветных карандашей. Сколько способов для выбора 3 из них?
Решение: Обозначим карандаши буквами а, в, с, d, е. Можно составить такие сочетания: авс, авd, abe, acd, ace, ade, bcd, bce, bed, cde.
Всего: 10 способов.
Определение: Сочетанием из n элементов по к называется любое множество, составленное из к элементов, выбранных из данных n элементов.
к
Число сочетаний из n элементов по к обозначается Сn.
В сочетаниях не имеет значения порядок элементов, сочетания отличаются составом элементов.
Допустим, имеется множество, содержащее n элементов, и из его элементов составлены
всевозможные сочетания по к элементов. Число таких сочетаний равно Сn. В каждом сочетании можно выполнить Рк перестановок. В результате мы получим все размещения,
к
которые можно составить из n элементов по к. Их число равно Аn.
К к к к
Значит, Аn = Cn·Pк. Отсюда Сn = Аn
кРк
Сn = n(n-1)(n-2)…(n-(k-1))
1·2·3·…·k
Умножим числитель и знаменатель, на (n-к)!
к
Сn= (n-1)(n-2)…(n-(k-1)(n-k)! = n
1·2·3·…·k·(n-k)! k!(n-k)!
Задачи:
ЗАДАЧИ
1. Сколькими способами можно расставить в ряд на одной полке 7 книг?
2. Сколькими способами можно выбрать трех человек на 3 различные должности из восьми кандидатов?
3. Из 11 футболистов нужно делегировать 3 человека. Сколькими способами это можно сделать?
4. Сколькими способами может разместиться семья из трех человек в четырехместном купе, если других пассажиров в купе нет?
5. На станции 7 запасных путей. Сколькими способами можно расставить на них 4 поезда?
6. Сколькими способами можно изготовить трехцветный флаг с горизонтальными полосами, если имеется материал 7 различных цветов?
7. На соревнованиях по легкой атлетике приехала команда из 12 спортсменов. Сколькими способами тренер может определить, кто из них побежит в эстафете 4 по 100 м на первом, втором, третьем и четвертом этапах?
8. Сколькими способами могут быть распределены первая, вторая и третья премии между 15 участниками конкурса?
9. Сколькими способами 6 учеников, сдающих зачет, могут занять места в кабинете, в котором стоят 20 одноместных столов?
10. Сколько четырехзначных чисел, в которых нет одинаковых цифр, можно составить из цифр: а) 1, 3, 5, 7, 9; б) 0, 2, 4, 6, 8.
11. Сколько существует семизначных телефонных номеров, в которых все цифры различные и первая цифра отличная от нуля?
12. В классе 7 человек успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде?
13. Учащимся дали список из 10 книг, которые рекомендуются прочитать во время каникул. Сколькими способами ученик может выбрать из них 6 книг?
14. Из лаборатории в которой работают заведующий и 10 сотрудников, надо отправить 5 человек в командировку. Сколькими способами это можно сделать, если: а) заведующий лабораторией должен ехать в командировку; б) заведующий лабораторией должен остаться?
15. В классе учатся 16 мальчиков и 12 девочек. Для уборки территории требуется выделить 4 мальчиков и трех девочек. Сколькими способами это можно сделать?
16. В библиотеке читателю предложили на выбор из новых поступлений 10 книг и 4 журнала. Сколькими способами он может выбрать из них 3 книги и 2 журнала?
17. Для ремонта школы прибыла бригада, состоящая из 12 человек. Трех из них надо отправить на четвертый этаж, а четырех - на пятый этаж. Сколькими способами это можно сделать?
18. В отделе работают 5 ведущих и 8 старших научных сотрудников. В командировку надо послать двух ведущих и трех старших научных сотрудников. Сколькими способами может быть сделан выбор сотрудников, которых надо послать в командировку?
19. Встретились 11 футболистов и 6 хоккеистов, и каждый стал по одному разу играть с каждым в шашки.
а) сколько встреч было между футболистами?
б) сколько встреч было между хоккеистами?
в) сколько встреч было между футболистами и хоккеистами?
г) сколько встреч было всего?
20. Встретились несколько человек и стали здороваться друг с другом. Известно, что
рукопожатий было от 60 до 70. Сколько человек встретились, если известно, что:
а) каждый здоровался с каждым;
б) только один человек не здоровался ни с кем;
в) только двое не поздоровались между собой.
21. В классе 15 девочек и 13 мальчиков. Нужно выбрать двух дежурных по классу.
Сколькими способами это можно сделать: а) при условии, что пару обязательно
должны составить мальчик и девочка? б) без указанного условия?
22. В оперном театре 10 певцов и 8 певиц, а в опере по замыслу композитора 5 мужских и
3 женских партии. Сколько существует различных певческих составов для спектакля,
если известно, что:
а) все певицы и певцы прекрасно ладят между собой;
б) певцы А и Б ни за что не будут петь вместе;
в) 6 певцов накануне сорвал голос на футболе, и одной певице придется петь мужскую
партию.
23. В шахматном кружке занимаются 16 человек. Сколькими способами тренер может
выбрать из них для предстоящего турнира:
а) команду из 4 человек;
б) команду из четырех человек, указав при этом, кто из членов команды будет играть
на первой, второй, третьей и четвертой досках?
24. Сколькими способами из класса, где учатся 24 учащихся, можно выбрать:
а) двух дежурных;
б) старосту и помощника старосты.
25. Из 20 вопросов к экзамену Вова 12 вопросов выучил, 5 совсем не смотрел, а в
остальных что– то знает, а что- то нет. На экзамене в билете будет три вопроса.
а) сколько существует вариантов билетов?
б) сколько из них тех, в которых Вова знает все вопросы?
в) сколько из них тех в которых есть вопросы всех трех типов?
Литература
1. Вишенкин Н. Я., Ивашев – Мусатов О. С., Шварцбурд С. И.
Алгебра и математический анализ для 11 класса. – М.: Просвещение, 1993.
2. Гусев В. А., Орлов А. И., Розенталь А. П.
Внеклассная работа по математике в 6 – 8 классах. – М.: Просвещение, 1997.
3. Дмитриев И. Г., Попов М. В., Федоров М. П.
Решение олимпиадных задач по математике. – Якутск: ДНСПО МО РС(Я), 2000.
4. Когаловский С.Р.
Роль комбинаторных задач в обучении математики. // Математика в школе. – 2004. - №4.
5. Макарычев Ю. Н., Миндюк Н. Г.
Алгебра: элементы статистики и теории вероятностей. – М.: Просвещение, 2003.
6. Семеновых А.
Комбинаторика. // Математика. – 2004, №15, № 16.
I. КОМБИНАТОРИКА
Часто приходится иметь дело с задачами выбора элементов из некоторой совокупности и расположения этих элементов в определенном порядке. Поскольку в таких задачах речь идет о тех или иных комбинациях объектов, их называют комбинаторными задачами. Роль таких задач важна не только в математике, но и физике, химии, биологии, технике и экономике. Комбинаторные задачи приходится рассматривать при определении наиболее выгодных коммуникаций внутри города, при организации автоматической телефонной связи, при выявлении связей внутри сложных молекул, генетического кода, математической статистики и т. д.
Трудно переоценить значимость той роли, которую играет обучение методам решения комбинаторных задач в общеобразовательной школе. Освоение методов решения таких задач способствует развитию умственных способностей и математического кругозора ученика. Комбинаторные задачи несут широкие возможности для способов решения таких задач, которые могут служить как формы общих методов решения задач.
Правило суммы
Для ознакомления первого правила комбинаторики-правила суммы мы предлагаем разбор следующей задачи:
Задача 1. На столе лежат 3 черных и 5 красных карандашей. Сколькими способами можно выбрать карандаш любого цвета?
Решение: Выбрать карандаш любого цвета можно 5+3=8 способами.
Правило суммы в комбинаторике:
Если элемент а можно выбрать m способами, а элемент в-n способами, причем любой выбор элемента а отличен от любого выбора элементов в, то выбор «а или в» можно сделать m+n способами.
Задача 2. В классе 10 учащихся занимаются спортом, остальные 6 учащихся посещают танцевальный кружок. 1)Сколько пар учащихся можно выбрать так, чтобы один из пары был спортсменом, другой танцором? 2)Сколько возможностей выбора одного ученика?
Решение: 1)Возможность выбора спортсменов 10, а на каждого из 10 спортсменов выборов танцора 6. Значит, возможность выбора пар танцора и спортсмена 10·6=60.
2) Возможность выбора одного ученика 10+6=16.
Правило произведения
Рассмотрим решение задачи, через которое сформулируем новое правило – правило произведения, неоднократно используемое при изучении последующего материала.
Задача 1. Из города А в город В ведут 3 дороги. А из города В в город С ведут 4 дороги. Сколько путей, проходящих через В, ведут из А в С?
Решение: Можно рассуждать таким образом: для каждой из трех путей из А в В имеется четыре способа выбора дороги из В в С. Всего различных путей из А в С равно произведению 3·4, т.е. 12.
Правило произведения:
Пусть нужно выбрать к элементов. Если первый элемент можно выбрать n1 способами, второй – n2 способами и т. д., то число способов к элементов, равно произведению n1· n2·… nк.
Задача 2. В школьной столовой имеются 2 первых, 5 вторых и 4 третьих блюд. Сколькими способами ученик может выбрать обед, состоящий из первых, вторых и третьих блюд?
Решение: Первое блюдо можно выбрать 2 способами. Для каждого выбора первого блюда существует 5 вторых блюд. Первые два блюда можно выбрать 2·5=10 способами. И, наконец, для каждой 10 этих выборов имеются четыре возможности выбора третьего блюда, т. е. Существует 2·5·4 способов составления обеда из трех блюд. Итак, обед может быть составлен 40 способами.
Перестановки
Простейшими комбинациями, которые можно составить из элементов конечного множества, являются перестановки.
Рассмотрим на примере перестановку без повторений.
Задача: На полке лежат 3 книги. В каком порядке можно расставить эти книги?
Решение: Обозначим их буквами а, в, с. Эти книги можно расставить на полке по – разному:
авс, асв, вас, вса, сав, сва.
Каждое из этих расположений называют перестановкой из трех элементов. При решении этой задачи можно воспользоваться правилом умножения. Выбор первого места на полке три. Для каждого выбора первого места есть две возможности выбора второго места. Из трех книг один выбран для первого места. Остаются 2 остальные книги. Наконец, для каждого выбора первых, вторых мест только один выбор третьего места.
Опредление: Перестановкой из n элементов называется каждое расположение этих элементов в определенном порядке.
Число перестановок из n элементов обозначается символом Рn.
Пусть мы имеем n элементов. На первое место можно поставить любой из них всего п выборов. На второе место любой из оставшихся, т. е. n-1 выбор. На третьем месте любой из оставшихся после первых двух выборов, т. е. n-2 выбора и т. д. В результате получим: Рn = n·(n-1)·(n-2)…2·1.
Если произведение обозначим 1·2·3…(n-1)·n = n!, то число всевозможных перестановок из к элементов вычисляется по формуле:
Рп = n!
Задачи:
Сколькими способами можно расставить 7 бегунов на 7 дорожках?
Решение: Р7 =1·2·3·4·5·6·7=5040 Ответ: 5040 способов.