Комбинаторика — справочник студента

Во многих практических случаях возникает необходимость подсчитать количе­ство возможных комбинаций объектов, удовлетворяющих определенным усло­виям. Такие задачи называются Комбинаторными. Разнообразие комбинаторных задач не поддается исчерпывающему описанию, но среди них есть целый ряд особенно часто встречающихся, для которых известны способы подсчета.

  • Размещения
  • Число всех функций (при отсутствии ограничений), или число всех возможных способов разместить П Предметов по Т Ящикам называется, Числом размещений И обозначается U(M,N).
  • ТЕОРЕМАU(Т, п)= Mn
  • Доказательство
  • Каждый из N предметов можно разместить M способами.
  • Пример

При игре в кости бросаются две кости и выпавшие на верхних гранях очки скла­дываются.

alt

Узнай стоимость своей работы

Бесплатная оценка заказа!

Оценим за полчаса!

Какова вероятность выбросить 12 очков? Каждый возможный исход соответствует функции F: {1,2}® {1,2,3,4,5,6} (аргумент — номер кости, ре­зультат — очки на верхней грани).

Таким образом, всего возможно U(6,2) = 62 = 36 различных исходов. Из них только один (6 + 6) дает двенадцать очков. Вероятность 1/36.

  1. Размещения без повторений
  2. Число инъективных функций, или число всех возможных способов разместить П Предметов по M ящикам, не более чем по одному в ящик, называется Числом размещений без повторений И обозначается А(M, п) или [M]n, или (M)n.
  3. ТЕОРЕМА Комбинаторика - Справочник студента
  4. Доказательство

Ящик для первого предмета можно выбрать M способами, для второго — M — 1 способами, и т. д. Таким образом,

Комбинаторика - Справочник студента

По определению считают, что А(Т, N) = 0 при П > Т И А(Т, 0) = 1.

Пример

В некоторых видах спортивных соревнований исходом является определение участников, занявших первое, второе и третье места.

Сколько возможно раз­личных исходов, если в соревновании участвуют П Участников? Каждый воз­можный исход соответствует функции F: {1,2,3} ® {1..N} (аргумент — номер призового места, результат — номер участника).

alt

Узнай стоимость своей работы

Бесплатная оценка заказа!
Читайте также:  Бихевиоризм - справочник студента

Оценим за полчаса!

Таким образом, всего возможно А(П,3) = П(П — 1)(N — 2) различных исходов.

  • Перестановки
  • Число взаимнооднозначных функций, или Число перестановок п Предметов, обо­значается Р(П).
  • ТЕОРЕМА Р(N) = N!
  • Доказательство

Р(N) = А(N, N) = N(N — 1)…(NN + 1)= N(N — 1)…1 = N!.

Пример

Последовательность E = (E1,…,Em) непустых подмножеств множества Е (E Ì 2E, Ei Ì Е, Ei ¹ Æ) называется Цепочкой В Е, Если

«IÎ1..M — 1 Ei Ì Ei+1 & Ei ¹ Ei+1.

Цепочка E называется Полной Цепочкой в Е, Если |E| = |Е|.

Сколько существует полных цепочек? Очевидно, что в полной цепочке каждое следующее подмноже­ство Ei+1 получено из предыдущего подмножества Ei Добавлением ровно одного элемента из Е И, таким образом, |E1| = 1, |E2| = 2, …, |Ет| = |Е| = т.

Следова­тельно, полная цепочка определяется порядком, в котором элементы Е Добавля­ются для образования очередного элемента полной цепочки. Отсюда количество полных цепочек — это количество перестановок элементов множества Е, Рав­ное M!.

  1. Сочетания
  2. Число строго монотонных функций, или число размещений П Неразличимых предметов по Т Ящикам, не более чем по одному в ящик, то есть число способов выбрать из m ящиков N ящиков с предметами, называется Числом сочетаний И обозначается С(Т, п) или или .
  3. ТЕОРЕМА Комбинаторика - Справочник студента
  4. Доказательство

1. Число размещений без повторений нужно разделить на число перестановок, поскольку предметы неразличимы.

2. Число сочетаний является числом строго монотонных функций, потому что строго монотонная функция F: 1..п ® L..M определяется набором своих значений, причем 1£ F(1)< … < F(N) £ M.

Другими словами, каждая строго монотонная функция определяется выбором N чисел из диапазона 1..m.

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

По определению С (M, N) = 0 при N > M.

Пример

В начале игры в домино каждому играющему выдается 7 костей из имеющихся 28 различных костей. Сколько существует различных комбинаций костей, которые игрок может получить в начале игры? Очевидно, что искомое число равно числу 7-элементных подмножеств 28-элементного множества. Имеем:

Читайте также:  Методы, ориентированные на людей и культуру - справочник студента

Комбинаторика - Справочник студента

  • Сочетания с повторениями
  • Число монотонных функций, или число размещений N неразличимых предме­тов по M ящикам, называется Числом сочетаний с повторениями И обозначается V(M, N).
  • ТЕОРЕМА V(M, N)=C(N + M — 1, N).
  • Пример

Сколькими способами можно рассадить N Вновь прибывших гостей среди M Го­стей, уже сидящих за круглым столом? Очевидно, что между то сидящими за круглым столом гостями имеется M Промежутков, в которые можно рассаживать вновь прибывших. Таким образом, это можно сделать

Комбинаторика - Справочник студента

Способами.

Источник: http://matica.org.ua/metodichki-i-knigi-po-matematike/diskretnaia-matematika-uchebnoe-posobie/glava-10-kombinatorika-kombinatornye-konfiguratcii

Учебно-методическое пособие по теме: Комбинаторика | Социальная сеть работников образования

  • Министерство образования и науки РФ.
  • ГБОУ СПОМО Фрязинский государственный техникум электроники, управления и права.
  • КОМБИНАТОРИКА
  • Учебное пособие
  • I курс
  • Специальности 210912
  •     030912
  • г. Фрязино
  • 2012 год
  • Согласовано        Утверждаю
  • предметно – цикловой комиссией        Зам. директора по УВР

протокол №                                                                                       _______Морозова О.Н.

«___»________  201___

Председатель ПЦК

 ________ Морозова Н.Е.

Рецензент:

__________Ивонин В.И.

Преподаватель:

__________Морозова Н.Е.

  1. 2
  2. АННОТАЦИЯ
  3. Данное методическое пособие содержит  теоретический материал по теме «Комбинаторика», рекомендации по применению формул комбинаторики, разобранные с объяснениями решения задач, подборку задач для самостоятельного решения с ответами.
  4. Предназначено для самостоятельной работы студентов и для аудиторной работы преподавателя.
  5. 4
  6. ВВЕДЕНИЕ

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

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

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

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

Начать надо с истории развития темы и основного определения.

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

Комбинации, которые возникали при бросании кости и в других играх всегда привлекали людей. Самая древняя кость была найдена при раскопках в северном Ираке. Её возраст около 5.000 лет.

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

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

  • С помощью комбинаторики и тесно связанных с ней разделов математики, таких как статистика и теория вероятностей, найдены строгие закономерности там, где их не должно было бы быть по самому смыслу – в мире случайных явлений, среди хаоса и беспорядка.
  • Родоначальники комбинаторики и теории вероятности: Б. Паскаль
  •                           П.Ферма
  •                           Я. Бернулли
  •                           П. Лаплас
  •                           Л. Эйлер

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

  1. 6
  2. ОСНОВНАЯ ЧАСТЬ
  3. КОМБИНАТОРИКА, ЕЁ ПРАВИЛА И ВИДЫ.

Если во множестве есть элементы, то их можно комбинировать друг с другом по различным свойствам и правилам. Это и есть комбинаторика – подсчет числа различных соединений элементов. Существует два основных правила: правило суммы и правило произведения.

Правила суммы: Если объект А можно выбрать К способами, а объект В – L способами, то объект   А либо В можно выбрать К+L способами.

Пример: В первом ящике 8 шаров, во втором – 5. Сколько существует способов извлечь шар или из первого или из второго ящика. Ответ: 8+5=13 способов.

Правило произведения: Если объект А можно выбрать К способами, а после этого другой объект В – L способами, то пары объектов и А и В можно выбрать К∙L способами.

Пример: В первом ящике 8 шаров, во втором – 5. Сколько существует способов извлечь один шар из первого и один из второго ящика. Ответ: 8∙5=40 способов, т.к. на каждый из 8 способов достать шар из первого ящика, существует 5 способов достать шар из второго, что видно из рисунка 1.

Источник: https://nsportal.ru/npo-spo/estestvennye-nauki/library/2013/09/13/kombinatorika

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

Наум РЇРєРѕРІР»РµРІРёС‡ Р’иленкин Рњ.: Наука, 1969. 328 СЃ. Тираж 100000 СЌРєР·.

Загрузить (Mb)
djvu (2.58) pdf (-) ps (-) html (-) tex (-)

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

Первая глава РєРЅРёРіРё посвящена общим правилам комбинаторики — правилам СЃСѓРјРјС‹ Рё произведения. Р’Рѕ второй главе изучаются размещения, перестановки Рё сочетания. Р’ главе 3 изучаются задачи, РІ которых РЅР° рассматриваемые комбинации налагаются те или иные ограничения. Р’ главе 4 рассмотрены задачи РЅР° разбиения чисел Рё рассказано Рѕ геометрических методах РІ комбинаторике. Глава 5 посвящена задачам Рѕ случайных блужданиях Рё различным модификациям арифметического треугольника. Р’ главе 6 рассказано Рѕ рекуррентных соотношениях, Р° РІ главе 7 — Рѕ производящих функциях, Рё РІ частности Рѕ биномиальной формуле.

Содержание

Предисловие

Глава I.

Общие правила комбинаторики     Суеверные велосипедисты     Размещения СЃ повторениями     Системы счисления     Секретный замок     РљРѕРґ РњРѕСЂР·Рµ     РњРѕСЂСЃРєРѕР№ семафор     Электронная цифровая вычислительная машина     Генетический РєРѕРґ     Общие правила комбинаторики     Задача Рѕ РґРѕРјРёРЅРѕ     Команда космического корабля     Задача Рѕ шашках     Сколько человек РЅРµ знают иностранных языков?     Формула включений Рё исключений     Р’ чем ошибка?     Решето Эратосфена

Глава II.

Размещения, перестановки Рё сочетания     Футбольное первенство     Размещения без повторений     Научное общество     Перестановки     Задача Рѕ ладьях     Лингвистические проблемы     РҐРѕСЂРѕРІРѕРґ     Перестановки СЃ повторениями     Анаграммы     Сочетания     Генуэзская лотерея     РџРѕРєСѓРїРєР° пирожных     Сочетания СЃ повторениями     РЎРЅРѕРІР° футбольное первенство     Свойства сочетаний     Частный случай формулы включений Рё исключений     Знакопеременные СЃСѓРјРјС‹ сочетаний

Глава III.

Комбинаторные задачи СЃ ограничениями     Львы Рё тигры     Постройка лестницы     Книжная полка     Рыцари короля Артура     Девушка спешит РЅР° свидание     Сеанс телепатии     Общая задача Рѕ смещении     Субфакториалы     Караван РІ пустыне     Катание РЅР° карусели     Очередь РІ кассу     Задача Рѕ РґРІСѓС… шеренгах     Новые свойства сочетаний

Глава IV.

Комбинаторика разбиений     Р�РіСЂР° РІ РґРѕРјРёРЅРѕ     Раскладка РїРѕ ящикам     Букет цветов     Задача Рѕ числе делителей     РЎР±РѕСЂ яблок     РЎР±РѕСЂ РіСЂРёР±РѕРІ     Посылка фотографий     Флаги РЅР° мачтах     Полное число сигналов     Разные статистики     Разбиения чисел     Отправка бандероли     Общая задача Рѕ наклейке марок     Комбинаторные задачи теории информации     Проблема абитуриента     Уплата денег     РџРѕРєСѓРїРєР° конфет     Как разменять гривенник?     Разбиение чисел РЅР° слагаемые     Диаграммная техника     Двойственные диаграммы     Формула Эйлера

  • Глава V. Комбинаторика РЅР° шахматной РґРѕСЃРєРµ     Человек Р±СЂРѕРґРёС‚ РїРѕ РіРѕСЂРѕРґСѓ     Арифметический квадрат     Фигурные числа     Арифметический треугольник     Расширенный арифметический треугольник     Шахматный король     Обобщенный арифметический треугольник     Обобщенные арифметические треугольники Рё m-ичная система счисления     Некоторые свойства чисел Cm(k,n)     Шашка РІ углу     Арифметический пятиугольник     Геометрический СЃРїРѕСЃРѕР± доказательства свойств сочетаний     Случайные блуждания     Броуновское движение     РЈ Шемаханской царицы     Поглощающая стенка     Блуждания РїРѕ бесконечной плоскости     Общая задача Рѕ ладьях     Симметричные расстановки     Два РєРѕРЅСЏ
  • Глава VI. Рекуррентные соотношения     Числа Фибоначчи     Другой метод доказательства     Процесс последовательных разбиений     Умножение Рё деление чисел     Задачи Рѕ многоугольниках     Затруднение мажордома     Счастливые троллейбусные билеты     Рекуррентные таблицы     Другое решение проблемы мажордома     Решение рекуррентных соотношений     Линейные рекуррентные соотношения СЃ постоянными коэффициентами     Случай равных корней характеристического уравнения     Третье решение задачи мажордома
  • Глава VII. Комбинаторика Рё СЂСЏРґС‹     Деление многочленов     Алгебраические РґСЂРѕР±Рё Рё степенные СЂСЏРґС‹     Действия над степенными рядами     Применение степенных СЂСЏРґРѕРІ для доказательства тождеств     Производящие функции     Бином Ньютона     Полиномиальная формула     Р СЏРґ Ньютона     Р�звлечение квадратных корней     Производящие функции Рё рекуррентные соотношения     Разложение РЅР° элементарные РґСЂРѕР±Рё     РћР± едином нелинейном рекуррентном соотношении     Производящие функции Рё разбиения чисел     РЎРІРѕРґРєР° результатов РїРѕ комбинаторике разбиений
  • Задачи РїРѕ комбинаторике
  • Решения Рё ответы
    Загрузить (Mb)
    djvu (2.58) pdf (-) ps (-) html (-) tex (-)

Источник: https://math.ru/lib/363

Элементы комбинаторики: размещение, сочетание, перестановки и комбинации с повторением

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

Размещение элементов комбинаторики

Пусть даны три элемента . Из них можно создать такие соединения:

1) по одному элементу: ;

Если, например, рассматривать соединения по два элемента, тогда некоторые из них отличаются элементами ( и ), другие – порядком элементов и . Такие соединения называются размещением из 3 элементов по 2.

Число размещений обозначается . Из вышеописанного, мы видим, что , , .

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

(1)

Действительно, пусть нам дано элементов: .

Рассмотрим размещение по одному элементу. Понятно, что их будет , то есть .

Читайте также:  Особенности развития и формирования личности - справочник студента

Теперь рассмотрим, какие возможные размещения по 2 элемента. Чтобы их получить, мы допишем к каждому из данных элементов ещё по одному, которые брались из остальных  элементов. Так, к элементу  допишем последовательно остальные элементы: ; к элементу последовательно остальные элементы: и т. д.

Получим все размещения из элементов по 2:

Записано строк, а число всех размещений в каждом из этих строк . Общее количество всех размещений равняется произведению на , то есть:

Чтобы получить рзмещение по 3 элемента в каждом, нам нужно к каждой из записанных пар элементов приобщить ещё по одному элементу из элементов, что остались.

Например, к необходимо приобщить один из элементов . Тогда всех размещений по 3 элемента будет:

  • Иногда встречаются задачи на размещение с повторениями.
  • Число размещений с повторениями обозначаются через  и вычисляются по формуле:
  • .
  • (2)

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

Согласно с определением:

Произведение всех натуральных чисел от до обозначается , а читается ( факториал).

Таким образом,

  1. Тогда формула для вычисления количества перестановок запишется:
  2. (3)
  3. При этом имеется ввиду, что .

Обратите внимание! Иногда встречается обозначение . Принято считать, что .

Комбинации или сочетание элементов комбинаторики

Число комбинаций вычисляется по формуле:

  • (4)
  • Формулу (4) объясним на таком примере:
  • Пусть даны 4 элемента , комбинациями из этих элементов по будут:
  • .
  • Порядок элементов в комбинации роли не играет. Если в каждой из этих комбинаций сделать всевозможные перестановки, тогда у нас получатся всевозможные размещения из 3 элементов:
  • Число таких размещений равняется .
  • Таким образом, число всех размещений из элементов по равняется числу всех возможных сочетаний элементов по , умноженному на число всех перестановок, которые можно сделать из элементов, то есть:
  • ,
  • откуда получается формула (4).
  • Посмотрите пример:
  • .
  • Умножим числитель и знаменатель в формуле (4) на . Тогда получим:
  • В итоге получаем:
  • (5)

По определению принимают . Это определение можно получить из формулы (5), если принять во внимание, что .

  1. При вычислении числа комбинаций иногда удобно пользоваться соотношением:
  2. (6)
  3. Действительно, если по формуле (5) записать , тогда получим:
  4. (7)
  5. Последнее выражение совпадает с правой частью в формуле (5).
  6. Отметим ещё, что числа – это коэффициенты в биноме Ньютона:
  7. (8)
  8. причём согласно с равенством (6) коэффициенты, равноотдалённые от окончания в формуле (8), равные между собой, то есть:

, , и т. д.

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

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

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

Примеры решения задач с элементами комбинаторики

Пример 1

Задача

Студенты группы изучают 9 дисциплин по 3 пары ежедневно. Сколько существует способов, чтобы распределить пары на один день?

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

Пример 2

Задача

Автомобильный номер состоит из 5 цифр (из такого набора: и двух букв. В соединении из букв для номеров автомобилей, какие зарегистрированы в Московской области, на первом месте стоит буква , а на втором месте одна из букв А, Б. В, И. К, Н. Сколько автомобильных номеров можно составить в области?

  • Решение
  • Числовая часть номера – один из размещений из по с повторениями. И количество:
  • Из них необходимо исключить размещение 000-00, так как такой номер не используется, то есть, всех числовых соединений будет:
  • .

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

  1. .
  2. Ответ
  3. Автомобильных номеров в одной области можно составить по числам – 99 999, а по буквам – 599994.

Пример 3

  • Задача
  • Сколько пятизначных телефонных номеров можно составить используя цифры 3, 4, 5, 6, 7 (без повторений)?
  • Решение
  • Так как каждый номер телефона складывается из 5 цифр, тогда такие номера будут отличаться только порядком цифр, то есть это будут перестановки, и их количество равняется:
  • .
  • Ответ
  • Всего можно составить 120 пятизначных номеров.

Пример 4

  1. Задача
  2. Сколько есть способов, чтобы заполнить карточку спортлото, в которой из 49 чисел необходимо выбрать 6?
  3. Решение
  4. Две заполненные карточки считаются разными, если среди выбранных 6 чисел они отличаются хотя бы одним числом, то есть это будут комбинации, и их количество равняется:
  5. .
  6. Ответ
  7. Количество комбинаций =

Пример 5

  • Задача
  • Сколько есть способов, чтобы в данном тайме тренер смог бы выставить на поле 5 баскетболистов, если в команде 10 игроков, причём одного из ведущих игроков тренер планирует задействовать в игре не заменяя на другого игрока весь тайм?
  • Решение
  • Так как один из ведущих игроков должен находится на поле в игре весь тайм, тогда менять придётся только 4 игрока из оставшихся 9, то есть у нас получается:
  • Ответ
  • Есть 126 способов.

Пример 6

  1. Задача
  2. Сколько есть способов, чтобы расставить на первой горизонтальной шахматной доски такие фигуры: две ладьи, два коня, два слона, одного ферзя и одного короля?
  3. Решение
  4. Всего 8 фигур, причём , , , , , тогда:
  5. .
  6. Ответ
  7. На первой горизонтальной шахматной доске с перестановками фигур можно расставить 5 040 раз.

Пример 7

  • Задача
  • Сколько разных соединений букв можно образовать, переставляя эти буквы:
  • 1. В слове “мама”;

2. в слове параллелограмм.

Записать соединения букв.

Решение

1. В слове “мама” буквы, при этом две буквы “м”, и две буквы “а”. По формуле (9) всех перестановок будет:

.

А сами перестановки будут такими: “мама”, “маам”, амам”, “аамм”, “амма”.

2. В слове “параллелограмм” 12 букв, из них букв “а” – 3, “г” – 1, “е” – 1, “л” – 2, “м” – 1, “о” – 1, “п” – 1, “р” – 2. Всех перестановок будет:

  1. .
  2. Ответ
  3. Всевозможных перестановок будет – .

Пример 8

Задача

На складе нужно получить 5 однотипных деталей, каждая из которых может быть покрашена в один из трёх цветов: красный, чёрный, зелёный. Сколько имеется способов, чтобы выбрать 5 деталей трёх цветов?

  • Решение
  • .
  • Ответ
  • Для того, чтобы выбрать 5 деталей 3 цветов, мы нашли 21 способ.

Источник: https://NauchnieStati.ru/spravka/elementy-kombinatorik/

Лекция 1: Элементы комбинаторики — Теория вероятности

План:

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

2.     
Общие правила комбинаторики.

3.     
Генеральная совокупность без повторений и
выборки без повторений.

4.     
Применение графов (схем) при решении
комбинаторных задач.

1.      Комбинаторика и ее возникновение.

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

Комбинаторика возникла в XVI веке. В жизни
привилегированных слоев тогдашнего общества большое место занимали азартные
игры (карты, кости). Широко были распространены лотереи.

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

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

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

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

Дальнейшее развитие комбинаторики
связано с именами Я. Бернулли, Г. Лейбница, Л. Эйлера. Однако, и в их работах
основную роль играли приложения к различным играм.

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

2.      Общие правила комбинаторики.

Правило суммы: Если некоторый объект А может быть выбран m способами, а объект В- k способами,
то объект «либо А, либо В» можно выбрать m+k
способами.

Примеры:

1.              Допустим, что в ящике находится n разноцветных шаров.
Произвольным образом вынимается 1 шарик. Сколькими способами это можно сделать? 

Ответ: n способами.

Распределим эти n шариков по двум ящикам: в первый- m шариков,
во второй- k шариков. Произвольным образом из произвольно выбранного
ящика вынимается 1 шарик. Сколькими способами это можно сделать?

Решение: Из первого ящика шарик можно вынуть m способами, из второго- k способами. Тогда всего
способов m+k=n.

2.     
Морской семафор.

В морском семафоре каждой букве
алфавита соответствует определенное положение относительно тела сигнальщика
двух флажков. Сколько таких сигналов может быть?

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

Правило произведения:  Если
объект А можно выбрать m
способами, а после каждого такого выбора другой объект В можно выбрать
(независимо от выбора объекта А) k способами, то пары объектов «А и В» можно выбрать m*k способами.

Примеры:

1.     
Сколько двузначных чисел существует?

Решение: Число десятков
может быть обозначено любой цифрой от 1 до 9. Число единиц может быть
обозначено любой цифрой от 0 до 9.

Если число десятков равно 1, то число единиц
может быть любым (от 0 до 9). Таким образом, существует 10 двузначных чисел, с
числом десятков- 1.  Аналогично
рассуждаем и для любого другого числа десятков.

Тогда можно посчитать, что
существует 9 *10 = 90 двузначных чисел. 

2.            Имеется 2 ящика. В одном лежит m разноцветных
кубиков, а в другом- k разноцветных шариков. Сколькими способами можно выбрать пару
«Кубик-шарик»?

Решение: Выбор шарика не зависит от
выбора кубика, и наоборот. Поэтому, число способов, которыми можно выбрать
данную пару равно m*k.

 3.      Генеральная совокупность без повторений и
выборки без повторений.

Генеральная совокупность без повторений— это набор некоторого
конечного числа различных элементов a1, a2, a3, …, an.

Пример: Набор из n разноцветных лоскутков.

Выборкой объема k (k n) называется
группа из m элементов данной генеральной совокупности.

Пример: Пестрая лента, сшитая из m разноцветных лоскутков, выбранных из данных n.

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

число размещений из n
по k.

Число размещений из n
по k
можно определить следующим способом: первый объект выборки можно выбрать n способами, далее
второй объект можно выбрать n-1
способом и т.д.

Источник: https://www.sites.google.com/site/teoriaveroyatnosti/teoria/elementy-kombinatoriki

Ссылка на основную публикацию