Задача на доказательство. Комбинаторика.

[Dosaev]

Ну вроде ясно... так смутно пока.

[Whitaker]

Что смутного?

[Dosaev]

Вообще, давайте разберем пожалуйста, что значит разложить(разместить) k объектов по n ящикам, и выбрать из n объектов k объектов. Это одно и то же, в случае если объекты неразличимые, а ящики разные? При этом нам неважен порядок объектов в ящике.

[Whitaker]

Давайте с более простого:
Пусть у нас $4$ элемента:$ \{a, b, c, d\}$
Выбрать $1$ элемент можно четыремя способами. Это следующие выборы: $a, b, c, d$.
Выбрать $2$ элемента можно $6$ способами. Это следующие выборы: $ab, ac, ad, bc, bd, cd$.
Выбрать $3$ элемента можно $4$ способами. Это выборы вида: $abc, abd, acd, bcd$.
Выбрать $4$ элемента можно одним способом и это $abcd$.

-- Вс дек 04, 2011 21:45:53 --

Вам понятно?

[Dosaev]

Да!

[Whitaker]

В курсе комбинаторики доказывается что число сочетаний из $n$ элементов по $k$ равно $C_{n}^{k}=\dfrac{n!}{k!(n-k)!}$. Надеюсь, Вы это можете доказать?

[Dosaev]

Хэ, да, я не очень понимаю доказательство этой формулы. А именно не понятно почему мы делим на k!. Ну и что, что нам не важен порядок в сочетаниях, почему именно делить на k! ?

[Whitaker]

Если Вы знаете, есть такая формула $A_n^k=k!C_n^k$.
$A_n^k$ - число размещений из $n$ по $k$. В размещениях порядок существен, а в сочетаниях нет.

[Dosaev]

Ну почему тогда мы умножаем именно на k! ?

[Whitaker]

Потому что $k$ различных элементов можно переставить $k!$ способами.
Так как для нас порядок несуществен именно поэтому делим $A_n^k$ на $k!$ и получаем $C_n^k$.

[Dosaev]

А умножаем мы на k! потому, что у нас есть $C_n^k$ способов выбрать неупорядоченных выборок, да еще k! cпособов их упорядочить. Тогда по правилу произведения получаем $k!C_n^k$способов размещения? Правильно?

[Whitaker]

Ну да получаем количество размещений из $n$ по $k$, т.е.$A_n^k=k!C_n^k$

[Dosaev]

Объект А - это k - выборка (неупорядоченная, без повторений). Объект А мы можем выбрать $C_n^k$ способами. Объект B - упорядоченная k - выборка, объект B может быть выбран k! способами, тогда выбор двух объектов A и B даст нам размещение $A_n^k$. Теперь все стало на свои места. Так вот...возвращаясь к вопросу : чем отличается разместить от выбрать?

[Whitaker]

Пусть нужно разместить элементы $\{a,b,c\}$ в $2$ неразличимых ящика.
В каждый способ я поставлю | в качестве разделителя.
Возможны такие случаи:
$a|b, c$
$b|c, a$
$c|a, b$
$a,b,c|$
Если ящики различимы, то:
$a|b, c$
$b|c, a$
$c|a, b$
$b, c|a$
$c, a|b$
$a, b|c$
$|a, b, c$
$a, b, c|$

[Dosaev]

ясно.

-- Вс дек 04, 2011 23:09:45 --

На примерах я все понимаю, но как дело заходит до общих формул, тут тупик.