Формула для числа сочетаний, на пальцах.

[Don-Don]

Как доказать, что $C_{n+1}^{k+1}=C_n^k+C_n^{k+1}$, не используя формулу для $C_n^k$? (как используя формулу это сделать -- знаю)

Почему число способов выбрать из $n+1$ предмета ровно $k+1$ равно сумме числа способов из $n$ выбрать $k$ и числа способов из $n$ выбрать $k+1$?

-- 04.11.2014, 20:46 --

Кстати, а как саму формулу $\dfrac{n!}{k!(n-k)!}$ можно объяснить на пальцах?

[Brukvalub]

Возьмем один предмет и выделим его. Первое слагаемое справа отвечает ситуации, когда этот предмет попадает в группу выбранных, а второе слагаемое - когда он не выбран.

[Don-Don]

Brukvalub в сообщении #926572 писал(а):

Возьмем один предмет и выделим его. Первое слагаемое справа отвечает ситуации, когда этот предмет попадает в группу выбранных, а второе слагаемое - когда он не выбран.

А почему первое справа -- когда попадает в группу выбранных? Ведь там из $n$ предметов выбирается $k$, то есть из невыбранных предметов формируется число... Или не так?

[Brukvalub]

Выделенный элемент считается заранее выбранным, добираются оставшиеся элементы.

[Ratix]

На счет объяснения на пальцах :
Представим что у нас есть $k$ предметов и $n$ свободных мест. Тогда разместить первый предмет мы сможем $n$ способами, второй - $n-1$, третий - $n-2$, ... $k$-й - $n-k+1$. Получаем $ N = n(n-1)(n-2)\cdot...\cdot(n-k+1) $ ; для удобства эту формулу представляют в виде $\frac{n!}{(n-k)!}$ , полагаю, вам она известна, это формула размещения из n элементов по k. Чем размещение отличается от сочетания? Тем что элементы сочетания неразличимы т.е. если мы поменяем любые из символов местами это будет тот же способ, что и прежде. Количество способов перестановки $k$ элементов между собой равно $k!$ ,отсюда и получаем формулу $C_n^k = \frac{n!}{(n-k)!k!}$

[Lia]

Ratix
Оформляйте все формулы.

(Оффтоп)

Ratix в сообщении #926595 писал(а):

k предметов

Ratix в сообщении #926595 писал(а):

n свободных

Ratix в сообщении #926595 писал(а):

n-1, третий - n-2, ... k-й - n-k+1.

и т.д.

[Don-Don]

Ratix в сообщении #926595 писал(а):

На счет объяснения на пальцах :
Представим что у нас есть $k$ предметов и $n$ свободных мест. Тогда разместить первый предмет мы сможем $n$ способами, второй - $n-1$, третий - $n-2$, ... $k$-й - $n-k+1$. Получаем $ N = n(n-1)(n-2)\cdot...\cdot(n-k+1) $ ; для удобства эту формулу представляют в виде $\frac{n!}{(n-k)!}$ , полагаю, вам она известна, это формула размещения из n элементов по k. Чем размещение отличается от сочетания? Тем что элементы сочетания неразличимы т.е. если мы поменяем любые из символов местами это будет тот же способ, что и прежде. Количество способов перестановки $k$ элементов между собой равно $k!$ ,отсюда и получаем формулу $C_n^k = \frac{n!}{(n-k)!k!}$

Спасибо, понятно!

-- 04.11.2014, 22:39 --

Don-Don в сообщении #926577 писал(а):

Brukvalub в сообщении #926572 писал(а):

Возьмем один предмет и выделим его. Первое слагаемое справа отвечает ситуации, когда этот предмет попадает в группу выбранных, а второе слагаемое - когда он не выбран.

А почему первое справа -- когда попадает в группу выбранных? Ведь там из $n$ предметов выбирается $k$, то есть из невыбранных предметов формируется число... Или не так?

Хорошо, но можно по-подробнее, что-то все равно не понимаю. $C_n^{k+1}$ отвечает ситуации, когда предмет попадает в группу избранных, но как отвечает, почему именно $C_n^{k+1}$?

[iifat]

Попробуйте таки на кой-нить вопрос ответить.
Вот у нас есть $n+1$ предметов — $a_1,\dots,a_{n+1}$. Сколько есть вариантов выбрать $k+1$ предметов при условии, что $a_{n+1}$ входит в выбранные?

[ewert]

Don-Don в сообщении #926570 писал(а):

Как доказать, что $C_{n+1}^{k+1}=C_n^k+C_n^{k+1}$, не используя формулу для $C_n^k$?

Помимо того, что $C_n^k$ -- это сочетания, это ещё и биномиальные коэффициенты. Т.е. в разложении $(x+1)^n=\sum\limits_{k=0}^nC_n^kx^k 1^{n-k}$ коэффициенты разложения -- это количества сочетаний независимо ни от каких факториалов. Теперь умножьте это разложение на $(x+1)$, раскройте скобки и приведите подобные; ровно то рекуррентное соотношение и получится.

[Brukvalub]

Don-Don в сообщении #926577 писал(а):

Brukvalub в сообщении #926572 писал(а):

Возьмем один предмет и выделим его. Первое слагаемое справа отвечает ситуации, когда этот предмет попадает в группу выбранных, а второе слагаемое - когда он не выбран.

Хорошо, но можно по-подробнее, что-то все равно не понимаю. $C_n^{k+1}$ отвечает ситуации, когда предмет попадает в группу избранных, но как отвечает, почему именно $C_n^{k+1}$?

Вы перепутали слагаемые. За ситуацию, когда выделенный предмет попадает в группу избранных, отвечает слагаемое $C_n^{k}$, поскольку из оставшихся $n$ предметов осталось выбрать $k$ штук.

[arseniiv]

(Если вдруг предыдущего недостаточно.)

Для наглядности можно нарисовать все сочетания из, скажем, 4 по 2 (колонка 1; o — предмет входит в сочетание, ⋅ — нет):

   1           2          3

o o ⋅ ⋅      o ⋅ ⋅
o ⋅ o ⋅      ⋅ o ⋅
o ⋅ ⋅ o      ⋅ ⋅ o
⋅ o o ⋅                 o o ⋅
⋅ o ⋅ o                 o ⋅ o
⋅ ⋅ o o                 ⋅ o o

из 4 по 2   из 3 по 1  из 3 по 2

Мы можем получить их, выбирая или не выбирая первый элемент, и взяв сочетания из оставшихся предметов (на 1 меньше) по оставшееся количество. В случае выбора элемента эти сочетания (2) — по меньшее на 1 количество, а в случае невыбора (3) — по то же.