Биномиальные коэффициенты

курсовая работа

1. Сочетания

1.1 Числа Сkn

Пусть X - множество, состоящее из n элементов. Любое подмножество Y множества X, содержащее k элементов, называется сочетанием k элементов из n; при этом, разумеется, k ? n.

Число различных сочетаний k элементов из n обозначается Сnk . Одной из важнейших формул комбинаторики является следующая формула для числа Сnk :

Её можно записать после очевидных сокращений следующим образом:

В частности,

Это вполне согласуется с тем, что в множестве X имеется только одно подмножество из 0 элементов - пустое подмножество.

Приведём доказательство формулы (2). Пусть Y - какое-либо подмножество множества X , содержащее k элементов. Составив всевозможные перестановки из этих элементов, получим k! различных строк длинной k. Если указанную операцию проделать с каждым подмножеством Y, содержащим k элементов, то получим всего Cnk · k! различных строк длинной k . Но очевидно, что таким путём должны получиться все без исключения строки длиной k без повторений, которые можно составить из элементов множества X. поскольку число таких строк равно Ank , то имеем соотношение Cnk · k! = An , из которого следует Cnk =Akn, т.е. формула (2).

Делись добром ;)