Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 5 down vote accepted

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

share|cite|improve this answer

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!

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.