.

Комбинаторика

Язык: русский
Формат: реферат
Тип документа: Word Doc
82 3369
Скачать документ

Реферат на тему:

Выполнил ученик 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 вариантов.

Пересекающиеся множества

– область пересечения.

Примеры задач

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.

Таким образом, количество вариантов при сочетании будет меньше
количества размещений.

.

.

Примеры задач

Сколько трехкнопочных комбинаций существует на кодовом замке (все три
кнопки нажимаются одновременно), если на нем всего 10 цифр.

Решение:

вариантов.

У одного человека 7 книг по математике, а у второго – 9. Сколькими
способами они могут обменять друг у друга две книги на две книги.

Решение:

. Значит всего по правилу произведения возможно 21*36=756 вариантов.

При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами
они могут это сделать?

.Размещения и сочетания с повторениями

.

Примеры задач

Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5?

.

В кондитерском магазине продавались 4 сорта пироженных: эклеры,
песочные, наполеоны и слоеные. Сколькими способами можно купить 7
пироженных.

.

Обезьяну посадили за пишущую машинку с 45 клавишами, определить число
попыток, необходимых для того, чтобы она наверняка напечатала первую
строку романа Л.Н. Толстого «Анна Каренина», если строка содержит 52
знака и повторений не будет?

вариантов.

Перестановки с повторениями

, где n-количество всех элементов, n1,n2,…,nr-количество одинаковых
элементов.

Примеры задач

Сколькими способами можно переставить буквы слова «ананас»?

.

Задачи для самостоятельного решения

Сколько перестановок можно сделать из букв слова «Миссисипи».

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

Интернет

HYPERLINK “http://www.mathclub.zala.ru/0921.html”
http:\www.mathclub.zala.ru/0921.html

PAGE

PAGE 10

Если множеств больше, например 5 языков, то также складывается
количество человек знающих английский, немецкий, французский и т.д.,
отнимается количество человек, знающих 2 языка одновременно,
прибавляется по 3, отнимаются по 4 и т.д.

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Ответить

Курсовые, Дипломы, Рефераты на заказ в кратчайшие сроки
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020