### ganesh_6's blog

By ganesh_6, 14 months ago, 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.  Comments (7)
| Write comment?
 » 14 months ago, # | ← Rev. 2 →   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.
•  » » 14 months ago, # ^ | ← Rev. 2 →   Can u share the url to that resource? How did u search it on google? I could not get any related results before posting here. Thanks
•  » » » https://www.wolframalpha.com/input?i2d=true&i=Sum%5Bk%21+*+nCr%5C%2840%29n%5C%2844%29k%5C%2841%29%2C%7Bk%2C0%2Cn%7D%5DHe did not google, he went straight to wolfram alpha, the best math formula solver website I know of. And wolfram alpha was, in fact, able to rearrange the formula. But it seems not to help, since the solution is the Incomplete Gamma Function: https://mathworld.wolfram.com/IncompleteGammaFunction.htmlWhich seems to take longer than O(1) to calculate: https://www.sciencedirect.com/science/article/pii/0377042785900342
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   Exactly. I soon figured that this would not be possible in $O(1)$ while I was thinking about how it could be done. (Basically the complete gamma function is implemented in the C++ STL. However, the incomplete variant is not.)
•  » » » » » Thank You Termii chromate00
 » 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.
 » 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.