Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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

1 Answer 1

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.

However, using the same method to estimate S(9,8) gives about 7 when the true value is 36; as with any normal approximation, it's better towards the center of the distribution than in the tails.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.