0
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Isn't this the same as the standard $2$ choose $x$? - unless that $n_i = 1$ for some $i$, then you have to be careful. $\endgroup$ Dec 22 '16 at 21:56
  • $\begingroup$ 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. $\endgroup$
    – GnomeSort
    Dec 22 '16 at 22:04
  • $\begingroup$ If you have $n_i$ for $1 \le i \le n$ such that $n_i = 1$ for $1 \le k \le n$ then there are $$ {n \choose 2} - k$$ ways of choosing subsets of size $2$ without replacement. $\endgroup$ Dec 22 '16 at 22:36
  • $\begingroup$ This is a combination with repetition problem. If each $n_i \geq 2$, $1 \leq i \leq n$, you can apply the formula for the number of solutions of the equation $$y_1 + y_2 + \cdots + y_k = n$$ in the nonnegative integers for $n = 2$ and $k = x$. However, if the number of objects of type $i$ is $n_i = 1$, you will have to subtract those solutions in which $n_i = 2$. $\endgroup$ Dec 23 '16 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.