Комбинаторика
еферат
на тему:

Выполнил ученик 10 класса «В»
средней школы №53
Глухов Михаил Александрович
г. Набережные Челны
2002 г.
Содержание
-
Из истории комбинаторики_________________________________________
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 - множества,
а
- область
пересечения.
П
Если множеств больше, например 5 языков, то также складывается количество человек знающих английский, немецкий, французский и т.д., отнимается количество человек, знающих 2 языка одновременно, прибавляется по 3, отнимаются по 4 и т.д.
римеры задач
20 человек знают английский и 10 - немецкий, из них 5 знают и английский, и немецкий. Сколько Человек всего?
Ответ: 10+20-5=25 человек.
Также часто для наглядного решения задачи применяются круги Эйлера. Например:
И
з
100 туристов,
отправляющихся
в заграничное
путешествие,
немецким языком
владеют 30 человек,
английским
- 28, французским
- 42. Английским
и немецким
одновременно
владеют 8 человек,
английским
и французским
- 10, немецким и
французским
- 5, всеми тремя
языками - 3. Сколько
туристов не
владеют ни
одним языком?
Решение: Выразим условие этой задачи графически. Обозначим кругом тех, кто знает английский, другим кругом - тех, кто знает французский, и третьим кругом - тех, кто знают немецкий.
В
семи
тремя языками
владеют три
туриста, значит,
в общей части
кругов вписываем
число 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, если цифры в числе не повторяются?
Решение:
Найдем количество всех перестановок из этих цифр: P6=6!=720
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/0921.html