Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
1  
Asymptotically (when n much larger than m or k) about 1/m of them. How precise a result do you need? –  The Masked Avenger Sep 11 '13 at 23:22
    
I made some edits needed as Ira Gessel noted.I am sorry for maybe confusing you,i want the sum to be a multiple of m. Is there a proof for the asymptotic value 1/k? Asymptotic estimates would do the job for me by the way! –  Konstantinos Gaitanas Sep 12 '13 at 8:21
    
For large n, take the smallest k-1 elements of a putative k subset of n. Find an element c larger than any of those but smaller than n, such that the sum will be 0 mod m. Most of the time, about 1/m out of the available choices for c will work. There are ways to make this more rigorous and more precise, but that is the basic idea. –  The Masked Avenger Sep 12 '13 at 15:00
1  
While the paper by Odlyzko and Stanley is related and interesting, it doesn't seem to answer your question since it looks at unrestricted subsets, so why accept that as the answer? Are you no longer interested in establishing results about subsets of a given cardinality? –  Douglas Zare Sep 13 '13 at 15:09
    
@DouglasZare you are right, i took a quick look at the abstract while i was too tired to focus at everything the article says and i supposed that the answer was there but i'd better read it later.It has some connection with my question but it doesn't seem to answer it- at least not with a little effort and some mathematical extensions from my side. –  Konstantinos Gaitanas Sep 13 '13 at 17:07

3 Answers 3

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.

share|improve this answer
    
i want the sum be a multiple of m. I made the edits.thank you very much for the response and for mentioning this misunderstanding! –  Konstantinos Gaitanas Sep 12 '13 at 8:17

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$.

share|improve this answer

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.

share|improve this answer
    
''applying the permutation (1 2 ... p)(p+1 p+2 ... 2p)... to a subset of size k adds k to the sum modp'' what exactly do you mean?shouldn't then p be less or equal to k? –  Konstantinos Gaitanas Sep 15 '13 at 22:26
1  
@Konstantinos Gaitanas: Apply that permutation to each element of the subset of size $k$. $p$ does not have to be less than $k$. For example, suppose you have the subset $\lbrace 4, 8,10 \rbrace$ with sum $22$ and $p=5$. $4 \mapsto 5, 8 \mapsto 9, 10 \mapsto 6$, so the subset maps to $\lbrace 5,9,6 \rbrace$. The sum of the new subset is $20 \equiv 22+3 \mod 5$. –  Douglas Zare Sep 16 '13 at 0:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.