2
$\begingroup$

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 ?

  • 0
    I answered pretty much the same question at http://math.stackexchange.com/questions/20238/6-letter-permutations-in-mississippi/20240#20240 using a generating function approach. Using generating functions is very convenient for such problems.2011-02-28
  • 0
    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.2011-02-28
  • 0
    @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$ ?2011-03-10
  • 0
    I've downloaded the book; I suspect it answers all my questions, so I'll read that.2011-03-10

1 Answers 1

3

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

  • 0
    Perhaps he accidentally did $^7C_2 \times 24$ or $^7C_5 \times 24$2011-02-28
  • 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.2011-02-28
  • 0
    5 is next to 2 on the calculator keypad...2011-02-28