Partial sum Stirling number of the first kind with factorial and exponential

Question

I am hoping to compute a closed, or at least more readily computable, form of

$$ \frac{1}{n!} \sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix} k! \ x^k $$

where the brackets represent the unsigned Stirling number of the first kind. In my particular case, I have

$$ \frac{1}{n!} \sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix} \frac{k!}{(log(1-p))^k} \ z^k$$

with |z|, |p| < 1. At first I was excited to recognize the fraction inside the sum from the identity

$$ \frac{(log(1-p))^k}{k!} = \sum_{n=k}^{\infty} (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix} \frac{(-p)^n}{n!} $$

but, disappointingly, that doesn't seem to be doing me any good.

With some manipulation I was able to get my problem (which includes an outer sum of $n$ = 0 to $m$, not shown above) into a form like

$$ \sum_{n=1}^m \sum_{k=0}^{\infty} (-z)^k \frac{\sum_{j=k}^{n-1} \frac{(-p)^j}{j!} s(j,k) } {\sum_{j=k}^{\infty} \frac{(-p)^j}{j!} s(j,k)} $$

(where $s(j,k)$ is the signed Stirling number of the first kind), which looks nice and symmetrical, but again I can't figure out how to know anything about the partial sum in the numerator or its ratio to the complete infinite sum in the denominator, which again matches the identity above.

Any thoughts or advice most welcome. I've scoured Knuth et al's Concrete Mathematics and have tried poking around with generating functions and Stirling transforms with no avail. I potentially need to compute this sum quickly for $n$ > 1000, so computing or looking up the Stirling numbers then dividing by huge factorials is obviously not a great approach!

Background

This problem arose from trying to compute the Laplace transform of the PDF for the crossing time needed for the cumulative count of a compound Poisson process to reach a given level. It is known that if the underlying distribution is logarithmic, the PMF for a compound Poisson process is negative binomial, and I end up needing to compute a sum of Laplace transforms of something that looks like a negative binomial PMF, i.e., each term has the form

$$\mathcal{L} \frac{\Gamma(t+n)}{\Gamma(t)} = \mathcal{L} \{ t \ (t+1) \cdots(t+n-1)\}= \sum_{k=0}^{n} \begin{bmatrix} n \\ k \end{bmatrix} \frac{k!}{s^{k+1}},$$

where the other pieces above come from needing to plug in a certain formula for $s$. I have some flexibility in my assumptions about the underlying distribution and could choose something else geometric- or logarithmic-ish, or approximate it with a similar continuous distribution like an exponential, if it would make the problem easier.

Answer 1

With two variables, $n$ and $x,$ it is difficult to come up with a uniform approximation. However, for $x$ of moderate to large size, say, $x>0.5,$ the following approximation for large $n$ is excellent:

$$ [A] \quad \quad \frac{(-1)^n}{n!} \sum_{k=0}^n S_1(n,k) \, k! \,(- x)^k \sim \frac{e^{-1/x}}{x\,n} (1-e^{-1/x})^{-(n+1)} $$

Note that the left-hand side (LHS) of eq. [A] is the same as that of the proposer's through the phase relation between signed and unsigned Stirling numbers of the first kind. The key step in my proof is to use the known relationship between $S_1$ and the Norlund polynomials,

$$ S_1(n,k) = \frac{(n-1)!}{(k-1)!} \frac{B_{n-k}^{(n)}(0)}{(n-k)!} $$ where the Norlund polynomials are defined by the generating function $$\Big( \frac{t}{e^t-1} \Big)^s e^{y\,t} = \sum_{m=0}^\infty \dfrac{B_m^{(s)}(y)}{m!} x^m$$

Inserting the penultimate equation into the LHS of [A] and cancelling gamma factors we find $$ LHS[A] = \frac{(-1)^n}{n} \sum_{k=0}^n \frac{k}{(n-k)!} (-x)^k B_{n-k}^{(n)}(0)= \frac{(-1)^n}{n} x\,\frac{d}{dx} \sum_{k=0}^n \frac{(-1)^k x^k}{(n-k)!} B_{n-k}^{(n)}(0)$$

In the last step the $k$ in the numerator has been freed by $x \, d/dx \, x^k = k \, x^k.$ Now change the order of summation by $k \to n-k.$ Since $n$ is large, set the upper summation index to $\infty$ and we find $$ LHS[A] = \frac{1}{n} x\, \frac{d}{dx} x^n \sum_{k=0}^n \frac{ (-x)^{-k}}{k!} B_k^{(n)}(0) \sim \frac{1}{n} x\, \frac{d}{dx} x^n \sum_{k=0}^\infty \frac{ (-x)^{-k}}{k!} B_k^{(n)}(0) = $$ $$ = \frac{1}{n} x\, \frac{d}{dx} x^n \Big( \frac{-1/x}{e^{-1/x}-1} \Big)^n = \frac{e^{-1/x}}{x\,n} (1-e^{-1/x})^{-(n+1)}.$$

For a computational check, I let $x=0.5.$ For $n=25$ there are about 3 digits agreement between the LHS and RHS of eq. [A], and for $n=100,$ about 8 digits.

Answer 2

Seems easy to get a recurrence for $\frac{k!}{n!} \begin{bmatrix}n \\ k\end{bmatrix}$.

The recurrence that applies to Stirling numbers is (from Eric Weisstein's Mathworld):

$$\begin{bmatrix}n+1 \\ k\end{bmatrix} = n\begin{bmatrix}n \\ k\end{bmatrix} + \begin{bmatrix}n \\ k-1\end{bmatrix}$$

You can apply that recurrence to your situation, and rearrange a bit to get a new recurrence. Starting with $$\frac{k!}{(n+1)!}\begin{bmatrix}n+1 \\ k\end{bmatrix}$$ Applying the recurrence, $$\frac{k!}{(n+1)!}n\begin{bmatrix}n \\ k\end{bmatrix} + \frac{k!}{(n+1)!}\begin{bmatrix}n \\ k-1\end{bmatrix}$$ Rearranging a bit, $$\frac{n}{n+1} \frac{k!}{n!} \begin{bmatrix}n \\ k\end{bmatrix} + \frac{k}{n+1} \frac{(k-1)!}{n!} \begin{bmatrix}n \\ k-1\end{bmatrix}$$ So, now you've got a recurrence for the coefficients in your sum. Define $$A(n,k)=\frac{k!}{n!}\begin{bmatrix}n \\ k\end{bmatrix}$$ The recurrence is $$A(n+1,k)=\frac{n}{n+1}A(n,k) + \frac{k}{n+1}A(n,k-1)$$ This is useful because your sum of interest has the form $$\sum_{k=0}^n A(n,k) x^k$$ So what you actually do is create a $n$ by $n$ matrix, and put $A(0,0)$ in the top left of it. What we're going to do is we're going to put $A(n,k)$ in row $n$, column $k$ of this matrix. Fill up each row after the first using the recurrence. When filling up row $n+1$, $A(n,k)$ is the entry above in the matrix, and $A(n,k-1)$ is the entry above and to the left.

Once you've filled up the whole matrix (really only the lower triangle of it, since that's what's defined), the bottom row is $A(n,0)$ to $A(n,n)$, the coefficients in your summation. So you can use them to do the summation.

This way you avoid computing large Stirling numbers and dividing them by huge factorials. Or at least, you avoid handling huge numbers. If $n$ is over a thousand, this algorithm I described could involve calculating over a million numbers. Doable but not ideal.

Or maybe a similar argument gets you a recurrence for your sum itself, although I haven't tried that.