# How many strings are there that use each character in the set $\{a, b, c, d, e\}$?

How many strings are there that use each character in the set $\{a, b, c, d, e\}$ exactly once and that contain the sequence $ab$ somewhere in the string?

My intuition is to do the following:

$a \; b \; \_ \; \_ \; \_ + \_ \; a \; b \; \_ \; \_ + \_ \; \_ \; a \; b \; \_ + \_ \; \_ \; \_ \; a \; b$

$3! + 3! + 3! + 3! = 24$

Can someone explain why you have to use the product rule instead of adding the $3!$ so I can understand this in an intuitive way. Thanks!

-
You've got four groups but you're only adding 3 3!, did you forget one? – Tyler Mar 14 '13 at 23:31
ooooh crap... Yeah man I need to get some sleep... – papercuts Mar 14 '13 at 23:33

Perhaps use $\{ab,c,d,e\}$ instead of $\{a,b,c,d,e\}$. I.e. treat $ab$ as a single object.

-

As Darren aptly pointed out:

Note that in treating $\{a, b, c, d, e\}\;$ like a set of four objects where $a$ and $b$ are "glued together" to count as one object: $\{ab\}$, then we have a set of four elements $\{\{ab\}, c, d, e\}$, and the number of possible permutations (arrangements) of a set of $n = 4$ objects equaling $n! = 4! = 24$.

In a sense, that's precisely what you did in your post: treating as one "placeholder" $\;\underline{a\; b}$

If you had remembered to add an additional term of $3!$ in your "intuitive" approach, (now edited to include it) note that $$3! + 3! + 3! + 3! = 4\cdot(3!) = 4\cdot (3\cdot 2\cdot 1) =4! = 24.$$

So in this way, you compute precisely what we computed above.

What's nice about combinatorics is that "double counting" - using different ways to compute the same result - is a much-utilized method of proof!

-
Sorry, papercuts, I made a major typo in the last result! You're approach precisely matches the "other" way of looking at things. What's nice about combinatorics is that "double counting": using different ways to compute the same result, is a significant method of proof! – amWhy Mar 15 '13 at 2:27