[Math] Generic method to distribute n distinct objects among r people such that each person gets at least one object

combinationscombinatoricspermutations

Is there any generic method to solve problems of the kind – "How many ways to distribute n distinct objects among r person(s) such that each person gets at least 1 object?". I am aware of 2 different methods to solve this depending on the inputs – n and r.

  1. If n and r are pretty close to each other, we can find out all
    mutually exclusive distribution cases, then find the number of
    different ways to form such distribution groups and finally the
    number of ways to distribute such distinct groups among the people.
    For example, if I had to find out the number of ways I can
    distribute 12 distinct objects among 9 persons such that each person
    gets at least 1,then I can form 3 distribution cases – A)One person
    gets 4 objects, remaining 8 gets 1 each. B)One person gets 3,another
    4 and remaining 7 gets 1 each object. C)Three people gets 3 objects
    each, remaining 6 people gets 1 each.I can form the group (A) in
    12!/(4!8!)ways, group (B) in 12!/(3!2!7!)ways and group (C) in
    12!/(2!2!2!3!6!)ways. Each of these groups can be distributed to 9
    persons in 9! ways, hence the answer would be summation of
    (A+B+C)*9!. This method is quicker for problems where n and r are close to each other.

  2. If say r<5 and the difference between n and r is significant, then we can solve the problem by a variant of Inclusion-Exclusion principle. For example, if I had to distribute 9 objects between 3 people such that each person gets at least 1, then we can find the total number of ways to distribute these 9 objects without any restriction i.e. $3^9$, then subtract from it the total number of ways where at least one among the 3 people doesn't get a single object i.e. in $\binom 31(2^9-2)$ ways and finally subtract the number of cases where all the objects are given to a single person in $\binom 31$ ways. Hence the answer will be $3^9-\binom 31(2^9-2)-3$. This method seems quicker for problems where r is small.

But I would like to know a generic method to approach this problem irrespective of the values of n and r, which yields quicker results. I also know if the objects are identical then we can construct a generating function G(x) and then find the co-efficient of $x^n$ which will give us all possible ways of distributing n identical objects. I would appreciate if anyone can guide to me to a generic solution for distinct objects.

Best Answer

There is no "nice" closed formula for what you are looking for. However, these numbers have been extensively studied, and are closely related to what is known as the Stirling numbers of the second kind (or the Stirling set numbers).

$S(n,r)$ denotes the number of ways of taking a set of $n$ distinct items and partitioning it into $r$ non-empty subsets. These subsets are not ordered, so for example if we were partitioning the set $\{1,2,3,4\}$, the partitions $\{ 1, 3 \} \cup \{2, 4\}$ and $\{2,4\} \cup \{1,3\}$ would be the same. However, if you are considering distributing items to $r$ (distinct) people, then you do want to have ordered sets. However, this can easily be achieved by ordering the $r$ subsets of any set partition, so you get a total of $r! S(n,r)$ ways of partitioning $n$ distinct items between $r$ people in such a way that everyone receives something.

Wikipedia has a reasonably extensive article on these numbers: https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

Related Question