Номер 500, страница 191 - гдз по алгебре 11 класс учебник Колягин, Ткачева

Глава 5. Комбинаторика. Упражнения к главе V - номер 500, страница 191.

Условие.

500. Сколькими способами $2n$ разных элементов можно разбить на пары?

Решение 1.

Решение 2.

Решение 3.

Для решения этой задачи воспользуемся рекуррентным подходом. Пусть $f(2n)$ — это искомое количество способов разбить $2n$ различных элементов на $n$ пар.

Выберем произвольный элемент из нашего множества. Чтобы составить пару для этого элемента, мы можем выбрать любой из оставшихся $2n-1$ элементов. Таким образом, у нас есть $2n-1$ способ сформировать первую пару.

После того как первая пара сформирована, у нас остается $2n-2$ элемента. Их, в свою очередь, нужно разбить на $n-1$ пару. Количество способов сделать это равно $f(2n-2)$.

Таким образом, мы получаем рекуррентное соотношение:$f(2n) = (2n-1) \cdot f(2n-2)$

В качестве базового случая рассмотрим разбиение двух элементов ($2n=2$). Их можно разбить на одну пару единственным способом, следовательно, $f(2) = 1$.

Теперь, используя полученное соотношение, мы можем выразить $f(2n)$:$f(2n) = (2n-1) \cdot f(2n-2)$$f(2n) = (2n-1) \cdot (2n-3) \cdot f(2n-4)$$f(2n) = (2n-1) \cdot (2n-3) \cdot (2n-5) \cdot \ldots \cdot f(2)$$f(2n) = (2n-1) \cdot (2n-3) \cdot (2n-5) \cdot \ldots \cdot 3 \cdot 1$

Это произведение называется двойным факториалом нечетного числа и обозначается как $(2n-1)!!$.

Результат можно также выразить через обычные факториалы. Для этого умножим и разделим выражение на произведение всех четных чисел от 2 до $2n$:$(2n-1)!! = \frac{(2n) \cdot (2n-1) \cdot (2n-2) \cdot (2n-3) \cdot \ldots \cdot 1}{(2n) \cdot (2n-2) \cdot \ldots \cdot 4 \cdot 2}$В числителе мы получили факториал числа $2n$, то есть $(2n)!$. В знаменателе вынесем 2 за скобки из каждого множителя:$(2n) \cdot (2n-2) \cdot \ldots \cdot 2 = (2 \cdot n) \cdot (2 \cdot (n-1)) \cdot \ldots \cdot (2 \cdot 1) = 2^n \cdot (n \cdot (n-1) \cdot \ldots \cdot 1) = 2^n n!$

Таким образом, итоговая формула имеет вид:$f(2n) = \frac{(2n)!}{2^n n!}$

Ответ: $\frac{(2n)!}{2^n n!}$