Counting number of arrangements

How many 8 length arrangements of word ABCDEFGH are possible with following constraints?

1. ABCD and EFGH strings should come in the same order.You cannot permute ABCD and EFGH among themselves
2. CD and EF should not interleave. It Means whenever CDEF comes in a particular arrangement then either it should be in order of CDEF or EFCD only.

My work:- total ways these can be arranged (8!)/(4!*4!). But i am not able to adjust second constraint.

• For the second constraint CD and EF should not interleave, does a backwards arrangement such as (DCFE) count? – Toby Mak Jul 11 '17 at 8:29
• No.Because as per first constraint ABCD should be in same order.CD is allowed but DC is not. – rahul sharma Jul 11 '17 at 8:31
• How about something like $BCDA$ then? – Toby Mak Jul 11 '17 at 8:34
• ABCD should maintain its order.EFGH should maintain its order.And for second constraint it says that CD and EF should not interleave means whenever CDEF comes in a particular arrangement then either it should be in order of CDEF or EFCD only.Please let me know if question is not clear. – rahul sharma Jul 11 '17 at 8:38
• Thanks for explaining. Can you put what you said in the actual question? – Toby Mak Jul 11 '17 at 8:40

This is my attempt. Let me first re-state your constraints, to ensure I understood them properly.

Let me use the notation $N < M$ to state the letter $N$ appears before the letter $M$.

The first constraint then reads $A < B < C < D$ and $E < F < G < H$

The second constraint reads $D < E$ OR $F < C$, as a result of the fact that $C<D$ and $E < F$ following the first constraint.

One starts observing that there is only one string such that $D < E$ (first case in the second constraint): ABCDEFGH. That possibility then is counted, we shall add it later.

We are left with the first constraint plus the constraint that $F < C$. The number of possibilities complying with such constraints is counted by considering the strings such that:

1) $A < B < C < D$ and $E < F < G < H$ (first constraint) plus $H<C$ (all $E, F, G, H$ before $C$)

2) $A < B < C < D$ and $E < F < G < H$ (first constraint) plus $G <C$ AND $H>D$ ($E, F, G$ before $C$, and $H$ after $C$)

3) $A < B < C < D$ and $E < F < G < H$ (first constraint) plus $F<C$ AND $G > D$ (only $E, F$ before $C$, and $G,H$ afterwards)

The number of possibilities for case is found by a stars and bars approach, and equals

$\binom{6}{4}$, $2 \binom{5}{3}$ and $3 \binom{4}{2}$ respectively (the factor multiplying the binomial coefficient coming from the number of ways in which the letters placed after $D$ can be placed in each case mentioned). Summing it all, without forgetting the ABCDEFGH string mentioned at the beginning, one gets 54 possibilities in total.

Method 1: We subtract those cases that fail to satisfy the second constraint from those that satisfy the first constraint.

If the second constraint were not a consideration, there would be $\binom{8}{4}$ ways of choosing the positions for A, B, C, D. They must be placed in the chosen positions in that order. The letters E, F, G, H must be placed in the remaining positions in that order.

From these, we must exclude those strings in which the letters C, D, E, F appear in one of the following orders: CEFD, CEDF, ECDF, ECDF.

If the letters CEFD appear in that order, the first two positions must be filled with A and B in that order. Since G must follow F, D must appear in one of the last three positions. Prohibited strings: ABCEFDGH, ABCEFGDH, ABCEGHD.

If the letters CEDF appear in that order, the first two positions must be filled with A and B in that order and the last two positions must be filled with G and H in that order. Prohibited string: ABCEDFGH.

If the letters ECDF appear in that order, E must be in one of the first three positions since A and B must precede C and the last two positions must be filled with G and H in that order. Prohibited strings: ABECDFGH, AEBCDFGH, EABCDFGH.

If the letters ECFD appear in that order, E must in one of the first three positions since A and B must precede C and D must appear in one of the last three positions since G and H must follow F. There are $3 \cdot 3 = 9$ such strings. Prohibited strings: ABECFDGH, ABECFGDH, ABECFGHD, AEBCFDGH, AEBCFGDH, AEBCFGHD, EABCFDGH, EABCFGDH, EABCFGHD.

Hence, the number of permissible strings is $$\binom{8}{4} - 3 - 1 - 3 - 9 = 54$$

Method 2: We do a direct count, pivoting on the position of the C.

Since D must follow C, C cannot appear after the seventh position. Since A and B must appear before C, C cannot appear before the third position.

Notice also that choosing the positions of A, B, C, and D completely determines the arrangement since the remaining positions must be filled by E, F, G, H in that order.

If C is in the seventh position, then D is in the last position and A and B must be in the first six positions. Choosing the positions of A and B completely determines the string since they must appear in that order in the selected positions and E, F, G, H must appear in that order in the remaining positions. The positions of A and B can be selected in $\binom{6}{2}$ ways.

If C is in the sixth position, it must be followed by D and H and preceded by A, B, E, F, and G. Since D must appear in one of the last two positions and A and B must appear in two of the first five positions, the number of such strings is $\binom{2}{1}\binom{5}{2}$.

If C is in the fifth position, it must be followed by D, G, and H and preceded by A, B, E, and F. Since D must appear in one of the last three positions and A and B must appear in two of the first four positions, the number of such strings is $\binom{3}{1}\binom{4}{2}$.

It is not possible for C to appear in the fourth position without violating the second constraint.

If C is in the third position, then it must preceded by AB and followed by DEFGH, so ABCDEFGH is the only such string.

Hence, the number of permissible strings is $$\binom{6}{2} + \binom{2}{1}\binom{5}{2} + \binom{3}{1}\binom{4}{2} + 1 = 15 + 2 \cdot 10 + 3 \cdot 6 + 1 = 15 + 20 + 18 + 1 = 54$$ as we found above.

If $CD$ comes before $EF$, then since $A$ and $B$ come before $C$, and $G$ and $H$ come after $F$, the order must be $ABCDEFGH$.

If $CD$ comes after $EF$, then since $G$ and $H$ must also come after $EF$, and $A$ and $B$ before $CD$, the first four letters must be $A,B,E,F$ with $A$ before $B$ and $E$ before $F$, which can be done in $\binom{4}{2} = 6$ ways. Similarly, the last four letters are $C,D,G,H$ with $C$ before $D$ and $G$ before $H$, which can be done in $6$ ways.

So there are a total of $1 + 6 \cdot 6 = 37$ valid strings.

• The answer i have with me is 54. I dont know if it is correct or not – rahul sharma Jul 11 '17 at 9:20
• Your answer is incorrect. You have not considered the possibility that at least one of the letters A and B could appear in the fifth or sixth positions. – N. F. Taussig Jul 11 '17 at 10:51

Apart from the obvious $ABCDEFGH$, here is a way to count the ones with $EFCD$,
though there could be a slicker way (which I'm not able to see immediately)

$GH$ can be inserted in $6$ ways in $EFCD$, yielding $6$ substrings, viz.
$EFGHCD, EFGCHD, EFGCDH, EFCGHD, EFCGDH, \;and\; EFCDGH,$

and then $B$ and $A$ can be inserted as explained under for $EFGHCD$:

• If $B$ is placed immediately to the left of $C$, starting with $EFGHBCD$, there are $5$ ways to insert $A; \;$ if $B$ is shifted one place to the left, there are $4$ ways for $A$, and so on down to just $1$ way for $A$ as $B$ is shifted left one by one, thus $5+4+3+2+1 = 15$ ways to insert $A$ and $B$

• For the next two substrings, similarly, there will be $2\times(4+3+2+1)=20$ ways,

• And for the next three substrings, there will be $3\times(3+2+1) = 18$ ways

Finally, totalling , we get the answer $1+15+20+18 =54$