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

      
 
 
 
 
 
 
 
 
 

Выполнил  ученик 10 класса «В»

средней школы №53

Глухов  Михаил Александрович 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

г. Набережные Челны 

2002 г. 
Содержание

 

 

Из  истории комбинаторики

    Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов  конечного множества. Некоторые  элементы комбинаторики были известны в Индии еще во 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 человек.

    Также часто для наглядного решения  задачи применяются круги Эйлера. Например:

     Из 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 элементов обозначают P_n.

    P_n=n!

    Действительно при n=m:

    

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

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

    Решение:

1. Найдем количество всех перестановок из этих цифр: P₆=6!=720
2. 0 не может стоять впереди числа, поэтому от этого числа необходимо отнять количество перестановок, при котором 0 стоит впереди. А это P₅=5!=120.

    P₆-P₅=720-120=600

 

    Квартет

    Проказница  Мартышка

    Осел,

    Козел,

    Да  косолапый Мишка

    Затеяли играть квартет

    …

    Стой, братцы стой! – 

    Кричит  Мартышка, - погодите!

    Как музыке идти?

    Ведь  вы не так сидите…

    И так, и этак пересаживались – опять  музыка на лад не идет.

    Тут пуще прежнего пошли у низ раздоры

    И споры,

    Кому  и как сидеть…