# Estimate Stirling numbers from normal distribution?

If I roll a die $100$ times, there are $6^{100}$ possible ordered outcomes.

Some of these outcomes, say $n$, will add to $347$, for example.

Is there a way to express $n$ in terms of Stirling numbers (or am I think of partitions?).

One way to estimate $n$:

• note that the sum has a mean of $350$ with a standard deviation of $17.08$.

• Use the normal distribution to calculate the probability that the sum is between $346.5$ and $347.5$.

• Multiply this probability by $6^{100}$

Does this provide a new (or even useful) way of estimating Stirling numbers?

-
Stirling numbers enumerate partitions of a set into a fixed number of subsets or cycles of arbitrary size, and here we have a partition of a number $n$ into a sum of a fixed number of terms of bounded size... What kind of connection do you expect? –  Alexander Shamov Aug 9 '12 at 15:36

Here's what I think you might be thinking of: Stirling numbers of the first kind count permutations according to their number of cycles. But the mean and variance of the number of cycles of permutations on $n$ elements are well-known. In particular, given a random variable $X_n$ which represents that number of cycles, $E(X_n) = 1 + 1/2 + \cdots + 1/n$ and $Var(X_n) = E(X_n) - (1 + 1/2^2 + \cdots + 1/n^2)$. In fact $X_n$ can be written as the sum of n independent Bernoulli random variables, where the kth such variable has mean 1/k. This decomposition then lets you invoke the Central Limit Theorem and say that the distribution is, in some limiting sense, normal.
So say we want to use this to estimate, for example, $S(9,3)$. The average number of cycles of a permutation on 9 elements is $1 + 1/2 + \cdots + 1/9 \approx 2.828968$; call this $\mu$. The variance of the number of cycles is $\mu - (1 + 1/2^2 + \cdots + 1/9^2) \approx 1.289201$; call this $\sigma^2$. Then by this normal approximation, the probability that a random permutation on 9 elements has 3 cycles is
$$\Phi \left( {3.5 - \mu \over \sigma} \right) - \Phi \left( {2.5 - \mu \over \sigma} \right)$$
where $\Phi$ is the standard normal CDF. This is $0.336726$; so we estimate S(9,3) is 9! times this, or 122191. The actual value is 118124, so this isn't a bad guess.