Data Science

Главная

САД. Комбинаторика

Следующая тема: САД. Теория вероятностей

Вернуться в раздел: Статистический анализ данных

Вернуться в оглавление: Я.Практикум

 

В теме:

1. Введение

2. Комбинации. Правило умножения

3. Перестановки. Число перестановок

4. Размещения. Число размещений

5. Сочетания. Число сочетаний

6. Заключение

7. Проверочные задания. Комбинаторика

Введение

Кратко:
  • Комбинаторика - раздел математики, изучающий комбинации элементов набора.
  • Комбинаторика полезна в физике, статистике, лингвистике, криптографии, логистике и других областях.
  • Комбинаторика решает практические задачи, связанные с подсчетом, перебором и группировкой объектов.
  • Некоторые элементы комбинаторики, такие как число сочетаний, пригодятся в будущих темах курса.
  • Курс «Статистический анализ данных» обучает использованию комбинаций, расчету числа перестановок и формул числа сочетаний и размещений.
  • Тогглы-спойлеры в курсе содержат дополнительную информацию по теме и сложные математические выкладки
Перед героем разложены кубики с буквами. Ему нужно распределить кубики по трём слотам.
Комбинаторика — это раздел математики, который изучает различные комбинации элементов некоторого набора. Проще говоря, комбинаторика изучает, сколькими способами вы можете выбирать, упорядочивать или группировать объекты. Это могут быть любые элементы: числа, слова, рекламные объявления, промежуточные точки маршрута на карте.
Комбинаторика полезна в разных прикладных областях: физике, статистике, лингвистике, криптографии, логистике и многих других. Её используют, чтобы решать практические задачи, связанные с подсчётом, перебором и группировкой объектов.
Некоторые элементы комбинаторики — например, число сочетаний — пригодятся вам в будущих темах этого курса.

Вы научитесь

  • пользоваться комбинациями,
  • считать число перестановок,
  • пользоваться формулами числа сочетаний и числа размещений.
В курсе «Статистический анализ данных» вы встретите несколько свёрнутых тогглов-спойлеров, которые можно развернуть по клику. Такие тогглы содержат дополнительную информацию по теме. Также в них содержатся сложные математические выкладки, например вывод формул. Такой материал необязателен для изучения, но приводится для тех, кому это интересно. Тогглы-спойлеры выглядят так (нажмите на тоггл, чтобы развернуть его):
 
Пример тоггла-спойлера
Дополнительная информация.
 

Комбинации. Правило умножения

Кратко:

  • Комбинация - это вариация набора объектов из некоторого количества наборов.
  • Комбинации бывают разные - о конкретных видах вы узнаете в следующих уроках.
  • Для ответа на вопрос можно использовать закон о комбинациях - правило умножения.
  • Если есть n объектов одного типа и m объектов другого типа, то составить комбинацию из двух объектов разного типа можно n· m способами.
  • Пусть есть n наборов объектов с количеством объектов в каждом из них k_1, k_2, …, k_n. Тогда составить комбинацию из n объектов разного типа можно k_1 · k_2 · ... · k_n различными способами.
  • Можно записать короче, используя возведение в степень.
  • Посчитайте количество всех возможных индексов.
Решая задачи, связанные с комбинаторикой, вы чаще всего будете работать с комбинациями.

Комбинации

💡 Комбинация — это вариация набора объектов из некоторого количества наборов.
Например, когда вы берёте с полки магазина несколько товаров и кладёте их в корзину, вы составляете комбинацию. Комбинации бывают разные — о конкретных видах вы узнаете в следующих уроках.
 
Представьте, что сервис доставки подарков решил создать составной подарок из мягкой игрушки и коробки со сладостями. Всего в ассортименте есть три вида плюшевых медведей и два вида сладостей:
 

Комбинации. Правило умножения

Решая задачи, связанные с комбинаторикой, вы чаще всего будете работать с комбинациями.

Комбинации

💡 Комбинация — это вариация набора объектов из некоторого количества наборов.
Например, когда вы берёте с полки магазина несколько товаров и кладёте их в корзину, вы составляете комбинацию. Комбинации бывают разные — о конкретных видах вы узнаете в следующих уроках.
Представьте, что сервис доставки подарков решил создать составной подарок из мягкой игрушки и коробки со сладостями. Всего в ассортименте есть три вида плюшевых медведей и два вида сладостей
 
Сколько различных вариантов подарка вида «игрушка + конфеты» можно составить? Порядок в этом случае неважен: «зелёный медведь + круглая коробка конфет» и «круглая коробка конфет + зелёный медведь» будут считаться одной и той же комбинацией.
Для ответа на вопрос можно использовать важный закон о комбинациях — правило умножения.

Правило умножения

Каждого из трёх медведей можно комбинировать с любой из двух коробок конфет. Поэтому, чтобы найти количество всех возможных пар, необходимо перемножить количество объектов в каждом из наборов: 3⋅2=6. То есть можно составить шесть пар. В общем виде правило умножения формулируется так:
 
💡 Если есть n объектов одного типа и m объектов другого типа, то составить комбинацию из двух объектов разного типа можно n⋅m способами. и m — это некоторые положительные целые числа.
 
Сотрудник компании выбирает два месяца для отпуска. Один отпуск он хочет взять весной, а другой — осенью. Сколько есть возможных комбинаций двух месяцев?
 
Правило умножения распространяется на любое количество наборов, из которых берётся хотя бы по одному объекту. Представьте, что у вас в гардеробе есть пиджака, рубашки, пары штанов и ремня. Тогда общее количество костюмов, которые можно составить из этих вещей, можно посчитать так: 2⋅4⋅3⋅2=48. Обобщим это математически:
 
💡 Пусть есть n наборов объектов с количеством объектов в каждом из них k1, k2, …, . Тогда составить комбинацию из n объектов разного типа можно k1⋅k2⋅...⋅kn различными способами.
 
Рассмотрим ещё один пример. В некотором городе номера телефонов состоят из семи цифр. Номер обязательно должен начинаться с цифры 2. Остальные цифры могут быть любыми. Сколько возможных номеров телефонов могут существовать в этом городе? Эту задачу тоже можно решить с помощью правила умножения. Известно, что:
  • есть 1 способ выбрать первую цифру — потому что она обязательно должна быть равна 2;
  • есть 10 способов выбрать каждую из оставшихся шести цифр — ими могут быть цифры от 0 до 9
Значит, существует один миллион возможных комбинаций: 1⋅10⋅10⋅10⋅10⋅10⋅10=1000000.
 
Как посчитать число комбинаций с помощью Python
Пользоваться правилом умножения и считать число комбинаций можно с помощью Python. Вам даже не понадобятся дополнительные библиотеки:
phones_amount = 1 * 10 * 10 * 10 * 10 * 10 * 10
print(phones_amount)
Можно записать короче, используя возведение в степень:
# 10 умножаем шесть раз подряд — это 10 в шестой степени
phones_amount = 1 * 10**6
print(phones_amount)

Задание 1

Индекс региона состоит из шести цифр. Для него существуют следующие условия:
  • первая цифра должна быть равна 3;
  • вторая цифра не должна быть равна 0;
  • остальные четыре цифры могут быть любыми.
Посчитайте количество всех возможных индексов.
# напишите ваш код здесь
index_amount = 1*9*10**4
print(index_amount)
  • Комбинация - это вариация набора объектов из некоторого количества наборов.
  • Комбинации бывают разные - о конкретных видах вы узнаете в следующих уроках.
  • Для ответа на вопрос можно использовать закон о комбинациях - правило умножения.
  • Если есть n объектов одного типа и m объектов другого типа, то составить комбинацию из двух объектов разного типа можно n· m способами.
  • Пусть есть n наборов объектов с количеством объектов в каждом из них k_1, k_2, …, k_n. Тогда составить комбинацию из n объектов разного типа можно k_1 · k_2 · ... · k_n различными способами.
  • Можно записать короче, используя возведение в степень.
  • Посчитайте количество всех возможных индексов.

Перестановки. Число перестановок

Кратко:

  • Перестановки - это упорядоченные наборы элементов, отличающиеся только порядком.
  • Число перестановок - это количество всевозможных перестановок набора из некоторых элементов.
  • Формула для числа перестановок n объектов равна произведению всех целых чисел от 1 до n, обозначается P_n.
  • Факториал числа n - это произведение всех целых чисел от 1 до n, обозначается n!.
  • Используя Python, найти количество перестановок можно следующим образом: просто и элегантно.
  • Задание 1: стриминговый сервис Яндекс Музыка позволяет перемешивать музыкальные треки. У одного из пользователей в коллекции 12 песен. Сколько различных плейлистов из этих 12 песен с различным порядком можно составить?
В прошлом уроке вы научились считать количество всех возможных комбинаций из двух и более наборов объектов. Теперь пора познакомиться с тремя особыми видами комбинаций — перестановками, размещениями и сочетаниями. В этом уроке вы изучите перестановки.

Перестановки

Разберём этот вид комбинаций на примере. Музыкальный магазин «PlayGuitar» проводит рекламную кампанию в социальной сети. Отдел маркетинга подготовил четыре поста для продвижения — каждый посвящён одной из гитар, продающихся в магазине.
 
Четыре поста посвящены четырём разным гитарам: жёлтой, красной с двумя «рожками», синей с языками пламени и зелёной с одним «рожком».
Симпатичные гитары, правда? Уже представили, как играете легендарное соло из Hotel California? А помните, как Джо Уолш на концерте в 1977... Не любите рок? Что ж, возможно, вы больше любите комбинаторику. Тогда вернёмся к уроку.
 
Маркетологи задумались, в каком порядке лучше показывать посты пользователям. Последовательность изображений выше — это один из возможных вариантов порядка, или перестановка.
 
💡 Перестановками называют упорядоченные наборы одних и тех же элементов, которые отличаются только порядком. Например, {1,2,3},{1,3,2},{3,1,2} — это некоторые из возможных перестановок набора целых чисел от 1 до 3. То есть перестановки содержат все элементы исходного набора, но в разном порядке.
 
А сколько всего перестановок этих постов можно получить? Это значение называют числом (или количеством) перестановок.

Число перестановок

💡 Число перестановок — это количество всевозможных перестановок набора из некоторых элементов.
Например, одно изображение можно переставить всего одним способом:
 
Пост с изображением зелёной гитары с одним «рожком».
То есть количество возможных перестановок для одного объекта равно единице.
Два поста можно переставить двумя способами:
 
Сначала пост про красную гитару с двумя «рожками», потом — про зелёную с одним «рожком». Или наоборот.
Получается, количество возможных перестановок для двух объектов равно двум.
 
А если поста три? Переставить три объекта всеми возможными способами уже сложнее.
 
Итак, есть три разных поста и три временных слота для них. Существует три способа поставить первый пост на один из этих трёх свободных слотов:
 
Схематичное изображение трёх постов и трёх свободных слотов. От первого поста протянуты три стрелочки к каждому из слотов.
Например, поставим его на первое место. Для второго поста осталось два свободных слота — то есть два способа его разместить.
 
От второго поста протянуты две стрелочки к каждому из двух оставшихся слотов.
Поставим его, допустим, на вторую позицию. В итоге, для третьей картинки остаётся только один вариант:
 
От третьего поста протянута стрелочка к оставшемуся слоту.
Ура! Все посты расставлены. Для первого было 3 варианта размещения, для второго — 2 варианта, для третьего — 1 вариант. Чтобы найти общее количество комбинаций, нужно перемножить количество возможных вариантов на каждом шаге: 3⋅2⋅1=6. Получается, число возможных перестановок трёх постов равно произведению целых чисел от 1 до 3.
 
Схематичное изображение сказанного выше.
Для большей наглядности можно построить схему-развилку для всех возможных вариантов:
 
Схема выглядит как ветви дерева. Три способа разместить первый пост — это три ветви. На каждой из них ещё по две веточки — это два способа разместить второй пост после того, как первый займёт какой-то из трёх слотов. Для третьего поста остаётся только один способ его разместить. В итоге получается шесть веточек — шесть вариантов комбинаций.
Можете посмотреть на все возможные перестановки трёх постов про гитары (мы вас не обманули, их действительно шесть):
 
Два поста вы легко переставили и без схем с подсчётами, хотя для них они тоже были бы справедливы. Есть 2 варианта размещения для первого поста и 1 вариант для второго, поэтому возможное количество комбинаций равно 1⋅2=2 — то есть произведению целых чисел от 1 до 2.
 
В общем виде правило расчёта числа возможных перестановок звучит так:
 
💡 Число перестановок n объектов равно произведению всех целых чисел от 1 до . Его обозначают Pn.
Помните про четыре поста из рекламной кампании музыкального магазина? Пришло время узнать, сколько есть вариантов порядка их показа!
 
24
Вы выяснили, что существует 24 варианта размещения четырёх рекламных постов. У отдела маркетинга PlayGuitar будет из чего выбрать!
 
В «Базовом Python» вы познакомились с понятием факториала. Факториал числа n — это произведение всех целых чисел от 1 до n. Факториал числа n обычно обозначается как n! (читается «эн факториал»). Используя факториал, формулу количества перестановок можно переформулировать:
 
💡 Число перестановок n объектов равно n!

Как посчитать число перестановок с помощью Python

Используя Python, найти количество перестановок можно следующим образом:
КодPYTHON
from math import factorial
n = 4
res = factorial(n)
print(f'Четыре рекламных поста можно переставить {res} различными способами.')
 
Просто и элегантно!

Задание 1

Стриминговый сервис Яндекс Музыка позволяет перемешивать музыкальные треки. У одного из пользователей в коллекции 12 песен. Сколько различных плейлистов из этих 12 песен с различным порядком можно составить?
from math import factorial
# напишите ваш код здесь
playlist_amount = factorial(12)
print(playlist_amount)

Размещения. Число размещений

Кратко:

  • Формула для числа размещений из n по k: A_n^k = n!/(n - k)!.
  • Размещения - это комбинации объектов исходного набора с заданным количеством элементов.
  • Чем размещения отличаются от перестановок? В перестановках тоже важен порядок элементов, но в отличие от размещений они содержат все элементы исходного набора объектов.
  • Размещения могут строиться и по всем элементам в том числе.
  • Число размещений можно найти с помощью правила умножения.
  • Формула числа размещений можно записать через факториал: A_n^k = n!/(n - k)!.
  • Количество размещений из n по n (то есть k = n) равно количеству перестановок n элементов: A_n^n = P_n.
  • Пример задачи: посчитать число размещений 5 букв из русского алфавита
В прошлом уроке вы изучили такой тип комбинаций, как перестановки. В этом вы познакомитесь с ещё одним видом комбинаций — размещениями.

Размещения

Вы наверняка знакомы со стриминговыми видеосервисами вроде «Кинопоиска». Они постоянно предоставляют своим пользователям рекомендации по фильмам, например подборки интересных картин определённых жанров. Представьте, что в одном из таких сервисов менеджер передал аналитику список из следующих четырёх фильмов:
  • Начало (2010)
  • Назад в будущее (1985)
  • Она (2013)
  • Бегущий по лезвию (1982)
Менеджер попросил аналитика составить из этих фильмов все возможные подборки из двух картин. При этом он уточнил, что порядок важен — от этого зависит, в каком порядке сервис будет рекомендовать пользователю смотреть фильмы. То есть
  • Начало (2010)
  • Назад в будущее (1985)
и
  • Назад в будущее (1985)
  • Начало (2010)
будут считаться разными комбинациями.
 
Такие комбинации называют размещениями.
 
💡 Размещения — это комбинации объектов исходного набора с заданным количеством элементов, которые различаются самими элементами и их расположением.
 
Чем размещения отличаются от перестановок? В перестановках тоже важен порядок элементов, но в отличие от размещений они содержат все элементы исходного набора объектов. Размещения же строятся по заданному количеству элементов из исходного набора. Они могут строиться и по всем элементам в том числе. Исходя из сказанного выше, уточним определение:
 
💡 Размещениями из n по k называют все возможные комбинации объектов исходного набора, содержащие по k элементов из n объектов исходного набора и различающиеся порядком элементов. При этом n и — это целые числа, а n должно быть больше либо равно k.

Число размещений

Подборки, содержащие два фильма из четырёх с различным порядком, — это размещения из по . Сколько же таких размещений может быть? Сколько подборок, содержащих два фильма с различным порядком, можно составить из четырёх картин?
 
Есть два свободных места для двух фильмов. Получается, что существует четыре способа выбрать первый из четырёх фильмов:
 
Схематичное изображение фильмов и свободных для них мест. К первому свободному месту ведут четыре стрелочки — от каждого фильма.
Допустим, первое место займёт второй фильм. Тогда останется три фильма и одно свободное место. Соответственно, есть три варианта выбора следующего фильма из оставшихся:
 
Ко второму свободному месту ведут три стрелочки — от оставшихся трёх фильмов.
Пусть второе место займёт, например, четвёртый фильм. Всё, свободных мест больше не осталось.
 
Чтобы найти количество возможных комбинаций, можно воспользоваться правилом умножения: 4⋅3=12. То есть существует вариантов выбора двух фильмов из четырёх с учётом порядка. Вот они:
 
1)
  • Начало (2010)
  • Назад в будущее (1985)
2)
  • Начало (2010)
  • Она (2013)
3)
  • Начало (2010)
  • Бегущий по лезвию (1982)
4)
  • Назад в будущее (1985)
  • Начало (2010)
5)
  • Назад в будущее (1985)
  • Она (2013)
6)
  • Назад в будущее (1985)
  • Бегущий по лезвию (1982)
7)
  • Она (2013)
  • Начало (2010)
8)
  • Она (2013)
  • Назад в будущее (1985)
9)
  • Она (2013)
  • Бегущий по лезвию (1982)
10)
  • Бегущий по лезвию (1982)
  • Начало (2010)
11)
  • Бегущий по лезвию (1982)
  • Назад в будущее (1985)
12)
  • Бегущий по лезвию (1982)
  • Она (2013)
А теперь представьте, что у вас 15 кинокартин и вам нужно составить из них подборки из четырёх фильмов с учётом порядка. Посчитать можно аналогично:
  • первый фильм можно выбрать из 15 возможных вариантов,
  • второй фильм можно выбрать из оставшихся 14 вариантов,
  • третий фильм можно выбрать из оставшихся 13 вариантов,
  • четвёртый фильм — из оставшихся 12 вариантов.
По правилу умножения получается размещений.
В общем виде правило расчёта числа размещений выглядит так:
 
💡 Число размещений из n по k равно n⋅(n−1)⋅(n−2)⋅...⋅(n−k+1), где — это количество объектов исходного набора, а — количество элементов в каждом размещении. То есть нужно найти произведение всех целых чисел от n−k+1 до . Число размещений обозначают Ank.
В примере выше:
  • n=15,
  • k=4,
  • n−k+1=15−4+1=12.
Таким образом, необходимо решить следующий пример:
 
A(15)(4)=.
 
Ту же формулу числа размещений можно переписать более компактным образом, используя факториал:
 
💡 Число размещений из n по равно A(n)(k)=n!/(n−k)!, где — это количество объектов исходного набора, а — количество элементов в каждом размещении.
 
Если вам интересно, как получить из первой формулы вторую, можете прочитать подробное объяснение ниже.
 
Как преобразовать формулу расчёта числа размещений в формулу с использованием факториала
 
Решите ещё пару примеров, чтобы запомнить формулу расчёта числа размещений.
На чемодане есть кодовый замок из 4 цифр. Цифры в коде не должны повторяться. Порядок цифр важен: 1234, 2341 и 4321 — это разные коды. Сколько комбинаций кода можно придумать?
5040
Сколько мелодий из 3 нот можно составить из 7 нот одной октавы? Порядок учитывается: «до, ре, ми» и «ми, ре, до» — это разные мелодии.
Правильный ответ
210
Обратите внимание, что количество размещений из n по n (то есть k=n) равно количеству перестановок n элементов: Ann=Pn. Размещения из n по — это перестановки всех исходных объектов.

Как посчитать число размещений с помощью Python

Вы уже умеете считать факториал с использованием Python, поэтому сможете написать код для подсчёта числа размещений. Попробуйте найти количество размещений 5 букв из русского алфавита:
from math import factorial
letters_to_take = 5
letters_total = 33
res = factorial(letters_total) / factorial(letters_total - letters_to_take)
print(res)
Существует 28 480 320 вариантов выбрать пять букв из тридцати трёх с учётом всех вариантов расположения букв между собой. Почти 28,5 миллионов — впечатляет!

Задание 1

Сколько музыкальных плейлистов длиной в 5 песен можно составить из 10 треков? Плейлисты с одинаковыми композициями и разным порядком песен считаются разными.
from math import factorial
playlist_songs = 5
total_songs = 10
# напишите ваш код здесь
playlist_amount = factorial(total_songs) / factorial(total_songs - playlist_songs)
print(playlist_amount)

Сочетания. Число сочетаний

Кратко:

  • Сочетания - это комбинации объектов исходного набора с заданным количеством элементов, которые различаются только самими элементами.
  • Сочетаниями из n по k называют все возможные комбинации объектов исходного набора, содержащие k элементов из n объектов исходного набора и не различающиеся порядком элементов.
  • Число сочетаний из n по k обозначается C_n^k и считается по формуле C_n^k = n!/k!(n - k)!.
  • Для нахождения числа сочетаний нужно разделить число размещений на k!.
  • Задание 1: Игрок участвует в телевизионной викторине. Требуется отгадать слово из 10 букв. Игрок может «открыть» любые 3 буквы. Сколько вариантов выбора у него есть?
В одном из заданий урока про перестановки вы считали, сколькими способами можно перемешать двенадцать песен, то есть количество их перестановок. Решите ещё один пример с песнями, чтобы вспомнить, как рассчитывается количество перестановок. Это пригодится для темы этого урока — расчёта числа сочетаний.
 
Выберите все корректные перестановки следующего набора треков:
1) Paramore — Ain’t It Fun.
2) Red Hot Chili Peppers — Wet Sand.
3) Queen — Under Pressure.
 
Правильный ответ
{Paramore — Ain’t It Fun, Queen — Under Pressure, Red Hot Chili Peppers — Wet Sand}
{Queen — Under Pressure, Paramore — Ain’t It Fun, Red Hot Chili Peppers — Wet Sand}
 
6

Сочетания

Перестановки вспомнили. Теперь вернёмся к задаче прошлого урока, в которой вам нужно было посчитать, сколько подборок, содержащих два фильма, можно составить из четырёх фильмов. Вы решили её с помощью формулы числа размещений: Ank=n!/(n−k)!=4!/(4−2)!=12. В этой задаче порядок был важен. Разное расположение фильмов — разный порядок просмотра и, соответственно, разные подборки.
А если порядок будет неважен? Например, вас попросили найти количество всех возможных подборок, содержащих два фильма из четырёх, но порядок разрешили не учитывать. Тогда
  • Начало (2010)
  • Назад в будущее (1985)
и
  • Назад в будущее (1985)
  • Начало (2010)
будут считаться одной и той же комбинацией.
Вспомните все варианты размещения двух фильмов из четырёх из прошлого урока и вычеркните все дубликаты:
1)
  • Начало (2010)
  • Назад в будущее (1985)
2)
  • Начало (2010)
  • Она (2013)
3)
  • Начало (2010)
  • Бегущий по лезвию (1982)
4)
  • «Назад в будущее» (1985)
  • «Начало» (2010)
5)
  • Назад в будущее (1985)
  • Она (2013)
6)
  • Назад в будущее (1985)
  • Бегущий по лезвию (1982)
7)
  • «Она» (2013)
  • «Начало» (2010)
8)
  • «Она» (2013)
  • «Назад в будущее» (1985)
9)
  • Она (2013)
  • Бегущий по лезвию (1982)
10)
  • «Бегущий по лезвию» (1982)
  • «Начало» (2010)
11)
  • «Бегущий по лезвию» (1982)
  • «Назад в будущее» (1985)
12)
  • «Бегущий по лезвию» (1982)
  • «Она» (2013)
В итоге из двенадцати комбинаций осталось шесть. Они и будут сочетаниями из четырёх по два.
 
💡 Сочетания — это комбинации объектов исходного набора с заданным количеством элементов, которые различаются только самими элементами. У сочетаний нет порядка элементов — это неупорядоченные комбинации.
 
💡 Сочетаниями из по называют все возможные комбинации объектов исходного набора, содержащие элементов из объектов исходного набора и не различающиеся порядком элементов.

Число сочетаний

Кроме случая, когда выбирают ровно один элемент, число сочетаний из по k всегда меньше, чем число размещений из n по k. Потому что, как в примере выше, из размещений как бы вычёркиваются все дубликаты с другим порядком тех же элементов. Количество таких дубликатов равно количеству перестановок длины k.
 
В примере с фильмами итоговый список сочетаний оказался в два раза меньше числа размещений. Выражаясь математически, число комбинаций сократилось в 2!=2 раза — именно столько существует перестановок длины 2.
 
То есть для нахождения числа сочетаний нужно разделить число размещений на k!:
 
💡 Число сочетаний из n по k обозначается Cnk и считается по формуле Cnk=n!/k!(n−k)!, где n — количество объектов исходного набора, а — количество элементов в каждом сочетании.
 
Тогда количество подборок по 5 фильмов из 20 без учёта порядка можно найти, решив такой пример:
 
C(20)(5)=20!/5!(20−5)!=20!/5!⋅15!=15504.
 
Решите ещё пару примеров, чтобы закрепить формулу.
 
Маркетинговое агентство планирует одновременно запустить рекламу в трёх городах в рамках акции. Всего компания представлена в шести городах. Сколько есть вариантов выбрать три города для акции?
 
Правильный ответ
20
 
У Василия есть пять дебетовых карт различных банков. В магазин он планирует взять две из них. Сколько вариантов есть у Василия? Введите ниже целое число без пробелов.
 
Ваш ответ правильный
10

Как посчитать число сочетаний в Python

Посчитать число сочетаний в Python, как и число размещений, можно с использованием факториала. Попробуйте найти количество сочетаний 5 букв из русского алфавита:
from math import factorial
letters_to_take = 5
letters_total = 33
res = factorial(letters_total) / (factorial(letters_to_take) * factorial(letters_total - letters_to_take))
print(res)
237 336 вариантов. Как и ожидалось, значительно меньше, чем число размещений пяти букв.

Задание 1

Игрок участвует в телевизионной викторине. Требуется отгадать слово из 10 букв. Игрок может «открыть» любые 3 буквы. Сколько вариантов выбора у него есть?
from math import factorial
word_length = 10 # укажите длину слова
letters_amount = 3 # укажите количество букв, которые можно узнать
choices = factorial(word_length) / (factorial(letters_amount) * factorial(word_length - letters_amount)) # найдите количество вариантов 
print(choices)

Заключение

Кратко:

  • Изучены основы комбинаторики для решения задач типа "Сколько всего вариантов есть?" или "Какое количество комбинаций можно составить?".
  • Рассмотрены комбинации, правило умножения, перестановки, число перестановок, размещения и число размещений, сочетания и число сочетаний.
  • Шпаргалка темы может быть использована для запоминания изученного материала.
  • Рекомендуется изучить задачи по комбинаторике и книгу Виликина Н. Я. "Комбинаторика" для более глубокого понимания темы
В этой теме вы изучили основы комбинаторики. Теперь решить задачи типа «Сколько всего вариантов есть?» или «Какое количество комбинаций можно составить?» для вас — плёвое дело.

Вы изучили

  • комбинации,
  • правило умножения,
  • перестановки и число перестановок,
  • размещения и число размещений,
  • сочетания и число сочетаний.

Заберите с собой

Чтобы ничего не забыть, скачайте шпаргалку темы.

Что можно изучить дополнительно

Проверочные задания. Комбинаторика

Чтобы пройти тест нужно правильно ответить на 5 вопросов из 8.
Время на прохождение: 18 минут

Задание 1 из 8

Сколько существует вариантов расставить цифры 5, 6, 7, 8, 9?
 
120
 
Варианты расстановки пяти чисел можно посчитать с помощью формулы числа перестановок пяти объектов: Pn=n!=5!=120.

Задание 2 из 8

Как называются комбинации из исходного набора n объектов с заданным количеством элементов k, которые различаются самими элементами и их расположением?
 
Правильный ответ
Размещения (Ank)
Размещения — это комбинации, которые различаются и самими элементами, и порядком их расположения.

Задание 3 из 8

Родители привели дочку в зоомагазин, чтобы купить ей двух попугаев. Всего в вольере магазина восемь попугаев. Сколько вариантов покупки существует?
 
28
Поскольку порядок попугаев во время покупки не имеет значения, нужно найти число сочетаний из 8 по 2: C82=8!2!(8−2)!=28.

Задание 4 из 8

У мальчика есть девять кубиков с цифрой на каждом от 1 до 9. Сколько различных трёхзначных чисел можно из них составить?
 
504
Порядок цифр важен: 321 и 123 — разные числа. Значит, нужно найти число размещений из по 3: A(9)(3)=504

Задание 5 из 8

Как называются комбинации из исходного набора n объектов с заданным количеством элементов k, которые различаются только самими элементами?
 
Правильный ответ
Сочетания (Cnk)
Комбинации элементов без порядка, которые различаются только самими элементами, — это сочетания.

Задание 6 из 8

Администратор должен выдать новому сотруднику клавиатуру и компьютерную мышь. У него есть 5 различных клавиатур и 3 различных мышки. Сколько пар комплектов можно из них собрать?
 
Правильный ответ
15
Используя правило умножения, можно найти количество комплектов: 5⋅3=15.

Задание 7 из 8

Как называются упорядоченные наборы одних и тех же элементов, которые различаются только порядком?
 
Перестановки (Pnk)
Упорядоченные наборы всех элементов, различающиеся только расположением, называются перестановками.

Задание 8 из 8

Как получить из формулы размещения формулу сочетаний? Напомним, что n — количество объектов в исходном наборе, k — количество объектов, которые нужно выбрать.
 
Правильный ответ
Формулу размещений нужно разделить на k!
Чтобы из формулы A(n)(k)=n!/(n−k)! получить формулу C(n)(k), нужно выполнить деление на k!: C(n)(k)=n!/k!(n−k)!

Следующая тема: САД. Теория вероятностей

Вернуться в раздел: Статистический анализ данных

Вернуться в оглавление: Я.Практикум

Категория: Я.Практикум Data Science
Просмотров: 5002