Из истории комбинаторики_________________________________________
|
3
|
Правило суммы___________________________________________________
|
4
|
Примеры
задач____________________________________________________
|
-
|
Правило произведения_____________________________________________
|
4
|
Примеры
задач____________________________________________________
|
-
|
Пересекающиеся множества________________________________________
|
5
|
Примеры
задач____________________________________________________
|
-
|
Круги Эйлера_____________________________________________________
|
-
|
Размещения без повторений________________________________________
|
6
|
Примеры
задач____________________________________________________
|
-
|
Перестановки без повторений_______________________________________
|
7
|
Примеры
задач____________________________________________________
|
-
|
Сочетания без повторений__________________________________________
|
8
|
Примеры задач____________________________________________________
|
-
|
Размещения и сочетания без повторений______________________________
|
9
|
Примеры
задач____________________________________________________
|
-
|
Перестановки с повторениями_______________________________________
|
9
|
Примеры задач____________________________________________________
|
-
|
Задачи для самостоятельного решения________________________________
|
10
|
Список используемой литературы___________________________________
|
11
|
Из истории комбинаторики
Комбинаторика занимается различного вида соединениями,
которые можно образовать из элементов конечного множества. Некоторые элементы
комбинаторики были известны в Индии еще во II в. до н. э. Нидийцы умели
вычислять числа, которые сейчас называют "сочетания". В XII в.
Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что
индийские ученые изучали соединения в связи с применением их в поэтике, науке о
структуре стиха и поэтических произведениях. Например, в связи с подсчетом
возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из n
слогов. Как научная дисциплина, комбинаторика сформировалась в XVII в. В книге
"Теория и практика арифметики" (1656 г.) французский автор А. Также
посвящает сочетаниям и перестановкам целую главу.
Б. Паскаль в "Трактате об арифметическом треугольнике" и в
"Трактате о числовых порядках" (1665 г.) изложил учение о
биномиальных коэффициентах. П. Ферма знал о связях математических квадратов и фигурных
чисел с теорией соединений. Термин "комбинаторика"
стал употребляться после опубликования Лейбницем в 1665 г. работы
"Рассуждение о комбинаторном искусстве", в которой впервые дано научное
обоснование теории сочетаний и перестановок. Изучением размещений впервые занимался
Я. Бернулли во второй части своей книги "Ars conjectandi" (искусство
предугадывания) в 1713 г. Современная символика сочетаний была предложена разными
авторами учебных руководств только в XIX в.
Все разнообразие комбинаторных формул может
быть выведено из двух основных утверждений, касающихся конечных множеств –
правило суммы и правило произведения.
Правило суммы
Если конечные множества не пересекаются, то число
элементов X U Y {или} равно сумме числа элементов множества X и числа элементов
множества Y.
То есть,
если на первой полке стоит X книг, а на второй Y, то выбрать книгу из первой
или второй полки, можно X+Y способами.
Примеры задач
Ученик должен выполнить практическую работу по
математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии.
Сколькими способами он может выбрать одну тему для практической работы?
Решение: X=17, Y=13
По правилу суммы X U Y=17+13=30 тем.
Имеется 5 билетов денежно-вещевой лотереи, 6 билетов
спортлото и 10 билетов автомотолотереи. Сколькими способами можно выбрать один
билет из спортлото или автомотолотереи?
Решение: Так как денежно-вещевая лотерея в выборе не
участвует, то всего 6+10=16 вариантов.
Правило произведения
Если элемент X можно выбрать k способами, а элемент
Y-m способами то пару (X,Y) можно выбрать k*m способами.
То есть, если на первой полке стоит 5 книг, а на второй
10, то выбрать одну книгу с первой полки и одну со второй можно 5*10=50 способами.
Примеры задач
Переплетчик должен переплести 12 различных книг в красный,
зеленый и коричневые переплеты. Сколькими способами он может это сделать?
Решение: Имеется 12 книг и 3 цвета, значит по правилу
произведения возможно 12*3=36 вариантов переплета.
Сколько существует пятизначных чисел, которые одинаково
читаются слева направо и справа налево?
Решение: В таких числах последняя цифра будет такая же,
как и первая, а предпоследняя - как и вторая. Третья цифра будет любой. Это
можно представить в виде XYZYX, где Y и Z -любые цифры, а X - не ноль.
Значит по правилу произведения количество цифр одинаково читающихся как слева
направо, так и справа налево равно 9*10*10=900 вариантов.
Пересекающиеся множества
Но бывает, что множества X и Y пересекаются,
тогда пользуются формулой, где X и Y - множества, а - область пересечения.
Примеры задач
20 человек знают английский и 10 - немецкий, из них 5 знают и английский, и немецкий. Сколько Человек всего?
Ответ:
10+20-5=25 человек.
Также часто для наглядного решения задачи применяются круги
Эйлера. Например:
Решение: Выразим условие
этой задачи графически. Обозначим кругом тех, кто знает английский, другим
кругом - тех, кто знает французский, и третьим кругом - тех, кто знают немецкий.
Всеми тремя языками владеют три туриста, значит, в общей
части кругов вписываем число 3. Английским и французским языком владеют 10
человек, а 3 из них владеют еще и немецким. Следовательно, только английским и
французским владеют 10-3=7 человек.
Аналогично получаем, что только английским
и немецким владеют 8-3=5 человек, а немецким и французским 5-3=2 туриста.
Вносим эти данные в соответствующие части.
Определим теперь, сколько человек владеют только одним
из перечисленных языков. Немецкий знают 30 человек, но 5+3+2=10 из них владеют
и другими языками, следовательно, только немецкий знают 20 человек. Аналогично
получаем, что одним английским владеют 13 человек, а одним французским - 30 человек.
По условию задачи всего 100 туристов. 20+13+30+5+7+2+3=80
туристов знают хотя бы один язык, следовательно, 20 человек не владеют ни одним
из данных языков.
Размещения
без повторений.
Сколько
можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были
различны?
Это пример задачи на размещение без
повторений. Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые
цифры стоят в разном порядке считаются разными.
Если X-множество, состоящие из n
элементов, m≤n, то размещением без повторений из n элементов множества X
по m называется упорядоченное множество X, содержащее m элементов называется
упорядоченное множество X, содержащее m элементов.
Количество всех размещений из n
элементов по m обозначают
n! - n-факториал (factorial анг.
сомножитель) произведение чисел натурального ряда от 1 до какого либо числа n
n!=1*2*3*...*n 0!=1
Значит, ответ на вышепоставленную
задачу будет
Задача
Сколькими способами 4 юноши могут
пригласить четырех из шести девушек на танец?
Решение: два юноши
не могут одновременно пригласить одну и ту же девушку. И варианты, при которых
одни и те же девушки танцуют с разными юношами считаются, разными, поэтому:
Возможно 360 вариантов.
Перестановки без повторений
В случае
n=m (см. размещения без повторений) из n элементов по m называется перестановкой
множества x.
Количество всех
перестановок из n элементов обозначают Pn.
Pn=n!
Действительно при n=m:
Примеры задач
Сколько
различных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, если
цифры в числе не повторяются?
Решение:
1)
Найдем
количество всех перестановок из этих цифр: P6=6!=720
2)
0 не может
стоять впереди числа, поэтому от этого числа необходимо отнять количество
перестановок, при котором 0 стоит впереди. А это P5=5!=120.
P6-P5=720-120=600
Квартет
Проказница
Мартышка
Осел,
Козел,
Да
косолапый Мишка
Затеяли
играть квартет
…
Стой,
братцы стой! –
Кричит
Мартышка, - погодите!
Как
музыке идти?
Ведь вы
не так сидите…
И
так, и этак пересаживались – опять музыка на лад не идет.
Тут пуще
прежнего пошли у низ раздоры
И споры,
Кому и
как сидеть…
Вероятно,
крыловские музыканты так и не перепробовали всех возможных мест. Однако способов
не так уж и много. Сколько?
Здесь идет
перестановка из четырех, значит, возможно
P4=4!=24
варианта перестановок.
Сочетания
без повторений
Сочетанием
без повторений называется такое размещение, при котором порядок следования элементов
не имеет значения.
Всякое подмножество X состоящее из m элементов, называется сочетанием
из n элементов по m.
Таким
образом, количество вариантов при сочетании будет меньше количества размещений.
Число
сочетаний из n элементов по m обозначается .
.
Примеры задач
Сколько
трехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаются
одновременно), если на нем всего 10 цифр.
Решение:
Так
как кнопки нажимаются одновременно, то выбор этих трех кнопок – сочетание.
Отсюда возможно вариантов.
У
одного человека 7 книг по математике, а у второго – 9. Сколькими способами они
могут обменять друг у друга две книги на две книги.
Решение:
Так
как надо порядок следования книг не имеет значения, то выбор 2ух книг
- сочетание. Первый человек может выбрать 2 книги способами. Второй человек может выбрать 2
книги . Значит
всего по правилу произведения возможно 21*36=756 вариантов.
При
игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут
это сделать?
Первый
игрок делает выбор из 28 костей. Второй из 28-7=21 костей, третий 14, а четвертый
игрок забирает оставшиеся кости. Следовательно, возможно .
Размещения и сочетания с повторениями
Часто в задачах по комбинаторике встречаются множества, в которых
какие-либо компоненты повторяются. Например: в задачах на числа – цифры. Для
таких задач при размещениях используется формула , а для сочетаний .
Примеры задач
Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5?
Решение. Так как порядок цифр в числе
существенен, цифры могут повторяться, то это будут размещения с повторениями из
пяти элементов по три, а их число равно .
В кондитерском магазине продавались 4 сорта пироженных: эклеры, песочные,
наполеоны и слоеные. Сколькими способами можно купить 7 пироженных.
Обезьяну посадили за пишущую машинку с 45 клавишами, определить число
попыток, необходимых для того, чтобы она наверняка напечатала первую строку
романа Л.Н. Толстого «Анна Каренина», если строка содержит 52 знака и повторений
не будет?
Решение: порядок букв имеет значение. Буквы
могут повторяться. Значит, всего есть вариантов.
Перестановки с
повторениями
, где n-количество всех элементов,
n1,n2,…,nr-количество одинаковых элементов.
Примеры задач
Сколькими способами можно переставить буквы слова «ананас»?
Решение: всего букв 6. Из них одинаковы n1«а»=3,
n2«н»=2, n3«с»=1. Следовательно, число различных перестановок
равно .
Задачи для самостоятельного решения
Сколько перестановок можно сделать из букв
слова «Миссисипи».
Ответ: 2520
Имеется пять различных стульев и семь
рулонов обивочной ткани различных цветов. Сколькими способами можно осуществить
обивку стульев.
Ответ: 16807
На
памятные сувениры в «Поле Чудес» спонсоры предлагают кофеварки, утюги, телефонные
аппараты, духи. Сколькими способами 9 участников игры могут получить эти сувениры?
Сколькими способами могут быть выбраны 9 предметов для участников игры?
Ответ: 49, 220
Сколькими
способами можно расставить на шахматной доске 8 ладей так, чтобы на одна из них
не могла бить другую?
Ответ: 40320
Сколько
может быть случая выбора 2 карандашей и 3 ручек из пяти различных карандашей и
шести различных ручек?
Ответ:200
Сколько
способов раздачи карт на 4 человека существует в игре «Верю ‑ не верю»
(карты раздаются полностью, 36 карт).
Ответ: .
В
течении 30 дней сентября было 12 дождливых дней, 8 ветреных, 4 холодных, 5 дождливых
и ветреных, 3 дождливых и холодных, а один день был и дождливым, и ветреным, и
холодным. В течение скольких дней в сентябре стояла хорошая погода.
Ответ: 15
На
ферме есть 20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и
одну свинью? Если такой выбор уже сделан, сколькими способами можно сделать его
еще раз?
Ответ: 480, 437
Сколькими
способами можно выбрать гласную и согласную буквы из слова «здание»?
Ответ: 9
Сколько
существует четных пятизначных чисел, начинающихся нечетной цифрой?
Ответ: 25000
В
книжный магазин поступили романы Ф. Купера «Прерия», «Зверобой», «Шпион»,
«Пионеры», «Следопыт» по одинаковой цене. Сколькими способами библиотека может
закупить 17 книг на выбранный чек?
Ответ:: 2985
Список используемой литературы
Савина
Л.Н., Попырев А.В. «КОМБИНАТОРИКА» издательство Елабужский государственный
педагогический институт 1999г
Халамайзер
А. Я. «Математика? – Забавно!» издание автора 1989г
Интернет
http:\www.mathclub.zala.ru/0921.html