C из n по k
Автор K0valSKy задал вопрос в разделе Естественные науки
Как самому вывести формулу числа сочетаний? и получил лучший ответ
Ответ от Зеркало[гуру]
Что есть число сочетаний? Допустим, у нас есть n коробок и k шариков, причём, шарики друг от друга не отличаются, а коробки отличаются. Число сочетаний из n по k - это число способов, которыми можно разместить эти k шариков в n коробках. Первый шарик можно разместить в любой из n коробок, второй - в любой их оставшихся (n-1) коробке, третий в любой из оставшихся (n-2) коробках ...k-й - в любой из оставшихся (n-k+1) коробках. Всего получается n*(n-1)*(n-2)*...*(n-k+1) способов. Представим это в виде дроби и домножим и числитель и знаменатель на (n-k)!: (n*(n-1)*(n-2)*...*(n-k+1)*(n-k)*(n-k-1)*...*1)/(n-k)! = n!/(n-k)!
А теперь вспомним, что нам не важен порядок, в котором мы выбирали шарики. Следовательно полученное число надо разделить ещё на число способов, которыми можно выбирать шарики. Всего шариков k. Первый шарик можно выбрать k способами, второй - (k-1) способом, третий - (k-2) способами ...последний единственным способом, следовательно число способов, которыми можно выбрать каждый шарик равно k*(k-1)*(k-2)*...*1 = k!
Таким образом, окончательно число сочетаний из n по k получается равным:
n!/((n-k)!*k!), ч. т. д.
Число размещений из n по k находится просто: A(n,k)=n(n-1)(n-2)...(n-k+1).
Число сочетаний отличается от него тем, что в нём не учитывается порядок выборки элементов.
След-но, чтобы получить C(n,k), необходимо поделить A(n,k) на число перестановок из k элементов, т. е. поделить на k!: C(n,k)=A(n,k)/k!.
Если теперь домножить числитель и знаменатель на (n-k)!, получите ту самую формулу.
Если я тебе её выведу, это уже будет, что ты её вывел не сам. А тебе надо - САМОМУ! Так что ручку в зубы и вперёд.