Arranging 5 D's, 6 E's and 3 F's such that the First D precedes the First E which precedes the First F

Question

I am trying to solve this problem and looking for any tips. I have 5 D's, 6 E's and 3 F's and I have two conditions.

The first D must be before the first E.

The first E must be before the first F.

I thought I could solve this through determining the ways to make a string of letters with a D before an E before an F, however, that is not enough because it does not cover instances like DEFDEF... or DEFFD... since there can be letters that come after the initial string that meets the conditions.

I also contemplated using the Inclusion Exclusion principle as follows

cases where a D comes before an E + cases where an E comes before an F subtract their intersection (which I'm not sure how I'd calculate) however I still cannot account for cases where there are letters after the initial D, E, F...

Any ideas?

Answer 1

Place one $E$ and three $F$s as follows: $$ E \wedge F \wedge F \wedge F \wedge $$ The remaining $E$s can be placed any where in the wedges where a wedge can be chosen multiple times. Thus we can place the remaining 5 $E$s in $\dbinom{4+5-1}{5} = 56$ ways. Now we have an arrangement $$ \wedge E \wedge F \cdots \cdots $$ There are 9 letters in the word and these create 10 positions. For placing $D$s, we need to choose the first position at least once. Thus the number of ways of choosing 5 places out of 10 places such that the first is chosen is the same as the number of solutions to $$x_1 + x_2 + \cdots +x_{10} = 5$$ with $x_1 \geq 1$ and $x_i \geq 0$ for $i \geq 2$. Thus the number of solutions is $\dbinom{10+4-1}{4} = \dbinom{13}{4}$. Thus the number of arrangements is $56 \dbinom{13}{4} = 56 \times 715 = 40040$.

Answer 2

Method 1: We have $5 + 6 + 3 = 14$ positions to fill. Since the first D must precede the first E and the first E must precede the first F, the first position must be filled with a D. Of the remaining $13$ positions, four must be filled with the remaining Ds. That leaves nine positions to fill. Since the first E must precede the first F, the first of these must be filled with an E. Of the remaining eight positions, five must be filled with the remaining Es. All three of the remaining positions must be filled with the three Fs. Hence, the number of arrangements of $5$ Ds, $6$ Es, and $3$ Fs in which the first D precedes the first E and the first E precedes the first F is $$\binom{1}{1}\binom{13}{4}\binom{1}{1}\binom{8}{5}\binom{3}{3} = \binom{13}{4}\binom{8}{5} = 40040$$ in agreement with the answer previously posted by @Muralidharan.

Method 2: If there were no restrictions, we would have $14$ positions to fill with $5$ Ds, $6$ Es, and $3$ Fs. To do so, we choose $5$ of the $14$ positions for the Ds, $6$ of the remaining nine positions for the Es, then fill all three of the remaining positions with the Fs, which can be done in $$\binom{14}{5}\binom{9}{6}\binom{3}{3}$$ ways.

Since the first D must precede the first E and the first E must preserve the first F, there must be a D in the first position and the first of the $6 + 3 = 9$ positions occupied by a E or an F must be occupied by an E. By symmetry, $5/14$ of the possible arrangements have a D in the first position and $6/9$ of the arrangements have the first E before the first F. Hence, the number of arrangements of $5$ Ds, $6$ Es, and $3$ Fs in which the first D precedes the first E and the first E precedes the first F is $$\frac{5}{14} \cdot \frac{6}{9} \cdot \binom{14}{5}\binom{9}{6}\binom{3}{3} = 40040$$