Комбинаторика (ОГЭ)

• Перестановка из ${\displaystyle n}$ предметов — это упорядоченный способ нумерации этих предметов или способ их расположения в ряд^[2].
• Факториал натурального числа ${\displaystyle n}$ — это произведение всех натуральных чисел от 1 до ${\displaystyle n}$. Обозначается факториал ${\displaystyle n!}$

• Число сочетаний — это количество способов, которыми можно выбрать ровно ${\displaystyle k}$ предметов из множества, в котором ${\displaystyle n}$ предметов. Обозначается ${\displaystyle C_{n}^{k}}$.

Если множество ${\displaystyle A}$ состоит из ${\displaystyle m}$ элементов, а множество ${\displaystyle B}$ — из ${\displaystyle k}$ элементов, причём эти множества не имеют общих элементов, то выбор «${\displaystyle a}$ или ${\displaystyle b}$», где ${\displaystyle a\in A}$, ${\displaystyle b\in B}$, можно осуществить ${\displaystyle m+k}$ способами.

Правило суммы можно обобщить для трёх и более множеств. Например, если множества ${\displaystyle A,B}$ и ${\displaystyle C}$ состоят соответственно из ${\displaystyle m,k}$ и ${\displaystyle n}$ элементов, причём ни у каких двух из этих множеств нет общих элементов, то выбор «${\displaystyle a}$ или ${\displaystyle b}$ или ${\displaystyle c}$», где ${\displaystyle a\in A}$, ${\displaystyle b\in B}$, ${\displaystyle c\in C}$, можно осуществить ${\displaystyle m+k+n}$способами.

Если элемент ${\displaystyle a}$ можно выбрать ${\displaystyle m}$ способами и после каждого такого выбора элемент ${\displaystyle b}$ можно выбрать ${\displaystyle k}$ способами, то выбор «${\displaystyle a}$ или ${\displaystyle b}$»  в указанном порядке можно осуществить ${\displaystyle mk}$ способами.

Правило произведения также естественно обобщить. Например, если элемент ${\displaystyle a}$ можно выбрать ${\displaystyle m}$ способами, после каждого такого выбора элемент ${\displaystyle b}$ можно выбрать ${\displaystyle k}$ способами и после того, как выбраны элементы ${\displaystyle a}$ и ${\displaystyle b}$, элемент ${\displaystyle c}$ можно выбрать ${\displaystyle n}$ способами, то выбор «${\displaystyle a}$ и ${\displaystyle b}$ и ${\displaystyle c}$» можно осуществить ${\displaystyle mkn}$ способами^[3].

${\displaystyle n!=1\cdot 2\cdot 3\cdot ...\cdot (n-1)\cdot n}$

 Число перестановок из ${\displaystyle n}$ элементов ${\displaystyle P_{n}=n!}$, где ${\displaystyle n!}$ — факториал числа ${\displaystyle n}$.

Число сочетаний из ${\displaystyle n}$ по ${\displaystyle k}$ вычисляется по формуле ${\displaystyle C_{n}^{k}={\dfrac {n!}{k!(n-k)!}}}$.

Если число ${\displaystyle n}$ небольшое, то число сочетаний ${\displaystyle C_{n}^{k}}$ можно взять из треугольной таблицы, которая называется треугольником Паскаля.

Числовой треугольник, содержащий числа сочетаний, известен по крайней мере с Х в. Его называют по имени французского учёного Блеза Паскаля, который в середине XVII в. издал «Трактат об арифметическом треугольнике», где подробно описал его свойства. Обычно его изображают в виде равнобедренного треугольника, поэтому столбцы в треугольнике получаются наклонные (Рис.1).

Рис.1

Столбцы и строки треугольника Паскаля нумеруются начиная с нуля. Число ${\displaystyle C_{n}^{k}}$ стоит в ${\displaystyle n}$-й строке и в ${\displaystyle k}$-м столбце. Каждая строка начинается и заканчивается единицей — ${\displaystyle C_{n}^{0}=1}$, так как выбрать 0 предметов можно единственным способом. Так же ${\displaystyle C_{n}^{n}=1}$, потому что выбрать все ${\displaystyle n}$ предметов из ${\displaystyle n}$ имеющихся можно тоже только одним способом^[4].

Например, чтобы найти ${\displaystyle C_{4}^{3}}$, находим, какое число стоит на пересечении 4-й строки и 3-го столбца.  Это число 4. Следовательно, ${\displaystyle C_{4}^{3}=4}$.

1. Какое число способов существует для расположения 4 книг на полке?

  ${\displaystyle P_{4}=4!=24}$ способа.

2. Сколькими способами из группы из 10 человек можно сформировать команду из 3 человек?

  ${\displaystyle C_{10}^{3}={\dfrac {10!}{3!(10-3)!}}=120}$ способов.

• Теория вероятностей: определение вероятностей событий путём подсчёта благоприятных исходов.
• Криптография: разработка и анализ кодов и шифров.
• Информатика: оптимизация алгоритмов и структур данных.
• Генетика: исследование сочетаний генов и закономерностей наследования признаков.

Комбинаторика — базовая область математики, необходимая для решения разнообразных практических задач, связанных с вычислением и анализом возможных комбинаций и конфигураций. Знание её основных принципов позволяет эффективно справляться с задачами в математике, информатике, физике и других науках.