Computing S(n,3) Stirling number of 2nd kind

1,456
44
1. The problem statement, all variables and given/known data
Compute ##S(n,3)##.

2. Relevant equations


3. The attempt at a solution
To compute this I used the fact that ##S(n,2) = 2^{n-1}-1## and used the recurrence relation ##S(n,k) = kS(n-1,k) + S(n-1,k-1)##, and used induction to get that ##S(n,3)=\frac{3^{n-1}+1}{2}-2^{n-1}##.

But is there a quicker way to do this? Is there a way to just see plainly, as in, just counting how many ways we could put ##n## distinguishable balls into ##3## indistinguishable boxes where no box is empty? I tried but it seems difficult.
 
663
294
Is there a way to just see plainly
For me at least, initially obscure mathematical relationships, that probably would on PF be regarded as part of material of intermediate mathematical difficulty level, are usually, but not always, plain enough after someone else sees them, and after I painstakingly choke through some explanations.

Once in a while I might notice or discover something "on my own", and find out later that it was published only, e.g., 300 years ago, but that's rare, at least for me.

If you haven't already looked at the wikipedia article on Stirling numbers of the second kind, I think you might be likely upon reading it to gain some new-to-you inights on your question. I think you're apparently already pretty close to a reasonably good understanding. If you skip ahead to the triangular table illustration, and read enough of the material to understand how it compares to Pascal's triangle for a binomial distribution, that, and the rest of the article, may help you to arrive at a visualization that you find satisfying.
 

Want to reply to this thread?

"Computing S(n,3) Stirling number of 2nd kind" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top