Combination of $n$ objects taken $p$ at a time where $n$ contains $r$, $s$, and $t$ identical objects.

Question

I am talking about something like this:
$ N = \{2, 3, 3, 3, 5, 5, 7\}$
$ n = 7$
$ s=3 $
$t=2$

In my case specifically, those numbers in $N$ are the prime factors of a number $Z$ repeated the number of times they divide $Z$.

And what I am looking for is to find all the numbers (non-prime included), that divide our number perfectly, from the combinations of these numbers in $N$.

I know I have to find the combination of elements in $N$ taken $i$ at a time where $i$ goes from $1$ to $7$ (# elements in $N$). Also the repeated elements are to be treated specially. I could find that in this particular case manually but I am dealing with large $N$ such that total combinations is at least $500$.

I want to be able to express the solution in a generalized formula. But, I am having hard time doing so. The standard combination formula $n\mathrm{C}r$ does not treat repeated numbers "specially" enough. Would anyone having more grasp into this help me please.

Answer 1

For a number $Z$ expressible in terms of it's $k$ prime factors:

$$Z = p_{1}^{r_{1}}p_{2}^{r_{2}}...p_{k}^{r_{k}}$$

Each factor can be formed by selecting a set of prime factors as follows:

• Include $0,1,2,...r_{1}$ copies of $p_{1}$
• Include $0,1,2,...r_{2}$ copies of $p_{2}$
  ...
• Include $0,1,2,...r_{k}$ copies of $p_{k}$

So the number of factors is given by:

$$\left(r_{1}+1\right)\left(r_{2}+1\right)...\left(r_{k}+1\right)$$

For the example you give we enumerate factors of $9450$: $$\left(1+1\right)\left(3+1\right)\left(2+1\right)\left(1+1\right) = 2\times 4 \times 3 \times 2 = 48$$
which also includes $1$ and itself.
You should make it clear in the question whether you are trying to enumerate factors or whether you are attempting to list them. If the latter then you will need to work through them systematically.

Answer 2

Take as the simplified problem counting all divisors of $Z $ when a prime factorization is known. There is a common arithmetic function $d(Z)$, the divisor function, which returns this count of divisors, including $Z $ itself.

The divisor function is multiplicative, meaning that if $m,n$ are coprime, then $d(mn)=d(m) d(n) $. Since the prime power factorization of $Z=p_1^{k_1} \cdot \ldots \cdot p_t^{k_t}$ is given, it suffices to take the product of $d(p^k)$ over all the prime power factors that uniquely multiply to $Z$.

In this we are helped by the fact that $p^k $ has exactly $k+1$ divisors, namely $1,p,\ldots,p^k $. Therefore $d(Z) = (k_1 + 1)\ldots(k_t + 1)$.

Example: The Question asks about counting divisors of $Z = 2\cdot 3^3\cdot 5^2 \cdot 7$. The divisor function $d(Z) = (1+1)(3+1)(2+1)(1+1) = 48$ depends only on the exponents of primes (the repetitions of prime factors) and not on the actual primes involved.

Stratifying these possibilities by the number of prime factors (counted as to multiplicity, from none to $\sum_{i=1}^t k_i$) turns out to be more difficult, as your computational experiments indicated. In fact it can be shown to be in the class of "hard" computations that are #P-complete.