6
$\begingroup$

Is there any way to count the number of distinct combinations of a set of objects where some objects may be identical? We have the basic formulas for $nPr$ and $nCr$, and I understand how to modify them in the case where sampling is done with replacement ($n^r$ in the first case, and $\binom{n+r-1}{r}$). But what happens in the case where we have $n$ objects of $k$ types: $p_1$ of type 1, $p_2$ of type 2, and so on up to $p_k$ of type k, and $\sum_{i=1}^k p_k = n$?

In the case of permutations, if we are selecting the entire set ($nPn$), then I think it makes sense to effectively treat it like a combination in the sense that each of $k$ types has some number of copies whose order doesn't matter, so the solution would be $\dfrac{n!}{\Pi_{i=1}^k (p_i !)}$. How do we do this calculation when we are not selecting the entire set, and therefore we do not know how many repeats there will be? What if we're interested in combinations instead, so the order doesn't matter? These seem like they should be computable, but I haven't been able to wrap my head around how.

One potential example of the latter would be trying to generate the set of all factors of a number given its prime factorization, which could consist of repeats of the same factor.

$\endgroup$
2
$\begingroup$

Suppose the set contains non-distinct objects

$$\{(P_i,Q_i)\}, i = 1, \ldots, N$$

where $P_i$ is the object that appears $Q_i$ times in the set. We can select this object in $0,1, \ldots, Q_i$ ways (starting with no object selected, to all $Q_i$ objects selected). Hence, each object can be selected $Q_i+1$ times.

None to all objects can be selected in number of ways given by,

$$\prod_{i = 1}^{N} (Q_i+1)$$

$\endgroup$
  • $\begingroup$ Please read this tutorial on how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Mar 8 '16 at 15:16

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.