1
$\begingroup$

Number of ways to divide a set of 11 distinct objects in 3 non-empty sets?

I tried to do this and couldn't come up with a way that would work for $n$ distinct objects into $k$ sets. I did brute force for the problem in title. Here is my effort

Firstly number of ways 11 objects can be divided into 3 sets is 10. \begin{array}{|c|c|} \hline n_1,n_2,n_3& ways \\ \hline 1,1,9 & 110\\ \hline 2,1,8 & 495\\ \hline 3,1,7 & 1320\\ \hline 4,1,6 & 2310\\ \hline 5,1,5 & 2272\\ \hline 2,2,7 & 2475\\ \hline 3,2,6 & 5940\\ \hline 4,2,5 & 6930\\ \hline 3,3,5 & 19800\\ \hline 4,3,4 & 11500\\ \hline \end{array} $$Total=53702$$

Is there a general method for this.

Edit:

Answer: Number of ways are given by the Stirling number of second kind $$S(n,k)=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n$$ This gives the answer to be 28510

$\endgroup$
  • 2
    $\begingroup$ Stirling numbers? $\endgroup$ – Lord Shark the Unknown Nov 8 '17 at 5:28
  • $\begingroup$ first kind or second kind $\endgroup$ – Sonal_sqrt Nov 8 '17 at 5:30
  • 1
    $\begingroup$ Focusing on the statement that there are $110$ ways to divide them into $1,1,9$, that comes from $11$ ways to choose the first $1$ and $10$ ways to choose the second. It seems strange that you care which $1$ is chosen first,or there would be $55$ ways, but not whether the $9$ is chosen first, which would give $330$ ways. Please carefully define what you consider to be different ways here. $\endgroup$ – Ross Millikan Nov 8 '17 at 5:30
  • $\begingroup$ If $9$ are chosen first then there are $55$ ways to do it, the next ball need to be chosen among the remaining two of which there are two ways so it still comes to $110$ $\endgroup$ – Sonal_sqrt Nov 8 '17 at 5:33
  • $\begingroup$ @RobertZ Thanks this seems to exactly solve the problem. $\endgroup$ – Sonal_sqrt Nov 8 '17 at 5:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.