Question Posted in class

Federico posted a question today about what  \sum_{k=0}^n k\binom{n}{k} equals. This is what I tried out, so let me know what you think. 

 He showed in class how \sum_{k=0}^n \binom{n}{k}x^k=(1+x)^n . By differentiating both sides we get \sum_{k=0}^n k\binom{n}{k}x^{k-1}=\sum_{k=1}^n k\binom{n}{k}x^{k-1}=n(1+x)^{n-1} . Thus we plug 1 and get that \sum_{k=1}^n k\binom{n}{k}=n2^{n-1} .

Thus we have that \sum_{k=0}^n k\binom{n}{k}=n2^{n-1}

I tried to make sense of this combinatorially and think that it tells us that for a set S such that |S|=n  the number of ways to choose an element of S and creating a subset containing it is equal to the number of ways to choose a subset of S and picking out an element from it. 

For example take \{1,2,3\} . For the first case say we pick the element 2, then we can create the subsets \{2\},\{1,2\},\{2,3\},\{1,2,3\} . Since we can pick 3 elements and do this for each one, we have a total of 12=3(4)=3(2^{3-1}) . Now for the second question we can choose the empty set but have no way of choosing an element ( 0 ways), choose a 1-set and then an element(\binom{3}{1}(1) ways), a 2-subset and then an element(\binom{3}{2}(2) ways), or a 3-subset and then an elements(\binom{3}{3}(3) ways). Thus giving us a total of \binom{3}{0}(0)+\binom{3}{1}(1)+\binom{3}{2}(2)+\binom{3}{3}(3)= 0+3+6+3=12  ways. 

Cool way to use analysis and algebra to get a not so obvious(at least to me) combinatorial result. 

Advertisements

6 comments

  1. paco9208

    For an algebraic proof we can use the identity $k*\{n\choose k} = n*\{(n-1)\choose(k-1)}$ and then just factor the n out, in case the interval of convergence for such series does not include x=1.

  2. Nice Paco. Dude the latex is a bit different here. To type a formula in WordPress type  without the signs .

  3. ***To type a formula in WordPress type $ latex Your LaTex code $ without the space between $ and latex.

  4. Three nice proofs! (Notice that there is no issue of convergence here because this is an equality of polynomials, so plugging in x=1 is fine.)

  5. suitored

    I know is kind of late for this but I just saw the video of lecture 2. Another nice interpretation is that sum_{k=0}^{n}k {n\choose k} is the “weight” of 2^[n] if we assume that the weight of a single element is 1. Then, if you take any element, the number of subsets containing it is 2^{n-1} so each element in {1, \dots ,n} appears 2^{n-1} times in 2^[n]. Now just multiply by because there are n elements.

  6. suitored

    Sorry, is 2^{[n]} in both strange things.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: