Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
3  
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
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
1  
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
add comment

Your Answer

 
discard

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.