Choosing objects from multiple sets of indistinguishable objects, without replacement

400 Views Asked by At

So I'm considering a harder variant on the standard problem of ordering a set of $N$ objects consisting of $n_1$ indistinguishable objects of type 1, $n_2$ indistinguishable objects of type 2, $n_3$ indistinguishable objects of type 3, etc. up to $n_x$ indistinguishable objects of type $x$.

I'm trying to figure out how many ways I can pick two elements of the set of $N = \sum n_i$ objects without replacement and without regard to order.

My first guess at this was the following:

\begin{align} \dfrac{N!}{\prod_i \left( n_i ! \right)} & \text{ gives the number of ways to order all of the objects; }\\ \text{there are } (N - 2)! & \text{ ways to order the } n-2 \text{ objects I don't care about; and thus there should be}\\ \dfrac{N!}{\prod_i \left( n_i ! \right)} \dfrac{1}{\left(N - 2\right)!} & \text{ ways to order the } 2 \text{ objects I do care about, giving }\\ \dfrac{1}{2}\dfrac{N!}{\prod_i \left( n_i ! \right)} \dfrac{1}{\left(N - 2\right)!} & \text{ ways to choose the } 2 \text{ objects I do care about.} \end{align}

But this is definitely wrong because it neglects any possible indistinguishability of the $N-2$ remaining objects! I just don't know how to write the $(N-2)!$ term to take into account the fact the number of objects of each type has changed, and would affect the number of ways in which I can arrange the remaining $N-2$ objects. This is what makes this problem much harder than drawing different-colored balls from an infinite supply, for example.

EDIT:

To clarify, it is essentially going to be number of choices = $x^2$ if all $n_i>1$ and $x(x−1)$ if any $n_i=1$. If possible I'd like to find an answer without min-functions and the like - i.e. pure factorials and the like.