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

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

• Число сочетаний — это количество способов, которыми можно выбрать ровно ${\displaystyle k}$ предметов из множества, в котором ${\displaystyle n}$ предметов. Обозначается ${\displaystyle C_{n}^{k}}$.
• Размещение из ${\displaystyle m}$ элементов по ${\displaystyle n}$ элементов (${\displaystyle n\leqslant m}$) — это соединения, каждое из которых содержит ${\displaystyle n}$ элементов, взятых из данных ${\displaystyle m}$ разных элементов, и которые отличаются одно от другого либо самими элементами, либо порядком их расположения. Обозначается ${\displaystyle A_{m}^{n}}$^[2].

Если множество ${\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 P_{n}=n!}$, где ${\displaystyle n!}$ — факториал числа ${\displaystyle n}$

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

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

Бином — в теории многочленов так называют двучлены ${\displaystyle (a+b)}$. Рассмотрим целые неотрицательные степени бинома ${\displaystyle (a+b)}$:

${\displaystyle {\begin{aligned}(a+b)^{0}&=1\\(a+b)^{1}&=a+b\\(a+b)^{2}&=a^{2}+2ab+b^{2},\\(a+b)^{3}&=a^{3}+3a^{2}b+3ab^{2}+y^{3},\\(a+b)^{4}&=a^{4}+4a^{3}b+6a^{2}b^{2}+4ab^{3}+b^{4},\\(a+b)^{5}&=a^{5}+5a^{4}b+10a^{3}b^{2}+10a^{2}b^{3}+5ab^{4}+b^{5}\end{aligned}}}$

В общем виде справедлива следующая формула, называемая биномом Ньютона^[4]:

Для любого ${\displaystyle n\in \mathbb {N} }$:${\displaystyle (a+b)^{n}=C_{n}^{0}a^{n}+C_{n}^{1}a^{n-1}b+...+C_{n}^{k}a^{n-k}b^{k}+...+C_{n}^{n-1}ab^{n-1}+C_{n}^{n}b^{n}}$, где ${\displaystyle C_{n}^{k}={\frac {n!}{k!(n-k)!}}}$ (1)

С использованием знака суммирования формулу записывают в виде ${\displaystyle (a+b)^{n}=\sum _{k=0}^{n}C_{n}^{k}a^{n-k}b^{k}}$.

Числа ${\displaystyle C_{n}^{k}}$ в формуле ${\displaystyle (1)}$ называют биномиальными коэффициентами.

1. ${\displaystyle C_{n}^{0}=C_{n}^{n}}$
2. ${\displaystyle C_{n}^{k}=C_{n}^{n-k}}$
3. ${\displaystyle C_{n}^{k-1}+C_{n}^{k}=C_{n+1}^{k}}$
4. ${\displaystyle C_{n}^{k}=C_{n}^{k-1}\centerdot {\frac {n-(k-1)}{k}}}$
5. ${\displaystyle C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+...+C_{n}^{n}=\sum _{k=0}^{n}C_{n}^{k}=2^{n}}$
6. ${\displaystyle C_{n}^{0}-C_{n}^{1}+C_{n}^{2}+...+(-1)^{n}C_{n}^{n}=0}$
7. ${\displaystyle C_{n}^{0}+C_{n}^{2}+C_{n}^{4}+...=C_{n}^{1}+C_{n}^{3}+C_{n}^{5}+...=2^{n-1}}$
8. Если показатель бинома чётный ${\displaystyle n=2l}$, то ${\displaystyle C_{n}^{l}}$ является наибольшим биномиальным коэффициентом и справедливы неравенства: ${\displaystyle C_{n}^{0}<C_{n}^{1}<...<C_{n}^{l-1}<C_{n}^{l}}$ и ${\displaystyle C_{n}^{l}>C_{n}^{l+1}>...>C_{n}^{2l-1}>C_{n}^{2l}}$
9. Если показатель бинома нечётный ${\displaystyle n=2l+1}$, то имеется два наибольших биномиальных коэффициента ${\displaystyle C_{n}^{l}=C_{n}^{l+1}}$и справедливы неравенства: ${\displaystyle C_{n}^{0}<C_{n}^{1}<...<C_{n}^{l-1}<C_{n}^{l}=C_{n}^{l+1}}$ и ${\displaystyle C_{n}^{l}=C_{n}^{l+1}>C_{n}^{l+2}>...>C_{n}^{2l-1}>C_{n}^{2l}}$.

Свойство ${\displaystyle (3)}$ позволяет вычислить биномиальные коэффициенты, используя только операцию суммирования, записав их в виде треугольной таблицы, называемой треугольником Паскаля. Числовой треугольник называют по имени французского учёного Блеза Паскаля, который в середине XVII в. издал «Трактат об арифметическом треугольнике», где подробно описал его свойства (Рис.1).

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

Рис.1

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

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

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

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

3. Сколькими способами можно образовать трёхзначное число из цифр 1, 2, 3, 4 без повторений?

  ${\displaystyle A_{4}^{3}={\dfrac {4!}{(4-3)!}}=24}$ способа.

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

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