Спирина, М.С. Дискретная математика

Решение задач, связанных с перебором вариантов, требует предварительного анализа комбинаторных вычислений, поиска соответствующего алгоритма и учета необходимых временных затрат. Задачи подсчета возможных комбинаций объектов, удовлетво­ ряющих определенным условиям, часто встречаются в практиче­ ской деятельности и получили название комбинаторных. Многообразие таких задач не всегда удается описать с помо­ щью математических формул. Однако для стандартных распрост­ раненных ситуаций способы подсчета вариантов определены. Задача 8. Разложить п различных деталей в т больших ящиков. Сколько вариантов таких размещений можно перебрать? Решение. Поскольку все п деталей могут поместиться и в один ящик, то на языке функций задано сюръективное соответствие между множеством X деталей (|Х| = и) и множеством Y ящиков (|У| = т), т.е. <р : Х-> Y. Такое часто встречающееся число подсчетов вариантов назы­ вают размещением с повторением и обозначают Ат. Так как каж­ дую из п деталей можно разместить в т ящиков, то необходимо п раз умножать число т, т.е. Ат=тп. Напомним, что такой же результат был получен и в подразд. 1.4, когда находили полное число функций ф: X -> Y. Задача 9. Сколько различных двоичных чисел длиной 6 можно записать с помощью цифр 0 и 1? Решение. Размещаем две цифры (0, 1) на шесть мест, т.е. на каждом из шести мест (т = 6) может быть одна из двух двоичных цифр. Всего таких вариантов будет Аг = 26 = 64 двоичных чисел: на каждом из шести мест по два варианта цифр. Задача 10. Сколько проводится матчей в Чемпионате РФ по футболу в премьер-лиге (16 команд) за сезон? Решение. Поскольку один матч проводится между двумя коман­ дами, каждый матч выделяет подмножество (упорядоченное, так как одна команда играет дома, вторая — на выезде) из двух эле­ ментов. По формуле размещений А \6 = 16 15 = 240. Все комбинаторные операции удобно представить в виде схе­ мы (рис. 1.19). Во второй половине XX в. теория множеств пополнилась новым, пер­ спективным и актуальным для современной практической деятельности направлением, связанным с понятием нечетких множеств. Благодаря создателю этого направления профессору университета г. Беркли (США) Лотфи Заде с середины 1960-х гг. появилась реальная возможность приближения математических рассуждений к тем приня­ тым схемам, которые используют люди в процессе непосредственного общения. 52