# Stars and Bars Computation With Distinct Stars [duplicate]

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}$$ ?

• The $n!$ overcounts permutations of elements in the same set. – Michael Burr Aug 18 '19 at 23:21
• are the buckets distinguishable? – Matthew Daly Aug 18 '19 at 23:22
• My mistake, the buckets are distinct – HoopsMcCann Aug 18 '19 at 23:23
• 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. – Matthew Daly Aug 18 '19 at 23:32
• 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. – Brian Moehring Aug 18 '19 at 23:42

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.