суббота, 20 июня 2015 г.

Вычисление количества сочетаний

Число 10 на математических часах представляется как
$10=C_5^2$

Эта запись означает количество сочетаний из 5 элементов по 2. Иными словами, сколькими способами можно выбрать из пяти различных предметов неупорядоченную пару

Искомое число можно подсчитать непосредственно. Из (1,2,3,4,5) можно выбрать такие пары (не забываем, что порядок в них неважен):

(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)
Всего их 10.

Как же вычислять $C_n^m$ не прибегая к непосредственному перечислению? Первый предмет можно выбрать n способами. Второй предмет можно выбрать (n-1) способами. Для третьего будет (n-2) способов, и т.д. до (n-m+1) способов выбрать m-й предмет.

Значит, количество способов выбрать m предметов из n при условии, что порядок важен, равно произведению $n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot(n-m+1)$.

Сами же эти m предметов можно переставить между собой m! способами. Значит, каждая непорядоченная группа из m предметов при нашем подсчёте оказалась подсчитанной m! раз.

Поэтому $C_n^m$ оказывается равно дроби: $\frac{n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot(n-m+1)}{m!}$

Эту формулу можно упростить, заметив, что $n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot(n-m+1) = \frac{n!}{(n-m)!}$

Таким образом, $C_n^m = \frac{n!}{m!(n-m)!}$

Комментариев нет:

Отправить комментарий

Популярные сообщения

Темы

число цифра простые геометрия юмор дроби язык степень делимость пи методы история квадрат самоописывающее время задача система счисления узор корень тригонометрия структура е сайты конструкция формулы игра факториал функции приближение программа фрактал комбинаторика последовательность график память логарифм вероятность палиндром пределы конкурс треугольник магический квадрат неизвестное правильно-неправильное действие видео интеграл уравнение комплексные софизм заблуждения процесс ряды цитаты книги окружность прогрессия среднее стереометрия число фи выражения графы матрица проценты разрезания логика парабола символ статистика 2014 Фибоначчи клеточный автомат кривая производная фокус головоломка действия иллюзия куб шахматы многоугольник новости оказывается оригами подобие построение сложение термин тетраэдр топология