3
$\begingroup$

Suppose we have a standard Stars and Bars problem with a restriction that each partition has at least one star.

With $n$ indistinguishable items and $k$ buckets, we can compute this by $n-1 \choose k-1$
But what if the items were distinct?
Would it be:
$n! {n-1 \choose k-1}$ ?

$\endgroup$
  • $\begingroup$ The $n!$ overcounts permutations of elements in the same set. $\endgroup$ – Michael Burr Aug 18 '19 at 23:21
  • $\begingroup$ are the buckets distinguishable? $\endgroup$ – Matthew Daly Aug 18 '19 at 23:22
  • $\begingroup$ My mistake, the buckets are distinct $\endgroup$ – HoopsMcCann Aug 18 '19 at 23:23
  • $\begingroup$ For problems like this, it's nice to keep a chart of the "twelvefold way" to count the number of mappings from N to K based on whether the elements of N are distinct, whether the elements of K are distinct, and whether the mapping needs to be surjective, injective, or unrestricted. $\endgroup$ – Matthew Daly Aug 18 '19 at 23:32
  • 1
    $\begingroup$ This scenario is what the Stirling numbers of the second kind are for. Otherwise, you need to use something like inclusion-exclusion as in Michael's answer below. $\endgroup$ – Brian Moehring Aug 18 '19 at 23:42
1
$\begingroup$

Hint: Since each object can go into one of $k$ buckets, there are $k^n$ ways to distribute the $n$ objects. In this case however, one of the buckets might be empty. Now, use inclusion/exclusion to reduce the number of buckets.

| cite | improve this answer | |
$\endgroup$

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