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.
Wolfram Alpha gives me this as a result.
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.
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%5D
He 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
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.