дискретная-математика - Дискретная математика: соотношения

В первом задании ответом будет $%0$% по причине того, что числа $%C_{2p+1}^k$% и $%C_{2p+1}^{2p+1-k}$% равны. Далее они возводятся в куб и умножаются на $%(-1)^k$% и $%(-1)^{2p+1-k}$% соответственно, но второе число противоположно первому по знаку. Поэтому все $%2p+2$% слагаемых (их будет именно столько по причине наличия $%(C_{2p+1}^0)^3$%) разобьются на пары чисел противоположного знака, и тем самым взаимно сократятся. Например, при $%p=2$% это будет выглядеть так: $$(C_5^0)^3-(C_5^1)^3+(C_5^2)^3-(C_5^3)^3+(C_5^4)^3-(C_5^5)^3$$ то есть $$1^3-5^3+10^3-10^3+5^3-1^3=0.$$

Во втором задании можно опереться на комбинаторное определение чисел Стирлинга II рода. В данном случае речь идёт о разбиении $%n$%-элементного множества на $%n-2$% части (непустые, и попарно не пересекающиеся). У каждой из таких частей есть по одному элементу, и остаётся ещё два дополнительных, которые надо куда-то поместить. Они могут входить в одну часть разбиения, или в разные. Первому случаю соответствует разбиение типа $%n=3+3+1+\cdots+1$%, когда одна часть состоит из трёх элементов, а все остальные одноэлементны. Ясно, что такое разбиение однозначно определяется трёхэлементной частью. Выбор её осуществляется $%C_n^3$% способами, что даёт первое слагаемое. Второму случаю соответствует разбиение типа $%n=2+2+1+\cdots+1$%, когда две части состоят из двух элементов, а все остальные одноэлементны. Здесь мы сначала выбираем четвёрку, что можно сделать $%C_n^4$% способами, а потом делим эту четвёрку на пары. Последнее осуществляется тремя способами: если перед нами имеется четвёрка $%\{a,b,c,d\}$%, то разбить её на две пары -- это всё равно что указать, с каким из трёх элементов вместе будет находиться $%a$%. Таким образом, второе слагаемое суммы будет равно $%3C_n^4$%, и вместе это всё даёт $$S(n,n-2)=C_n^3+3C_n^4.$$ Можно также было бы воспользоваться рекуррентными формулами для чисел Стирлинга II рода и доказать требуемое равенство методом математической индукции, но комбинаторное рассуждение проще.