Основы математической обработки информации Элементы комбинаторики

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

Правило суммы Если элемент А можно выбрать n различными способами и независимо от него элемент B можно выбрать m различными способами, то выбрать все различные комбинации элементов «A или B» можно n+m способами. Объем (численность) множества Х будем обозначать |X|. Пример: Школьникам на предстоящий зачет дается на выбор 5 тем по алгебре или 7 по геометрии. Сколькими способами можно выбрать тему по алгебре или геометрии? Решение: |X|=5, |Y|=7. Множества не пересекаются, значит можно применить правило суммы: |X|+|Y|=5+7=12 способов. Ответ: 12 способами ученик может выбрать тему.

Правило произведения Если элемент A можно выбрать n различными способами и независимо от него элемент B можно выбрать m различными способами, то все различные комбинации элементов «A и B» можно выбрать n m способами. Пример: На первой полке стоит 10 книг, а на второй 5. Сколькими способами можно взять книги с обеих полок? Решение: |X|=10, |Y|=5. По правилу произведения: |X|*|Y|=10*5=50. Ответ: 50 способами. Правила суммы и произведения естественным образом обобщаются и на случай комбинаций многих элементов, а именно, если первый элемент совокупности из k различных элементов можно выбрать n 1 способами, второй n 2 способами и так далее, k-й элемент n k способами, то всевозможных комбинаций соответственно n 1 +n n k и n 1 n 2... n k.

Задача Сколькими способами из 28 костей домино можно выбрать две кости так, чтобы их можно было приложить друг к другу (т.е. чтобы какое-то число очков встретилось на обеих костях)? Решение. Сначала выберем одну кость. Это можно сделать 28 способами. При этом в 7 случаях выбранная кость окажется "дублем", т.е. костью вида 00, 11, 22, 33, 44, 55,66, а в 21 случае - костью с различными числами очков(например, 05, 13 и т.д.). В первом случае вторую кость можно выбрать 6 способами (например, если на первом шагу выбрана кость 11, то на втором шагу можно взять одну из костей 01, 12, 13, 14, 15, 16). Во втором случае вторую кость можно выбирать 12 способами (для кости 35 подойдут кости 03, 13, 23, 33, 34, 36, 05, 15, 25, 45, 55, 56). По правилу произведения в первом случае получаем 7*6=42 выбора, а во втором 21*12=252 выбора. Значит по правилу суммы получаем =294 способов выбора пары.

Размещения Размещением из n элементов по k элементов называется упорядоченное подмножество, содержащее k различных элементов данного множества. Эти подмножества могут отличаться друг от друга составом элементов или порядком элементов. Количество возможных размещений вычисляется по формуле: - факториал числа n, 0!=1 Пример размещения четырех шаров по двум ячейкам.

Задача Студенту необходимо сдать 4 экзамена за 8 дней. Сколькими способами это можно сделать? Чему равно число способов, если известно, что последний экзамен будет сдаваться на восьмой день? Решение. Искомое число способов равно числу 4–элементных упорядоченных подмножеств из 8 элементов, т.е.

Размещения с повторениями из n элементов по k элементов называется упорядоченное подмножество, содержащее k элементов данного множества. Эти подмножества могут отличаться друг от друга составом элементов (элементы в каждом множестве могут повторяться) или порядком элементов. Количество возможных размещений вычисляется по формуле: Количество последовательностей длины K из N различных символов равно N K. Пример. Сколько существует наборов длины 7 из нулей и единиц? Размещения с повторениями

Перестановки Перестановкой из n элементов называется размещение из n элементов по n элементов. Различные перестановки отличаются друг от друга только порядком элементов. Количество всех возможных перестановок вычисляются по формуле: Пример. Сколько существует перестановок из четырех элементов?

Задачи Сколькими способами могут сесть в автомобиль 5 человек, каждый из которых может быть водителем? P 5 = 5! = 1 · 2 · 3 · 4 ·5 = 120 P 5 = 5! = 1 · 2 · 3 · 4 · 5 = книг стоит на книжной полке, из них 27 различных книг и одного автора три книги. Сколькими способами можно расставить эти книги на полке так, чтобы книги одного автора стояли рядом? · Решение. Будем считать три книги одного автора за одну книгу, тогда число перестановок будет P 28. А три книги можно переставлять между собой P 3 способами, тогда по правилу произведения имеем, что искомое число способов равно: P 3 ·P 28 =3! · 28!

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

Задача Рота состоит из трех офицеров, шести сержантов и 60 рядовых. Сколькими способами можно выделить из них отряд, состоящий из офицера, двух сержантов и 20 рядовых? Решение. Одного офицера из трех можно выбрать 3 способами, двух сержантов из 6 можно выбрать 20 рядовых из 60 можно выбрать Всего способов

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

Пусть, например, есть автомат, формирующий двузначные десятичные целые положительные числа (исходное множество информационных элементов {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}). В соответствии с положениями комбинаторики, данный автомат генерирует размещения (различаются числа, например, 34 и 43) из 10 элементов (используются 10 цифр) по 2 (по условию задачи, формируются двузначные числа) с повторениями (очевидно, возможны числа, состоящие из одинаковых цифр, например, 33). Тогда можно оценить, сколько различных сообщений (двузначных чисел) может сформировать автомат, иначе говоря, можно оценить информационную емкость данного устройства: Р n (10 2 ) = 10 2 = 100.

Пример. Определить емкость ASCII-кода, представленного в двоичной или шестнадцатеричной системе счисления. ASCII-код – это сообщение, которое формируется как размещение с повторениями: для двоичного представления – из информационных элементов {0, 1}, сообщение длиной (объемом) 8 символов; для шестнадцатеричного представления – из информационных элементов {0, 1, 2, …., А, В, С, …. F}, сообщение длиной (объемом) 2 символа. Тогда в соответствии с положениями комбинаторики: I (двоичное) = Р n = 2 8 = 256; I (шестнадцатеричное) = Р n = 16 2 = 256, где I (двоичное), I (шестнадцатеричное) – количества информации, соответственно, для двоичного и шестнадцатеричного представления ASCII-кода. Таким образом, емкость ASCII-кода для двоичного и шестнадцатеричного представления одинакова и равна 256.

Задачи Наряд студентки состоит из блузки, юбки и туфель. Девушка имеет в своем гардеробе четыре блузки, пять юбок и трое туфель. Сколько нарядов может иметь студентка? Решение. Пусть сначала студентка выбирает блузку. Этот выбор может быть совершен четырьмя способами, так как студентка имеет четыре блузки, затем пятью способами произойдет выбор юбки и тремя способами выбор туфель. По принципу умножения получается 4 5 3=60 нарядов (комбинаций).

Сколько существует перестановок букв w, e, d, i, g, m, a, t, h, в которых последовательности букв не образуют слова we dig math? Например, перестановка d, g, i, w, e, t, h, a, m не подходит, потому что включает сочетание we. Необходимые нам перестановки входят во множество всех возможных перестановок букв w, e, d, i, g, m, a, t, h Число перестановок, содержащих комбинацию we, то есть число всех перестановок символов we, d, i, g, m, a, t, h: Число перестановок, содержащих комбинацию dig, то есть число всех перестановок символов w, e, dig, m, a, t, h: Число перестановок, содержащих комбинацию dig, то есть число всех перестановок символов w, e, d, i, g, math

В задаче требуется найти численность (объем) множества S1S1 S2S2 S3S3 Число перестановок, содержащих комбинацию dig, и we (we, dig, m, a, t, h): Число перестановок, содержащих комбинацию dig, и math (w, e, dig, math): Число перестановок, содержащих комбинацию we, и math (we, d, i,g, math): Число перестановок, содержащих комбинацию we, dig, math (we, dig, math):