Комбинаторика количество сочетаний без повторений: формула, определение, примеры решения задач из комбинаторики

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

Лекция №1 Основы комбинаторики

Основы комбинаторики

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

Правило суммы. Если объект А может быть выбран m способами, а объект B – n способами, причем выборы объектов взаимно исключают друг друга, то выбор «либо A, либо B» может быть осуществлен m + n способами.

Правило суммы можно распространить на выбор любого конечного числа объектов.

Пример 1. На полке в книжном шкафу стоят 25 книг, среди которых учебники: 5 книг по математике, 4 книги по физике, 6 книг по химии, остальные книги – художественная литература. Сколькими способами можно выбрать учебник с этой полки?

Решение: Взять любую из 5 книг по математике можно 5 способами, книгу по физике – 4 способами, книгу по химии – 6 способами. Выбор одной книги не влияет на выбор другой книги. Значит, по правилу суммы учебник с полки можно выбрать 5 + 4 + 6 = 15 способами.

Правило произведения. Если объект А может быть выбран m способами и после каждого из этих выборов объект B может быть выбран n способами, то выбор пары А, B может быть осуществлен m×n способами.

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

к действий. Если первое действие можно выполнить n₁ способом, после чего второе действие можно выполнить п₂ способами, после чего третье действие можно выполнить n₃ способами и т. д. до к-го действия, которое можно выполнить п_к способами, то все к действий вместе могут быть выполнены n₁× п₂× n₃×п_к способами.

Пример 2. Сколько трехзначных чисел можно составить из цифр 2, 4, 5, если цифры в числе не повторяются?

Решение: На месте сотен поставим любую из трех цифр. Это можно сделать тремя способами. После каждого такого выбора на месте десятков можно поставить любую из двух оставшихся цифр (т.е. двумя способами), так как цифры в числе не повторяются. Наконец, на месте единиц можно поставить оставшуюся одну цифру (т.е. одним способом). Применяя правило произведения два раза получим: 3

×2×1 = 6 способов, и соответственно, шесть трехзначных чисел.

Пример 3. Бросают две игральные кости разного цвета. Сколько существует результатов опыта? Каждая кость может упасть независимо от другой шестью способами.

Ответ: 6*6=36.

Пример 4. У велосипедистов есть суеверие: в нагрудном номере не должно быть цифры 8. Сколько человек участвовало в соревновании, если были розданы все трехзначные номера, не содержащие цифры 8. Ответ: . 9×9×9=729

Пример 5. В урне 4 красных, 3 белых и 6 синих шаров. Сколькими способами можно достать последовательно 3 шара так, чтобы первым был вынут красный шар, вторым − белый, третьим − синий? Ответ:4 ×3 ×6=72.

Графической иллюстрацией правила произведения является специальная схема, условно называемая «дерево». Для рассмотренного примера соответствующая схема будет выглядеть так:

2

4

5

5

4

245

254

Рассмотрим пример на применение этих двух правил.

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

Решение: Слово «рисунок» состоит из семи различных букв. Применяя правило произведения соответствующее число раз, можно подсчитать, что существует:

N1 = 7 × 6× 5× 4 × 3 = 2520 «слов» из пяти букв (выбираемых из букв слова «рисунок»), N2 = 7 × 6× 5× 4× 3× 2 = 5040 «слов» из шести букв, N3 = 7× 6 × 5× 4 × 3× 2× 1 = 5040 «слов» из семи букв. Тогда по правилу суммы, существует N = N1 + N2 + N3 = 2520 + 5040 + 5040 = 12 600 «слов», состоящих не менее чем из пяти букв слова «рисунок».

Существуют следующие комбинации: перестановки, размещения, сочетания.

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

А. Перестановки без повторений (n различных объектов).

Упорядоченные множества из

n элементов называются перестановками из n элементов. Таким образом, перестановки из n элементов отличаются только порядком следования элементов.

Перестановками из n элементов называют различные упорядочения данного конечного множества, состоящего из n элементов.

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

P_n = n! = 1 × 2× 3 ×…× n

Факториал – произведение всех натуральных чисел от 1 до n включительно называют «n-факториал».

Факториал нуля равен единице: 0!=1.

Пример 7.

Сколькими способами можно расставить 6 различных книг на одной полке?

Решение: Искомое число способов равно P₆ = 6! = 1 × 2× 3 ×4× 5 × 6 = 720. Действительно, первую книгу можно выбрать шестью способами, вторую — пятью способами и т.д., последнюю — одним способом. По правилу умножения общее число способов равно 6- 5-4• 3• 2-1 = 720.

Пример 8. Сколькими способами можно расположить на полке 10 различных книг? Ответ: 10! .

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

В том случае, если некоторые переставляемые объекты совпадают, то число перестановок будет меньше. Предположим, что имеется k различных типов объектов и известно, что имеется n₁ элементов 1-го типа, n₂ элементов 2-го типа, …, n_kэлементов k-го типа. При этом n₁+ n₂

+… + n_k =n. Перестановки такого типа будем называть n-перестановками с повторениями и обозначать P(n₁, n₂ ,…, n_k).

P(n₁, n₂ ,…, n_k)= n!/ (n₁! ×n₂! ×…×n_k!)

Перестановка п элементов, среди которых k₁элемент первого типа, k₂элементов второго типа, …, k_m элементов m-го типа (k₁ + k₂ + … + k_m = п), причем элементы разных типов различны, называется перестановкой с повторениями п элементов, среди которых k₁ элементов первого типа, k₂ элементов второго типа, …, k_m

элементов m-го типа

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

Решение: Так как в слове «криминалистика» 14 букв, то п = 14. Элементов первого типа (буквы «к») 2 штуки (k1 = 2). Далее: k2 = 1 (буква «р»), k3 = 4 (буква «и»), k4 = 1 (буква «м»), k5 = 1 (буква «н»), k6 = 2 (буква «а»), k7 = 1 (буква «л»), k8 = 1 (буква «с»), k9 = 1 (буква «т»). Следовательно, количество всех слов: Р(2, 1, 4, 1, 1, 2, 1, 1, 1) = 14! /(2!4!2!)=

Размещения

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

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

Упорядоченные подмножества из n элементов по k элементов каждое, называются размещениями из n элементов по k элементов (или кратко: размещениями из n по k). Таким образом, размещения отличаются либо составом элементов, либо их порядком.

Пусть дано множество, состоящее из п элементов. Размещением из п элементов по к (к < п) элементов называется упорядоченное подмножество, содержащее к различных элементов данного множества Все эти подмножества отличаются друг от друга или составом элементов, или порядком их распределения. Но число элементов во всех этих подмножествах равно к.

Размещениями из n по m называются всевозможные упорядоченные подмножества, содержащие

m элементов из данных n. Обозначаются и вычисляются по формуле:

Пример 10. Сколько можно составить четырехзначных чисел, содержащих различные цифры из 5 цифр.

Решение: Четырехзначное число – это упорядоченная последовательность цифр, т. е. имеем дело с размещениями без повторений: А₅⁴=5!/(5-4)!=5!/1!=5432=120.

Пример 11. В классе 10 учебных предметов и 5 разных уроков в день. Сколькими способами может быть составлено расписание на 1 день?

Решение:

Пример 12. Сколькими способами можно выбрать 3 из 10 различных шаров?

Ответ: А₁₀³=720.

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

Размещением с повторениями из m элементов по k элементов называется такое упорядоченное множество, которое содержит k элементов, причем один и тот же элемент может входить в это множество несколько раз (от нуля до k). Число всех размещений с повторениями из m по k равно m^k , т.е. Ā^k_m = m^k

Размещениями с повторениями из n элементов по k элементов называются упорядоченные множества, каждое из которых содержит k необязательно различных элементов из данного множества n элементов. Число размещений с повторениями вычисляется по формуле:

Пример 13. Сколько различных пятизначных чисел можно составить при помощи цифр 1, 2, 3?

Решение. Согласно предыдущему, искомое число равно Ā⁵₃ =3⁵=243

Пример 14. Кодовый замок имеет на диске 12 букв. Секретное слово состоит из 5 букв. Сколько неудачных попыток можно сделать? Общее число комбинаций Ā⁵₁₂ =12⁵=248832. Число неудачных попыток 248832-1=248831.

Пример 15. В стену здания вмонтированы 8 гнезд для флажков. В каждое гнездо вставляется либо голубой, либо красный флажок. Сколько различных случаев распределения флажков на здание.

Решение: Так как порядок расположения элементов важен и не все элементы используются в данном соединении, то это размещение. А так как всего 8 гнезд, а флажков 2 вида (голубой и красный), то они будут повторяться, т.е. это размещение с повторением.

Сочетания

Определение. Подмножества из n элементов по k элементов каждое, отличающиеся хотя бы одним элементом, называются сочетаниями из n элементов по k элементов (или кратко: сочетания из n по k). Таким образом, сочетания отличаются только составом элементов. Число сочетаний из n по k обозначается: C^k_n.

Пусть дано множество, состоящее из п элементов. Сочетанием из п элементов по к (0 < к < п) элементов называется любое подмножество, которое содержит к различных элементов данного множества. Таким образом, различными подмножествами считаются только те, которые отличаются составом элементов. Подмножества, отличающиеся друг от друга лишь порядком следования элементов, не считаются различными. Число всех возможных сочетаний из п элементов по к обозначается C^k_n. Так как число перестановок из к равно k!, то число размещений из п элементов по к — А^k_n будет в к! раз больше, чем число сочетаний из п

элементов по к — С^k_n , т.е. А^k_n =n! × C^k_n.

Отсюда: C^k_n= А^k_n /k!= n!/(n—k)! ×k!

Пусть имеются n различных элементов. k- сочетаниями без повторений из n элементов называют k-расстановки, составленные из этих элементов, и отличающиеся друг от друга составом, но не порядком элементов. Число k-сочетаний без повторений из n различных элементов обозначается С^k_n.

Сочетаниями из n по m называются всевозможные подмножества данных n элементов, состоящие из m элементов. Для подсчета их числа используются следующие обозначение и формула:

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

Пример 16. В бригаде из 25 человек нужно выделить четырех для работы на определенном участке. Сколькими способами это можно сделать?

Решение: Так как порядок выбранных четырех человек не имеет значения, то это можно сделать C⁴₂₅ способами: C⁴₂₅ = 25!/(25-4)! ×4!=12650

Пример 17. Сколькими способами можно выбрать при игре в спортлото 6 из 49 номеров?

Ответ: C⁶₄₉=69919080

Пример 18. В кондитерской продавалось 4 вида пирожных: наполеоны, эклеры, песочные, слоеные. Сколькими способами можно купить 7 пирожных?

Ответ: C⁴₇=

Сочетанием с повторениями из m элементов по k элементов (или короче: сочетанием с повторениями из m по k) называется множество, содержащее k элементов, причем каждый элемент принадлежит к одному из m типов. Число всех вышеупомянутых сочетаний с повторениями из m по k обозначается Ĉ^k_m (обратите внимание на отличие от обозначения числа сочетаний из n по k – черта сверху).Число сочетаний с повторениями из т по k равно:

Пусть имеется n различных типов предметов. Сколько k-расстановок можно составить, которые отличаются друг от друга составом, но не порядком входящих элементов? Такие k -расстановки называются k-сочетаниями с повторениями из n типов предметов. Число k -сочетаний с повторениями из n типов предметов обозначается Ĉ^k_m.

Сочетания из n элементов, в каждое из которых входит m элементов, причем один и тот же элемент может повторяться в каждом сочетании любое число раз, но не более m, называются сочетаниями с повторениями. Число сочетаний с повторениями вычисляется по формуле:

Пример 19. На почте продаются открытки 10 сортов. Сколько вариантов существует для покупки 12 открыток.

Решение: Порядок расположения элементов не имеет значения, следовательно, это сочетание. А так как открытки в наборе могут повторяться, то это сочетание с повторениями.

.

Таким образом, из 10 открыток можно выбрать набор из12 штук 293930 способами.

Пример 20.Число различных бросаний двух одинаковых кубиков равно

Пример 21. Напишем все сочетания с повторениями из трех элементов А, В, С по 3. Сколько их?

Вот они: ААА ВВВ ССС, АВВ ВСС, АСС ВВС, ААВ, ААС, АСВ. Их 10 штук, т.е.Ĉ³₃.=10.

Свойства сочетаний

1) С^k_n = С^n—k_n

2) С^k_n = С^k-1_n-1+ С^k_n-1

3) С⁰_n + С¹_n + С²_n + …+ Сⁿ_n = 2ⁿ

4) С^k_n * С^m—k_n—k= С^k_m+ С^m_n

Все сочетания легко вычисляются, если записать их в виде треугольной таблицы (треугольника Паскаля ):

1 С_о°

1 1 C₁⁰ С₁¹

1 2 1 С₂⁰ С₂¹ С₂²

1 3 3 1 С₃⁰С₃¹ С₃²С₃³

1 4 6 4 1 С₄⁰ С₄¹С₄²С₄³С₄⁴

1 5 10 10 5 1 С₅⁰С₅¹С₅²С₅³С₅⁴С₅⁵

На основании данной таблицы можно увидеть справедливость указанных выше свойств сочетаний.

При определении вида комбинации удобно пользоваться схемой:

КОМБИНАТОРНЫЕ ЗАДАЧИ

Задача 1. Максимально возможное количество матчей, которое можно организовать в высшей лиге футбольного дивизиона страны не должно превышать 160 в один круг. Сколько (максимально) команд можно включить в состав высшей лиги.

Решение. Обозначим возможное количество команд через n, тогда число сыгранных матчей равно C²_n . По условию C²_n ≤ 160. Пусть C²_n = 160, тогда:

n!/(n-2)!* 2!=160. Тогда n=18,4;-17,4.

Число команд должно быть натуральным числом, поэтому n = 18.

Ответ. 18 команд.

Задача 2. Имеется 4 сорта чая, 5 сортов конфет и 6 сортов печенья. Сколькими способами можно организовать чаепитие-дегустацию на трех человек, если каждый может выпить одну чашку чая определенного сорта с одной конфетой и одним печеньем?

Решение. Используя правило произведения, подсчитаем, что:

1) число способов распределить сорта чая для трех дегустаторов равно 4³;

2) число способов распределить по одной конфете определенного сорта для трех дегустаторов равно 5³;

3) число способов распределить по одному печенью определенного для трех дегустаторов равно 6³.

Применяя еще раз правило произведения, мы получим, что число способов организовать данное чаепитие-дегустацию равно 4³* 5³* 6³= 1 728 000.

Задача 3. В соревнованиях принимают участие 16 команд Сколькими способами могут распределиться три первых места, т е необходимо найти число всех подмножеств, состоящих из трех элементов, отличающихся составом (номерами команд) или порядком их размещения (подмножества № 1, № 2, № 3 и № 2, № 1, № 3 являются разными). Таким образом, имеем дело с размещением. Тогда искомое число равно A³₁₆=3360

Задача 4. В отделении 10 солдат. Необходимо составить наряд из 4-х человек. Сколько существует способов составления такого наряда?

Решение. Поскольку порядок, в котором мы выбираем участников наряда, не важен, то мы имеем дело с сочетаниями их 10 по 4. Итак, C⁴₁₀=210

Задача 5. Сколько существует четырехзначных чисел, состоящих из различных цифр?

Решение. Ноль не может быть первой цифрой, следовательно, есть 9 возможностей выбрать первую цифру. Далее может следовать любая упорядоченная тройка оставшихся цифр, а для этого есть A³₉ способов. Итого, получаем 9* A³₉=4536

Задача 6. Сколькими способами можно раскрасить диаграмму из 4 столбцов четырехцветной ручкой так, чтобы каждый столбец был окрашен в определенный цвет.

Решение: Порядок расположения элементов имеет значение и в диаграмме 4 столбца, а ручка тоже четырехцветная, т. е. все элементы присутствуют в соединении, следовательно, это соединение – перестановка. А так как окраска столбцов не повторяется (в условии сказано, что столбцы имеют разные цвета), то это перестановка без повторения. Итак, P_n= n! = 4! = 1234 = 24 Ответ: столбцы можно закрасить 24 способами.

Задача 7. Имеется 5 кружков: 3 белых и 2 черных. Сколько различных узоров можно получить, располагая кружки в ряд.

Решение: Порядок расположения элементов имеет значение и в узоре 5 кружков, т.е. все элементы присутствуют в соединении, следовательно, это соединение – перестановка. А так как окраска кружков повторяется (в условии сказано, что 3 белых и 2 черных), то это перестановка с повторением. Итак,

Ответ: узор можно составить 10 способами.

Задача 8. Сколько словарей надо издать, чтобы можно было непосредственно выполнить перевод с любого из 5 языков на любой из 5 языков.

Решение: Порядок имеет значение (так как русско-английский и англо-русский словари различны) и не все элементы присутствуют в соединении (а только 2 из 5), значит, это размещение. Так как языки различны, то это размещение без повторения. Итак, . Ответ: надо составить 20 словарей.

Задача 9. На железнодорожной станции имеется 5 светофоров. Сколько может быть дано различных комбинаций их сигналов, если каждый светофор имеет 3 состояния.

Решение: Порядок имеет значение и не все элементы присутствуют в соединении, значит, это размещение. Так как цвета повторяются, то это размещение с повторением. Итак, . Ответ: может быть дано 243 различных комбинаций цветов.

Задача 10. 12 человек играли в городки. Сколькими способами они могут разбиться на команды по 4 человека в каждой.

Решение: Порядок расположения игроков в команде не имеет значения, следовательно, это сочетание. А так как игроки не повторяются (все члены команды различные люди), то это сочетание без повторения. Итак, .

Ответ: игроки могут разбиться на команды по 4 человека в каждой 495 способами.

Задача 11. В цветочном магазине продаются цветы 6 видов. Сколько можно составить букетов из 10 цветов в каждом (букеты отличающиеся лишь расположением цветов считать одинаковыми).

Решение: Порядок расположения цветов в букете не имеет значения, следовательно, это сочетание. А так как цветы повторяются, то это сочетание с повторением. Итак, . Ответ: букеты можно составить 3003 способами.

Задача 12. В группе 25 студентов, из которых 5 отличников, 11 хорошистов и остальные троечники. Сколькими способами можно выбрать группу для выполнения лабораторной работы, состоящей из 3 хорошистов, 1 отличника и 1 троечника.

Решение: Сначала узнаем сколькими способами можно выбрать 3 хорошистов из 11 человек. Порядок расположения студентов не важен, значит, это сочетание. А так как люди в группе не повторяются, то это соединение – сочетание без повторения. Итак, одного хорошиста можно выбрать способами. Аналогично рассуждая, приходим к тому, что 1 отличника можно выбрать способами и одного троечника можно выбрать способами. Так как команда для выполнения лабораторной работы выбирается одновременно, т.е. 5 хорошистов, затем 1 отличник, затем 1 троечник, то, применив правило произведения, получим: способами. Ответ: группу для выполнения лабораторной работы можно составить 3300 способами.

Задача 13: Имеется 4 чашки, 5 блюдец, 6 ложек (все чашки, блюдца, ложки различны). Сколькими способами можно накрыть стол к чаю на 3 человека, если каждый получает 1 чашку, 1 блюдце и 1 ложку.

Решение: Выберем для 3 человек чашки из 4 имеющихся. Порядок расположения элементов имеет значение, и не все элементы входят в соединение, значит, это размещение. Но так чашки не повторяются, то это размещение без повторения. Итак, из 4 чашек 3 можно выбрать способами. Аналогично рассуждая, получим, что из 5 блюдец 3 можно выбрать способами, а из 6 ложек 3 можно выбрать способами. Так блюдце, чашка и ложка входят в набор одновременно, то стол можно накрыть способами. Ответ: стол можно накрыть 172800 способами.

Задача 14. Группу из 20 студентов можно разместить в аудитории по 2 человека за каждой партой. Порядок их размещения имеет значения.

Решение. Количество возможных вариантов размещений вычисляется по формуле:

Задача 15. Найти количество трехзначных чисел с неповторяющимися цифрами, которые можно составить из цифр: 1, 2, 3, 4, 5.

Решение. Количество трехзначных чисел в данном примере определяется по формуле размещений (3) и равно:

Задача 16. Группу из 20 студентов следует рассадить в аудитории по 2 человека за каждой партой. Порядок их размещения не имеет значения. Определить количество возможных вариантов сочетаний.

Решение. Количество возможных вариантов сочетаний вычисляется по формуле 4):

Задача 17. Флаг государства может комбинироваться из трёх полос разного цвета. Определить число комбинаций из пяти разных цветов, которые можно получить, выбирая из них три полосы разного цвета.

Решение. Если учитывать порядок в комбинации, то число вариантов равно:

Если же порядок в комбинации не имеет значения, то количество разных вариантов равно:

Комбинаторика в Python / Хабр

Стандартная библиотека python, начиная с версии 2.2, предоставляет множество средств для генерирования комбинаторных объектов, но в интернете мне не удалось найти ни одной статьи, которая подробно рассказывала бы о работе с ними. Поэтому я решил исправить это упущение.

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

Допустим, у нас есть строка, состоящая из n разных букв и мы хотим вычислить все способы переставить эти буквы местами так, чтобы получить новую строку. На первую позицию в строке мы можем выбрать одну из n букв, имеющихся у нас, на вторую позицию одну из n-1-ой буквы и так далее. В итоге получаем произведение n (n-1)… *1 = n! количество перестановок из n элементов без повторений.

Теперь представим, что количество букв в строке ограничено. У нас есть n доступных букв и мы хотим вычислить количество способов составить из них строку длины k, где k < n, каждую букву мы можем использовать лишь единожды. Тогда на первую позицию в строке мы можем поставить одну из n букв, на вторую позицию одну из n-1 буквы и на k-ую позицию одну из n-k+1 буквы. k количество размещений из n по k с повторениями.

До этого мы перебирали последовательности с учетом порядка элементов, а что если порядок для нас не имеет значения. Например, у нас есть есть n разных конфет и мы хотим выбрать k из них, чтобы подарить другу, при чем k < n. Сколько существует способов выбрать k конфет из n без учета порядка? Ответ прост, в начале найдем размещение из n по k без повторений, но тогда одинаковые наборы конфет, имеющие разный порядок их следования будут повторяться. Сколько существует способов переставить k конфет? Правильно, перестановка из k элементов без повторений. Итоговый ответ: размещения из n по k делим на перестановки из k без повторений. Формула: количество сочетаний из n по k.

Рассмотрим случай посложнее, у нас есть n коробок каждая из которых содержит множество конфет одного вкуса, но в разных коробках вкусы разные. Сколько существует способов составить подарок другу из k конфет, при чем один и тот же вкус может встречаться любое количество раз? Так как порядок для нас значения не имеет, давайте разложим подарочные сладости следующим образом: в начале будут лежать последовательно конфеты первого вкуса, затем второго и так далее, а между конфетами разных вкусов положим спички, если конфеты какого-то вкуса отсутствуют в нашем подарке — спички, которые должны были окаймлять этот вкус слева и справа будут стоять рядом. Того у нас получится последовательность, состоящая из k конфет и n-1 спички, ибо вкусов всего n, а спички разделяют их. Теперь заметим, что по расположению спичек, мы можем восстановить исходное множество. Тогда ответом будет количество способов разместить n-1 спичку в n+k-1 ячейку без учета порядка, что равно количеству сочетаний из n+k-1 по n-1, формула: количество сочетаний из n по k с повторениями.

Теперь рассмотрим несколько задач на комбинаторику, чтобы закрепить материал.

Задача 1

Есть 20 человек, сколько существует способов разбить их на пары
Решение: возьмем первого человека, сколько существует способов выбрать ему пару: , возьмем второго человека, сколько существует способов выбрать ему пару: . Ответ: 19!!! = 654729075

Задача 2

Есть 10 мужчин и 10 девушек, сколько существует способов разбить их на компании, состоящие из одинакового количества и мужчин и девушек, пустая компания не считается
Решение:
Cпособ 1: количество способов собрать компанию из одного мужчины и одной девушки равно произведению количества способов выбрать одну девушку и количества способов выбрать одного мужчину. Количество способов выбрать одну девушку из 10 равно сочетанию из 10 по 1 без повторений, с мужчинами аналогично, поэтому возведем в квадрат. Далее аналогично вычислим сочетания из 10 по 2, из 10 по 3 и так далее до сочетания из 10 по 10. Итоговая формула: .
Способ 2: рассмотрим множество мужчин, входящих в компанию и множество девушек, не входящих в нее. По этому множеству можно однозначно восстановить компанию, а количество людей в нем всегда равно 10, так как , k — количество мужчин в компании, — количество девушек, не вошедших в нее. Количество таких множеств равно количеству сочетаний из 20 по 10, в конечном ответе мы также вычтем единицу, чтобы не учитывать пустую компанию, когда в нашем множестве 10 девушек. Итоговая формула: .

Итак, мы разобрались с теорией, теперь научимся генерировать комбинаторные объекты с помощью стандартной библиотеки python.
Работать мы будем с библиотекой itertools

from itertools import *

С помощью функции permutations можно сгенерировать все перестановки для итерируемого объекта.

Пример 1

for i in permutations('abc'):
    print(i, end=' ') # abc acb bac bca cab cba
print()
for i in permutations('abb'):
    print(i, end=' ') # abb abb bab bba bab bba 

Исходя из второго вызова заметим, что одинаковые элементы, стоящие на разных позициях, считаются разными.

Пример 2

for i in permutations('abc', 2):
    print(i, end=' ') # ab ac ba bc ca cb 

Размещение отличается от перестановки ограничением на количество доступных ячеек

Пример 3

for i in product('abc', repeat=2):
    print(i, end=' ') # aa ab ac ba bb bc ca cb cc

C помощью размещений с повторениями можно легко перебрать все строки фиксированной длины, состоящие из заданных символов

Пример 4

for i in combinations('abcd', 2):
    print(i, end=' ') # ab ac ad bc bd cd 

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

Пример 5

for i in combinations_with_replacement('abcd', 2):
    print(i, end=' ') # aa ab ac ad bb bc bd cc cd dd  

Результат аналогичен вызову combinations, но в результат также добавлены множества с одинаковыми элементами.

Материалы:
Н.В. Горбачев «Сборник олимпиадных задач по математике»
Документация по python на русском

Комбинаторный калькулятор, калькулятор комбинаций, вариаций, перестановок

Узнайте, сколькими способами можно выбрать k предметов из n предметов набора. С/без повторения, с/без порядка.

Расчет:

Ck​(n)=(kn​)=k!(n−k)!n!​  n=10 k=4 C4​(10)=(410​)=4!(10 −4)!10!​=4⋅3⋅2⋅110⋅9⋅8⋅7​=210

Количество комбинаций: 210

Вариантов

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

Количество вариаций можно легко подсчитать, используя комбинаторное правило произведения. Например, если у нас есть набор n = 5 чисел 1,2,3,4,5, и мы должны сделать вариации третьего класса, их V ₃ (5) = 5 * 4 * 3 = 60.

Vk​(n)=n(n−1)(n−2)…(n−k+1)=(n−k)!n!​

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

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

Перестановка является синонимом вариации n-го класса n-элементов. Таким образом, это любая упорядоченная группа из n элементов, состоящая из n элементов. Элементы не повторяются и зависят от порядка элементов в группе.

P(n)=n(n−1)(n−2)…1=n!

Типичный пример: у нас есть 4 книги, сколькими способами мы можем расположить их на полке рядом?

Вариации с повторением

Разновидностью k-го класса из n элементов является упорядоченная группа k-элементов, состоящая из множества n элементов, причем элементы могут повторяться и зависят от их порядка. Типичным примером является образование чисел из цифр 2,3,4,5 и нахождение их числа. Рассчитаем их количество по комбинаторному правилу произведения:

Vk′​(n)=n⋅n⋅n⋅n…n=nk

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

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

Pk1​k2​k3​…km​′​(n)=k1​!k2​!k3​!…km​!n!​

Типичный пример — выяснить, сколько семизначных чисел образовано из чисел 2,2,2, 6,6,6,6.

Комбинации

Комбинация k-го класса из n элементов представляет собой неупорядоченную группу k-элементов, образованную из множества n элементов. Элементы не повторяются, и порядок элементов группы не имеет значения. В математике неупорядоченные группы называются множествами и подмножествами. Их количество является комбинационным числом и рассчитывается следующим образом:

Ck​(n)=(kn​)=k!(n−k)!n!​

Типичный пример комбинаций: у нас 15 учеников, и мы должны выбрать троих. Сколько их будет?

Комбинации с повтором

Здесь мы выбираем k групп элементов из n элементов, независимо от порядка, и элементы могут повторяться. k логически больше n (иначе мы получили бы обычные комбинации). Их счет:

Ck′​(n)=(kn+k−1​)=k!(n−1)!(n+k−1)!​

Пояснение к формуле — количество комбинаций с повторением равно количеству мест расположения n − 1 разделителей на n-1 + k местах. Типичный пример: мы идем в магазин, чтобы купить 6 шоколадок. Предлагают всего 3 вида. Сколько вариантов у нас есть? к = 6, п = 3.

Основы комбинаторики в текстовых задачах

• Определенный 66594
  Маренька должна прочитать три книги из пяти назначенных книг. Сколькими способами можно выбрать три книги для чтения?
• Расчет CN
  Рассчитать: (486 выбрать 159) — (486 выбрать 327)
• (2 66504
  K (2, 8) + K (3, 4) =
• Троица
  Сколько различных триад можно выбрать
• Карты
  Игрок получает восемь карт из 32. Какова вероятность того, что он получит а) все четыре туза б) хотя бы один туз
• Шестеро
  Шесть мальчиков будут подниматься на холм на двухместном лифте. Сколько есть вариантов?
• Футбольные команды
  Нужно организовать футбольные команды. Есть три возрастные группы. Сколькими способами можно организовать десять команд для каждой возрастной группы? Это перестановка или комбинация?
• Разные 68754
  У нас есть шесть мячей разных цветов. Подбираем сразу два шара. Сколько вариантов?
• Зоомагазин 2
  В зоомагазине проходит розыгрыш призов. спиннер показывает тип игрушки, которую клиент может выиграть для своего питомца. если клиент крутит спиннер, и он приземляется на кошку, он выиграет бесплатную кошачью игрушку. Если блесна вращается 540 раз в течение дня, примерно как
• Аккорды
  Сколько четырехтональных аккордов (аккорд = одновременно звучащие разные тона) можно сыграть в пределах 7 тонов?
• Функция распределения
  X 2 3 4 P 0,35 0,35 0,3 По данным этой таблицы я вычисляю функцию распределения F(x) и затем вероятность p(2,5 < ξ < 3,25) p(2,8 < ξ) и p(3,25 > ξ)
• Перестановки без повторений
  Из скольких элементов можно составить 720 перестановок без повторений?
• Трехзначное число 2
  Найдите количество всех трехзначных натуральных чисел, которые можно составить из цифр 1, 2, 3, 4 и которые при соблюдении одного и того же времени имеют следующие условия: на одной позиции стоит одно из чисел 1, 3, 4, на месте сотен 4 или 2.
• Комбинации
  Из скольких элементов можно составить 990 комбинаций 2-го класса без повторений?
• Олимпийские металлы
  Сколькими способами можно выиграть призовые места шести спортсменов на Олимпийских играх? Цвет металла имеет значение.
• Экзамен
  В классе 25 человек. Сколькими способами можно выбрать 5 студентов для экзамена?

больше математических задач »

с повторением и без с примерами

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

Быстрый доступ

!Нажмите на кнопки ниже, чтобы перейти прямо к разделу статьи, которую вы ищете!

Определение комбинации

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

Чтобы лучше понять значение и использование комбинации, мы собираемся показать следующий пример: Если из 5 человек мы хотим случайным образом выбрать двух из них для участия в действии, в перестановке порядок, в котором мы выбираем люди будут иметь значение, например, если мы сначала выберем человека А, а затем человека Б, это будет одна перестановка, и если мы выберем человека Б, а затем человека А, это будет другая перестановка, , но в комбинации, эти два сценария будут считаться только одной комбинацией, независимо от того, будет ли порядок выбора «A и B» или «B и A»

Комбинация записывается буквами nCr, где «n» — количество элементов набора, а «r» — количество элементов, которые мы собираемся выбрать, где «r» не может быть старше, чем «n». «, потому что это приведет к ошибке.

Еще одно свойство комбинации состоит в том, что существует два типа комбинаций: одна с повторением, а другая без повторения.

Комбинация с повторением

Это когда элементы набора могут повторяться, для пояснения этого типа вот пример: Человек идет в кондитерскую, где есть 10 разных вкусов конфет, но этот человек возьму только 4, по одному на каждого из его детей, это пример комбинации с повторением, потому что, хотя есть 10 разных вкусов, ничто не позволяет этому человеку выбрать один и тот же вкус дважды, трижды или даже четыре раза.

Формула с повторением

Комбинация без повторения

Это когда элементы набора не могут быть повторены, например: в компании, где работает 20 человек, принимается решение о формировании директивы, составленной из 3 человек, в этом В этом случае у нас была бы комбинация без повторения, потому что человека нельзя выбрать дважды.

Формула без повторения

• nCr =

  n!/(n-r)! * р!

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

Примеры комбинаций

Пример 1: Человек идет в кондитерскую, где есть 8 видов вкусов, если этот человек собирается купить только 3, определите все возможные комбинации

С повторением n = 8 r = 3 nCr = ?

• nCr =

  (n + r-1)!/r! * (н-1)!

• 8C3 =

  (8 + 3-1)!/3! * (8-1)!

• 8C3 =

  (10)!/3! * 7!

• 8С3 =

  10 * 9*8* 7! /3! * 7!

• 8С3 =

  10*9*8/3!

• 8C3 =

  10 * 9 * 8/3*2*1

• 8C3 =

  720/6

• 8C3 = 120

Иисус любит тебя

Иисус — сын Божий, который был послан на смерть, чтобы каждый, кто верит в него, имел жизнь вечную.

Узнать больше

Пример 2: 2 девушки пойдут на вечеринку, если у них есть 4 пары модной обуви, определите комбинацию обуви, которую могут носить эти две девушки

Без повторения n = 4 r = 2 nCr = ?

• 4C2 =

  н!/(н-р)! * р!

• 4C2 =

  4!/(4-2)! * 2!

• 4C2 =

  4*3*2*1/2*1 * 2*1

• 4C2 =

  24/4

• 4С2 = 6

Пример 3: Человек поедет в путешествие на 3 дня, поэтому он возьмет с собой 3 рубашки, если у него 7 рубашек, сколько комбинаций рубашек он может взять.

Без повторения n = 7 r = 3 nCr = ?

• nCr =

  n!/(n-r)! * р!

• 7C3=

  7!/(7-3)! * 3!

• 7C3=

  7!/4! * 3!

• 7C3=

  7*6*5*4!/4! * 3!

• 7C3=

  7*6*5* 4! / 4! *3!

• 7C3=

  7*6*5/3!

• 7C3=

  7*6*5/3*2*1

• 7C3=

  210/6

• 7C3= 35

Пример 4: В ведерке 10 шаров, каждый шар пронумерован от 1 до 10, если кто-то случайно вытащит 3 из этих шаров, сколько комбинаций он сможет составить.