Как сделать комбинаторику в excel

Как сделать комбинаторику в excel?

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

Комбинаторика — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения элементов) и отношения на них. Термин комбинаторика был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». Excel поддерживает ряд функций комбинаторики. Чтобы разобраться, какую формулу использовать, следует ответить на ряд вопросов:

Как сделать комбинаторику в excel

Рис. 1. Дерево решений, какую формулу комбинаторики использовать

Скачать заметку в формате Word или pdf, примеры в формате Excel

Перестановки без повторений

Возьмем несколько различных элементов (предметов) и будем переставлять их всевозможными способами, оставляя неизменным их число и меняя только их порядок (рис. 2). Каждая из получившихся таким образом комбинаций носит название перестановки. Перестановкой из n элементов называется упорядоченное множество, составленное из всех элементов множества.

Как сделать комбинаторику в excel

Рис. 2. Перестановки (картинка взята здесь)

Если все n элементы разные, то число перестановок обозначается Pn от perturbation.

Как сделать комбинаторику в excel

С другой стороны, произведение n первых натуральных чисел называется n-факториал и обозначается n!

По определению: 1! = 1; 0! = 1.

Функция в Excel =ФАКТР(n). Факториал растет очень быстро. Существенно быстрее экспоненты (рис. 3).

Как сделать комбинаторику в excel

Рис. 3. Расчет числа перестановок без повторений с помощью факториала

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

Если в основном n множестве не все элементы разные, то число перестановок будет меньше n! Например, если наше множество состоит из трех яблок и одной груши, то всего возможно 4 перестановки (рис. 4). Груша может быть первой, второй, третьей или четвертой, а яблоки неразличимы).

Рис. 4. Перестановки с повторениями (картинка найдена здесь)

В общем случае, можно сказать: последовательность длины n, составленная из k разных символов, первый из которых повторяется n1 раз, второй – n2 раз, третий – n3 раз, …, k-й – nk раз (где n1 + n2 + … + nk = n) называется перестановкой с повторениями из n элементов.

Как сделать комбинаторику в excel

Пример. Сколько различных пятибуквенных слов можно составить из букв слова «манна»?

Решение. Буквы а и н повторяются 2 раза, а буква м один раз.

Размещение без повторений

Размещением из n элементов по m называется упорядоченный набор из m различных элементов, выбранных из n-элементного множества (все элементы множества уникальны; позиции элементов в выборке важны). Число размещений обозначается от arrangement.

Как сделать комбинаторику в excel

Например, два элемента из трех можно выбрать и расположить шестью способами (рис. 4):

Как сделать комбинаторику в excel

Рис. 5. Размещение без повторений (картинка из презентации)

Если m = n количество элементов совпадает с количеством имеющихся мест для размещения. Знаменатель в формуле (4) превращается в 0! = 1. Остается только числитель n! А это – изученная выше перестановка без повторений; см. формулу (1).

Название функции в Excel несколько обескураживает. Но… что поделаешь: =ПЕРЕСТ(n;m)

Как сделать комбинаторику в excel

Рис. 6. Размещение без повторений; обратите внимание на смешанные ссылки, которые позволяют протянуть формулу на всю таблицу

Размещение с повторениями

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

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

Как сделать комбинаторику в excel

Рис. 7. Размещение с повторениями

В общем случае размещение с повторениями или выборка с возвращением – это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз. По правилу умножения количество размещений с повторениями из n по k:

Задача. Сколько различных номеров можно составить в одном коде региона?

Подсказка. В номере используется 12 букв алфавита, также существующих и в латинском алфавите (А, В, Е, К, М, Н, О, Р, С, Т, У, Х).

Как сделать комбинаторику в excel

Рис. 8. Номер автомобиля

Решение. Можно воспользоваться формулой для размещения с повторениями:

Как сделать комбинаторику в excel

Каждую цифру можно выбрать 10 способами, а всего цифр 3, при этом они могут повторяться, и их порядок важен. Каждую букву можно выбрать 12 способами, при этом буквы могут повторяться, и их порядок важен.

Сочетания без повторений

Сочетаниями из n множества по m элементов называются комбинации, составленные из данных n элементов по m элементов, которые различаются хотя бы одним элементом (в сочетаниях не учитывается порядок элементов).

Например, два элемента из 4 сочетаются 6 способами (порядок следования не важен):

Как сделать комбинаторику в excel Как сделать комбинаторику в excel Как сделать комбинаторику в excel

Как сделать комбинаторику в excel

Рис. 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 можно вычислить по формуле:

Как сделать комбинаторику в excel

Например, количество 4-х элементных комбинаций из 6 чисел <1; 2; 3; 4; 5; 6>равно 15=6!/(4!(6-4)!)

Примечание : Для Сочетаний из n элементов по k также используется и другая запись: Как сделать комбинаторику в excel

Очевидно, что k меньше или равно n, т.к. нельзя выбрать из множества элементов n больше элементов, чем в нем содержится (предполагается, что элементы после выбора обратно не возвращаются). При k=n количество сочетаний всегда равно 1.

Примечание : О Сочетаниях с повторениями (с возвращением элементов) можно прочитать в статье Сочетания с повторениями: Комбинаторика в MS EXCEL

Вывод всех комбинаций Сочетаний

В файле примера созданы формулы для вывода всех Сочетаний для заданных n и k.

Задавая с помощью элементов управления Счетчик количество элементов множества (n) и количество элементов, которое мы из него выбираем (k), с помощью формул можно вывести все Сочетания.

Как сделать комбинаторику в excel

В файле примера не забывайте увеличивать количество строк с формулами, чтобы поместились все ваши комбинации. Для этого выделите последние ячейки с формулами (сочетание №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), …

Как сделать комбинаторику в excel

Выставив в ячейках В5 и В6 значения 7 и 4 соответственно, определим все варианты размещений машин в автовозе (см. столбцы AJ:AM).

Как сделать комбинаторику в excel

Источник

Размещения c повторениями: Комбинаторика в EXCEL

Подсчитаем в MS EXCEL количество Размещений с повторениями из n по k (выборка с возвращением). Также с помощью формул выведем на лист соответствующие варианты Размещений (английский перевод термина: sequence with repetition или permutations with repetition).

Как сделать комбинаторику в excel

Примечание : О Размещениях без повторений (т.е. без возвращения элементов) можно прочитать в статье Размещения без повторений: Комбинаторика в MS EXCEL

Как сделать комбинаторику в excel

Как сделать комбинаторику в excel

В файле примера MS EXCEL приведен подсчет количества Размещений с повторениями и создана универсальная формула для вывода всех размещений для заданных n и k.

Задавая с помощью элемента управления Счетчик количество элементов множества (n) и количество элементов, которое мы из него выбираем (k), с помощью формулы массива можно вывести все размещения с повторениями.

Как сделать комбинаторику в excel

Задача

Богатый автолюбитель решил сделать подарки своим 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

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

Комбинаторика — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения элементов) и отношения на них. Термин комбинаторика был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». Excel поддерживает ряд функций комбинаторики. Чтобы разобраться, какую формулу использовать, следует ответить на ряд вопросов:

Как сделать комбинаторику в excel

Рис. 1. Дерево решений, какую формулу комбинаторики использовать

Скачать заметку в формате Word или pdf, примеры в формате Excel

Перестановки без повторений

Возьмем несколько различных элементов (предметов) и будем переставлять их всевозможными способами, оставляя неизменным их число и меняя только их порядок (рис. 2). Каждая из получившихся таким образом комбинаций носит название перестановки. Перестановкой из n элементов называется упорядоченное множество, составленное из всех элементов множества.

Как сделать комбинаторику в excel

Рис. 2. Перестановки (картинка взята здесь)

Если все n элементы разные, то число перестановок обозначается Pn от perturbation.

Как сделать комбинаторику в excel

С другой стороны, произведение n первых натуральных чисел называется n-факториал и обозначается n!

Как сделать комбинаторику в excel

Как сделать комбинаторику в excel

По определению: 1! = 1; 0! = 1.

Функция в Excel =ФАКТР(n). Факториал растет очень быстро. Существенно быстрее экспоненты (рис. 3).

Как сделать комбинаторику в excel

Рис. 3. Расчет числа перестановок без повторений с помощью факториала

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

Если в основном n множестве не все элементы разные, то число перестановок будет меньше n! Например, если наше множество состоит из трех яблок и одной груши, то всего возможно 4 перестановки (рис. 4). Груша может быть первой, второй, третьей или четвертой, а яблоки неразличимы).

Как сделать комбинаторику в excel

Рис. 4. Перестановки с повторениями (картинка найдена здесь)

В общем случае, можно сказать: последовательность длины n, составленная из k разных символов, первый из которых повторяется n1 раз, второй – n2 раз, третий – n3 раз, …, k-й – nk раз (где n1 + n2 + … + nk = n) называется перестановкой с повторениями из n элементов.

Как сделать комбинаторику в excel

Пример. Сколько различных пятибуквенных слов можно составить из букв слова «манна»?

Решение. Буквы а и н повторяются 2 раза, а буква м один раз.

Как сделать комбинаторику в excel

Размещение без повторений

Размещением из n элементов по m называется упорядоченный набор из m различных элементов, выбранных из n-элементного множества (все элементы множества уникальны; позиции элементов в выборке важны). Число размещений обозначается Как сделать комбинаторику в excelот arrangement.

Как сделать комбинаторику в excel

Например, два элемента из трех можно выбрать и расположить шестью способами (рис. 4):

Как сделать комбинаторику в excel

Как сделать комбинаторику в excel

Рис. 5. Размещение без повторений (картинка из презентации)

Если m = n количество элементов совпадает с количеством имеющихся мест для размещения. Знаменатель в формуле (4) превращается в 0! = 1. Остается только числитель n! А это – изученная выше перестановка без повторений; см. формулу (1).

Название функции в Excel несколько обескураживает. Но… что поделаешь: =ПЕРЕСТ(n;m)

Как сделать комбинаторику в excel

Рис. 6. Размещение без повторений; обратите внимание на смешанные ссылки, которые позволяют протянуть формулу на всю таблицу

Размещение с повторениями

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

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

Как сделать комбинаторику в excel

Рис. 7. Размещение с повторениями

В общем случае размещение с повторениями или выборка с возвращением – это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз. По правилу умножения количество размещений с повторениями из n по k:

Как сделать комбинаторику в excel

В Excel используется функция ПЕРЕСТА(n;k).

Задача. Сколько различных номеров можно составить в одном коде региона?

Подсказка. В номере используется 12 букв алфавита, также существующих и в латинском алфавите (А, В, Е, К, М, Н, О, Р, С, Т, У, Х).

Как сделать комбинаторику в excel

Решение. Можно воспользоваться формулой для размещения с повторениями:

Как сделать комбинаторику в excel

Каждую цифру можно выбрать 10 способами, а всего цифр 3, при этом они могут повторяться, и их порядок важен. Каждую букву можно выбрать 12 способами, при этом буквы могут повторяться, и их порядок важен.

Сочетания без повторений

Сочетаниями из n множества по m элементов называются комбинации, составленные из данных n элементов по m элементов, которые различаются хотя бы одним элементом (в сочетаниях не учитывается порядок элементов).

Как сделать комбинаторику в excel

Например, два элемента из 4 сочетаются 6 способами (порядок следования не важен):

Как сделать комбинаторику в excel

Как сделать комбинаторику в excel

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

Как сделать комбинаторику в excel

где n – номер строки, m – номер элемента в строке, начиная с нулевого. Например, в строке 7:

Как сделать комбинаторику в excel

Как сделать комбинаторику в excel

Рис. 10. Треугольник Паскаля; чтобы увеличить изображение кликните на нем правой кнопкой мыши и выберите Открыть картинку в новой вкладке

В Excel используется функция =ЧИСЛКОМБ(n;m).

Сочетания с повторениями

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

Например, два предмета из четырех можно выбрать 10 способами, если после каждого выбора предмет возвращается назад (рис. 11).

Как сделать комбинаторику в excel

В общем случае, число сочетаний с повторениями:

Как сделать комбинаторику в excel

Для нашего примера с фруктами

Как сделать комбинаторику в excel

В Excel для подсчета числа сочетаний с повторениями используется функция =ЧИСЛКОМБА(n;m). В нашем примере =ЧИСЛКОМБА(4;2) = 10.

Презентация по теме «Комбинаторика в Excel»

Добавляйте авторские материалы и получите призы от Инфоурок

Еженедельный призовой фонд 100 000 Р

Как сделать комбинаторику в excel Как сделать комбинаторику в excelКак сделать комбинаторику в excel

Как сделать комбинаторику в excel

Описание презентации по отдельным слайдам:

Лавлинский М.В., 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

Как сделать комбинаторику в excel

Как сделать комбинаторику в excel

Как сделать комбинаторику в excel

Как сделать комбинаторику в excel

Номер материала: ДБ-555371

Не нашли то что искали?

Вам будут интересны эти курсы:

Как сделать комбинаторику в excel

Как сделать комбинаторику в excel

Как сделать комбинаторику в excel

Как сделать комбинаторику в excel

Как сделать комбинаторику в excel

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение редакции может не совпадать с точкой зрения авторов.

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

Источник

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *