2 combinatorics questions

[bugzpodder]

Could someone find a proof other than induction for these two equations?

1) nC1+2(n-1)*(nC2)+3(n-1)^2*(nC3)+...+n(n-1)^(n-1)*(nCn) = n^n

where n in N and n >= 2

2) Sum (from 3 to n) [3Pk*nCk] =(3Pn)*2^(n-3)



by the way, 3Pk is k!/(k-3)! some ppl like to write kP3

[krtxmrtz]

Originally posted by bugzpodder
nC1+2(n-1)*(nC2)+3(n-1)^2*(nC3)+...+n(n-1)^(n-1)*(nCn) = n^n

Is this a typo?

I may be wrong but are you sure the formula should not begin with "1" instead of "n"? i.e.

C1+2(n-1)*(nC2)+3(n-1)^2*(nC3)+...+n(n-1)^(n-1)*(nCn) = n^n

[bugzpodder]

looks fine to me! nCk=n choose k=n!/[(n-k)!k!]

[krtxmrtz]

Right, I was misled probably because the first C term was not enclosed within parenthesis and after 8 hours work my brain is somewhat overheated.
Just wanted to make sure before I tried my luck on this one.