0

I am a software developer, had maths 15 years ago (so I beg for forgiveness if my notation below hurts your eyes), and would like to calculate the number of elements a certain algorithm will produce. The algorithm is implemented, works fine, and I know how to calculate the number of elements using a complex formula: $$C(n) = n!/(n-1)! + n!/(n-2)! + n!/(n-3)! + ... + n!/0!)$$

where:
n = number of input elements (positive integer)
C(n) = count of all generated elements for input of size n

E.g.

$$ C(1) = 1!/0! = 1/1 = 1$$ $$ C(2) = 2!/1! + 2!/0! = 2 + 2 = 4$$ $$ C(3) = 3!/2! + 3!/1! + 3!/0! = 3 + 6 + 6 = 15$$ $$ C(4) = 4!/3! + 4!/2! + 4!/1! + 4!/0! = 4 + 12 + 24 + 24 = 64$$ $$ C(5) = 325$$ $$ C(6) = 1956$$ etc.

Is there a way to present the formula in a simpler, more concise way? I tried, but the simplest notation I count come up with is this:

$$C(n) = n + n*(n-1) + n*(n-1)*(n-2) + n*(n-1)*(n-2)*(n-3) + ... + n*(n-1)*(n-2)* ... * (n-(n-1))$$

Let's take 4 as an example:

$$ C(4) = 4!/3! + 4!/2! + 4!/1! + 4!/0!$$ $$ C(4) = 4*3!/3! + 4*3*2!/2! + 4*3*2*1!/1! + 4*3*2*1*0!/0!$$ $$ C(4) = 4 + 4*3 + 4*3*2 + 4*3*2*1$$

bit it is still complex and I can't generalize it for n. When I think of it, it seems kind of like an arithmetic progression, but there is no common difference. Any help?

clathratus
  • 17,161
wujek
  • 103

2 Answers2

2

This is sequence A007526 in the On-Line Encyclopedia of Integer Sequences, given by $C(0)=0$ and $C(n)=n\cdot (C(n-1)+1)$. The entry lists some formulas, in particular a rather explicit one: $$ C(n) = \lfloor e\cdot n! - 1\rfloor, $$ where $\lfloor - \rfloor$ denotes rounding down. For example $$ C(6) = \lfloor e\cdot 6! - 1\rfloor = \lfloor 720e -1 \rfloor = \lfloor 1956.163 \rfloor = 1956. $$ Using Stirling's approximation for factorials, you can obtain an approximation as $$ C(n) \approx e\sqrt {2\pi n} \left({\frac {n}{\mathrm {e} }}\right)^{n} - 1. $$

Christoph
  • 24,912
  • 1
    Holy Moly, that formula with e works like a charm. This is pure magic. – wujek Mar 29 '20 at 12:51
  • Note that $e = \sum_{k=0}^\infty \frac{1}{k!}$. All the above formula does is multiply by $n!$, get rid of the $n$-th term and by rounding get rid of all the other terms that don't appear in your formula for $C(n)$. It's really just the definition $e$ that makes this work, not a lot of magic ;-) – Christoph Mar 29 '20 at 13:01
1

Just for the magical part with the $e$.

We have

$$C(n) = \sum_{k=1}^n\frac{n!}{(n-k)!}= n!\sum_{i=0}^{n-1}\frac 1{i!}$$

Now, Taylor ($e^x=\sum_{i=0}^{\infty}\frac{x^i}{i!}$) gives $$e - \sum_{i=0}^{n-1}\frac 1{i!} =\frac{e^t}{n!} \text{ with } 0<t<1$$

So, using $t = \frac 12$ we get a very good estimate for $C(n)$ up to $\pm 1$ by

$$C(n) \approx (n!e -\sqrt{e}) \text{ rounded to the nearest integer}$$

trancelocation
  • 32,243