Как посчитать все возможные комбинации чисел в excel

Как посчитать все возможные комбинации чисел в 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 рюмки?

Итак, имеем 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 букв "б"?

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

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

Хотя выше я и писал:

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

Имеется 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 имеет С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 ), я попытался. Убив кучу времени, получил дикую и неуниверсальную при этом формулу, убедился в правильности выделенного красным 🙂

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

Функция ЧИСЛКОМБ

В этой статье описаны синтаксис формулы и использование функции ЧИСЛКОМБ в Microsoft Excel.

Описание

Возвращает количество комбинаций для заданного числа элементов. Функция ЧИСЛКОМБ используется для определения общего числа всех групп, которые можно составить из элементов данного множества.

Синтаксис

Аргументы функции ЧИСЛКОМБ описаны ниже.

Число — обязательный аргумент. Количество элементов.

Число_выбранных — обязательный аргумент. Количество элементов в каждой комбинации.

Замечания

Числовые аргументы усекаются до целых чисел.

Если хотя бы один из аргументов не является числом, то #VALUE! значение ошибки #ЗНАЧ!.

Пример

Скопируйте образец данных из следующей таблицы и вставьте их в ячейку A1 нового листа Excel. Чтобы отобразить результаты формул, выделите их и нажмите клавишу F2, а затем — клавишу ВВОД. При необходимости вы можете настроить ширину столбцов, чтобы видеть все данные.

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

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