Размещения

Пусть имеется nn различных объектов.  Будем выбирать из них mm объектов и переставлять всеми возможными способами между собой (то есть меняется и состав выбранных объектов, и их порядок). Получившиеся комбинации называются размещениями из nn объектов по mm, а их число равно

Amn=n!(n−m)!=n⋅(n−1)⋅...⋅(n−m+1)Anm=n!(n−m)!=n⋅(n−1)⋅...⋅(n−m+1)

Пример всех размещений из n=3n=3 объектов (различных фигур) по m=2m=2 - на картинке справа. Согласно формуле, их должно быть ровно A23=3⋅(3−2+1)=3⋅2=6A32=3⋅(3−2+1)=3⋅2=6.

На сайте вы можете найти число размещений: онлайн калькулятор размещений.

Сочетания

Пусть имеется nn различных объектов.  Будем выбирать из них mm объектов все возможными способами (то есть меняется состав выбранных объектов, но порядок не важен). Получившиеся комбинации называются сочетаниями из nn объектов по mm, а их число равно

Cmn=n!(n−m)!⋅m!Cnm=n!(n−m)!⋅m!

Пример всех сочетаний из n=3n=3 объектов (различных фигур) по m=2m=2 - на картинке справа. Согласно формуле, их должно быть ровно C23=3!(3−2)!⋅2!=3C32=3!(3−2)!⋅2!=3. Ясно, что сочетаний всегда меньше чем размещений (так как при размещениях порядок важен, а для сочетаний - нет), причем именно в m!m! раз, то есть верна формула связи:

Amn=Cmn⋅Pm.

Математические термины

Во всём последующем материале никак не фигурирует понятие "модуль числа" в привычном смысле (|x||x|). Речь идёт о "сравнении по модулю". Если вы не знакомы с этим понятием, вкратце сравнение по модулю выглядит следующим образом:

a≡b(modm).a≡b(modm).

Это читается "aa сравнимо с bb по модулю mm", и в привычных для информатики терминах обозначает следующее:

(a−b)modm=0(a−b)modm=0

или

amodm=bmodm,amodm=bmodm,

где modmod – операция взятия остатка от деления.

Поле по модулю

В некоторых задачах фигурирует условие следующего вида: "выведите остаток от деления ответа на 1000000007" или "выведите ответ по модулю 1000000007". Это вовсе не значит, что вам нужно посчитать ответ обычным способом и вывести ans % 1000000007. Ответ в таких задачах часто настолько огромен, что его сложно представить даже с помощью длинной арифметики. Для их решения нужно вносить изменения во все промежуточные вычисления, чтобы не выйти за границы целочисленного типа.

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

(a+b)modm=((amodm)+(bmodm))modm(a−b)modm=((amodm)−(bmodm))modm(ab)modm=((amodm)∗(bmodm))modm(a+b)modm=((amodm)+(bmodm))modm(a−b)modm=((amodm)−(bmodm))modm(ab)modm=((amodm)∗(bmodm))modm

Таким образом, мы можем выполнять три важнейшие математические операции, даже не зная точных значений чисел, только их остатки от деления на заданное число (модуль). Деление – отдельная тема, которую мы обсудим позже.

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

Примечание: термин "поле" применим только в том случае, когда модуль – простое число. В противном случае это называется "кольцо". Отличие заключается в том, что для поля определена операция деления, а для кольца – нет.