Комбинаторика в Excel
 Скачать 0.98 Mb.
|
|
Комбинаторика в Excel Комбинаторика — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения элементов) и отношения на них. Термин комбинаторика был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». Excel поддерживает ряд функций комбинаторики. Чтобы разобраться, какую формулу использовать, следует ответить на ряд вопросов: 1. Исходное множество содержит только уникальные элементы, или некоторые из них могут повторяться? 2. Операция выполняется со всеми элементами множества, или только с некоторой выборкой из них? 3. Важен ли порядок элементов в выборке? 4. После выбора элемента мы его возвращаем назад? Рис. 1. Дерево решений, какую формулу комбинаторики использовать Перестановки без повторений Возьмем несколько различных элементов (предметов) и будем переставлять их всевозможными способами, оставляя неизменным их число и меняя только их порядок (рис. 2). Каждая из получившихся таким образом комбинаций носит название перестановки. Перестановкой из n элементов называется упорядоченное множество, составленное из всех элементов множества. Оперируем со всеми элементами? Важен порядок? Все элементы множества уникальны? Перестановки без повторений Перестановки с повторениями Лишено смысла Важен порядок в выборке? Возвращаем после выбора? Размещения без повторений Размещения с повторениями Возвращаем после выбора? Сочетания без повторений Сочетания с повторениями Да Да Нет Да Нет Да Нет Нет Нет Да Да Нет, с выборкой Рис. 2. Перестановки (понравившаяся картинка взята здесь ) Если все n элементы разные, то число перестановок обозначается P n от perturbation. (1) 𝑃 𝑛 = 𝑛 ∙ (𝑛– 1) ∙ (𝑛– 2) ∙ … ∙ 2 ∙ 1 = 𝑛! С другой стороны, произведение n первых натуральных чисел называется n-факториал и обозначается n! (2) 𝑛! = 1 ∗ 2 ∗ 3 ∗ … ∗ (𝑛 – 1) ∗ 𝑛 Например (2а) 5! = 1 ∗ 2 ∗ 3 ∗ 4 ∗ 5 = 120 По определению: 1! = 1; 0! = 1. Функция в Excel =ФАКТР(n). Факториал растет очень быстро. Существенно быстрее экспоненты (рис. 3). Рис. 3. Расчет числа перестановок без повторений с помощью факториала Перестановки с повторениями Если в основном n множестве не все элементы разные, то число перестановок будет меньше n! Например, если наше множество состоит из трех яблок и одной груши, то всего возможно 4 перестановки (рис. 4). Груша может быть первой, второй, третьей или четвертой, а яблоки неразличимы). Рис. 4. Перестановки с повторениями (картинка найдена здесь ) В общем случае, можно сказать: последовательность длины n, составленная из k разных символов, первый из которых повторяется n 1 раз, второй – n 2 раз, третий – n 3 раз, …, k-й – n k раз (где n 1 + n 2 + … + n k = n) называется перестановкой с повторениями из n элементов. (3) 𝑃̅(𝑛 1 , 𝑛 2 , … , 𝑛 𝑘 ) = 𝑛! 𝑛 1 ! ∙ 𝑛 2 ! ∙ … ∙ 𝑛 𝑘 ! Пример. Сколько различных пятибуквенных слов можно составить из букв слова «манна»? Решение. Буквы а и н повторяются 2 раза, а буква м один раз. (3а) 𝑃̅(2,2,1) = 5! 2! ∙ 2! ∙ 1! = 30 Размещение без повторений Размещением из n элементов по m называется упорядоченный набор из m различных элементов, выбранных из n-элементного множества (все элементы множества уникальны; позиции элементов в выборке важны). Число размещений обозначается 𝐴 𝑛 𝑚 от arrangement. (4) 𝐴 𝑛 𝑚 = 𝑛 ∙ (𝑛– 1) ∙ (𝑛– 2) ∙ … ∙ (𝑛– 𝑚 + 1) = 𝑛! (𝑛 – 𝑚)! Например, два элемента из трех можно выбрать и расположить шестью способами (рис. 4): (4а) 𝐴 3 2 = 3 ∙ 2 = 6 или 𝐴 3 2 = 3! (3 – 2)! = 3! 1! = 1 ∙ 2 ∙ 3 1 = 6 Рис. 5. Размещение без повторений (картинка из презентации ) Если m = n количество элементов совпадает с количеством имеющихся мест для размещения. Знаменатель в формуле (4) превращается в 0! = 1. Остается только числитель n! А это – изученная выше перестановка без повторений; см. формулу (1). Название функции в Excel несколько обескураживает. Но... что поделаешь: =ПЕРЕСТ(n;m) Рис. 6. Размещение без повторений; обратите внимание на смешанные ссылки, которые позволяют протянуть формулу на всю таблицу Размещение с повторениями Размещение с повторениями по смыслу отличается от перестановок с повторением. Перестановки с повторением – это операция над множеством, которое состоит из нескольких видов элементов, так что каждый вид представлен несколькими одинаковыми элементами. Размещение с повторениями – выборки из множества с возвращением выбранного элемента назад перед каждым новым выбором. Например, если у вас множество, включающее грушу, яблоко и лимон, и вам нужно выбрать два элемента, так что после первого выбора вы возвращаете выбранный предмет назад, то существует девять различных комбинаций (рис. 7). Рис. 7. Размещение с повторениями В общем случае размещение с повторениями или выборка с возвращением – это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз. По правилу умножения количество размещений с повторениями из n по k: (5) 𝐴 𝑛 𝑘 ̅̅̅̅ = 𝑛 𝑘 Задача. Сколько различных номеров можно составить в одном коде региона? Подсказка. В номере используется 12 букв алфавита, также существующих и в латинском алфавите (А, В, Е, К, М, Н, О, Р, С, Т, У, Х). Рис. 8. Номер автомобиля Решение. Можно воспользоваться формулой для размещения с повторениями: (5а) Число номеров = 10 3 ∙ 12 3 = 1 728 000 Каждую цифру можно выбрать 10 способами, а всего цифр 3, при этом они могут повторяться, и их порядок важен. Каждую букву можно выбрать 12 способами, при этом буквы могут повторяться, и их порядок важен. Сочетания без повторений Сочетаниями из n множества по m элементов называются комбинации, составленные из данных n элементов по m элементов, которые различаются хотя бы одним элементом (в сочетаниях не учитывается порядок элементов). (6) С 𝑛 𝑚 = 𝑛! 𝑚! ∙ (𝑛 – 𝑚)! Например, два элемента из 4 сочетаются 6 способами (порядок следования не важен): (6а) С 4 2 = 4! 2! ∙ (4 – 2)! = 1 ∙ 2 ∙ 3 ∙ 4 1 ∙ 2 ∙ 1 ∙ 2 = 6 Рис. 9. Сочетания без повторений из 4 по 2 Сочетания без повторений образуют знаменитый треугольник Паскаля (рис. 10). В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси. Числа в строках, составляющие треугольник Паскаля, являются сочетаниями (7) С 𝑛 𝑚 = 𝑛! 𝑚! ∙ (𝑛 – 𝑚)! где n – номер строки, m – номер элемента в строке, начиная с нулевого. Например, в строке 7: (7а) С 7 0 = 7! 0! ∙ (7 – 0)! = 1; С 7 1 = 7! 1! ∙ (7 – 1)! = 7; С 7 2 = 7! 2! ∙ (7 – 2)! = 6 ∙ 7 2 = 21 С 7 3 = 7! 3! ∙ (7 – 3)! = 5 ∙ 6 ∙ 7 2 ∙ 3 = 35; С 7 4 = 7! 4! ∙ (7 – 4)! = 4 ∙ 5 ∙ 6 ∙ 7 2 ∙ 3 ∙ 4 = 35; … Рис. 10. Треугольник Паскаля В Excel используется функция =ЧИСЛКОМБ(n;m). Сочетания с повторениями Сочетания с повторениями по смыслу похожи на размещение с повторениями – это выборки из множества с возвращением выбранного элемента назад перед каждым новым выбором. При этом порядок в выборке не важен. Например, два предмета из четырех можно выбрать 10 способами, если после каждого выбора предмет возвращается назад (рис. 11). Рис. 11. Сочетания с повторениями В общем случае, число сочетаний с повторениями: (8) С 𝑛 𝑘 ̅̅̅̅ = (𝑛 + 𝑘 – 1)! 𝑘! ∙ (𝑛 – 1)! Для нашего примера с фруктами (8а) С 4 2 ̅̅̅̅ = (4 + 2 – 1)! 2! ∙ (4 – 1)! = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 1 ∙ 2 ∙ 1 ∙ 2 ∙ 3 = 10 В Excel для подсчета числа сочетаний с повторениями используется функция =ЧИСЛКОМБА(n;m). В нашем примере =ЧИСЛКОМБА(4;2) = 10. |