In how many ways we can choose three numbers the set of first $11$ natural numbers $(1,2,\cdots,11)$ so that their sum is a multiple of $3$? In how many ways we can choose three numbers from first $11$ natural numbers $(1,2,\cdots,11)$ so that their sum  is a multiple of $3$?
I tried using "stars and bars", but as this is about selection i.e $(1,2,3)$ is same as $(3,2,1)$ it's not giving the right answer, any other ideas?
 A: You might as well work modulo $3$.  So what you have are three $0$s, four $1$s and four $2$s, and you need to select combinations that add up to $0$ mod $3$.
A: Suppose that you have $n$ distinct numbers, of which $a$ are congruent to $0$ modulo $3$, $b$ are congruent to $1$, and $c$ are congruent to $2$.
There are two ways that a sum of $3$ numbers chosen from these can be divisible by $3$: (i) all the chosen numbers are distinct modulo $3$ or (ii) all the chosen numbers are congruent modulo $3$.
There are $\binom{a}{1}\binom{b}{1}\binom{c}{1}$ possibilities of type (i) and $\binom{a}{3}+\binom{b}{3}+\binom{c}{3}$ possibilities of type (ii).
A: Given two of the numbers, only certain choices for the third number will give you a multiple of 3 as your total. It appears to me that regardless of what the first two numbers total to, roughly one third of the remaining numbers will be suitable.
There are thus 11 choices for the first number, 10 choices for the second number, and roughly 3 valid choices for the third number, yielding about 330 possible sequences.
If you're saying that the ordering doesn't matter, then I'd guess you need to divide 330 by the number of possible ways that 3 items can be rearranged (i.e., 6). That gives 55.
That's my guess. Now to go try an exhaustive search and see what the actual answer is...
Edit: It appears the exact answer is 342 ordered combinations, or 57 unordered ones. This is close to my estimate above.
