I have been trying to wrap my head around a problem. The problem is reduced form of a problem from a programming contest. I have been trying to apply inclusion-exclusion principle toward solving this, but I have been unable to get to it.
We are to count the number of lists of fixed size $N$ such that any value in the list can have a maximum value of $M$. This value is clearly $M^{N}$.
However, we are given a list of divisors (can assume prime if it makes any difference) : $\langle K_1, K_2 ... K_r \rangle$ such that for every $K_i$ , there exists a number in our lists that we construct, which is divisible by $K_i$ .
When the size of divisor list is one, we can easily see that the count reduces to:
$C_1 = \sum_{t = 0} ^{N-1}{(M - P)^t .P.M^{N-t-1}}$ where $P = \frac{M}{K_1}$
However, I am unable to extend this calculation in any form (closed formula or recurrence) to a divisor list of arbitrary size. It will be helpful if someone can give any pointers. Thanks in advance.
EDIT: It can be assumed that the product of all numbers (primes) in the divisor list is always less than or equal to M i.e.
$\prod_{i=1}^{r}{K_i} \leq M$
I'd probably assume the $K_i$ are pairwise coprime, so that satisfying one $K_i$ is in some sense independent of satisfying another.
I'll extend your definition, $P_i = \left \lfloor \frac{M}{K_i} \right \rfloor$
$C_0 = M^N$
$C_1 = C_0 - (M-P_1)^N$ (exclude the cases where we pick all unsuitable numbers)
first approximation: $C_2 = C_0 - (M-P_1)^N - (M-P_2)^N + (M-P_1-P_2)^N$ (inclusion-exclusion)
For $C_2$ we probably need to start thinking about the relative size of the divisors compared to the limit $M$. If $M$ is relatively large, there is little constraint on having multiple $K_i$ values satisfied by one of the members of the list. The non-numerical parallel might be a set of balls with various colour dots on - the presence of one colour dot does not exclude a dot of another colour on the same ball. More likely for interesting problems some of the $K_i$ might be large enough to exclude others, e.g. several $K_i > \sqrt M$
By the same thought process, if $r>N$ then things might also get complicated - we might stray into packing problem territory.
OK, incorporating the knowledge that the $K_i$ are small relative to $M$, we need to refine the "first approximation" I gave above with the knowledge that some of the selected numbers might satisfy multiple $K_i$. Adding back the double removal of non-qualifying answers needs to account for the shared factors - in case of M=6, K={2,3}, we have two numbers co-prime to (2,3) rather than one, because 6 is shared. So, second approximation, which I think will probably work :
$C_2 = C_0 - (M-P_1)^N - (M-P_2)^N + (M-P_1-P_2+P_{12})^N$
where $P_{12} = \left \lfloor \frac{M}{K_1K_2} \right \rfloor$
By analogy we might need to calculate all the partial products of factors and coprime counts for higher numbers of test factors.