Given a set of $n$ objects that has $p_1$ identical objects of one kind, $p_2$ identical objects of another kind, … and so on until $p_k$ objects of the $k$th kind (so that $p_1 + p_2 + … + p_k = n$), in how many ways can one select $r$ objects out of the $n$, with order irrelevant, where $r$ is less than the largest greater than or equal to the smallest number of identical objects (so $r \geq \max \{ p_1, …, p_k \}$)?
E.g. in how many ways can you select two letters from the letters in some word like "chincherinchee"?
I feel I should be able to compute this with factorials in some form, but I can't wrap my head around it.
Best Answer
I think this is about selection with constraints, which is similar to partition with constraints.
We want to select $r$ objects from a population with $t$ various types but we have limits on how many of some/all the types are available, with inclusion/exclusion to cope with multiple cases of limit breaking.
So we partition $r$ into $t$ types freely, then subtract off any cases which might break the constraints, then add back in double counted constraint breaking, etc.
For example choosing $r=5$ letters form "chincherinchee". There are $t=6$ letters $(t_i)=$ (c,h,i,n,e,r) with limits $(\ell_i)=(3,3,2,2,3,1)$.
The basic free selection from those $6$ types is sticks-and-stones (or stars&bars) division into categories, $$\binom{5+6-1}{6-1}=\binom{10}{5}$$
Then to remove cases where we have selected more of a given type than allowed, we repeat this division but with each type in turn allocated a limit-breaking $\ell_i{+}1$, which is removed from the total available. So for example when we consider breaking the limit on letter "n"($c_4$), this means we remove $\ell_4+1=3$ items from general allocation because they are preallocated to break the limit for "n", meaning the options for this case are $\binom{2+6-1}{6-1}=\binom{7}{5}$. So over all possible letters this adjusts the total to $$\binom{10}{5}-\left(\binom{6}{5}+\binom{6}{5}+\binom{7}{5}+\binom{7}{5}+\binom{6}{5}+\binom{8}{5}\right)$$
However there are now some cases which have been removed twice, where two constraints were broken, which is handled similarly by preallocating enough slots to break two constraints simultaneously, then selecting from the reduced pool. In my example though these are very limited - we could have chosen $3\times$"i"${}+2\times$"r", or $3\times$"n"${}+2\times$"r" - only two options for double constraint breaking (and none for breaking more than two constraints). So we add these $2$ options back in for the result: $$\binom{10}{5}-\left(3\binom{6}{5}+2\binom{7}{5}+\binom{8}{5}\right)+2$$