5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I just realized this question has been asked before, but the answer they settled on was inclusion-exclusion. $\endgroup$ – Noble Mushtak Jun 24 '16 at 15:52
  • 2
    $\begingroup$ @NobleMushtak Yes that will work for smaller values, in that particular case it was 3. The second answer for the linked question is wrong, it cannot be solved by bars and stars as the objects are distinct. $\endgroup$ – NINCOMPOOP Jun 24 '16 at 15:57
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for pointing that out. $\endgroup$ – NINCOMPOOP Jun 24 '16 at 16:12

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.