|
Необходимо вывести комбинаторное доказательство формул. 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 
zhildemon |
|
Первое равенство имеет следующий комбинаторный смысл: в любом $%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 
falcao спасибо большое, без вас никак не получалось уловить смысл данного коэффициента
(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
|
|
Пусть $%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 
splen |
|
Используйте бином Ньютона и поставьте в него $%-1$%. Второе легко доказывается с помощью производной. отвечен 26 Янв '13 22:36 
DocentI Спасибо, но мне необходимо доказательство в рамках комбинаторики и теории множеств... к примеру: доказать что сумма биномиальных коэфициентов равна 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
|
первую сделал, осталась 2-я