Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics Sum

  1. Feb 25, 2013 #1
    Hi all,

    Can anyone gimme any clues to solve the sum below (or solve it outright :D)?

    [tex]\sum_{i=k}^{n} \frac{i!}{(i-k)!}[/tex]

    I'm trying to solve one of Feyman's logic problems (bored geek alert) and I'm stuck at this point. And since my highschool days are so far behind...

    Thanks in advance!
  2. jcsd
  3. Feb 25, 2013 #2
    if it helps it's the sum of k! * i choose k

    or you could break it down into gamma(i+1)/(gamma(i-k+1)
  4. Feb 25, 2013 #3
    Thanks for the input, jwatts, but I'm afraid I didn't get much, I did warn you my highschool days are way behind me..

    What do you mean by "choose k"?

    As for the gamma function, I kinda think I'm gonna get even farther from the answer, considering my current ability.
  5. Feb 25, 2013 #4
    n choose k = n!/k!(n-k)! it's called the binomial coefficient

    saying it's k!*(n choose k) is kind of redundant but it let's you look at it in a different way
    same way as looking at it like a gamma, even though gamma is used for continuous situations normally
  6. Feb 25, 2013 #5
    ok so the sum goes a bit like this k!(1+ (k+1)+((k+2)(k+1)/2)+((k+1)(k+2)(k+3)/3)+...)
  7. Feb 25, 2013 #6
    Oh, I see what you mean. Unfortunately that doesn't help, as it's precisely the way I got up to this point :) I'm not familiar with the "n choose k" terminology, that's why I was confused.

    Thanks anyway, I'll keep trying.
  8. Feb 28, 2013 #7
    It's possible with generating functions: use the fact that (i choose k) is the coefficient of x^k in (1+x)^i, so the sum is the coefficient of x^k in k!*((1+x)^n-(1+x)^k)/x.
  9. Mar 1, 2013 #8


    User Avatar

    Last edited: Mar 1, 2013
  10. Mar 1, 2013 #9
    Thanks a lot for your help, ssd! I really really appreciate it :)

    However, in the meantime I changed my approach a bit (was trying to solve Feynman's Restaurant Problem) and I managed to get to a simpler sum, which I was able to calculate, to my complete surprise. I guess it just was way easier, although the method I used is for sure not optimal :)

    [tex]\sum_{i=k}^{n} i{i-1 \choose k-1}=k{n+1 \choose k+1}[/tex]

    But thanks again for your solution, I'll sure learn something from your reasoning.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook