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.

The answer is 2454, apparently. I am getting 1446, however. Can anyone point out my error ?

We need to partition the solution into the mutually exclusive cases of choices of 4 letters where we have no repetitions (e.g. MATH), where we have one repetition (e,g, MATT) and where we have two repetitions (e.g. MMTT). Then we compute the corresponding number of perms of each case, and add, thus:

We have 8 unique letters, so we can make 8C4 selections with no repetitions.

We have 3 pairs of repetitions {MM, AA, TT} which gives us 3 * 7C2 choices with one repetition, since having chosen, say, MM, we need to select 2 more letters from the remaining 7 unique letters.

We have 3C2 choices with 2 repetitions taken from the set {MM, AA, TT}

So our total number of perms is:

(#choices of 4, no reps * 4!) + (#choices of 4, 1 rep * 4!/2!) + (#choices of 4, 2 reps * 4!/(2!2!) ) = (8C4 * 24) + (3 * 7C2 * 12) + (3C2 * 6) = 672 + 756 + 18 = 1446

Where did I go wrong ?

share|improve this question
    
I answered pretty much the same question at math.stackexchange.com/questions/20238/… using a generating function approach. Using generating functions is very convenient for such problems. –  svenkatr Feb 28 '11 at 17:28
    
The corresponding polynomial for this problem is $4!(1+x)^5 (1+x+x^2/2)^3$. The coefficient of $x^4$ in this polynomial is 2454, which is the answer. –  svenkatr Feb 28 '11 at 17:30
    
@svenkatr: the generating function approach looks interesting, though I've never come across it before. I'll have to try to figure out how it works. I guess it's the same kind of reasoning that is used to show that binomial coefficients are $^nC_k$ ? –  user7597 Mar 10 '11 at 13:51
    
I've downloaded the book; I suspect it answers all my questions, so I'll read that. –  user7597 Mar 10 '11 at 14:28
add comment

1 Answer 1

$^8C_4 * 24$ is $1680$, not $672$.

share|improve this answer
    
Perhaps he accidentally did $^7C_2 \times 24$ or $^7C_5 \times 24$ –  Henry Feb 28 '11 at 12:23
1  
Thanks. That's embarrassing. I was hoping that it'd be a subtle combinatorial error, but I guess I'll have to live with the ignominy of a miscalculation. I have no idea how I managed to get to 672. –  user7597 Feb 28 '11 at 12:38
    
5 is next to 2 on the calculator keypad... –  TonyK Feb 28 '11 at 15:32
add comment

Your Answer

 
discard

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