On the number of ways to get a sum with given parity

75 Views Asked by At

Fix some integers $a_1,\dots,a_n\geq 0$. Denote by $E$ and $O$ the number of ways to choose $(x_1,\dots,x_n)$ so that $0\leq x_i\leq 2a_i$ and such that $\sum_{i=1}^n x_i$ is even and odd, respectively. Using induction on $n$, one can prove that $$E=\frac{(2a_1+1)\cdots(2a_n+1)+1}{2},\qquad O=\frac{(2a_1+1)\cdots(2a_n+1)-1}{2}.$$ In particular, $E-O=1$.

Is there a more direct way to observe that this difference equals $1$?

2

There are 2 best solutions below

0
On BEST ANSWER

A bijection between even-sum & odd-sum arrangements is as follows: find the first positive coordinate; if it's odd, increment it by 1, and if it's even, decrement it by 1. The only arrangement left unpaired is $(0,0,0,...)$, which has even sum.

1
On

Consider the product $$ \prod_{i=1}^n \Big((-1)^0 + (-1)^1 + (-1)^2 + \dots + (-1)^{2a_i}\Big). $$ We can compute this product in two ways.

One is to distribute. For each choice of $x_1 \in \{0,1,\dots,2a_1\}$ through $x_n \in \{0,1,\dots,2a_n\}$, this gives us a term equal to $(-1)^{x_1} (-1)^{x_2} \dotsb (-1)^{x_n}$, which is $-1$ if $\sum_{i=1}^n x_i$ is odd and $+1$ if $\sum_{i=1}^n x_i$ is even. As a result, the product simplifies to $E - O$.

The other way to simplify this product is to notice that every factor is equal to $1$. Therefore $E-O=1$.


This generalizes. If $x_i$ is not restricted to the range $\{0,1,\dots,2a_i\}$, but is instead chosen from a set with $E_i$ even values and $O_i$ odd values, the same argument says that $$E - O = \prod_{i=1}^n (E_i - O_i).$$