# Combinatorics Sum

1. Feb 25, 2013

### nowonda

Hi all,

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

$$\sum_{i=k}^{n} \frac{i!}{(i-k)!}$$

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...

Cheers!

2. Feb 25, 2013

### jwatts

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)

3. Feb 25, 2013

### nowonda

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.

4. Feb 25, 2013

### jwatts

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

5. Feb 25, 2013

### jwatts

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)+...)

6. Feb 25, 2013

### nowonda

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.

7. Feb 28, 2013

### bpet

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.

8. Mar 1, 2013

### ssd

Last edited: Mar 1, 2013
9. Mar 1, 2013

### nowonda

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 :)

$$\sum_{i=k}^{n} i{i-1 \choose k-1}=k{n+1 \choose k+1}$$

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

Cheers!