Сочетания

Пример сочетаний из четырёх элементов

Сочета́ния в математике — соединения, составленные из n элементов по k элементов в каждой группе и отличающиеся друг от друга хотя бы одним элементом. Сочетания, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми. В зависимости от того, повторяются или нет элементы в множестве, из которого их выбирают, различают сочетания без повторения и с повторением. Сочетания являются примером простейших комбинаторных конфигураций наряду с перестановками и размещениями.

Число сочетаний

Число сочетаний из n элементов по k обозначается символом $C\,_{n}^{k}$ или ${\binom {k}{n}}$ и равно ${\frac {n!}{k!(n-k)!}}$. Здесь $n!=1\cdot 2\cdot 3\cdot ...\cdot n$ — так называемый факториал числа n.

Числа $C\,_{n}^{k}$ получаются как коэффициенты разложения n-й степени двучлена (бинома): $(a+b)^{n}=C\,_{n}^{0}a^{n}+C\,_{n}^{1}a^{n-1}b+C\,_{n}^{2}a^{n-2}b^{2}+...+C\,_{n}^{n-1}ab^{n-1}+C\,_{n}^{n}b^{n}$. Они называются биномиальными коэффициентами.

При составлении сочетаний каждый элемент может повторяться несколько раз. Число сочетаний из n элементов по m с повторениями равно ${\overline {C\,_{n}^{m}}}=C\,_{n+m-1}^{m}={\frac {(n+m-1)!}{m!(n-1)!}}$.

Свойства сочетаний

Основные свойства сочетаний выражаются формулами:

1. $C\,_{n}^{n}=1$;
2. $C\,_{n}^{0}=1$;
3. $C\,_{n}^{k}=C\,_{n}^{n-k}$;
4. $C\,_{n}^{k}=C\,_{n-1}^{k}+C\,_{n-1}^{k-1}$ — рекуррентное свойство.

История

Фрагмент треугольника Паскаля

Термин «сочетание» (фран. combination) появляется у Блёза Паскаля в 1653 году, а в публикациях употребляется с 1665 года. В «Трактате об арифметическом треугольнике» («Traitd du triangle arithmdtique», 1665 год) Паскаль привёл основные соотношения между биномиальными коэффициентами. Каждая n-я строка арифметической конструкции, названной впоследствии «треугольником Паскаля», содержит биномиальные коэффициенты: $C_{n}^{0},C_{n}^{1},C_{n}^{2},...C_{n}^{n}$.

Обозначение $C\,_{n}^{k}$ по первой букве латинского названия введено британским математиком Робертом Поттсом в 1880 году (правда, в несколько иной форме: $^{n}C_{p}$). Второе принятое сейчас обозначение введено Леонардом Эйлером в виде $\left({\frac {n}{m}}\right)$, $\left[{\frac {n}{m}}\right]$, эти обозначения он употреблял в рукописях 1778, 1781 годов. Обозначения упрощены до современного вида венским математиком Андреасом фон Эттингсхаузеном (1827 год).

Примечания

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Знание.Вики» («znanierussia.ru») под названием «Сочетания», расположенная по следующим адресам: — «https://baza.znanierussia.ru/mediawiki/index.php/Сочетания» — «https://znanierussia.ru/articles/Сочетания» Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Знание.Вики предлагается прочитать материал «Почему Циклопедия?».