MedoN11's blog

By MedoN11, history, 9 days ago, In English,

Hello.

Recently, I was solving a problem to which I simplified it to evaluating this summation:

C is n choose k. N is up to 1000, and K is up to 2^30.

Answer appears to be I guess {K * (N - 1)K}

I can't get however how to arrive at this, or perhaps compute the original summation in a smart way, I tried messing expanding nCk to factorials, but didn't get anywhere. <.<

 
 
 
 
  • Vote: I like it  
  • +12
  • Vote: I do not like it  

»
9 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Hi. Do you have to modulo the answer by some prime number?

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Modulo any number from 1 to 10^5 range.

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I mean, do you have to modulo the final answer by 1e9+7 or some other prime number? Because the final answer could be very big

»
9 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Answer should be K·NK - 1.

You can see it like this: For all sequences constisting of 0 and 1 we sum number of ones multiplied by (N - 1)zeroes. It is equal to sum for all sequences for all ones (N - 1)zeroes. Then group summands by index of 1. We will get Sum for all positions .

  • »
    »
    8 days ago, # ^ |
    Rev. 7   Vote: I like it 0 Vote: I do not like it

    Nice solution. Thanks !

    If someone else searches this in future or interested, there is also another way to look at it : Imagine K loops each from 1 to n, and in the final one you pick the K items your indices chose from N. It's equivalent to the summation. There will be K*N^K values picked in total, so you can see each element will contribute (K * NK) / N times.

»
9 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Wolfram alpha says that the answer to this sum is ( K * N^(K-1) ) and not ( K * (N-1)^K), but I still don't know how to get to that

Sum link
http://www.wolframalpha.com/input/?i=summation++from+i+%3D+0+to+i+%3D+k+of++%5Bi+*+(N-1)%5E(k-i)+*+(k+choose+i)%5D

»
8 days ago, # |
  Vote: I like it +7 Vote: I do not like it

The answer is K·NK - 1.

The last equality follows from the binomial theorem.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I initially could arrive at the second equation but didn't figure out the third simplification, do you mind explaining how did you move from the second one to the third? Maybe it's easy but I don't seem to see it. :(

    Thanks!

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Just expand the formula for and simplify. Alternatively, there's a combinatorial explanation. We count the number of ways to choose a team of i people from K and choose a observer from the rest K - i.

      Answer 1: ways to choose the team. K - i to choose the observer. The answer is

      Answer 2: This time we choose the observer first. He can be chosen K ways. The team can be chosen from the rest K - 1 in ways. The answer is