# Finding the number of 3-element subsets from the set {1,2,3,…,11,12,13} such that the sum of the 3 elements is divisible by 3

I found this problem from an old math questionnaire.

How many 3-element subsets of {1,2,3,...,11,12,13} are there for which the sum of the 3 elements is divisible by 3?

At first, I tried listing down all of them. But then, I realized they were too many and so, I just stopped. Next, I tried using stars and bars technique. I represented the 3 elements as a,b,c and their sum as a+b+c=m where m is the set of positive integers divisible by 3 from 3 to 39. From there, I tried out each equation with stars and bars from a+b+c=3 to a+b+c=15, and found a total of 185 subsets satisfying the given conditions. I stopped at here since I noticed that if I continued doing this from a+b+c=18 to a+b+c=39, I would have an error since I was not able to limit the values of a,b,c at most 13.

I do not know how to proceed right now. Can anyone help?

• @Ross Millikan, Jack D' Aurizio and Batominovski, I really appreciate your help. Unfortunately, the solutions you suggested were honestly too much for me to handle. I really do not understand a single one you, guys, suggested. – Carl Terence Valdellon Aug 29 '16 at 1:07

Hint: There are five elements of your set that are $1 \bmod 3$, four that are $0 \bmod 3$ and four that are $2 \bmod 3$. You can get a sum that is $0 \bmod 3$ by taking three of the same kind or one of each kind.

• but remember that you have to take them in order – G Cab Aug 28 '16 at 16:26
• @GCab: we were asked for subsets, so order doesn't matter. – Ross Millikan Aug 28 '16 at 16:28
• Oops, perhaps there is some misunderstanding: as far as I know sets and subsets are ordered lists, so in the present case one of the specified subsets would be for instance ${3,6,9}$, while ${6,3,9}$ is not a subset: am I wrong ? – G Cab Aug 28 '16 at 21:40
• @GCab: No, sets are not ordered. $\{6,3,9\}$ is a subset of the given set, but it is the same subset as $\{3,6,9\}$. It should only be counted once. – Ross Millikan Aug 28 '16 at 21:45
• so.. I'm not native english speaker, but (probably) understood the "punctualization" you want to make about the concept of set and that's right . However coming to counting, so in combinatorics at least, subsets (understanding different subsets) bi-ject to tuples : can we say that? – G Cab Aug 28 '16 at 23:58

A more general approach is given by generating functions.
We may consider the bivariate polynomial

$$q(x,y)=(1+yx)(1+yx^2)\cdot\ldots\cdot(1+yx^{12})(1+yx^{13})$$ and the coefficient of $y^3$ in $q(x,y)$, that is $$[y^3]\,q(x,y) = r(x) = x^6+x^7+2 x^8+3 x^9+4 x^{10}+5 x^{11}+7 x^{12}+8 x^{13}+10 x^{14}+12 x^{15}+14 x^{16}+15 x^{17}+17 x^{18}+17 x^{19}+18 x^{20}+18 x^{21}+18 x^{22}+17 x^{23}+17 x^{24}+15 x^{25}+14 x^{26}+12 x^{27}+10 x^{28}+8 x^{29}+7 x^{30}+5 x^{31}+4 x^{32}+3 x^{33}+2 x^{34}+x^{35}+x^{36}$$ then sum the coefficients of the monomials of the form $x^{3k}$. If $\omega=\exp\left(\frac{2\pi i}{3}\right)$, that sum is just $$\frac{1}{3}\left( r(1)+r(\omega)+r(\omega^2) \right)$$ or the coefficient of $y^3$ in the polynomial $\frac{1}{3}\left(q(1,y)+q(\omega,y)+q(\omega^2, y)\right)$, where:

$$\frac{1}{3}\left(q(1,y)+q(\omega,y)+q(\omega^2, y)\right) = (1+y)^4\cdot\left(1+20 y^2+14 y^3+\ldots\right)$$ gives us the answer: $$14+4\cdot 20+4 = \color{red}{98}.$$ Not by chance, this number is close to one third of the total number of $3$-subsets, given by $\binom{13}{3}=286$.

• I am sorry, I do not have a background of generating functions. Is there any other solution that can be used? I believe that generating functions are too advanced for me. – Carl Terence Valdellon Aug 29 '16 at 1:17
• @CarlTerenceValdellon: Ross Millikan already provided you an elementary solution: $$98=\binom{4}{3}+\binom{4}{3}+\binom{5}{3}+4\cdot 4\cdot 5.$$ – Jack D'Aurizio Aug 29 '16 at 1:23

Jack D'Aurizio's answer can be generalized. However, I don't think that the computation is simple.

Let $m$, $n$, and $p$ be positive integers such that $m\leq n$. The polynomial $f_{m,n}(x,y)\in\mathbb{Z}[x,y]$ is given by $$f_{m,n}(x,y):=\prod_{i=1}^n\,\left(1+xy^i\right)-1\,.$$ For any positive integer $s$, write $\omega_s:=\exp\left(\frac{2\pi\text{i}}{s}\right)$. Then, the number of $m$-subsets of $\{1,2,\ldots,n\}$ whose sum is $k$ modulo $p$, where $k\in\{0,1,2,\ldots,p-1\}$, is given by $$N_{m,n,p,k}:=\frac{1}{pn}\,\sum_{r=0}^{p-1}\,\omega_p^{-rk}\,\left(\sum_{j=0}^{n-1}\,\omega_n^{-jm}\,f_{m,n}\left(\omega_n^j,\omega_p^r\right)\right)\,.\tag{1}$$

Alternatively, let $$\tilde{f}_{m,n}(x,y):=\prod_{i=1}^n\,\left(1+xy^i\right)\,.$$ Then, $$N_{m,n,p,k}=\frac{1}{p(n+1)}\,\sum_{r=0}^{p-1}\,\omega_p^{-rk}\,\left(\sum_{j=0}^{n}\,\omega_{n+1}^{-jm}\,\tilde{f}_{m,n}\left(\omega_{n+1}^j,\omega_p^r\right)\right)\,.\tag{2}$$ The only difference between (1) and (2) is that (2) handles the trivial case $m=0$, while (1) does not.

• I am sorry, but I do not understand how this solution works. – Carl Terence Valdellon Aug 29 '16 at 1:16
• My post is not a solution per se. I wanted to make this as a comment on Jack D'Aurizio's answer, but commenting under his answer was not an option. For a real solution, Ross Millikan already gave that to you. – Batominovski Aug 29 '16 at 1:20