0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Nick H Dec 18 '14 at 3:03
  • $\begingroup$ 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. $\endgroup$ – Titandrake Dec 18 '14 at 7:56
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Titandrake Dec 18 '14 at 9:10
  • $\begingroup$ Could you please give a small example, suppose k=n=3 . I am not able to follow your statement actually. $\endgroup$ – arindam mitra Dec 18 '14 at 11:40
  • $\begingroup$ 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. $\endgroup$ – Titandrake Dec 18 '14 at 22:54
0
$\begingroup$

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*}

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

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.