Given: Base = q, Length of sequence = r
To count the number of r-digit base q sequences with an even number of 1s.
I have given it a try and come up with the following solution:
(A) Since, $(q-2)^n$ of them contain sequences with symbols except 0 and 1, they can be counted as sequences containing an even number of 1s.
(B) Out of the remaining $(q^n - (q-2)^n)$ sequences, groups can be formed according to the patterns of the symbols (except 0 and 1, e.g., patterns of 2s, 3s, 4s,... ) in the sequences.
Since half of the sequences in each of the groups (formed in step (B)) have an even number of 1s. Hence, the general formula should be
$(q-2)^n + (q^n - (q-2)^n)/2$.
Am I going wrong somewhere?
If yes, kindly elucidate.
If no, what are the other efficient ways to arrive at a solution?
Thank you