Теория комбинаторики. Историческая справка

• Название: Историческая справка
• Анкор: Теория комбинаторики.doc
• Дата: 02.05.2018
• Размер: 416 Kb.
• Имя файла: Теория комбинаторики.doc
• Тип: Документы; #18792
• Категория: Информатика. Вычислительная техника

Историческая справка

Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. Нидийцы умели вычислять числа, которые сейчас называют "сочетания". В XII в. Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские ученые изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Например, в связи с подсчетом возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из n слогов. Как научная дисциплина, комбинаторика сформировалась в XVII в. В книге "Теория и практика арифметики" (1656 г.) французский автор А. Также посвящает сочетаниям и перестановкам целую главу.

Б. Паскаль в "Трактате об арифметическом треугольнике" и в "Трактате о числовых порядках" (1665 г.) изложил учение о биномиальных коэффициентах.
П. Ферма знал о связях математических квадратов и фигурных чисел с теорией соединений. Термин "комбинаторика" стал употребляться после опубликования Лейбницем в 1665 г. работы "Рассуждение о комбинаторном искусстве", в которой впервые дано научное обоснование теории сочетаний и перестановок. Изучением размещений впервые занимался Я. Бернулли во второй части своей книги "Ars conjectandi" (искусство предугадывания) в
1713 г. Современная символика сочетаний была предложена разными авторами учебных руководств только в XIX в.Разрозненные комбинаторные задачи человечество решало с незапамятных времён. К концу XVI века накопились знания, относящиеся к:

1. 
   свойствам фигурных чисел,
   
2. 
   построению магических (и иных числовых) квадратов,
   
3. 
   свойствам биномиальных коэффициентов.
   

Термин "комбинаторика" был введён в математический обиход знаменитым Лейбницем. Готфрид Вильгельм Лейбниц (1.07.1646 - 14.11.1716) - всемирно известный немецкий учёный, занимался философией, математикой, физикой, организовал Берлинскую академию наук и стал её первым президентом. В математике он вместе с И. Ньютоном разделяет честь создателя дифференциального и интегрального исчислений. В 1666 году Лейбниц опубликовал "Рассуждения о комбинаторном искусстве". В своём сочинении Лейбниц, вводя специальные символы, термины для подмножеств и операций над ними находит все k -сочетания из n элементов выводит свойства сочетаний: , , ,

- строит таблицы сочетаний до n = k = 12, после чего рассуждает о приложениях комбинаторики к логике, арифметике, к проблемам стихосложения и др.

В течение всей своей жизни Лейбниц многократно возвращался к идеям комбинаторного искусства. Комбинаторику он понимал весьма широко, именно, как составляющую любого исследования, любого творческого акта, предполагающего сначала анализ (расчленение целого на части), а затем синтез (соединение частей в целое). Мечтой Лейбница, оставшейся, увы, неосуществлённой, оставалось построение общей комбинаторной теории.Комбинаторике Лейбниц предрекал блестящее будущее, широкое применение.

В XVIII веке к решению комбинаторных задач обращались выдающиеся математики. Так, Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о циклических расстановках, о построении магических и латинских квадратов.

В 1713 году было опубликовано сочинение Я. Бернулли "Искусство предположений", в котором с достаточной полнотой были изложены известные к тому времени комбинаторные факты. "Искусство предположений" появилось после смерти автора и не было автором завершено. Сочинение состояло из 4 частей, комбинаторике была посвящена вторая часть, в которой содержатся формулы:

• 
  для числа перестановок из n элементов,
  
• 
  для числа сочетаний (называемого Я. Бернулли классовым числом) без повторений и с повторениямими,
  
• 
  для числа размещений с повторениями и без повторений.
  

Для вывода формул автор использовал наиболее простые и наглядные методы, сопровождая их многочисленными таблицами и примерами. Сочинение Я. Бернулли превзошло работы его предшественников и современников систематичностью, простотой методов, строгостью изложения и в течение XVIII века пользовалось известностью не только как серьёзного научного трактата, но и как учебно-справочного издания. В работах Я. Бернулли и Лейбница тщательно изучены свойства сочетаний, размещений, перестановок. Перечисленные комбинаторные объекты относятся к основным комбинаторным конфигурациям . В математике в XIX веке появился сначала термин "геометрическая конфигурация" в лекциях по проективной геометрии профессора университета в Страсбурге К.Т. Рейе (1882).

В 1896 году американский математик Элиаким Гастингс Мур (1862-1932) ввёл термин тактическая конфигурация в статье "Tactical memoranda", понимая под этим термином систему n множеств, содержащих, соответственно, a1, a2, … , anэлементов. Тактическую конфигурацию Мур задаёт квадратной матрицей порядка n, в которой элемент akk, стоящий на главной диагонали, равен числу ak (числу элементов в k-ом множестве); элемент aij (i j) равен числу элементов i-ого множества, инцидентных j -ому множеству. К тактическим конфигурациям Мур относит сочетания, размещения, системы решений задачи Киркмана о 15 школьницах, подгруппы некоторых групп. Он демонстрирует широкий спектр задач из геометрии, теории групп, которые приводят к тактическим разложениям или используют тактические

разложения. Мур обогатил список известных комбинаторных конфигураций построением новых, обобщающих системы троек Штейнера, и системы троек Киркмана. Мур построил системы
S[k, l, m], m k l ( m, k, l - натуральные числа), содержащие такие k -сочетания (блоки) из m элементов, что каждое l -сочетание входит точно в одно k -сочетание. Число k -сочетаний в системе S[k, l, m] равно . Мур в своей статье ссылается на Артура Кэли, который подчёркивал высокую значимость тактических задач в алгебре.

Термин "тактика" ввёл в математику английский математик Джеймс Джозеф Сильвестр (1814-1897) в 1861 году. Сильвестр определял тактику как раздел математики, изучающий расположение элементов друг относительно друга. В сфере этого раздела находится, по мнению Сильвестра, теория групп, комбинаторный анализ и теория чисел. Мысли Сильвестра о тактике разделял его друг Артур Кэли.

Комбинаторика, пройдя многовековой путь развития, обретя собственные методы исследования, с одной стороны, широко используется при решении задач алгебры, геометрии, анализа, с другой стороны, сама использует геометрические, аналитические и алгебраические методы исследования. В конце XVIII века учёные, принадлежащие комбинаторной школе Гинденбурга, попытались построить общую комбинаторную теорию, используя бесконечные ряды. Исследователи этой школы изучили большое количество преобразований рядов: умножение, деление, возведение в степень, извлечение корней, обращение рядов, разложение трансцендентных функций. Использование производящих функций в комбинаторике можно отнести к (уже) классическим традициям.

В XX веке комбинаторика подверглась мощному процессу алгебраизации благодаря работам Дж.-К. Рота (1964), а затем Р. Стенли. Изучение ими частично упорядоченных множеств, свойств функции Мёбиуса, абстрактных свойств линейной зависимости, выявление их роли при решении комбинаторных задач способствовали обогащению комбинаторных методов исследования и дальнейшей интеграции комбинаторики в современную математику.
Начало формы

Конец формы

Конец формы

1. Понятие множества. Подмножества

Под множеством понимают объединение в одно целое объектов, связанных между собой неким свойством. Термин "множество" в математике не всегда обозначает большое количество предметов, оно может состоять и из одного элемента и вообще не содержать элементов, тогда его называют пустым и обозначают .
Множество B называют подмножеством множества А, если любой элемент множества В является элементом множества А. Обозначается В  А.



Свойства включения множеств:

1. 
   Пустое множество является подмножеством любого множества:   А.
   
2. 
   Любое множество является подмножеством самого себя, т. е. для любого множества А справедливо включение А  А.
   
3. 
   Если А - подмножество множества В, а В - подмножество множества С, то А - подмножество множества С.
   

Универсальное множество - это самое большее множество, содержащее в себе все множества, рассматриваемые в данной задаче.
На диаграмме Эйлера - Венна универсальное множество обозначают в виде прямоугольника и буквы U:

2. Операции над множествами

Равными называются множества, состоящие из одних и тех же элементов.

Два множества равны, если каждое из них является подмножеством другого (A = B  (A  B и В  А)).

Множества не равны, если хотя бы в одном множестве существует хотя бы один элемент, не принадлежащий другому множеству.

Объединением множеств А и В называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из множеств А или В. Обозначается AB.



Отметим разницу в употреблении союза "или" в математике и в обыденной речи. В обыденной речи союз "или" употребляется чаще в разделительном смысле - "либо… либо", тогда как в математике - в объединительном.

Свойства объединения множеств:
1.
2.
3.
4.
5.
6.
Пересечением множеств А и В называется множество, состоящее из всех элементов, принадлежащих обоим множествам А и В. Обозначается А  В.



Свойства пересечения множеств:
1.
2.
3.
4.
5.
6.
Разностью множеств А и В называется множество элементов, принадлежащих множеству А, которые не принадлежат множеству В. Обозначается А \ В.



Свойства разности множеств:
1. Если то А \ В = А.
2. Если А  В, то А \ В = .
3. А \ В = А \ (АВ).
Разность между универсальным множеством U и множеством А называется дополнением множества А. Обозначается = U \ A.

Свойства разности и дополнения:

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

Комбинаторика является древнейшей и, возможно, ключевой ветвью математики. Всякому анализу предшествует комбинаторное рассмотрение, всякая серьёзная теория имеет комбинаторный аналог.

Комбинаторика располагает столь многообразными методами, решает столь разнообразные задачи, что трудно чётко обозначить её границы. Условно в комбинаторной теории можно выделить следующие три большие части (см. схему):

• 
  Теорию конфигураций, включающую блок - схемы, группы подстановок, теорию кодирования.
  
• 
  Теорию перечисления, содержащую производящие функции, теоремы обращения и исчисление конечных разностей.
  
• 
  Теорию порядка, включающую конечные упорядоченные множества и решётки, матрицы и теоремы существования, подобные теоремам Холла и Рамсея.
  

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

4.Теория конфигураций и теория перечисления

Теория конфигураций является традиционным и наиболее разработанным разделом комбинаторики. Теория конфигураций рассматривает задачи выбора и расположения элементов некоторого, обычно конечного, множества, в соответствии с заданными правилами. Перечислительная комбинаторика основным методом исследования провозгласила метод производящих функций, используя который было доказано громадное число комбинаторных тождеств.

5. Основные формулы комбинаторики

На практике часто приходится выбирать из некоторого множества объектов подмножества элементов, обладающих теми или иными свойствами, располагать элементы одного или нескольких множеств в определенном порядке и т. д. Поскольку в таких задачах речь идет о тех или иных комбинациях объектов, их называют "комбинаторные задачи".

Комбинаторика занимается различного рода соединениями, которые можно образовать из элементов некоторого конечного множества. Термин "комбинаторика" происходит от латинского combina - сочетать, соединять.

Комбинаторика - область математики, в которой рассматриваются задачи о тех или иных комбинациях объектов.

Элементарными комбинаторными конфигурациями являются сочетания, размещения, перестановки. Для подсчёта числа этих конфигураций используются правила суммы и произведения.

Правило суммы:

• 
  Если элемент A можно выбрать m способами, а элемент B можно выбрать k способами, то выбор элемента A или B можно осуществить m + k способами.
  
• 
  Правило суммы можно перефразировать на теоретико-множественном языке. Обозначим через | A | число элементов множества A, через A B - объединение множеств A и B, через AxB - декартово произведение множеств A и B. Тогда для непересекающихся множеств A и B выполняется равенство:
  

| A B | = | A | + | B |.

• 
  Если имеется n попарно непересекающихся множеств A1, A2, …, An, содержащих m₁, m₂, …, m_n элементов соответственно. Число способов, которыми можно выбрать один элемент из всех этих множеств, равно
  

m₁+ m₂ +…+ m_n.

Обобщением правила суммы является правило произведения.

Правило произведения:

• 
  Если элемент A можно выбрать m способами, а после каждого выбора элемента A элемент B можно выбрать k способами, тогда, упорядоченную пару элементов (A, B) можно выбрать m*k способами. На теоретико-множественном языке правило произведения формулируется так: | Aх B | = | A | | B |.
  
• 
  Правило произведения можно распространить на выбор последовательности (x₁, x₂, …, x_n) произвольной конечной длины n. Пусть имеется n множеств A1, A2, …, An содержащих m₁, m₂, …, m_n элементов соответственно. Число способов, которыми можно выбрать по одному элементу из каждого множества, т. е. построить кортеж (а₁, а₂, ..., а_n), где а_i принадлежит Аi (i = 1, 2, …, n), равно
  

m₁ · m₂ · … · m_n .

• 
  Кортеж - конечная последовательность (допускающая повторения) элементов какого-нибудь множества.
  

Перестановки без повторений.

Назовём множество, содержащее n элементов, n -множеством. Последовательность (x₁, x₂, …, x_n) длины n без повторяющихся элементов из элементов данного n-множества назовёмP_nперестановкой без повторений элементов(от "permutation"- перестановка).. Используя правило произведения, вычислим число P_n. . Элемент x1 можно установить n способами. После каждого выбора x1 элемент x2 можно установить в новой выборке (n - 1) способами. После каждого выбора элементов x1 и x2 элемент x3 можно установить (n - 2) способами, и т.д. После каждого выбора элементов x₁ , x₂, …, x_k-1 элемент x_k можно установить (n - (k - 1)) = (n - k + 1) способами. Тогда, по правилу произведения, последовательность (x₁; x₂; , …, x_n) можно выбрать числом способов, равным n(n - 1)(n - 2) … (n - k + 1)…2*1. Число P_n перестановок из n элементов без повторяющихся элементов

P_n = n! (1)

Размещения без повторений.

Назовём множество, содержащее n элементов, n-множеством. Последовательность (x₁, x₂, …, x_k ) длины k без повторяющихся элементов из элементов данного n-множества назовём k-размещением без повторений элементов. Обозначим символом число размещений из n по k элементов (от фран. "arrangement" - размещение). Используя правило произведения, вычислим число . Пусть произвольное размещение длины k имеет вид (x₁, x₂, …, x_k ). Элемент x1 можно выбрать n способами. После каждого выбора x1 элемент x2 можно выбрать (n - 1) способами. После каждого выбора элементов x1 и x2 элемент x3 можно выбрать (n - 2) способами, и т.д. После каждого выбора элементов x1 , x2, …, xk-1 элемент xk можно выбрать (n - (k - 1)) = (n - k + 1) способами. Тогда, по правилу произведения, последовательность (x₁, x₂, …, x_k) можно выбрать числом способов, равным n(n - 1)(n - 2) … (n - k + 1) . Произведение умножим и разделим на (n - k)!, получим:

.                                     (2)

Если в форуме (2) k = n, то есть число P_n перестановок из n элементов P_n = n!.

Сочетания без повторений .

k-подмножество из неповторяющихся элементов данного n-множества называется k-сочетанием без повторений. Обозначим через число k-сочетаний из данных n элементов. Формулу для числа сочетаний получим, рассуждая следующим образом. Если каждое сочетание упорядочить всеми возможными способами, то получим все k-последовательностей из n элементов, без повторений, то есть все k-размещения.
Иными словами, Откуда , полагая, что n и k - целые положительные числа и 0!=1.:       (3)

Основные свойства сочетаний.

1. 
   Условились, что
   
2. 
   
   
3. 
   
   
4. 
   
   
5. 
   
   

Сочетания и размещения широко используются при вычислении классической вероятности случайных событий.

Пример. В корзине находятся 20 орехов, из которых 7 грецких. Наудачу выбирают 5 орехов. Найти вероятность того, что среди выбранных орехов содержатся 2 грецких.

Решение. Число исходов опыта . Случайное событие A - среди пяти выбранных орехов содержатся 2 грецких ореха. Число исходов, благоприятствующих событию A, равно: . Искомая вероятность .

Задачи.

1. 
   Найти вероятность того, что случайно выбранное 5-значное (десятичное) число не содержит цифры 5.
   
2. 
   Предприятие располагает 5 вакансиями для мужчин, 5 вакансиями для женщин и 4 вакансиями для работников любого пола. В отдел кадров предприятия обратилось 20 человек, среди которых 12 мужчин и 8 женщин. Сколькими способами предприятие может заполнить имеющиеся вакансии?
   
3. 
   В классе 25 учеников, из которых 13 юношей и 12 девушек. Сколькими способами 25 учеников могут встать в шеренгу так, чтобы юноши после удаления из строя девушек, оказались построенными по росту; аналогично девушки после удаления из строя юношей оказались построенными по росту?
   

В современной литературе наиболее употребителен для обозначения числа k-сочетаний из n элементов символ , n называют верхним индексом, k - нижним индексом.
Используя свойства сочетаний 1, 2, 4, составим таблицу1.

Таблица 1.Треугольник Паскаля

n
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1
7	1	7	21	35	35	21	7	1
8	1	8	28	56	70	56	28	8	1
9	1	9	36	84	126	126	84	36	9	1
10	1	10	45	120	210	252	210	120	45	10	1

Заметим, что Блез Паскаль называл числовой треугольник, начало которого содержится в таблице1, арифметическим. Паскаль посвятил свойствам арифметического треугольника основополагающий "Трактат об арифметическом треугольнике" (1654). Справедливости ради, стоит упомянуть, что биномиальные коэффициенты были хорошо известны в Азии за много веков до рождения Паскаля. В Италии треугольник Паскаля называют треугольником Тартальи.
Сочетания имеют многочисленные интерпретации и приложения. Сочетания являются биномиальными коэффициентами в разложении бинома

     (1.4)

В этой интерпретации индексы могут принимать вещественные значения. Используя свойства биномиальных коэффициентов (при разных ограничениях на выбор верхних и нижних индексов), доказано громадное число комбинаторных тождеств, составивших самостоятельный раздел комбинаторной математики. В частности, из формулы 1.4 при x = 1, получим , при
x = -1, n > 0, получим , продифференцировав равенство 1.4, получим при x = 1, и т.д.
Существует тесная связь между подмножествами множества и разложениями целого (положительного) числа. Разложение n есть представление числа n в виде упорядоченной суммы положительных целых чисел. Например, существует восемь разложений числа 4, именно:
1+1+1+1   3+1
2+1+1      1+3
1+2+1       2+2
1+1+2         4
Если разложение содержит в точности k слагаемых, то говорят, что имеет k частей и называется k-разложением. Для k-разложения числа n: a₁ + a₂ + …+ a_n - определим
(k - 1)-подмножество ( ), (n - 1)-множества {1, 2, …, n-1}, формулой.

( ) ={ a₁, a₁ + a₂,…, a₁ + a₂ +…+ a_k-1 }        (1.5)

Эта формула устанавливает биекцию между всеми k-разложениями числа n и (k - 1)-подмножествами (n - 1)-множества.
Следовательно, существует k-разложений числа n и 2^n-1 разложений числа n. Биекцию часто схематично изображают строкой, состоящей из n точек и k - 1 разделяющей вертикальной черты. Точки разделились по k линейно упорядоченным "купе"; числа точек в "купе" соответствуют слагаемым в k-разложении числа n. Например, строка | | | | | соответствует разложению 1+2+1+1+3+2. Другая проблема, тесно связанная с разложениями, есть задача подсчёта числа N(n,k) решений уравнения

x₁ + x₂ + …+ x_k = n                (1.6)
Неотрицательные целые решения уравнения 1.6 называются слабыми k-разложениями числа n. Число неотрицательных целых решений уравнения 1.6 равно числу положительных решений уравнения

y₁ + y₂ + … + y_k = n + k,

то есть числу k-разложений числа n + k. Таким образом, N(n,k) = .

Если k-сочетание содержит повторяющиеся элементы, то такое k-сочетание называют
k-мультимножеством. Число всех k-сочетаний с повторениями из данного n-элементного множества обозначим через , где

       (1.7)

Сочетание можно интерпретировать, как распределение элементов n-множества S между двумя категориями, первая из которых содержит k элементов, вторая содержит n - k элементов. Обобщим это представление. Пусть (a₁, a₂, …, a_m)- последовательность неотрицательных целых чисел, сумма которых равна n. Рассмотрим m категорий C₁, C₂, … C_m.
Обозначим символом        (1.8)
число способов распределения n элементов среди категорий C₁, C₂, … C_m так, чтобы категории C_i принадлежало точно a_i элементов. Тогда        (1.9)

Блок-схемы

Комбинаторные конфигурации наиболее общего вида были исследованы в 30-е годы XX столетия и были названы блок-схемами (block design). Блок-схемы состоят из наборов элементов, называемых блоками. Выбор элементов и пар элементов в блоки подчиняются определённым правилам.

Уравновешенной неполной блок-схемой называется такое размещение v различных элементов по b блокам, что каждый блок содержит точно k различных элементов, каждый элемент появляется точно в k различных блоках и каждая пара различных элементов a_i , a_jпоявляется точно в блоках.

Множество всех сочетаний из v элементов по k, взятых в качестве блоков, образует полную блок-схему. Часть этих сочетаний, в которых каждая пара a_i, a_j появляется одно и то же число раз, является неполной, но уравновешенной блок-схемой. Между пятью параметрами блок-схемы выполняются следующие два соотношения:

bk = vr                     (1.10)
r (k - 1) = (v - 1)       (1.11)

Частным случаем блок-схем являются так называемые конечные плоскости. Выберем конечное множество P. Элементы из P назовём точками. Некоторые подмножества из P назовём прямыми. Пусть отношение инцидентности между точками и прямыми удовлетворяет следующим геометрическим аксиомам.

1. 
   На каждой прямой лежит n точек B.
   
2. 
   Через каждую точку проходят n прямых.
   
3. 
   Любые две прямые пересекаются в одной точке.
   
4. 
   Через любые две точки проходит единственная прямая.
   
5. 
   Существуют 4 точки неколлинеарные по три.
   

Тогда конечное множество P точек и множество L прямых образует конечную проективную плоскость.

Пример:
P = {1, 2, 3, 4, 5, 6, 7}.
L = {l₁, l₂, l₃, l₄, l₅, l₆, l₇}
l₁ = {1, 2, 3}, l₂ = {3, 4, 5}, l₃ = {1, 5, 6}, l₄ = {1, 4, 7}, l₅ = {2, 5, 7},
l₆ = {3, 6, 7}, l₇ = {2, 4, 6}.


Размещения с повторениями (n различных элементов, элементы могут повторяться):



Пример. Возьмем буквы Б, А, Р. Какие размещения из этих букв, взятых по две, можно получить? Сколько таких наборов получиться, если: 1) буквы в наборе не повторяются; 2) буквы могут повторяться?
1) Получатся следующие наборы: БА, БР, АР, АБ, РБ, РА.



2) Получатся наборы: ББ, БА, БР, АА, АБ, АР, РР, РБ, РА.



Перестановки c повторениями (k различных элементов, где элементы могут повторяться m₁, m₂, …, m_k раз и m₁ + m₂ + … + m_k = n, где n - общее количество элементов):



Пример. Возьмем буквы Б, А, Р. Какие перестановки из этих букв можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) буква А повторяется два раза?
1) Получатся наборы: БАР, БРА, АРБ, АБР, РАБ, РБА.




2) Получатся наборы: БАРА, БРАА, БААР, ААРБ, ААБР, АБАР, АРАБ, АРБА, АБРА, РАБА, РААБ, РБАА.



Сочетания c повторениями (n элементов, взятых по m, где элементы в наборе могут повторяться):



Пример. Возьмем плоды: банан (Б), ананас (А) и репа (Р). Какие сочетания из этих плодов, взятых по два, можно получить? Сколько таких наборов получится, если: 1) плоды в наборе не повторяются; 2) можно брать по два одинаковых плода?
1) Получатся наборы: БА ("банан, ананас" и "ананас, банан" - один и тот же набор), АР и РБ.



2) Получатся наборы: ББ, БА, БР, АА, АР, РР.

Вопросы

1. Приведите примеры множеств и их подмножеств.
2. Проиллюстрируйте примерами "из жизни" пересечение, объединение и разность множеств.
3. Постройте диаграммы Эйлера - Венна на свойства разности и дополнения множеств.
4. Назовите виды комбинаций, где важен порядок при составлении наборов и где он не важен.

Список литературы

• 
  Айгнер М. Комбинаторная теория. М.: Мир, 1982.
  
• 
  Стенли Р. Перечислительная комбинаторика. М.: Мир, 1990.
  
• 
  Холл. М. Комбинаторика. М.: Мир, 1970.
  
• 
  Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М.: Мир, 1998.
  
• 
  Рыбников К.А. Введение в комбинаторный анализ. М: МГУ, 1985.
  
• 
  Рыбников К.А. История математики. М.: МГУ, 1994.
  
• 
  Бородин А.И., Бугай А.С. Биографический словарь деятелей в области математики. Киев: Ряданська школа, 1979.
  
• 
  Клейн Ф. Лекции о развитии математики в XIX столетии. М.: Наука, 1989.
  
• 
  История математики с дрвнейших времён до начала XIX столетия / Под ред. А.Н. Колмогорова, А.П. Юшкевича. М: Наука, 1970-1972. T.1-3.
  
• 
  История возникновения и развития комбинаторки: www.combinatorics.by.ru/stories.htm
  
• 
  Задачи по комбинаторике:
  www.math.omsu.omskreg.ru/info/learn/terver/3(001).htm
  
• 
  Библиотека алгоритмов. Комбинаторика:
  alglib.dore.ru/combin/index.html#salman
  
• 
  Введение в комбинаторику:
  combinatorika.narod.ru
  
• 
  Биография Лебница Готфрида Вильгельма:
  www.math.rsu.ru/mexmat/polesno/leibn.ru.html
  schools.techno.ru/sch444/MUSEUM/1_17_119.htm
  historyvt.narod.ru/leibnic.htm
  

• 
  Готфрид Вильгельм Лейбниц
  
• 
  Элиаким Гастингс Мур
  
• 
  Джеймс Джозеф Сильвестр
  

Данный сайт был создан Колпаковой Анной - студенткой 6 курса (магистратуры) факультета информатики и экономики Пермского государственного педагогического университета 2002 г.

Сайт Пермского государственного педгогического универмитета: www.pspu.ac.ru

http://www.problems.ru/view_by_subject_new.php?parent=189&start=30

Конец формы