Number of ways to form n groups of any size

[rflrob]

So as part of a problem I'm working on, I've come across the need to determine how many different ways there are to form exactly n groups of any size out of k objects. For instance, if I had n=2, k=4, then I could assign the objects to groups in 14 ways (i.e. {1,1,2,2}, {1,2,1,2}, {1,2,2,1}, {2,2,1,1}, {2,1,2,1}, {2,1,1,2}, {1,2,2,2}, {2,1,2,2}, {2,2,1,2}, {2,2,2,1}, {1,1,1,2}, {1,1,2,1}, {1,2,1,1}, and {2,1,1,1}, assuming I'm not missing any). In other words,

\frac{4!}{3!1!} + \frac{4!}{2!2!} + \frac{4!}{1!3!}

The problem is, as far as I can tell, it becomes much harder to even enumerate those sums as n and k grow (typical numbers I'm hoping to bring this up to are in the thousands). For instance, if I have n =3, k=5, then I now have

\frac{5!}{3!1!1!} + \frac{5!}{2!2!1!} + \frac{5!}{2!1!2!} + \frac{5!}{1!3!1!} + \frac{5!}{1! 2! 2!} + \frac{5!}{1!1!3!}

I'm failing to think about why this is right, but it kind of looks like there's going to be _kC_n separate terms. Is there any good way to approximate this sum in an analytic function? Farther down the line, I'm going to be taking derivatives with respect to n, so it would be nice not to have sums of sums getting in the way.

[jestingrabbit]

For instance, if I had n=2, k=4, then I could assign the objects to groups in 14 ways (i.e. {1,1,2,2}, {1,2,1,2}, {1,2,2,1}, {2,2,1,1}, {2,1,2,1}, {2,1,1,2}, {1,2,2,2}, {2,1,2,2}, {2,2,1,2}, {2,2,2,1}, {1,1,1,2}, {1,1,2,1}, {1,2,1,1}, and {2,1,1,1}, assuming I'm not missing any). In other words,

\frac{4!}{3!1!} + \frac{4!}{2!2!} + \frac{4!}{1!3!}

Or, in other words, every sequence of 1s and 2s of length 4, apart from those with consist entirely of 1s or 2s ie 2^4 - 2.

[rflrob]

Or, in other words, every sequence of 1s and 2s of length 4, apart from those with consist entirely of 1s or 2s ie 2^4 - 2.

While that's fine for the n=2 case, I don't think it scales easily to anything larger. For instance, with n=5, k=10, I'm looking for every length 10 sequence of 1s, 2s, and 3s, 4s, and 5s, so long as that sequence has at least one 1, at least one 2, at least one 3, at least one 4, and at least one 5. In that case, there will be some number of sequences that have no 3s, some number of sequences with no 4s, and some of those will have both no 3s and no 4s, and keeping track of all of those also seems like it's going to balloon pretty quickly.

[Nitrodon]

These numbers can be written as k!*S(n,k), where S(n,k) is a Stirling number of the second kind. The Wikipedia article gives a few explicit formulas with k terms.

Or, in other words, every sequence of 1s and 2s of length 4, apart from those with consist entirely of 1s or 2s ie 2^4 - 2.

While that's fine for the n=2 case, I don't think it scales easily to anything larger. For instance, with n=5, k=10, I'm looking for every length 10 sequence of 1s, 2s, and 3s, 4s, and 5s, so long as that sequence has at least one 1, at least one 2, at least one 3, at least one 4, and at least one 5. In that case, there will be some number of sequences that have no 3s, some number of sequences with no 4s, and some of those will have both no 3s and no 4s, and keeping track of all of those also seems like it's going to balloon pretty quickly.

If you do it this way, you will want to use the inclusion-exclusion principle to keep track of all of those. This method leads directly to one of the formulas mentioned above.