Здравствуйте. Завтра экзамен по дискретной математике и для подготовки была дана такая задача:

Найти то, что изображено на картинке, доступной по ссылке ниже.

вот картинка формулы: http://hostingkartinok.com/show-image.php?id=9d5d956e012eb3a495d53f4bf1e079ef

Помогите пожалуйста.

задан 24 Июн '13 16:33

изменен 24 Июн '13 16:35

10|600 символов нужно символов осталось
1

При $%k\ge2$% имеет место следующее тождество: $$k(k-1)C_n^k=k(k-1)\frac{n!}{k!(n-k)!}=n(n-1)\frac{(n-2)!}{(k-2)!(n-k)!}=n(n-1)C_{n-2}^{k-2}.$$ Далее мы суммируем в пределах $%2\le k\le n$%. Множитель $%n(n-1)$% не зависит от $%k$%, а сумма сочетаний из $%n-2$% по всем числам $%k-2=0,...,n-2$% равна $%2^{n-2}$%. В ответе получается $%n(n-1)2^{n-2}$%, где $%n\ge2$%.

Второй способ подсчёта, чисто комбинаторный: рассмотрим половину суммы; слагаемые при этом имеют вид $%C_n^k\cdot C_k^2$%. Это значит, что мы сначала выбираем из $%n$% элементов какие-то $%k\ge2$%, а затем из $%k$% элементов отмечаем какие-то два. Что получается в результате? Два отмеченных элемента -- их выбор осуществляется $%C_n^2$% способами, а также разбиение оставшихся элементов на два подмножества, в одном из которых имеется $%k-2\ge0$% элементов, а в другом $%n-k$%. Ясно, что после выбора отмеченной пары мы ровно $%2^{n-2}$% способами можем задать $%(k-2)$%-элементное подмножество для всевозможных значений $%k$%, так как при суммировании число $%k-2$% принимает все значения от $%0$% до $%n-2$%. Тем самым, найденная нами полусумма составляет $%C_n^2\cdot2^{n-2}$%, и после умножения на $%2$% мы приходим к тому же ответу.

ссылка

отвечен 24 Июн '13 17:35

10|600 символов нужно символов осталось
3

Рассмотрим формулу бинома $%(1+x)^n=\sum\limits_{k=0}^{n} C_n^k x^k$%... найдём от неё две производные $%n(n-1)(1+x)^{n-2}=\sum\limits_{k=2}^{n} k(k−1)C_n^k x^{k-1}$%... и подставим $%x=1$%...

ссылка

отвечен 24 Июн '13 22:48

изменен 25 Июн '13 0:39

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×810
×746

задан
24 Июн '13 16:33

показан
976 раз

обновлен
25 Июн '13 0:39

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru