# Stars and bars with minimum number of categories

I've been trying to figure out a closed form solution to this problem, but I haven't been able to find one yet.

How many ways are there to pick $n$ items from $k$ categories, such that at least $\ell$ categories are picked?

My first guess/natural solution was to choose $\ell$ categories, set aside 1 item for each category, then do stars and bars on the remainder, but this overcounts and worse overcounts by a different amount on each option. (If there are $c$ categories with at least 1 item it counts it $\binom{c}{\ell}$ times.)

Other solutions I've thought of run into the same problem, so I'm interested to see if a clean combinatorial solution exists or not.

• When you say such that at least $l < k$ categories are picked I think the wording is a little awkward. Are you asking for at least $l$ categories, implying the total should include $l$, $l+1$, $l+2,\ldots, l = k-1$? That's how I interpret your question. – Nick H Dec 18 '14 at 3:03
• It's meant as a bound on $\ell$, because it's impossible for $\ell$ to exceed $k$, but it is okay to have every category be picked. I'll edit it. – Titandrake Dec 18 '14 at 7:56

Pick first $n-l$ items without any restriction in $n-l+k-1 \choose k-1$ ways and then choose remaining $l$ elements each from a different category in $k \choose l$ ways. Thus , the answer is ${n-l+k-1 \choose k-1}*{k \choose l }$.

• This does the same overcounting that I mention in the question statement - suppose $n=k$ and consider the way where each category has 1 item. Then for any of the $\binom{k}{l}$ choices of different categories, we can get this way of picking items, so this gets counted more than once. – Titandrake Dec 18 '14 at 9:10
• Could you please give a small example, suppose k=n=3 . I am not able to follow your statement actually. – arindam mitra Dec 18 '14 at 11:40
• Let $\ell = 2, n=3,k=3$. This can be done by $**|*|, *|**|, **||*, *||**, |**|*, |*|**, *|*|*$ which is 7 ways. Your expression gives $\binom{3}{2} \cdot \binom{3}{2} = 9$. The problem is that the situation $*|*|*$ is counted 3 times, not once. When placing the 1st item without restriction, place it in either category 1,2,or 3. When choosing the remaining $\ell$ elements, choose the two categories that are not used. Then we end up with $*|*|*$, but count it $\binom{3}{2}$ times, corresponding to the number of ways we can choose the remaining $\ell$ categories. – Titandrake Dec 18 '14 at 22:54

So, the basic formula is $n-1 \choose k-1$ to find out how many ways one can partition $n$ items into $k$ groups. We could find the number of ways to choose $n$ objects into $l$ groups simply by $n-1 \choose l-1$. Now this counts the number of ways to pick $n$ items from $l$ categories, but does not account for the fact that there are $k \choose l$ ways to select the $l$ categories.

If we say ${k \choose l}{n-1 \choose l-1}$ we would count all the ways to select $l$ categories and all the ways to choose $n$ items from each category.

If we want to find the number of ways to choose from at least $l$ categories, we could find the number of ways to choose from $l$, $l+1$, $l+2,\ldots,k$ categories.

\begin{align*} \displaystyle \sum_{l}^{l=k} {k \choose l}{n-1 \choose l - 1} \end{align*}

• This was the solution I got, I was more wondering if there's a closed form for the summation or not. – Titandrake Dec 18 '14 at 7:58
• i guess you should go till l=k . – arindam mitra Dec 18 '14 at 8:31