Skip to main content
3 of 4
added 363 characters in body
Michael
  • 2.2k
  • 34
  • 42

For the sums the number of $\Sigma(S_i)$ dividing $m$ should be approximately $C^k_n/m$ (rounded down, to be exact), where $C^k_n=\frac{n!}{k!(n-k)!}$ is the total number of $S_i$s. Also, the number of $\Sigma(S_i)$ relatively prime with $m$ will be $C^k_n\phi(m)/m$, where $\phi(m)$ is the Euler $\phi$ function.

For a similar question for the products $\Pi(S_i)=a_{i1}...a_{ik}$ the answer would be more interesting. It's easy enough to see that the number of $\Pi(S_i)$ relatively prime with $m$ would be approximately $C^k_n(\phi(m)/m)^k$. I cannot tell right away, though, how many $\Pi(S_i)$ would divide $m$.

Michael
  • 2.2k
  • 34
  • 42