Number of subsets with fixed cardinality k, and sum of elements a multiple of m

Question

I need some help on a problem on combinatorics.

Let $n$ be a natural number greater than $1$ and $k,m$ be two fixed natural numbers not exceeding $n$ with $m\leq\frac{k(k+1)}{2}$.

Let $N=\{{1,2,...,n}\}$ and $S_i=\{a_{i1},a_{i2},...,a_{ik}\}$ with $S_i\subseteq{N}$ .

Denote the sum of elements of $S_i$ by $\sum({S_i})=a_{i1}+a_{i2}+...+a_{ik}$.

My question is:How many $S_i\subseteq{N}$ exist with $m\mid\sum{(S_i)}$? In other words: how many subsets of $N$ with fixed cardinality $k$ we can choose with the property: the sum of its elements is a multiple of $m$?

(It is not necessary that $S_i\bigcap{S_j}=\emptyset$)

Note that the condition $m\leq\frac{k(k+1)}{2}$ is necessary because $S_i$ could be the set $\{1,2,...,k\}$ with $\sum{(S_i)}=\frac{k(k+1)}{2}$

I am really wondering if this is a new question and if not, if somebody could help me with this.

Thank you for viewing!

Answer 1

It's not clear whether Gaitanas wants his sum to divide $m$ or be a multiple of $m$. If he wants the sum to be a multiple of $m$, then some related questions are studied in the paper "Enumeration of Power Sums Modulo a Prime" by Andrew M. Odlyzko and Richard P. Stanley, J. Number Theory 10 (1978), 263-272. They study the following question: given a positive integer $n$, an odd prime $p$, and an integer $\alpha$, how many subsets $S$ of $\{1,2,\dots, p-1\}$ are there with $$\sum_{x\in S} x^n \equiv \alpha \pmod p?$$ They also give references to related results, where $p$ need not be a prime.

Answer 2

For the number of the sums $\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 be divisible by $m$.

Answer 3

Suppose $m=2$. If $k$ is odd, and $n$ is even, then there are involutions switching even numbers and odd numbers up to $n$ such as $1 \leftrightarrow 2, 3 \leftrightarrow 4 ...$. Letting one of these act on subsets of size $k$ switches the parity of the sum, so there are equally many subsets of size $k$ with an odd sum as with an even sum. For no other cases with $m=2$ are the subsets divided equally by the parities of their sums.

Let $f_2(n,k) = \# \text{subsets of } \lbrace 1, ..., n\rbrace ~\text{of size } k ~\text{with even sum}$.

Let $g_2(n,k) = 2f_2(n,k) - {n\choose k},$ the count with even sum minus the count with odd sum.

$g_2(2a, 2c) = (-1)^c {a \choose c}$

$g_2(2a, 2c+1) = 0$

$g_2(2a+1,2c) = g_2(2a,2c)$

$g_2(2a+1,2c+1) = -g_2(2a,2c)$

For example, let $n=30$ and $k=10$. There are $30,045,015$ subsets of $\lbrace 1, 2, ..., 30\rbrace$ size $10$, of which $f_2(30,10) = 15,021,006$ have an even sum and $15,024,009$ have an odd sum. The difference is $-{15 \choose 5} = -3,003$.

To prove these formulas, consider the group action of $C_2^a$ with generators switching $1 \leftrightarrow 2, ..., 2a-1\leftrightarrow 2a$. If for some pair $(2t-1,2t)$ only one of these is in a subset, then the orbit of that subset has equally many subsets with even and odd sums since switching $2t-1 \leftrightarrow 2t$ changes the parity of the sum. What is left over is the subsets which contain both $2t-1$ and $2t$ or neither, and there are $a \choose c$ of these left over. The parities of these are all the same, and the parity is determined by the parities of $c, n, k$ as indicated above.

---

Suppose $p$ is an odd prime.

Let $f_p(n,k)$ be the number of subsets of $\lbrace1,...,n\rbrace$ of size $k$ with sum divisible by $p$. If $n$ is divisible by $p$, and $k$ is not, then $f_p(n,k) = {n\choose k}/p$, since applying the permutation $(1 ~2~ ...~ p)(p+1 ~~p+2~~ ...~ 2p)...$ to a subset of size $k$ adds $k$ to the sum $\mod p$, and repeating this hits every congruence class once in each orbit.

Let $g_p(n,k) = p f_p(n,k) - {n\choose k}.$

Let $n=p a + b, k = pc + d$, with $0 \le b,d \lt p$. Consider the action of $C_p^a$ generated by $(1 2 ... p), (p+1 ~~ p+2 ~ ... ~2p),...$. If the intersection of a subset with $\lbrace (t-1)p+1, (t-1)p+2, ... tp \rbrace$ has size from $1$ to $p-1$, then its orbit is evenly split among the congruence classes. So, the imbalance comes from the subsets containing $c$ complete blocks of size $p$, together with some subset of size $d$ of the last $b$ elements. Note that if $d \gt b$ then this is impossible so $g_p(n,k) = 0$.

$g_p(pa+b,pc+d) = {a \choose c} g_p(b,d)$.

Crude estimates for $g_p(n,k)$ with $n,k \lt p$, such as $|g_p(n,k)| \le p 2^n$ turn into general bounds for larger $n,k$. $$|g_p(pa+b,pc+d)| \le {a \choose c} p 2^b.$$

One simplification compared with $m=2$ is that $1+2+...+p$ is divisible by $p$ when $p$ is an odd prime. That $1+2$ is odd produced the $(-1)^c$ factor.

If $m$ is composite, then some of the arguments used for $m$ prime don't work.