3
$\begingroup$

Consider an n-digit quaternary sequence. I want to count how many such sequences have BOTH the same number of 0s as 1s and same number of 2s as 3s (e.g.if n=6, one such sequence is 001123). Thanks in advance.

$\endgroup$

2 Answers 2

2
$\begingroup$

Clearly $n$ is even; say $n=2m$. There are $\binom{2m}m$ ways to choose $m$ positions for the $0$’s and $2$’s. If there are $k$ $0$’s, there are $\binom{m}k$ ways to choose which $k$ of those $m$ positions are for $0$’s; the other $m-k$ positions will of course contain $2$’s. There must also be $k$ $1$’s, and there are $\binom{m}k$ ways to place them among the $m$ positions reserved for $1$’s and $3$’s. Thus, the desired number is

$$\binom{2m}m\sum_{k=0}^m\binom{m}k^2=\binom{2m}m\sum_{k=0}^m\binom{m}k\binom{m}{m-k}=\binom{2m}m^2$$

by Vandermonde’s identity.

The result can also be derived as follows. As before, there are $\binom{2m}m$ ways to choose the $m$ places that will be occupied by $0$’s and $2$’s; call this set of positions $A$. There are also $\binom{2m}m$ ways to choose the $m$ positions that will be occupied by $0$’s and $3$’s; call this set of positions $B$. Then the sets $A\cap B$, $[2m]\setminus(A\cup B)$, $A\setminus B$, and $B\setminus A$ contain the positions of the $0$’s, $1$’s, $2$’s, and $3$’s, respectively. (Here $[2m]=\{1,\ldots,2m\}$.) It’s not hard to verify that

$$|A\cap B|=|[2m]\setminus(A\cup B)|$$

and

$$|A\setminus B|=|B\setminus A|$$

for all sets $A,B\subseteq[2m]$ such that $|A|=|B|=m$, and that every legal string can be formed in this way.

$\endgroup$
0
$\begingroup$

n cannot be odd.

Break down the n spaces into half and fill it with 0s and 2s. Naturally, the other half will be filled with the same number of 1s and 3s as per your condition.

To do this, you must first assign a number from 0 to (n/2) for the number of 0s. This decides the number of 2s (and naturally, 1s and 3s) in your sequence.

Now, for a given number of 0s (say m), there are C(m,n).C(m,n-m).C(n/2 - m,n-2m) sequences. This is n!/m!m![(n/2)-m]![(n/2)-m]!.

So, the total number of sequences for a given "n" is the sum from m=0 to m=(n/2) of the above function.

$\endgroup$
5
  • $\begingroup$ Why do you say that $n$ can't be less than 4? Both the empty string and, say, 01 seem to satisfy the condition. $\endgroup$ Nov 17, 2013 at 3:01
  • $\begingroup$ doesn't the sequence have to have atleast one each of 1,2,3,4? (quaternary)? $\endgroup$
    – Akshara
    Nov 17, 2013 at 3:18
  • $\begingroup$ x @user99323: Where do you see such a requirement? $\endgroup$ Nov 17, 2013 at 3:24
  • $\begingroup$ okay, then here, does quarternary mean that it doesnt contain anything other than 1,2,3,4? $\endgroup$
    – Akshara
    Nov 17, 2013 at 3:27
  • $\begingroup$ x @user99323: In this context, "quaternary" seems to mean that every element of the sequence must be picked among 0, 1, 2, or 3. $\endgroup$ Nov 17, 2013 at 3:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .