What's the lower bound of the sum $S(n) = \sum_{k=1}^n \prod_{j=1}^k(1-\frac j n)$?

If we have

$$ S(n) = \sum_{k=1}^n \prod_{j=1}^k(1-\frac j n) $$

What the lower bound of $S(n)$ when $n\to\infty$?

PS: If I didn't make any mistake when I calculate $S(n)$, then it should be $\Omega(n)$. But I don't know how to get it.

We can do a bit better then a lower bound. We can find the main term, which is $\sqrt{\frac{\pi n}{2}}$.

Notice that $$\prod_{j=1}^{k}\left(1-\frac{j}{n}\right)=\frac{1}{n^{k}}\prod_{j=1}^{k}\left(n-j\right)=\frac{1}{n^{k}}\frac{(n-1)!}{(n-k-1)!}=\frac{\left(n-1\right)_{k}}{n^{k}}.$$ Using this, and the fact that the $k=n$ term is $0$, we can rewrite our series as

$$(n-1)!\sum_{k=1}^{n-1}\frac{1}{n^{k}(n-k-1)!}=\frac{(n-1)!}{n^{n-1}}\sum_{k=1}^{n-1}\frac{n^{n-k-1}}{(n-k-1)!}=\frac{(n-1)!}{n^{n-1}}\sum_{j=0}^{n-2}\frac{n^{j}}{j!}.$$

Where the last line follows from the substitution $j=n-k-1$. This last sum is the truncated exponential series with $x=n$. Specifically we have that $$\sum_{k=0}^{n-2}\frac{n^{k}}{k!}\sim \frac{1}{2}e^{n}.$$ Thus our series is $$\sim\frac{e^{n}(n-1)!}{2n^{n-1}}.$$ By Stirling's Formula, the main term is $$\frac{e^{n}(n-1)!}{n^{n-1}}=\sqrt{2\pi n}+O\left(\frac{1}{\sqrt{n}}\right),$$ so we are able to conclude that $$\sum_{k=1}^{n}\prod_{j=1}^{k}\left(1-\frac{j}{n}\right)\sim\sqrt{\frac{\pi n}{2}}.$$

Hope that helps,

Edit: A factor of two was missing earlier. Thanks to Didier Piau for pointing this out.

This is $Q(n)-1$, where $Q(n)$ is a sum that appears repeatedly in Knuth's work and that I mention in my answer to your other question. A slight adaptation of the argument there shows that the dominant term is (in the notation of the answer) $T_n(0)$, and so we get $$Q(n) = S(n)+1 = \sqrt{\frac{\pi n}{2}} + O(1).$$ If you want a more precise asymptotic, you can check out Knuth's Art of Computer Programming, Vol. 1 (3rd ed.), Section 1.2.11.3 (again, as I mention in my other answer). He gives $$Q(n) = S(n)+1 = \sqrt{\frac{\pi n}{2}} - \frac{1}{3} + \frac{1}{12} \sqrt{\frac{\pi }{2n}} - \frac{4}{135n} + O(n^{-3/2}).$$