2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3  След.
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 21:31 
Аватара пользователя
Ну вроде ясно... так смутно пока.

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 21:32 
Аватара пользователя
Что смутного?

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

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 21:44 
Аватара пользователя
Давайте с более простого:
Пусть у нас $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 --

Вам понятно?

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 21:46 
Аватара пользователя
Да!

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

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 21:58 
Аватара пользователя
Хэ, да, я не очень понимаю доказательство этой формулы. А именно не понятно почему мы делим на k!. :-) Ну и что, что нам не важен порядок в сочетаниях, почему именно делить на k! ?

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 22:01 
Аватара пользователя
Если Вы знаете, есть такая формула $A_n^k=k!C_n^k$.
$A_n^k$ - число размещений из $n$ по $k$. В размещениях порядок существен, а в сочетаниях нет.

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 22:04 
Аватара пользователя
Ну почему тогда мы умножаем именно на k! ?

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 22:10 
Аватара пользователя
Потому что $k$ различных элементов можно переставить $k!$ способами.
Так как для нас порядок несуществен именно поэтому делим $A_n^k$ на $k!$ и получаем $C_n^k$.

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

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 22:24 
Аватара пользователя
Ну да получаем количество размещений из $n$ по $k$, т.е.$A_n^k=k!C_n^k$

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

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 23:00 
Аватара пользователя
Пусть нужно разместить элементы $\{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|$

 
 
 
 Re: Задача на доказательство. Комбинаторика.
Сообщение04.12.2011, 23:09 
Аватара пользователя
ясно.

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

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

 
 
 [ Сообщений: 41 ]  На страницу Пред.  1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group