Как сделать комбинаторику в excel
Как сделать комбинаторику в excel?
Комбинаторика в Excel
Комбинаторика — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения элементов) и отношения на них. Термин комбинаторика был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». Excel поддерживает ряд функций комбинаторики. Чтобы разобраться, какую формулу использовать, следует ответить на ряд вопросов:
Рис. 1. Дерево решений, какую формулу комбинаторики использовать
Скачать заметку в формате Word или pdf, примеры в формате Excel
Перестановки без повторений
Возьмем несколько различных элементов (предметов) и будем переставлять их всевозможными способами, оставляя неизменным их число и меняя только их порядок (рис. 2). Каждая из получившихся таким образом комбинаций носит название перестановки. Перестановкой из n элементов называется упорядоченное множество, составленное из всех элементов множества.
Рис. 2. Перестановки (картинка взята здесь)
Если все n элементы разные, то число перестановок обозначается Pn от perturbation.
С другой стороны, произведение n первых натуральных чисел называется n-факториал и обозначается n!
По определению: 1! = 1; 0! = 1.
Функция в Excel =ФАКТР(n). Факториал растет очень быстро. Существенно быстрее экспоненты (рис. 3).
Рис. 3. Расчет числа перестановок без повторений с помощью факториала
Перестановки с повторениями
Если в основном n множестве не все элементы разные, то число перестановок будет меньше n! Например, если наше множество состоит из трех яблок и одной груши, то всего возможно 4 перестановки (рис. 4). Груша может быть первой, второй, третьей или четвертой, а яблоки неразличимы).
Рис. 4. Перестановки с повторениями (картинка найдена здесь)
В общем случае, можно сказать: последовательность длины n, составленная из k разных символов, первый из которых повторяется n1 раз, второй – n2 раз, третий – n3 раз, …, k-й – nk раз (где n1 + n2 + … + nk = n) называется перестановкой с повторениями из n элементов.
Пример. Сколько различных пятибуквенных слов можно составить из букв слова «манна»?
Решение. Буквы а и н повторяются 2 раза, а буква м один раз.
Размещение без повторений
Размещением из n элементов по m называется упорядоченный набор из m различных элементов, выбранных из n-элементного множества (все элементы множества уникальны; позиции элементов в выборке важны). Число размещений обозначается от arrangement.
Например, два элемента из трех можно выбрать и расположить шестью способами (рис. 4):
Рис. 5. Размещение без повторений (картинка из презентации)
Если m = n количество элементов совпадает с количеством имеющихся мест для размещения. Знаменатель в формуле (4) превращается в 0! = 1. Остается только числитель n! А это – изученная выше перестановка без повторений; см. формулу (1).
Название функции в Excel несколько обескураживает. Но… что поделаешь: =ПЕРЕСТ(n;m)
Рис. 6. Размещение без повторений; обратите внимание на смешанные ссылки, которые позволяют протянуть формулу на всю таблицу
Размещение с повторениями
Размещение с повторениями по смыслу отличается от перестановок с повторением. Перестановки с повторением – это операция над множеством, которое состоит из нескольких видов элементов, так что каждый вид представлен несколькими одинаковыми элементами. Размещение с повторениями – выборки из множества с возвращением выбранного элемента назад перед каждым новым выбором.
Например, если у вас множество, включающее грушу, яблоко и лимон, и вам нужно выбрать два элемента, так что после первого выбора вы возвращаете выбранный предмет назад, то существует девять различных комбинаций (рис. 7).
Рис. 7. Размещение с повторениями
В общем случае размещение с повторениями или выборка с возвращением – это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз. По правилу умножения количество размещений с повторениями из n по k:
Задача. Сколько различных номеров можно составить в одном коде региона?
Подсказка. В номере используется 12 букв алфавита, также существующих и в латинском алфавите (А, В, Е, К, М, Н, О, Р, С, Т, У, Х).
Рис. 8. Номер автомобиля
Решение. Можно воспользоваться формулой для размещения с повторениями:
Каждую цифру можно выбрать 10 способами, а всего цифр 3, при этом они могут повторяться, и их порядок важен. Каждую букву можно выбрать 12 способами, при этом буквы могут повторяться, и их порядок важен.
Сочетания без повторений
Сочетаниями из n множества по m элементов называются комбинации, составленные из данных n элементов по m элементов, которые различаются хотя бы одним элементом (в сочетаниях не учитывается порядок элементов).
Например, два элемента из 4 сочетаются 6 способами (порядок следования не важен):
Рис. 9. Сочетания без повторений из 4 по 2
Сочетания без повторений образуют знаменитый треугольник Паскаля (рис. 10). В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси. Числа в строках, составляющие треугольник Паскаля, являются сочетаниями
где n – номер строки, m – номер элемента в строке, начиная с нулевого. Например, в строке 7:
Рис. 10. Треугольник Паскаля; чтобы увеличить изображение кликните на нем правой кнопкой мыши и выберите Открыть картинку в новой вкладке
В Excel используется функция =ЧИСЛКОМБ(n;m).
Сочетания с повторениями
Сочетания с повторениями по смыслу похожи на размещение с повторениями – это выборки из множества с возвращением выбранного элемента назад перед каждым новым выбором. При этом порядок в выборке не важен.
Например, два предмета из четырех можно выбрать 10 способами, если после каждого выбора предмет возвращается назад (рис. 11).
Рис. 11. Сочетания с повторениями
В общем случае, число сочетаний с повторениями:
Для нашего примера с фруктами
В Excel для подсчета числа сочетаний с повторениями используется функция =ЧИСЛКОМБА(n;m). В нашем примере =ЧИСЛКОМБА(4;2) = 10.
Калькулятор ниже предназначен для генерации всех сочетаний из n по m элементов.
Число таких сочетаний, как можно рассчитать с помощью калькулятора Элементы комбинаторики. Перестановки, размещения, сочетания.
Описание алгоритма генерации под калькулятором.
Алгоритм
Комбинации генерируются в лексикографическом порядке. Алгоритм работает с порядковыми индексами элементов множества.
Рассмотрим алгоритм на примере.
Для простоты изложения рассмотрим множество из пяти элементов, индексы в котором начинаются с 1, а именно, 1 2 3 4 5.
Требуется сгенерировать все комбинации размера m = 3.
Сначала инициализуется первая комбинация заданного размера m — индексы в порядке возрастания
1 2 3 Далее проверяется последний элемент, т. е. i = 3. Если его значение меньше n — m + i, то он инкрементируется на 1.
1 2 4 Снова проверяется последний элемент, и опять он инкрементируется.
1 2 5 Теперь значение элемента равно максимально возможному: n — m + i = 5 — 3 + 3 = 5, проверяется предыдущий элемент с i = 2.
Если его значение меньше n — m + i, то он инкрементируется на 1, а для всех следующих за ним элементов значение приравнивается к значению предыдущего элемента плюс 1.
1 (2+1)3 (3+1)4 = 1 3 4
Далее снова идет проверка для i = 3.
1 3 5 Затем — проверка для i = 2.
1 4 5 Потом наступает очередь i = 1.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
И далее,
2 3 52 4 53 4 5 — последнее сочетание, так как все его элементы равны n — m + i.
Сочетания без повторений: Комбинаторика в EXCEL
Подсчитаем в MS EXCEL количество сочетаний из n элементов по k. С помощью формул выведем на лист все варианты сочетаний (английский перевод термина: Combinations without repetition).
Сочетаниями из n различных элементов по k элементов называются комбинации, которые отличаются хотя бы одним элементом. Например, ниже перечислены ВСЕ 3-х элементные сочетания, взятые из множества, состоящего из 5 элементов <1; 2; 3; 4; 5>:
(1; 2; 3); (1; 2; 4); (1; 2; 5); (1; 3; 4); (1; 3; 5); (1; 4; 5); (2; 3; 4); (2; 3; 5); (2; 4; 5); (3; 4; 5)
Отличие Сочетаний от Размещений
Подсчет количества Сочетаний
Число всех Сочетаний из n элементов по k можно вычислить по формуле:
Например, количество 4-х элементных комбинаций из 6 чисел <1; 2; 3; 4; 5; 6>равно 15=6!/(4!(6-4)!)
Примечание : Для Сочетаний из n элементов по k также используется и другая запись: 
Очевидно, что k меньше или равно n, т.к. нельзя выбрать из множества элементов n больше элементов, чем в нем содержится (предполагается, что элементы после выбора обратно не возвращаются). При k=n количество сочетаний всегда равно 1.
Примечание : О Сочетаниях с повторениями (с возвращением элементов) можно прочитать в статье Сочетания с повторениями: Комбинаторика в MS EXCEL
Вывод всех комбинаций Сочетаний
В файле примера созданы формулы для вывода всех Сочетаний для заданных n и k.
Задавая с помощью элементов управления Счетчик количество элементов множества (n) и количество элементов, которое мы из него выбираем (k), с помощью формул можно вывести все Сочетания.
В файле примера не забывайте увеличивать количество строк с формулами, чтобы поместились все ваши комбинации. Для этого выделите последние ячейки с формулами (сочетание №330) и скопируйте их вниз на нужно количество строк. При увеличении строк с формулами размер файла быстро растет, а скорости пересчета листа падает. Если строк 4 тысячи, то размер файла составляет около 2 Мб.
Задача
Автовоз может перевозить по 4 легковые машины. Необходимо перевезти 7 разных машин (LADA Granta, Hyundai Solaris, KIA Rio, Renault Duster, Lada Kalina, Volkswagen Polo, Lada Largus). Сколькими различными способами можно заполнить первый автовоз? Конкретное место машины в автовозе не важно.
Нам нужно определить число Сочетаний 7 машин на 4-х местах автовоза. Т.е. n=7, а k=4. Оказывается, что таких вариантов =ЧИСЛКОМБ(7;4) равно 35.
Произвольным образом сопоставим маркам машин числовые значения и сделаем сокращения названий марок: LADA Granta (LG=1), Hyundai Solaris (HS=2), …
Выставив в ячейках В5 и В6 значения 7 и 4 соответственно, определим все варианты размещений машин в автовозе (см. столбцы AJ:AM).
Размещения c повторениями: Комбинаторика в EXCEL
Подсчитаем в MS EXCEL количество Размещений с повторениями из n по k (выборка с возвращением). Также с помощью формул выведем на лист соответствующие варианты Размещений (английский перевод термина: sequence with repetition или permutations with repetition).
Примечание : О Размещениях без повторений (т.е. без возвращения элементов) можно прочитать в статье Размещения без повторений: Комбинаторика в MS EXCEL
В файле примера MS EXCEL приведен подсчет количества Размещений с повторениями и создана универсальная формула для вывода всех размещений для заданных n и k.
Задавая с помощью элемента управления Счетчик количество элементов множества (n) и количество элементов, которое мы из него выбираем (k), с помощью формулы массива можно вывести все размещения с повторениями.
Задача
Богатый автолюбитель решил сделать подарки своим 3 любимым родственницам: жене, маме и сестре. К сожалению, женщины не смогли однозначно определиться с марками машин, но указали 4 марки, которые им всем троим нравятся в одинаковой степени: Volkswagen Polo, Hyundai Solaris, KIA Rio и Renault Duster. Автолюбитель решает довериться случаю и делает 4 записки, с указанием марок машин. Все записки кладет в мешок. После каждого выбора, автолюбитель кладет выбранную записку обратно в мешок. Определить число различных вариантов распределения марок между родственницами.
Нам нужно определить число размещений с повторениями 4-х марок машин 3-м родственницам. Т.е. n=4, а k=3. Оказывается, что таких вариантов =4^3 равно 64.
По аналогии с решением задачи в статье Размещений без повторений сопоставим произвольным образом маркам машин числовые значения и сделаем сокращения названий марок: Hyundai Solaris (HS=1), KIA Rio (KR=2), …
Выставив в ячейках В5 и В6 значения 4 и 3 соответственно, определим все варианты размещений.
Как сделать комбинаторику в excel?
Комбинаторика в Excel
Комбинаторика в Excel
Комбинаторика — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения элементов) и отношения на них. Термин комбинаторика был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». Excel поддерживает ряд функций комбинаторики. Чтобы разобраться, какую формулу использовать, следует ответить на ряд вопросов:
Рис. 1. Дерево решений, какую формулу комбинаторики использовать
Скачать заметку в формате Word или pdf, примеры в формате Excel
Перестановки без повторений
Возьмем несколько различных элементов (предметов) и будем переставлять их всевозможными способами, оставляя неизменным их число и меняя только их порядок (рис. 2). Каждая из получившихся таким образом комбинаций носит название перестановки. Перестановкой из n элементов называется упорядоченное множество, составленное из всех элементов множества.
Рис. 2. Перестановки (картинка взята здесь)
Если все n элементы разные, то число перестановок обозначается Pn от perturbation.
С другой стороны, произведение n первых натуральных чисел называется n-факториал и обозначается n!
По определению: 1! = 1; 0! = 1.
Функция в Excel =ФАКТР(n). Факториал растет очень быстро. Существенно быстрее экспоненты (рис. 3).
Рис. 3. Расчет числа перестановок без повторений с помощью факториала
Перестановки с повторениями
Если в основном n множестве не все элементы разные, то число перестановок будет меньше n! Например, если наше множество состоит из трех яблок и одной груши, то всего возможно 4 перестановки (рис. 4). Груша может быть первой, второй, третьей или четвертой, а яблоки неразличимы).
Рис. 4. Перестановки с повторениями (картинка найдена здесь)
В общем случае, можно сказать: последовательность длины n, составленная из k разных символов, первый из которых повторяется n1 раз, второй – n2 раз, третий – n3 раз, …, k-й – nk раз (где n1 + n2 + … + nk = n) называется перестановкой с повторениями из n элементов.
Пример. Сколько различных пятибуквенных слов можно составить из букв слова «манна»?
Решение. Буквы а и н повторяются 2 раза, а буква м один раз.
Размещение без повторений
Размещением из n элементов по m называется упорядоченный набор из m различных элементов, выбранных из n-элементного множества (все элементы множества уникальны; позиции элементов в выборке важны). Число размещений обозначается от arrangement.
Например, два элемента из трех можно выбрать и расположить шестью способами (рис. 4):
Рис. 5. Размещение без повторений (картинка из презентации)
Если m = n количество элементов совпадает с количеством имеющихся мест для размещения. Знаменатель в формуле (4) превращается в 0! = 1. Остается только числитель n! А это – изученная выше перестановка без повторений; см. формулу (1).
Название функции в Excel несколько обескураживает. Но… что поделаешь: =ПЕРЕСТ(n;m)
Рис. 6. Размещение без повторений; обратите внимание на смешанные ссылки, которые позволяют протянуть формулу на всю таблицу
Размещение с повторениями
Размещение с повторениями по смыслу отличается от перестановок с повторением. Перестановки с повторением – это операция над множеством, которое состоит из нескольких видов элементов, так что каждый вид представлен несколькими одинаковыми элементами. Размещение с повторениями – выборки из множества с возвращением выбранного элемента назад перед каждым новым выбором.
Например, если у вас множество, включающее грушу, яблоко и лимон, и вам нужно выбрать два элемента, так что после первого выбора вы возвращаете выбранный предмет назад, то существует девять различных комбинаций (рис. 7).
Рис. 7. Размещение с повторениями
В общем случае размещение с повторениями или выборка с возвращением – это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз. По правилу умножения количество размещений с повторениями из n по k:
В Excel используется функция ПЕРЕСТА(n;k).
Задача. Сколько различных номеров можно составить в одном коде региона?
Подсказка. В номере используется 12 букв алфавита, также существующих и в латинском алфавите (А, В, Е, К, М, Н, О, Р, С, Т, У, Х).
Решение. Можно воспользоваться формулой для размещения с повторениями:
Каждую цифру можно выбрать 10 способами, а всего цифр 3, при этом они могут повторяться, и их порядок важен. Каждую букву можно выбрать 12 способами, при этом буквы могут повторяться, и их порядок важен.
Сочетания без повторений
Сочетаниями из n множества по m элементов называются комбинации, составленные из данных n элементов по m элементов, которые различаются хотя бы одним элементом (в сочетаниях не учитывается порядок элементов).
Например, два элемента из 4 сочетаются 6 способами (порядок следования не важен):
Сочетания без повторений образуют знаменитый треугольник Паскаля (рис. 10). В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси. Числа в строках, составляющие треугольник Паскаля, являются сочетаниями
где n – номер строки, m – номер элемента в строке, начиная с нулевого. Например, в строке 7:
Рис. 10. Треугольник Паскаля; чтобы увеличить изображение кликните на нем правой кнопкой мыши и выберите Открыть картинку в новой вкладке
В Excel используется функция =ЧИСЛКОМБ(n;m).
Сочетания с повторениями
Сочетания с повторениями по смыслу похожи на размещение с повторениями – это выборки из множества с возвращением выбранного элемента назад перед каждым новым выбором. При этом порядок в выборке не важен.
Например, два предмета из четырех можно выбрать 10 способами, если после каждого выбора предмет возвращается назад (рис. 11).
В общем случае, число сочетаний с повторениями:
Для нашего примера с фруктами
В Excel для подсчета числа сочетаний с повторениями используется функция =ЧИСЛКОМБА(n;m). В нашем примере =ЧИСЛКОМБА(4;2) = 10.
Презентация по теме «Комбинаторика в Excel»
Добавляйте авторские материалы и получите призы от Инфоурок
Еженедельный призовой фонд 100 000 Р
Описание презентации по отдельным слайдам:
Лавлинский М.В., LavlinskiMV@mail.ru Бенуа Мандельброт (1924 — 2010) Создатель фрактальной геометрии Фрактал — математическое множество, обладающее свойством самоподобия Не должно судить о ценности научного открытия, исходя из причин его совершения.
I. Комбинаторные формулы в Excel Задача 1. [Перестановки] Функция в Excel: ФАКТР(n) #. Сколькими способами можно развесить 10 цветных шаров на гирлянде? Решение: =ФАКТР(10) Ответ: 3628800
Задача 2. [Размещения] Функция в Excel: ПЕРЕСТ(n, k) #. Сколькими способами можно расставить на полке 3 выбранных книги из 5 книг, имеющихся в наличии? Решение: =ПЕРЕСТ(5;3) Ответ: 60
Задача 3. [Сочетания] Функция в Excel: ЧИСЛКОМБ(n, k) #. Сколькими способами можно выбрать 3 книги из 5, имеющихся в наличии? Решение: =ЧИСЛКОМБ(5;3) Ответ: 10
II. Треугольник Паскаля Задача 4. [ЧИСЛКОМБ] При помощи Excel построить треугольник Паскаля. Решение: Способ основан на том, что треугольник Паскаля состоит из Алгоритм: 1) Задать начальные значения параметров n и k
2) Использовать функцию вычисления числа сочетания, учесть случай n 0. =ЕСЛИ($A2>=B$1;ЧИСЛКОМБ($A2;B$1);0)
Задача 4. [сумма верхнего и левого элемента] При помощи Excel построить треугольник Паскаля. Решение: Способ основан на использование прямоугольной ориентации треугольника Паскаля Алгоритм: В 1-ой строке и 1-ом столбце установить единицы В остальных ячейках сумма верхнего и левого элемента =B1+A2
III. Треугольник Серпинского (1915 год) Если в треугольнике Паскаля все нечётные числа окрасить в чёрный цвет, а чётные — в белый, то образуется треугольник Серпинского.
Задача 5. [связь треугольников Паскаля и Серпинского] При помощи Excel построить треугольник Серпинского. Алгоритм: Достаточно выписывать не коэффициенты, а только их четность. 1) Установить размер ячеек, 7 на 7 пикселей 2) Стать в ячейку B2 3) Выделить область B2:DY129 — для этого нажать Ctrl + G и в поле ссылка написать B2:DY129. 4) В строке формул написать: =ЕСЛИ(ИЛИ(СТРОКА()=2;СТОЛБЕЦ()=2);1;ОСТАТ(A2+B1;2)) 5) Нажать Ctrl + Enter, чтобы заполнить подобной формулой всю выделенную область 6) Осуществить условное форматирование: для значений ячеек равных 1 указать цвет ячейки. Возвращает номер строки Возвращает номер столбца
Домашнее задание Лицей ИГУ, liguirk.ru * Конспект «15_[ДЗ]Комбинаторика в Excel+Подготовка к КР.doc» КР «Элементы комбинаторики» Для любознательных: М. И. Бинимелис Басса — Новый взгляд на мир. Фрактальная геометрия (Мир математики Т. 10) — 2014
Номер материала: ДБ-555371
Не нашли то что искали?
Вам будут интересны эти курсы:
Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение редакции может не совпадать с точкой зрения авторов.
Ответственность за разрешение любых спорных моментов, касающихся самих материалов и их содержания, берут на себя пользователи, разместившие материал на сайте. Однако редакция сайта готова оказать всяческую поддержку в решении любых вопросов связанных с работой и содержанием сайта. Если Вы заметили, что на данном сайте незаконно используются материалы, сообщите об этом администрации сайта через форму обратной связи.