Сочетания без повторений: Комбинаторика в EXCEL

history

Подсчитаем в 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)

Примечание : Это статья о подсчете количества сочетаний с использованием MS EXCEL. Теоретические основы советуем прочитать в специализированном учебнике. Изучать сочетания по этой статье - плохая идея.

Отличие Сочетаний от Размещений

В отличие от Размещений следующие 3-х элементные комбинации (1; 2; 3); (1; 3; 2); (2; 1; 3); (2; 1; 3); (3; 2; 1); (3; 1; 2) считаются одинаковыми, и в набор Сочетаний включается только одна из этих комбинаций. Очевидно, что для тех же n и k число Сочетаний всегда меньше чем число Размещений (так как при размещениях порядок важен, а для сочетаний - нет), причем в k! раз.

Подсчет количества Сочетаний



Число всех Сочетаний из n элементов по k можно вычислить по формуле:

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

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

В MS EXCEL для подсчета количества комбинаций без повторов существует специальная функция ЧИСЛКОМБ() , английское название функции - COMBIN(). Для предыдущего примера формула =ЧИСЛКОМБ(6;4) , разумеется, также вернет 15. Альтернативная формула для подсчета сочетаний =ФАКТР(6)/ФАКТР(6-4)/ФАКТР(4) .

Очевидно, что 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).

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


Комментарии

Только для авторизованных пользователей

Аноним, 14 апреля 2016 г.
непонятно как создать таблицу возможных сочетаний.
Михаил, 10 июля 2016 г.
Ее не нужно создавать, она уже есть в файле примера )))
Михаил, 10 июля 2016 г.
Если речь идет о формуле, то я сам уже не понимаю как она работает )))
Аноним, 12 сентября 2016 г.
👍
Аноним, 29 сентября 2019 г.
блин как это работает
Михаил, 29 сентября 2019 г.
работает и ладно ))
Аноним, 2 октября 2019 г.
Максимум в экселе чуть больше миллиона строк, как быть дальше? Как перенести формулы(ячейки) на другой лист, чтобы продолжить комбинации ? Спасибо
Михаил, 2 октября 2019 г.
Первое, что Вам нужно сделать - это еще раз скачать файл примера, т.к. я исправил формулу (при k>7 она работала неправильно) Второе, чтобы получить комбинации 1млн+ нужно сделать следующее (пусть в таблицу сочетаний на листе влезает 999 строк): -откройте еще 1 файл с теми же параметрами -в строке 3 таблицы с сочетаниями поставьте номер 999 (вместо 3) -в той же строке вставьте как значения комбинацию сочетания 999 (она известна) -продолжите нумерацию сочетаний в столбце А с 1000 и дальше.
Alexey, 21 ноября 2020 г.
Spasibo ogromnoe, vash file sekonomil mne kuchu vremini! Nashel odnu nebolshuyu oshibku. Vyborki "iz 11 po 5" i "iz 11 po 6" dolzhny davat' po 462 sochetaniya. Odnako tabliza soderzhala tol'ko po 330 sochetaniy. Oshibka byla v tom, chto tabliza "Сочетания (числа)" byla zapisana ol'ko do 330 strochki. Ya raschiril eyo do 462 i vsio zarabotalo. Spasibo!
Михаил, 23 ноября 2020 г.
это не ошибка, формулы нужно протягивать в зависимости от необходимости. Может и 1 млн быть вариантов. Размер файла растет. Рад, что вы догадались скопировать формулы вниз.
(только для авторизованных пользователей)

© Copyright 2013 - 2024 Excel2.ru. All Rights Reserved