6
$\begingroup$

How many different 5-letter strings can be formed using the letters from the word ABRACADABRA if duplicated letters are allowed but no letter can be used more times than it occurs in the word?

Though this seems like a duplicate, there is a nuance in my question in which i am about to explain:

According to an answer key it is 1271 because

if we set the variables vwxyz, there are 5! ways, which i understand, but

if there is a repeated letter

vvxyz, then there are $3*4*(5!/2!)$ many ways and so on and so forth, But why is it $3*4*(5!/2!)$ ? why do you multiply the 4 and the 3?

I was wondering that there are 5 ! configurations with 2! repeated letters so wouldnt that just be $\frac{5!}{2!}?$

$\endgroup$
0

2 Answers 2

Reset to default
9
$\begingroup$

Let's only consider the case when there is only one pair of repeated letters, such as VVXYZ.

You're correct to think that VVXYZ has $5!$ configurations with $2!$ repeated letters, so the number of ways of arranging VVXYZ is $\frac{5!}{2!}$.

But we're not just arranging VVXYZ in this example. There are many ways to get one pair of repeated letters, such as AABRC or BBRCD or RRCDA...

So there are 3 possibilities for the double-letter pair (either AA or BB or RR) - that's why you need to multiply by 3.

Then, for each double-letter pair, there are four possibilities (technically, 4C3) for the remaining letters (such as AABRC, AABRD, AABCD, AARCD). That's why you also need to multiply by 4.

$\endgroup$
3
  • $\begingroup$ @CatherinParayil I'm slightly stuck on the final steps of getting the solution. I get that you have to sum the number of words with no repetitions, those with $1$ repetition, ... up to $5$ repetitions so $n=\frac{5!}{1!}+3\times4\times\frac{5!}{2!}+\binom{4}{2}\times\frac{5!}{3!}+\binom{4}{1}\times\frac{5!}{4!}+1$ but this is $981$ so can someone tell me where I've gone wrong please? Thanks very much. $\endgroup$
    – Jam
    May 17, 2017 at 8:08
  • 2
    $\begingroup$ @Jam You overlooked two cases. They are two pairs of repeated letters and one other letter and three A's and one pair. The first case can be arranged in $$\binom{3}{2}\binom{3}{1} \cdot \frac{5!}{2!2!}$$ ways (pick two of the three repeated letters, one of the three letters you did not pick, then arrange the two pairs and singleton); the second case can be arranged in $$\binom{2}{1} \cdot \frac{5!}{3!2!}$$ ways (pick two B's or two R's, then arrange the three letters and the pair). $\endgroup$
    – N. F. Taussig
    May 17, 2017 at 10:06
  • $\begingroup$ @N.F.Taussig You're a star, thanks so much. $\endgroup$
    – Jam
    May 17, 2017 at 10:18
1
$\begingroup$

Multinomial coefficient: ABRACADABRA or 12314151231 has type $1^52^23^24^15^1$. So $11 \choose 5,2,2,1,1$.

$\endgroup$
4
  • 1
    $\begingroup$ It would help if you could explain your notation. $\endgroup$
    – Shaun
    May 17, 2017 at 6:44
  • $\begingroup$ sorry im not very good at combinatorics, could you explain what $11 \choose 5,2,2,1,1$ would look like when expanded out? $\endgroup$
    – John Rawls
    May 17, 2017 at 6:57
  • $\begingroup$ Hang on, I upvoted this but I now realise that $\binom{11}{5,2,2,1,1}=\frac{11!}{5!\cdot 2! \cdot 2!}=83160\neq1271$. Also the multinomial coefficient is for counting the ways of depositing $n$ objects into $m$ bins with $k_i$ objects in bin $i$ but surely we this would mean we're putting multiple letters into one position in the word? Wouldn't we instead want to count the ways of taking $n=5$ objects from $m=5$ bins with $5$ objects in bin $1$ (for As), $2$ objects in bin $2$ (for Bs) ... ? $\endgroup$
    – Jam
    May 17, 2017 at 7:57
  • $\begingroup$ This is the number of words with 11 letters you can get from ABRACADABRA, but you need the number of words with 5 letters. $\endgroup$
    – Thern
    May 17, 2017 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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