Реферат: Комбинаторика
/>Реферат на тему:
/>
Выполнилученик 10 класса «В»
среднейшколы №53
ГлуховМихаил Александрович
г. Набережные Челны
2002 г.
Содержание
Из истории комбинаторики
Комбинаторика занимается различного вида соединениями,которые можно образовать из элементов конечного множества. Некоторые элементыкомбинаторики были известны в Индии еще во II в. до н. э. Нидийцы умеливычислять числа, которые сейчас называют «сочетания». В XII в.Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, чтоиндийские ученые изучали соединения в связи с применением их в поэтике, науке оструктуре стиха и поэтических произведениях. Например, в связи с подсчетомвозможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из nслогов. Как научная дисциплина, комбинаторика сформировалась в XVII в. В книге«Теория и практика арифметики» (1656 г.) французский автор А. Такжепосвящает сочетаниям и перестановкам целую главу.
Б. Паскаль в «Трактате об арифметическом треугольнике» и в«Трактате о числовых порядках» (1665 г.) изложил учение обиномиальных коэффициентах. П. Ферма знал о связях математических квадратов и фигурныхчисел с теорией соединений. Термин "комбинаторика"стал употребляться после опубликования Лейбницем в 1665 г. работы«Рассуждение о комбинаторном искусстве», в которой впервые данонаучное обоснование теории сочетаний и перестановок. Изучением размещенийвпервые занимался Я. Бернулли во второй части своей книги «Arsconjectandi» (искусство предугадывания) в 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 человек.
Также часто для наглядного решения задачи применяются круги Эйлера.Например:
/>Из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, еслицифры в числе не повторяются?
Решение:
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