2
1

Необходимо вывести комбинаторное доказательство формул.

1.$$ \sum_{k=0}^n (-1)^k C_n^k = 0$$ 2.$$ \sum_{k=1}^n k C_n^k = n2^{n-1}$$ Без использования аналитических преобразований или ММИ. Или подскажите литературу где есть несколько примеров с доказательствами. В любом случае буду очень признателен.

задан 26 Янв '13 18:47

изменен 26 Янв '13 23:42

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

первую сделал, осталась 2-я

(28 Янв '13 10:48) zhildemon
10|600 символов нужно символов осталось
3

Первое равенство имеет следующий комбинаторный смысл: в любом $%n$%-элементном множестве, при $%n\ge1$%, имеется одинаковое количество подмножеств с чётным и с нечётным числом элементов. Поэтому для комбинаторного доказательства надо установить взаимно-однозначное соответствие между "чётными" и "нечётными" подмножествами -- так будем их условно называть.

Если число $%n$% нечётно, то это совсем легко: каждому подмножеству ставим в соответствие его дополнение. Ясно, что "чётным" подмножествам при этом соответствуют "нечётные", и наоборот.

Пусть теперь $%n$% чётно. Поскольку $%n$% не равно нулю (для пустого множества сам факт вообще неверен), то зафиксируем какой-то элемент $%a$% из нашего $%n$%-элементного множества. Далее, в каждое подмножество, которому $%a$% не принадлежит, добавим этот элемент. А если $%a$% принадлежит подмножеству, то исключим его. Ясно, что при таком соответствии (оно будет взаимно-однозначным, будучи обратно самому себе) каждое множество меняет свою "чётность": количество элементов увеличивается или уменьшается на $%1$%.

По второму равенству: у слагаемого $%kC_n^k$% комбинаторный смысл таков: это число $%k$%-элементных подмножеств заданного $%n$%-элементного множества с одним выделенным элементом. Левая часть равенства, таким образом, равна общему количество (непустых) подмножеств с выделенным элементом. Эту же величину подсчитаем другим способом.

Выделить элемент мы можем $%n$% способами. Далее к нему добавим какое-то количество элементов из $%n-1$% оставшихся (включая случай, когда мы не добавляем ничего). Это значит, что мы к выделенному элементу присоединяем произвольное подмножество $%(n-1)$%-элементного множества, а таковых у нас имеется $%2^{n-1}$%. Далее применяем правило произведения, и получаем значение правой части равенства.

ссылка

отвечен 28 Янв '13 15:15

изменен 28 Янв '13 15:23

спасибо большое, без вас никак не получалось уловить смысл данного коэффициента

(28 Янв '13 18:18) zhildemon

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

Помимо стандартного равенства с суммой биномиальных коэффициентов, есть ещё хороший пример со свойством треугольника Паскаля --- когда требуется показать, что $$C_{n+1}^m=C_n^{m-1}+C_n^m$$ для всех $%1\le m\le n$%, а также факт относительно суммы квадратов биномиальных коэффициентов, то есть равенство $$(C_n^0)^2+(C_n^1)^2+\cdots+(C_n^n)^2=C_{2n}^n.$$

(28 Янв '13 19:47) falcao

Вообще говоря это мне тоже необходимо доказывать, как и ещё штук 20 других формул... Но надо научиться самому. Спасибо ещё раз.

(29 Янв '13 2:09) zhildemon
10|600 символов нужно символов осталось
2

Пусть $%A_1, A_2, ..., A_n$% - множества, состоящие из одного и того же единственного элемента. Тогда в силу формулы включений-исключений $$\left| \bigcup_{i=1}^n A_i \right| = $$ $$= \sum_{1 \leq i \leq n}|A_i|-\sum_{1 \leq i < j \leq n}|A_i \cap A_j|+\sum_{1 \leq i < j < k \leq n}|A_i \cap A_j \cap A_k| - ...+(-1)^{n-1} |A_1 \cap A_2 \cap ... \cap A_n|,$$ а в данном случае - $$ 1 = C_n^1 - C_n^2 + C_n^3 - ... +(-1)^{n-1}C_n^n,$$ или $$\sum_{k=0}^n (-1)^k C_n^k = 0.$$

ссылка

отвечен 29 Янв '13 1:01

изменен 29 Янв '13 14:31

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

Используйте бином Ньютона и поставьте в него $%-1$%. Второе легко доказывается с помощью производной.

ссылка

отвечен 26 Янв '13 22:36

Спасибо, но мне необходимо доказательство в рамках комбинаторики и теории множеств... к примеру: доказать что сумма биномиальных коэфициентов равна 2^n Доказательство: число всех k-элементных подмножеств в множестве без повторений - это число сочетаний из n по k, всего подмножеств в n-элементном множестве 2^n отсюда следует что сумма всех k-элементных подмножеств равна 2^n

(27 Янв '13 8:13) zhildemon

Минус вряд ли имеет комбинаторный смысл. Может, перенести эти слагаемые направо?

(27 Янв '13 11:40) DocentI

имеет смысл, если мы собираемся делать какие-то алгебраические преобразования, однако их делать нельзя... препод забраковал все алгебраические доказательства и доказательства с помощью тождества для (1+х)^n и сказал, что хочет видеть комбинаторное доказательство... что в общем непонятно как делать, кроме того случая, что я привёл в качестве примера

(27 Янв '13 13:13) zhildemon
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×746

задан
26 Янв '13 18:47

показан
4317 раз

обновлен
29 Янв '13 14:31

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

по почте:

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

по RSS:

Ответы

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

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