[Guest]

Hi all,

The binomial equation is quite well known:

Sum(^NC_r), {0 <= r <= N} = 2^N

^NC_r is the number of combinations of N objects taken r at a time.

Can you find a similar closed form expression (http://en.wikipedia.org/wiki/Closed-form_expression) for permutations? In the scope of this puzzle, a factorial operation is included in the allowed operations of "closed form expression", along with others such as addition, multiplication etc.

Sum(^NP_r), {0 <= r <= N} = ?

^NP_r is the number of permutations of N objects taken r at a time.

This is an original puzzle, so googling won't help. I'm sure this has never come up elsewhere until now.

Have fun.

[Guest]

Edit: I'm using the term "closed form" loosely.. to mean a simpler form. For e.g, 2^N is a "simpler" form than the summation expression.

[k-man]

e*N! rounded to the nearest whole number

Edited January 31, 2011 by k-man

[Guest]

e*N! rounded to the nearest whole number

Great! Can you post your solution?

[EventHorizon]

The number of permutations of n objects taken r at a time is n!/(n-r)!

The sum of this over all r leaves n! as the numerator of each, so that can be moved out of the summation.

The summation is left as 1/(n-r)! where r is from 0 to n, which is the same as the sum of 1/r! over the same range (just flipped the order).

According to wikipedia, that sum is equal to e as r approaches infinity.

This leaves e*n! as the number it approaches at n increases.

[Guest]

if N = 1, we have 2. 1!/0! +1!/1! 1!*(1+1) = 2

if N = 2, we have 5. 2!/0! +2!/1! +2!/2! = 2!*(1+1+1/2) = 2! *(5/2) = 5

if N = 3, we have 16. 3!/0! +3!/1! +3!/2! +3!/3! =3!*(1+1+1/2+1/6) = 3!*(16/6) = 16

if N = 4, we have 65. 4!/0! +4!/1! +4!/2! +4!/3! +4!/4! = 4!*(1+1+1/2+1/6+1/24) = 4!*(65/24) = 65

recursively, we have that the next value, N, is the previous value, multiplied by the input, and add 1.

so N =25 =1 +25*(1+24*(1 +23*(1 +22*...2*(1+1))...)

which is about as exact as your gonna get :-)

[Guest]

floor(N!*e), where floor(x) is the greatest integer lesser than x

But I'm looking for a mathematical proof..

Prove that the summation Sum(N!/r!), {0 <= r <= N} equals floor(N!*e)