Основные элементы комбинаторики

                         КазНУ им. Аль-Фараби

 

 

 

 

 

    Реферат

Дисциплина: введение в статистические методы в экономике (ВШЭиБ)

На тему: Основные элементы комбинаторики 

 

 

 

 

 

 

 

 

 

                                                                              Выполнила: Давлетбаева Яна

                                                             1 курс, группа Эк12Р

                                      

                                             2013 г.                                            

   Термин «комбинаторика» происходит от латинского слова «combina», что в переводе на русский означает – «сочетать», «соединять». Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиально возможное количество различных вариантов развития событий. Комбинаторика связана с другими областями математики и имеет широкий спектр применения в генетике, инженерии и т.д.

Разделы комбинаторики:

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

Структурная комбинаторика. К данному разделу относятся некоторые вопросы теории графов, а также теории матроидов.

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

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

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

Инфинитарная комбинаторика. Инфинитарная комбинаторика (англ.) — применение идей и методов комбинаторики к бесконечным (в том числе, несчётным) множествам.                                 

                               Элементы комбинаторики.

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

Правило суммы  и произведения:

Правило суммы:  Если объект А можно выбрать n различными способами, а объект В m различными способами, то выбрать один объект А или В можно n+m различными способами.

Пример 1: В ящике лежат 4 красных шара и 5 зелёных шара. Сколькими способами можно выбрать цветной шар?

Решение: Выбрать цветной шар  это значит выбрать или красный  или зелёный шар. Количество способов равно 4+5=9.

 Пример 2: Встретились 6 друзей, и каждый пожал руку каждому. Сколько всего было рукопожатий?

Решение: Каждый пожал руку каждому, то есть каждый человек сделал 5 рукопожатий. Но общее количество рукопожатий получается по правилу суммы: n1 + n2 + ... + n6 = 6 × 5 = 30. Учтём теперь то, что каждое рукопожатие мы посчитали дважды, и получим в результате 15 рукопожатий.

Правило произведения: Если элемент X можно выбрать k способами, а элемент Y можно выбрать m способами то пару ХY можно выбрать k*m способами.

Пример 1: Пусть из пункта А в пункт В имеется 6 дорог, а из пункта В в пункт С имеется 4 дороги. Сколько существует различных вариантов проезда из пункта А в пункт С? Сколько вариантов существует проезда из пункта В в пункт С и обратно?

    Решение: 1) Существует 6 различных  вариантов проезда из пункта А в пункт В, причём это первая часть пути, а из пункта В в пункт С существует 4 различных вариантов проезда, значит проехать из пункта А в пункт С можно 6*4=24 способами.                                                                                                                       2) В пункт С из пункта В можно проехать 4 различными дорогами и обратно тоже, значит из пункта С в пункт В можно проехать 4*4=16 способами.   

      Пример 2: Сколькими способами можно поставить на шахматную доску чёрную и белую ладью так, чтобы они не били друг друга?

Решение: Чёрную ладью можно поставить на шахматную доску p = 64 различными способами. Независимо от выбора поля чёрная ладья бьёт 15 полей, поэтому для второй ладьи остаётся 64 – 15 = 49 полей, то есть q = 49. Всего число возможных способов, по правилу произведения, равно pq = 64 ∙ 49 = 3136.                                                                                                    

                                            Размещение

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

Пример 1 . Сколько различных четырехзначных чисел можно составить из цифр 2, 8, 9, 1.

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

Пример 2: Сколько различных пятибуквенных «слов» можно составить из 26 букв латинского алфавита?

Решение: По формуле   где n = 26, k = 5, получаем: 

Размещение без  повторений. Из множества, содержащего m различных элементов, надо выбрать упорядоченное подмножество из kэлементов (k£m), то есть такое подмножество, в котором элементы располагаются в определенном порядке, и изменение порядка элементов изменяет подмножество. Кроме этого, элементы в выбранном подмножестве не повторяются. Требуется выяснить, сколько таких комбинаций существует. По правилу произведения получаем, что первый элемент можно выбрать m способами, второй элемент – (m-1) способом, и так далее, а элемент с номером k можно выбрать (m – k + 1) способами. Следовательно, число упорядоченных k-элементных подмножеств, взятых из множества, содержащего m элементов равно m(m-1)(m-2)…(m-k+1). Такие подмножества называются размещениями из m элементов по k элементов, а их общее число можно выразить формулой  .

Пример 1 . Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из пяти языков: русского, английского, немецкого, французского, испанского - на любой другой из этих пяти языков?

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

Пример 2: В районе построили новую школу. Из пришедших 25 человек нужно выбрать директора школы, завуча начальной школы, завуча среднего звена и завуча по воспитательной работе. Сколькими способами это можно сделать?

Решение: На должность директора выбираем из 25 человек, на завуча начальной - из 24, завуча среднего звена - из 23, завуча по воспитательной работе - 22. По правилу умножения получаем: 
25х24х23х22 = 303600 
Или, зная формулу размещения, получаем 

                                             Перестановки 

Пусть множество содержит m различных элементов. Рассмотрим все возможные варианты перестановок элементов этого множества. Получаемые при этом упорядоченные множества отличаются друг от друга только порядком входящих в них элементов. Такие упорядоченные множества называются перестановками. Число перестановок из m элементов равно: 

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

Решение. Количество чисел равно числу перестановок из четырех элементов: 

Перестановки с повторяющимися элементами. Если среди m элементов имеется m1 одинаковых элементов одного типа, m2 одинаковых элементов другого типа и т. д., то при перестановке этих элементов всевозможными способами получаем комбинации, количество которых определяется по формуле:

                                                       Сочетания  

Сочетанием из n элементов по m элементов называется неупорядоченный набор, состоящий из m элементов, выбранных из данных n элементов, причем элементы в этом неупорядоченном наборе не повторяются.  

 Число всех сочетаний из n элементов по m элементов обозначается   и вычисляется по формуле:

          

  Учитывая формулы для вычисления   и  , получим:

Числа    обладают рядом замечательных свойств. Перечислим их, не приводя доказательств:

1. 

2. 

Пример 1 : В кафе в продаже имеются 5 сортов пирожных. Сколькими способами 8 студенток могут заказать себе по одному пирожному?

Решение. Зашифруем каждую покупку 8 пирожных единицами по 5 сортам, разделяя сорта нулями. Тогда каждой покупке  будет соответствовать упорядоченный  набор из 8 единиц и 4 (= 5 - 1) разделительных нулей, а общее число покупок  будет соответствовать числу  перестановок этих нулей и единиц  . Таким образом,

 

  Пример 2 : В группе 10 студентов. Сколькими способами можно выбрать из этой группы троих студентов для участия в конференции?

Решение. Число способов равно числу сочетаний из 10 элементов по 3 элемента:  .

Пример 3: В палитре художника 8 различных красок. Художник берет кистью наугад любую из красок и ставит цветное пятно на ватмане. Затем берет следующую кисть, окунает её в любую из красок и делает второе пятно по соседству. Сколько различных комбинаций существует для шести пятен? Порядок пятен на ватмане не важен.

Решение: Пусть количество пятен первого цвета равно k₁, второго цвета – k₂, третьего – k₃ и так далее. Запишем каждое из этих чисел последовательностью из соответствующего количества единиц, а на границах между числами поставим нули. Так, если у нас первого цвета 1 пятно, второго – 3 пятна, третьего и четвёртого – ни одного, пятого и шестого – по одному пятну, а седьмого и восьмого – снова не одного, то запись будет выглядеть следующим образом: 1011100010100. В этой цепочке содержится m₁ = 6 единиц, m₀ – 1 = 8 – 1 = 7 нулей – всего n = m₀ + m₁ – 1 = 13 цифр. Количество перестановок с повторениями этих цифр равно 

 

 

 

 

 

 

 

Список использованной литературы:

1. Елисеева И.И., Князевский В.С., Ниворожкина Л.И., Морозова З.А. Теория статистики с основами теории вероятностей. – М.: ЮНИТИ, 2001
2. Ерош И. Л. Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 c.
3. Риордан Дж. Введение в комбинаторный анализ. — пер. с англ. — М., 1963.
4. Мухамедиев Б.М. Эконометрика и эконометрическое прогнозирование. Алматы, 2007.
5. Айвазян С.А., Мхитарян В.С. Прикладная статистика в задачах и упражнениях. – М.: ЮНИТИ, 2001.
6. Интернет ресурс www.wikipedia.org