ganesh_6's blog

By ganesh_6, 2 months ago, In English

For the expression, do we have a formula like we have for $$$\binom{n}{0} + \binom{n}{1} + \binom{n}{2}+\binom{n}{3}+\binom{n}{4}+... = 2^n$$$

$$$\binom{n}{0} * 0! + \binom{n}{1} * 1!+ \binom{n}{2}*2!+\binom{n}{3}*3!+\binom{n}{4}*4!+...$$$ ?

This gives an intuition like taking 0 or 1 0r 2 0r 3... items from n items and permute them in a given place.

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ganesh_6 (previous revision, new revision, compare).

»
2 months ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

Wolfram Alpha gives me this as a result.

$$$\sum_{k=0}^n {k! {n \choose k}}=e Γ(n+1,n)$$$

Now I have a headache on understanding this...

UPD: I have found an OEIS entry (A000522) for this sequence. I hope this helps you as well.

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Let S(n)=1+n+n*(n-1)+n*(n-1)*(n-2)....... which is equivalent to the sum you have given.
now after sum algebra, we have a recurrence relation, S(n)=n*S(n-1)+1 and hence to find the final sum you will have to use incomplete gamma function which I don't think you can find in O(1).
So the best I can tell you is O(n).
Wolfram for the same idea.
I will also be interested in knowing if there exists a O(1) method.

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

This is $$$\sum_{i=0}^{n} \frac{n!}{i!}$$$, which is equal to $$$\lfloor e\cdot n!\rfloor$$$ as $$$\sum_{i=0}^{\infty} \frac{1}{i!}=e$$$ and $$$n!\cdot \sum_{i=n+1}^{\infty}\frac{1}{i!}<1$$$. This is not $$$O(1)$$$ obviously but might be what you are looking for.