# A Counting Problem

Suppose letters $a, b, c , d$ are to be arranged such that $a$ should always come before $b$ and so with $c$ should always come first before $d$. By brute force, I got the following arrangements:

$$abcd,acbd,acdb,cdab,cadb,cabd$$.

Now, there are six ways in arranging $a,b,c,d$. My question now is, what is the combinatorial way of finding the number $6$? Thanks.

-
Do you have a generalization in mind? With such a small problem, some combinatoricists might already be done brute-forcing it before they think of other approaches. –  user2357112 Mar 16 '14 at 7:55
Yes...somehow, ... ijust have to prove and write them down. –  Keneth Adrian Mar 16 '14 at 7:59

One way to do it is this: There are $4!=24$ arrangements of all four letters with no restrictions. In half of those arrangements, $a$ precedes $b$, and in half of them, $c$ precedes $d$. The order of $a$ and $b$ and the order of $c$ and $d$ are independent, so we multiply $\frac12\cdot\frac12=\frac14$. One fourth of $24$ is $6$.

Here's another way: place $a$ and $b$ first, and there's only one way to do that. Now we get to place $c$ and $d$, and they get to go in the three spaces surrounding our $a$ and $b$ (before $a$, between the two, and after $b$). We know which order they go in. There are $\binom31=3$ ways to put them adjacent, and $\binom32=3$ ways to put them non-adjacent. That makes six.

-
thanks for two approaches to solve the problem.. –  Keneth Adrian Mar 16 '14 at 4:13

Exactly half of all arrangements have $a$ before $b$, and exactly half have $c$ before $d$. Hence your answer is $$\frac{4!}{2\cdot 2}=\frac{24}{4}=6$$

-

There are $4$ chairs in a row. There are $4!$ ways to arrange our $4$ people in a row.

There are $\binom{4}{2}$ ways to choose the pair of chairs to be occupied by $a$ and $b$. Once we have done that, where everybody sits is determined.

Thus the required probability is $\frac{\binom{4}{2}}{4!}$.

-