Блог пользователя ganesh_6

Do we have O(1) formula for this?
Автор ganesh_6, 2 года назад, По-английски

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.

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
2 года назад, # |
← Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

→ Ответить