- The order of the groups does not matter
- The size of group must be at least 1
For example, in a more specific question How many ways to split 5 number in 2 groups?, we got the answer 15 from Jared, which is the sum of 5 ways to split in group size 1 and 4, and 10 ways to to split in group size 2 and 3.
For more general cases, what is the formula to calculate this?
$\endgroup$ 12 Answers
$\begingroup$These numbers are not very well mannered, They are called the Stirling numbers of the second kind.
see $s(5,2)=15$
For more info see twelvefold way
$\endgroup$ 1 $\begingroup$Hint 1: Firstly, solve the problem "considering the order of the groups". You would be looking for the number of surjective functions
$ f: \left\{ 1, \ldots , n\right\} \to \left\{ 1, \ldots , k\right\} $
The $ j $ -th group would be the inverse image $ f^{-1}(j) $.
Think about it: Firstly, try to solve other problems about the number of such functions. Consider all the functions $\left\{ 1, \ldots , n\right\} \to \left\{ 1, \ldots , k\right\} $. How many are there? How many such injections are there?
Finally, how many surjections are there?
These questions are the most studied ones in an elementary course of combinatorics.
Hint 2: Consider the set of functions between two finite sets, id est, the set of functions $A\to B $, in which $ A $ and $ B$ are finite sets. We denote the set of such functions by $Set(A,B) $. We may know the cardinality of $ Set (A, B) $. But, now, we wish to consider an equivalence relation in $ Set (A, B) $.
Two functions $ f,g: A\to B $ are equivalent if $ \alpha \circ f = g $ for some bijection $ \alpha : B\to B $.
Prove that it is an equivalence relation. And denote this equivalence relation by $ \cong $. Then consider the set of equivalence classes $ Set (A, B)/ \cong $.
How many elements $ Set (A, B)/ \cong $ has?
To solve this problem, it is worth to know how many bijections $ B\to B $ are there, which probably you know: there are $ card (B) ! $ bijections $B\to B $. Now, you know the cardinality of each equivalence class of $ Set (A, B) / \cong $, which is the cardinality of $ Bijections (B,B) $, since, for each, $ f\in Set (A,B) $ the equivalence class of $ f $ is the set below
$ \left\{ g\in Set (A, B): f\cong g \right\} = \left\{ \alpha\circ f: \alpha\in Bijc(B,B)\right\} $
Therefore the number of elements of $ Set (A,B)/\cong $ is $ card (Set (A,B))/(card(B) !) $.
Since the injections (or surjections) are closed by our defined relation, we can compute how many elements $ Injections (A,B)/ \cong $, that is, $ card ( Injections (A, B))/ (card(B)!) $
Solution:
The number of surjections can be found at
Remember that $k$ should be such that $ k\leq n $. And, when $ k = n $, the problem is reuced to compute the number of bijections. And you may use that formula and remember you should divide that by $(card (B) !) $
If $ A = \left\{ 1, \ldots , n\right\} $ and $ B = \left\{ 1, \ldots , k \right\} $, your solution would be $ card(surjections (A,B))/k! $
$\endgroup$ 1
