Yr 10 Combinatorics -- Rearranging the letters of ABRACADABRA per this rule....

[Darkmisc]

Homework Statement

Decide in how many ways the letters of ABRACADABRA can be arranged in a row if C, D and R are not to be together

Relevant Equations

11!/5!/2!/2! - 9!*3!/5!/2!/2

Hi everyone

Can anyone help with this combinatorics problem? I have the answers, but don't understand how the answer was derived.

Here's my attempt and reasoning.

Step 1: Determine all possible combinations

Since A, B and R have multiple letters, the number of possible combinations is given by 11!/5!/2!/2!

Step 2: Find all possible ways the unwanted condition can occur.

Treat C,D,R as a single block. Letters can be thought of as 8 letters + a block of 3. Within the block, there are 3! ways to arrange C, D and R.

So 9!*3!/5!/2! = 9072.

Subtracting the unwanted combinations from the total possible combinations gives 83,160 - 9072 = 74, 088.

However, the answer is 78,624, which you get with 83,160 - (9072/2).

I knew the second R was significant, but I didn't know how. For example, you might get four-letter strings like RCDR, which could be read as either RCD or CDR, but I didn't know how to factor that into the calculation.

Can someone explain to me why 9072 needed to be halved?Thanks

 

[FactChecker]

Is the problem statement that none of C, D, and R can be together, not even two of the three? Or is it that all three can not be together?

 

[anuttarasammyak]

Homework Statement:: Decide in how many ways the letters of ABRACADABRA can be arranged in a row if C, D and R are not to be together
Relevant Equations:: 11!/5!/2!/2! - 9!*3!/5!/2!/2

Can someone explain to me why 9072 needed to be halved?

One of two Rs is accounted as triplet of CDR. The other is accounted as ordinary letter. Exchanging the two results the same so the number of the case must be halved.

 

[PeroK]

I'm not convinced by the book answer. I would split the solution into the cases where CDRR appears as a group of four and where CDR appears as a group of three with the second R separate.

Try the book technique with just ACDRR and see what you get.

I think the book double counts cases where the letters appear as a group of four.

 

[PeroK]

PS I get $80,262$, which I haven't double checked!

 

[Darkmisc]

Is the problem statement that none of C, D, and R can be together, not even two of the three? Or is it that all three can not be together?

It seems to be that the three of them can't be together.

 

[Darkmisc]

One of two Rs is accounted as triplet of CDR. The other is accounted as ordinary letter. Exchanging the two results the same so the number of the case must be halved.

If the second R were an ordinary letter, would you use 9!*3!/5!/2! to calculate the permutations? That's what I used (treating R as R). I put 9!*3!/5!/2!/2 in the equation box because I figured that's how the book got the answer.

 

[Darkmisc]

I'm not convinced by the book answer. I would split the solution into the cases where CDRR appears as a group of four and where CDR appears as a group of three with the second R separate.

Try the book technique with just ACDRR and see what you get.

I think the book double counts cases where the letters appear as a group of four.

Using the book technique with just ACDRR, I'd get 5!/2! - 3!*3!/2 = 60 - 18 = 42

I'm only dividing by 2 because it seems the book does so. My calculation would be 5!/2! - 3!*3! = 14

Although, I think my calculation would treat the second R as an ordinary letter so that in sequences such as RCDR, only one forbidden string of CDR is counted.

 

[anuttarasammyak]

I put 9!*3!/5!/2!/2 in the equation box because I figured that's how the book got the answer.

I once again tell how /2 appears. Say RR were Rr , two different ones, and CDR strings you would like to make. Then

If the second R were an ordinary letter, would you use 9!*3!/5!/2! to calculate the permutations? That's what I used (treating R as R).

Actually r is R, so the above was double counted To be halved /2.

 

[PeroK]

Using the book technique with just ACDRR, I'd get 5!/2! - 3!*3!/2 = 60 - 18 = 42

I'm only dividing by 2 because it seems the book does so. My calculation would be 5!/2! - 3!*3! = 14

Although, I think my calculation would treat the second R as an ordinary letter so that in sequences such as RCDR, only one forbidden string of CDR is counted.

The idea was that you can check manually which, if either, of those answers is right.

I get 28 just counting manually. But it's early morning.

 

[PeroK]

PS I get $80,262$, which I haven't double checked!

This is not quite right as I think I took away strings like CRRD. This number needs to be adjusted upward again.

In any case, I suggest focusing on the simple case of ACDRR. Get the right answer by doing it manually and see which technique works.

 

[PeroK]

PPS I assume CRRD is allowed.

 

[PeroK]

PPS a quick calculation in my head gives 28 using my technique. Which agrees with what I counted.

I think I'm right but best to double check, as I'm out all day today.

 

[PeroK]

Let's sort this problem out. First, the simplified version with only ACDRR.

This is simple enough that we can count the $28$ permutations that do not have the three letters C, D and R consecutively. The way I did it was to look at the position of the A:

If A is first or last we have two possibilities: ACRRD and ADRRC.

If the A is second or fourth we have six possibilities.

If the A is third we have twelve possibilities.

That gives a total of $28$ by counting directly.

Alternatively, we start with the $60$ permutations and subtract those that have C, D and R consecutively.

Now, to use my technique, first we consider cases where the four letters CDRR appear together. Of the 12 possibilities only 10 have C, D and R together, as we can exclude the two cases where there is RR in the middle.

For each of these we can put the A at the start or end. That's $20$ cases discounted.

Second, we consider the cases where C, D and R appear consecutively but the second R is separate. We have six permutations of CDR, the A can go before or after and the second R must go in only one place. That's 12 more to discount.

And that gives us 28.

Applying the same technique to the full abracadabra problem I get $74,424$.

Hopefully that calculation is free from errors!

The book calculation is definitely wrong, as it's not that simple to deal with the second R.

 

[WWGD]

Does the order matter, i.e., are the triplets rdc, dcr, etc. , considered equal to each other?

 

[Darkmisc]

I think you have to treat each permutation as unique to get the book's answer, i.e. use 3! to count the permutations.

 

[PeroK]

I think you have to treat each permutation as unique to get the book's answer, i.e. use 3! to count the permutations.

First, you were right that there is no reason to divide by 2. The only problem with your original method was that you double counted cases where the four letters appeared together and you have C D and R togetherin two different ways!. I.e. where you have RCDR or RDCR.

You can fix your method by removing the double counting.

There are $\frac{8!}{5!2!} = 168$ possibilities for each of the two cases above. Take this away from your 9072 and you get 8736, which is what I got by my different method. Then subtract this from 83,160.

It's always good in these problems to count in two independent ways (and get the same answer!).

I hope this all makes sense.

 

[anuttarasammyak]

Let's sort this problem out. First, the simplified version with only ACDRR.

I take more simplified version of letters CDRR.
The OP way of /2 tells the number is
$$\frac{4!}{2!1!1!}-\frac{3! 2!}{1!1! 2}=12-6=6$$
if not halved
$$\frac{4!}{2!1!1!}-\frac{3! 2!}{1!1! }=12-12=0$$
Obviously the answer is two from CRRD and DRRC. The way referred does not seem to work in both the way.

[EDIT]
$$\frac{4!}{2!1!1!}-(\frac{3! 2!}{1!1! }-2)=12-10=2$$
seems to work where -2 corresponds to reducing double counts of RCDR and RDCR.

 

[PeroK]

I take more simplified version of letters CDRR.
The OP way of /2 tells the number is
$$\frac{4!}{2!1!1!}-\frac{3! 2!}{1!1! 2}=12-6=6$$
if not halved
$$\frac{4!}{2!1!1!}-\frac{3! 2!}{1!1! }=12-12=0$$
Obviously the answer is two from CRRD and DRRC. The way referred does not seem to work in both the way.

The book solution is patently wrong. There is no reason to half the number, except for the special cases I identified.

 

[Darkmisc]

First, you were right that there is no reason to divide by 2. The only problem with your original method was that you double counted cases where the four letters appeared together and you have C D and R togetherin two different ways!. I.e. where you have RCDR or RDCR.

You can fix your method by removing the double counting.

There are $\frac{8!}{5!2!} = 168$ possibilities for each of the two cases above. Take this away from your 9072 and you get 8736, which is what I got by my different method. Then subtract this from 83,160.

It's always good in these problems to count in two independent ways (and get the same answer!).

I hope this all makes sense.

Thanks. I think I get it. You treat RDCR and RCDR as a block. That leaves you with 7 remaining letters, 5 of which being As and 2 being Bs. Thus 8!/5!/2!, which you then double.

 

[PeroK]

Thanks. I think I get it. You treat RDCR and RCDR as a block. That leaves you with 7 remaining letters, 5 of which being As and 2 being Bs. Thus 8!/5!/2!, which you then double.

Yes, and those were the only ones that were double counted. Not all cases, as the book assumed.

Do you see why they were double counted?

 

[Darkmisc]

I'm not sure that I do.

I think 11!/5!/2!/2! - 9!*3!/5!/2! takes one R and puts it in a block of CDR (and all its permutations). The second R is treated as if it were any other letter. A 4-letter block of RCDR would get counted once as RCD and then a second time as CDR, but I think the equation would see it the first time as

RCDXXXXXXXX (X being any letter that's not R, C or D) and then the second time as XCDRXXXXXXX.

The fact that one of the R's goes into a block is what's causing me confusion. If I were simply counting permutations of ABRACADABRA without restrictions, then I'd see why the identical R's would lead to double counting.

 

[anuttarasammyak]

The fact that one of the R's goes into a block is what's causing me confusion.

Along the text after doing
$$\frac{11!}{5!2!2!1!1!}-3!*\frac{(11-2)!}{5!2!1!1!}$$
it is too much subtraction because "one R makes a triplet" double counts "two Rs make triplets". i.e. permutation including code RCDR or RDCR. For an example RCDR is once counted as R|CDR and second counted as RCD|R though they are the same. That number is
$$\frac{(11-3)!}{5!2!1!}*2$$
So the result is
$$\frac{11!}{5!2!2!1!1!}-3!*\frac{(11-2)!}{5!2!1!1!}+\frac{(11-3)!}{5!2!1!}*2$$
$$=\frac{11!}{5!2!2!1!1!}-3!\frac{(11-2)!}{5!2!1!1!}(1-\frac{2}{9*3!})$$
instead of halved that the text says. I hope now I get to an exact number.

 

[PeroK]

I'm not sure that I do.

I think 11!/5!/2!/2! - 9!*3!/5!/2! takes one R and puts it in a block of CDR (and all its permutations). The second R is treated as if it were any other letter. A 4-letter block of RCDR would get counted once as RCD and then a second time as CDR, but I think the equation would see it the first time as

RCDXXXXXXXX (X being any letter that's not R, C or D) and then the second time as XCDRXXXXXXX.

The fact that one of the R's goes into a block is what's causing me confusion. If I were simply counting permutations of ABRACADABRA without restrictions, then I'd see why the identical R's would lead to double counting.

You counted the cases for all permutations of CDR.

When you counted the cases for CDR this included all the cases where the second R came immediately before this string. I.e. where you had RCDR.

But, you also counted the cases for RCD, including the cases where the R came immediately after this string. That counts cases where you have RCDR again.

That's why you double counted the cases where you have RCDR or RDCR.