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

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

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

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

  1. Исходное множество содержит только уникальные элементы, или некоторые из них могут повторяться?
  2. Операция выполняется со всеми элементами множества, или только с некоторой выборкой из них?
  3. Важен ли порядок элементов в выборке?
  4. После выбора элемента мы его возвращаем назад?

Рис. 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 букв алфавита, также существующих и в латинском алфавите (А, В, Е, К, М, Н, О, Р, С, Т, У, Х).

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

Читать еще:  Как в excel сделать по горизонтали буквы?

Каждую цифру можно выбрать 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»

Устанавливая рекомендуемое программное обеспечение вы соглашаетесь
с лицензионным соглашением Яндекс.Браузера и настольного ПО Яндекса .

Курс повышения квалификации за 340 рублей!

Эмоциональное выгорание педагогов. Профилактика и способы преодоления

Международные дистанционные олимпиады «Эрудит III»

Доступно для всех учеников
1-11 классов и дошкольников

Рекордно низкий оргвзнос

по разным предметам школьной программы (отдельные задания для дошкольников)

Идёт приём заявок

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

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

Устанавливая рекомендуемое программное обеспечение вы соглашаетесь
с лицензионным соглашением Яндекс.Браузера и настольного ПО Яндекса .

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

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

  • Лавлинский Максим Викторович
  • Написать
  • 992
  • 14.06.2017

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

Международные дистанционные олимпиады «Эрудит III»

Доступно для всех учеников
1-11 классов и дошкольников

Рекордно низкий оргвзнос

по разным предметам школьной программы (отдельные задания для дошкольников)

Идёт приём заявок

Устанавливая рекомендуемое программное обеспечение вы соглашаетесь
с лицензионным соглашением Яндекс.Браузера и настольного ПО Яндекса .

  • 14.06.2017
  • 221
  • 14.06.2017
  • 821
  • 14.06.2017
  • 561
  • 14.06.2017
  • 676
  • 14.06.2017
  • 5118
  • 14.06.2017
  • 467
  • 14.06.2017
  • 132

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

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

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

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

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

Pers.narod.ru. Обучение. Excel: Считаем число перестановок и комбинаций

Перестановка Ч это любое множество или подмножество объектов или событий, в котором внутренний порядок имеет значение.

Как правило, перестановки считаются для заданного числа объектов, которые выбираются из общего числа объектов.

Традиционно, общее число объектов или событий обозначают N , выбираемое число объектов или событий — K , а число перестановок из N по K обозначают Pk,n . Существует формула, позволяющая легко определить число перестановок из N по K :

Здесь N! — факториал числа N , то есть, произведение вида 1*2*. *N .

В Excel считать перестановки очень удобно, не нужно даже вычислять факториалы:

Вместо N и K задаются целые положительные числа, N≥K .

Например, красный, синий и зелёный шарики можно переставить шестью способами:

Выбрать 2 рюмки из трёх, стоящих на столе, можно также шестью способами:

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

В этом смысле число всех возможных перестановок для множества из n различных элементов считается по формуле

Наши три рюмки можно переставить 6 способами, потому что 3!=3*2*1=6

Получается, что перестановки выбором всех элементов можно считать частным случаем размещения при n=k .

Кроме перестановок, в комбинаторике различают собственно комбинации или сочетания, в этой задаче считается число всех возможных сочетаний N объектов в группы по K элементов, причём порядок элементов в группе несущественен. В тех же обозначениях, формула для определения числа сочетаний по K объектов из N имеет вид

Очень часто число сочетаний из N по K обозначают как CN K .

В Excel число комбинаций считает функция

Значения N и K также должны быть целыми и положительными, N≥K

С этой точки зрения выбрать 2 рюмки из трёх можно всего тремя способами:

В этой статье — реализации основных комбинаторных алгоритмов на Паскале

Часть 2. Выборки с повторениями в Excel

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

Для выборок с повторениями основные комбинаторные формулы будут другими.

Пусть имеется выборка из n элементов, причем k элементов из них — одинаковые.

1. Число различных перестановок элементов такой выборки равно:

— число перестановок с k повторениями на множестве из n элементов.

Пример: на столе стоит 3 белых рюмки и 1 синяя. Сколько можно сделать различных выборок по 3 рюмки?

Читать еще:  Excel как сводную таблицу сделать обычной

Итак, имеем 4 рюмки, 3 из которых — одинаковые. Нам важен также порядок, в котором стоят рюмки. Получаем

Как быть, если «сортов»объектов больше двух? Ответ — в п. 4

Кстати, если порядок рюмок неразличим, у нас всего 2 варианта:

Подумайте — какие здесь работают комбинаторные законы? (см. замечание)

2. Сочетание с повторениями из n элементов по k — неупорядоченная выборка k элементов с возвращением из множества, содержащего n элементов:

— число различных сочетаний с повторениями из n элементов по k

Запись в Excel (общий вид):

Пример. В задаче про 4 рюмки мы теперь как бы возвращаем каждую вынутую рюмку на место, а значит, существует 20 способов выпить трижды с использованием этих четырёх рюмок:

3. Размещения с повторениями из n элементов по k — расположение n различных объектов по k различным ячейкам (местоположениям).

— число различных размещений с повторениями.

Пример — сколько различных 5-буквенных слов можно составить из букв «а» и «б»? У нас 2 объекта-буквы и 5 позиций, куда их можно размещать.

4. Наконец, верно обобщение первой формулы: число различных перестановок на множестве из n элементов, среди которых имеется
k1 элементов первого вида,
k2 элементов второго вида,
Е
kn элементов n-го вида
равно:

Общий вид формулы в Excel:

Пример — сколько различных 5-буквенных слов можно составить из 3 букв «а» и 2 букв «б»?

Обратите внимание на отличие — теперь число объектов (букв) каждого вида фиксировано!

Файл-пример с реализацией основных комбинаторных формул в Excel (21 Кб)

Замечание: об одной комбинаторной задаче

Хотя выше я и писал: Кстати, если порядок рюмок неразличим, у нас всего 2 варианта: Подумайте — какие здесь работают комбинаторные законы?

На самом деле, думать можно очень долго — под известные комбинаторные формулы такая задача просто не подходит. В общем виде условие можно сформулировать так:

Имеется N объектов, относящихся к L сортам.

Количество объектов каждого сорта известно и равно k1, k2, . kL , сумма ki=N .

Определить число различных сочетаний по M объектов из N , если объекты, относящиеся к одному сорту, считаются неразличимыми между собой.

Доступный пример: N=4, L=2, k1=3, k2=1, M=3 , например, имеем 3 белых рюмки и 1 синюю.

Число сочетаний по 3 из 4 равно в данном случае 2 — (Б, Б, Б) и (Б, Б, C) .

Формула числа сочетаний С4 3 даст 4, так как в ней все объекты считаются различимыми.

Под сочетания с повторениями, число которых здесь = 20, наш случай тем более не подходит — неразличимы-то только объекты одного вида.

Известная формула для числа различных перестановок на множестве из n элементов, среди которых имеется ki элементов i -го вида — нам тоже не подойдёт, у нас не перестановки.

Видимо, решать нужно так: найти число решений уравнения
x1 + . + xL = M
при ограничениях

Фактически, всё свелось к решению диофантова уравнения «в общем виде», а это невозможно (десятая проблема Гильберта, алгоритмическая неразрешимость которой считается доказанной). Похоже, что простой замкнутой формулы нет в принципе. Сложный расчёт с вложенными суммами можно сделать, но вычисление по такой формуле-монстру мало чем будет отличаться просто от перебора. Ещё существуют производящие функции — но практический счёт они никак не упростят. Лучше всего — рекуррентный подсчёт с конкретными числами.

Ну а само по себе приведённое уравнение вполне исследовано — например, известно, что диофантово уравнение x1 + . + xL = M имеет СM-1 L-1 различных решений в натуральных числах. Увы, нам это не поможет — скажем, имеем 3 белых рюмки, 2 синих, выбираем всего 2 (L=2, M=2, формула даёт C1 1 , на самом деле ответ = 3 (ББ, БС, СС).

Если учесть «вырожденные» решения уравнения, то есть, случаи, когда какого-то вида объектов нет в наборе, и соответствующий xi=0 , для него формула будет CM+L-1 L-1

Пример того, что и эта формула не подходит — 3 белых, 1 синяя, выбираем всего 3 (L=2, M=3): C4 1 =4

Это потому, что посчитались и те комбинации, для которых не хватит рюмок (2 последних):

Можно попытаться вычитать из СM+L-1 L-1 (число сочетаний с перестановками для нашей задачи) все лишние «цэшки», которые получаются при ki (если не хватает рюмок какого-то вида, их число меньше числа выбираемых M ), я попытался. Убив кучу времени, получил дикую и неуниверсальную при этом формулу, убедился в правильности выделенного красным 🙂

Вот здесь есть скрипт-решалка для одного класса линейных диофантовых уравнений.

Ссылка на основную публикацию
Adblock
detector