Choosing three distinct numbers giving even sum.

combinatorics

In how many ways can we choose three distinct numbers from the set $\{1,2,…,99\}$ so that their sum is even?

I found a solution in this StackExchange post .

My question is:

When working with the case with two odd numbers and one even number, I first use the principle of counting to find all sequences containing two odd numbers and one even number as $50\times49\times49$. Then I divide by $3!$ as different permutations of the sequence don't count. I get a fractional value. Instead, if I divide by $2!$, i.e., only stripping away the arrangements of the two odd numbers (not all three digits!), I get the right answer.

I have some difficulties understanding this problem:

  1. $\binom{50}{2}\times\binom{49}{1}$ implies we are considering arrangements of 2-subsets of the set of odd numbers and 1-subsets of the set of even numbers. I don't understand why we don't divide this by $2!$ to discount the permutations of these two subsets.

  2. Why is dividing by $3!$ incorrect?

Best Answer

For me, it often helps to think of sample objects which I am counting.

One of your confusions seems to be what $a \times b$ means in a counting formula. I like to think of it as choosing among $a$ options first, and then, choosing among $b$ options, in that order (if order matters). A typical object being chosen is a $2$-vector $(A,B)$, where $A$ is one of the $a$ options and $B$ is one of the $b$ options. In particular a typical object is not a $2$-set $\{A, B\}$.

  • For ${50 \choose 2} \times {49 \choose 1}$, a typical object is a $2$-vector $(A,B)$ where $A$ is a $2$-subset of odd numbers and $B$ is a $1$-subset of even number. Every desired $3$-subset of $2$ odd numbers and $1$ even number can be written in this way in exactly one way. So no need to divide. E.g. $\{23, 4, 17\} = (\{23, 17\}, \{4\})$.

    • In particular ${50 \choose 2} \times {49 \choose 1}$ does not count $2$odd-even "as well as" even-$2$odd. For that you would need ${50 \choose 2} \times {49 \choose 1} + {49 \choose 1} \times {50 \choose 2}$... and then of course you need to divide by $2!$.
  • For $50 \times 49 \times 49$, first decide which $49$ means what. The fact that they are the same number is just a coincidence. Lets say you arrived at that formula thinking the first $49$ is choosing the second odd number, i.e. you're choosing odd-odd-even. So then a typical object is a $3$-vector $(A,B,C)$ where $A, B$ are distinct odd numbers and $C$ is even. Any desired $3$-subset can be written in this $3$-vector form in $2$ ways, e.g. $\{23, 4, 17\} = (23,17,4)$ or $(17,23,4)$, and crucially, $(23,17,4) \neq (17,23,4)$, so you divide by $2!$.

    • If you decide the first $49$ means the even number, i.e. you're choosing odd-even-odd, it's the same deal. But again, $50 \times 49 \times 49$ does not include odd-odd-even "as well as" odd-even-odd. For that you would need $50 \times 49 \times 49 + 50 \times 49 \times 49$. And if you include even-odd-odd you would need $50 \times 49 \times 49 + 50 \times 49 \times 49 + 49 \times 50 \times 49$... and then you would truly need to divide by $3!$.