1. ## Number of arrangements

Hi I have this problem.

Calculate the number of arrangements of 2 red, 3 green and 4 blue bottles in a line, given that at least 2 bottles of the same colour are always to be in succession.

I know that...
#arrangements w/o restrictions is $\binom{9}{2,3,4}=\frac{9!}{2!3!4!} = 1260$ ways

need to find # arrangements so at least 2 bottles of the same colour are in succession.
So,

if i take #arrangements w/o restrictions - #arrangements with no colour in succession,

would that work out?

2. Originally Posted by lpd
Hi I have this problem.

Calculate the number of arrangements of 2 red, 3 green and 4 blue bottles in a line, given that at least 2 bottles of the same colour are always to be in succession.

I know that...
#arrangements w/o restrictions is $\binom{9}{2,3,4}=\frac{9!}{2!3!4!} = 1260$ ways

need to find # arrangements so at least 2 bottles of the same colour are in succession.
So,

if i take #arrangements w/o restrictions - #arrangements with no colour in succession,

would that work out?
Maybe it's just me but I'm not sure how to interpret "at least 2 bottles of the same colour are always to be in succession" -- is it that we have to have at least one pair of same-color bottles next to each other, or is it that for each of the three colors there must be at least one pair next to each other?

For example this is legal in the first but not the second: RRBGBGBGB

Edit: Ah I guess by "need to find # arrangements so at least 2 bottles of the same colour are in succession" it is the first interpretation.

"#arrangements w/o restrictions - #arrangements with no colour in succession" is valid, but the question is whether it's easy to count #arrangements with no colour in succession

I'm thinking it over; has it seemed to work out for you yet?

3. I'm trying to get my head around it too...

I think "at least 2 bottles of the same colour are always to be in succession"... goes with your first interpretation. -having at least 1 pair of the same colour bottle nxt to each other, no matter what colour it is.

like... what you had... and like RBBGBGRBG, where blue bottles are together. this is hard! its doing my head in!

4. Originally Posted by lpd
I'm trying to get my head around it too...

I think "at least 2 bottles of the same colour are always to be in succession"... goes with your first interpretation. -having at least 1 pair of the same colour bottle nxt to each other, no matter what colour it is.

like... what you had... and like RBBGBGRBG, where blue bottles are together. this is hard! its doing my head in!
Well I'm assuming that you are expected to be able to answer this with paper and pencil methods. Nevertheless I wrote a program that can be used to check answers. Since 3^9 is small I just used a very naive algorithm. Java: (used PHP tags to get syntax highlighting)

[php]
public class ColouredBottlePairs {
public static void main(String[] args) {
long t = time();
int i, au = 0, ar = 0;
String s;
for (i = 0; i < 19683; i++) {
if (isValidSelection(s)) {
au++;
if (isValidArrangement(s)) ar++;
}
}
System.out.println("Unrestricted arrangements: " + au);
System.out.println("Restricted arrangements: " + ar);
System.out.println("Elapsed: " + (time() - t) / 1000.0 + " s");
}

static boolean isValidSelection(String s) {
int d, i, c[] = new int[3];
for (i = 0; i < 9; i++) {
d = Integer.parseInt(s.substring(i, i + 1));
c[d]++;
}
return c[0] == 2 && c[1] == 3 && c[2] == 4;
}

static boolean isValidArrangement(String s) {
return s.contains("00") || s.contains("11") || s.contains("22");
}

if (s.length() >= x) return s;
}

static long time() {
return System.currentTimeMillis();
}
}
[/php]
Output:

Code:
Unrestricted arrangements: 1260
Restricted arrangements: 1181
Elapsed: 0.072 s

5. Originally Posted by undefined
Well I'm assuming that you are expected to be able to answer this with paper and pencil methods. Nevertheless I wrote a program that can be used to check answers. Since 3^9 is small I just used a very naive algorithm. Java: (used PHP tags to get syntax highlighting)

[php]
public class ColouredBottlePairs {
public static void main(String[] args) {
long t = time();
int i, au = 0, ar = 0;
String s;
for (i = 0; i < 19683; i++) {
if (isValidSelection(s)) {
au++;
if (isValidArrangement(s)) ar++;
}
}
System.out.println("Unrestricted arrangements: " + au);
System.out.println("Restricted arrangements: " + ar);
System.out.println("Elapsed: " + (time() - t) / 1000.0 + " s");
}

static boolean isValidSelection(String s) {
int d, i, c[] = new int[3];
for (i = 0; i < 9; i++) {
d = Integer.parseInt(s.substring(i, i + 1));
c[d]++;
}
return c[0] == 2 && c[1] == 3 && c[2] == 4;
}

static boolean isValidArrangement(String s) {
return s.contains("00") || s.contains("11") || s.contains("22");
}

if (s.length() >= x) return s;
}

static long time() {
return System.currentTimeMillis();
}
}
[/php]Output:

Code:
Unrestricted arrangements: 1260
Restricted arrangements: 1181
Elapsed: 0.072 s
i know this thread is a bit old... but i was looking through the question again... and i got a different answer than what you got...

if we assume there are only two kinds of bottles, ie let us forget about the red.

So we have:

_ B _ B _ B _ B _

and we must choose exactly 3 of the _ to place our G.

So there are $\binom{5}{3}$ different ways of doing this.

Now how do I also include the fact that there are 2 red bottles?

Well for any arrangement of the 7 non-red bottles looks like this:

_ X _ X _ X _ X _ X _ X _ X _ X _

Where X denotes any of the non-red bottles. We know how many ways there are of arranging the X's, and now we know that for each arrangement we must choose exactly 2 of the _ to place the red bottles. There are $\binom{8}{2}$ ways of doing this.

So in total there are $\binom{5}{3} \binom{8}{2}$ ways.

1260-280=980 ways?

6. Originally Posted by undefined
Well I'm assuming that you are expected to be able to answer this with paper and pencil methods. Nevertheless I wrote a program that can be used to check answers. Since 3^9 is small I just used a very naive algorithm. Java: (used PHP tags to get syntax highlighting)

[php]
public class ColouredBottlePairs {
public static void main(String[] args) {
long t = time();
int i, au = 0, ar = 0;
String s;
for (i = 0; i < 19683; i++) {
if (isValidSelection(s)) {
au++;
if (isValidArrangement(s)) ar++;
}
}
System.out.println("Unrestricted arrangements: " + au);
System.out.println("Restricted arrangements: " + ar);
System.out.println("Elapsed: " + (time() - t) / 1000.0 + " s");
}

static boolean isValidSelection(String s) {
int d, i, c[] = new int[3];
for (i = 0; i < 9; i++) {
d = Integer.parseInt(s.substring(i, i + 1));
c[d]++;
}
return c[0] == 2 && c[1] == 3 && c[2] == 4;
}

static boolean isValidArrangement(String s) {
return s.contains("00") || s.contains("11") || s.contains("22");
}

if (s.length() >= x) return s;
}

static long time() {
return System.currentTimeMillis();
}
}
[/php]Output:

Code:
Unrestricted arrangements: 1260
Restricted arrangements: 1181
Elapsed: 0.072 s
i know this thread is a bit old... but i was looking through the question again... and i got a different answer than what you got...

if we assume there are only two kinds of bottles, ie let us forget about the red.

So we have:

_ B _ B _ B _ B _

and we must choose exactly 3 of the _ to place our G.

So there are $\binom{5}{3}$ different ways of doing this.

Now how do I also include the fact that there are 2 red bottles?

Well for any arrangement of the 7 non-red bottles looks like this:

_ X _ X _ X _ X _ X _ X _ X _ X _

Where X denotes any of the non-red bottles. We know how many ways there are of arranging the X's, and now we know that for each arrangement we must choose exactly 2 of the _ to place the red bottles. There are $\binom{8}{2}$ ways of doing this.

So in total there are $\binom{5}{3} \binom{8}{2}$ ways.

1260-280=980 ways?

7. Originally Posted by lpd
if we assume there are only two kinds of bottles, ie let us forget about the red.

So we have:

_ B _ B _ B _ B _

and we must choose exactly 3 of the _ to place our G.

So there are $\binom{5}{3}$ different ways of doing this.
This excludes arrangements like GGGBBBB, doesn't it?

8. i was trying to find the #arrangements with no colour in succession with that procedure.

9. Originally Posted by lpd
i was trying to find the #arrangements with no colour in succession with that procedure.
Oh I see, the thread's old so I wasn't thinking along those lines.

But then don't you allow GBGBGBB when you shouldn't?

10. Originally Posted by undefined
Oh I see, the thread's old so I wasn't thinking along those lines.

But then don't you allow GBGBGBB when you shouldn't?
i see what you mean... damn. oh well i give up!

11. Originally Posted by lpd
i see what you mean... damn. oh well i give up!
Well if we treat each of the 5C3 blue green arrangements as separate cases, we can get to the answer, starting with GBGBGBB and next GBGBBGB and ending with BBGBGBG I get sum

8+8+1+8+1+1+28+8+8+8=79

12. Hello, lpd!

Calculate the number of arrangements of 2 red, 3 green and 4 blue bottles in a line,
given that at least 2 bottles of the same colour are always to be in succession.

I know that...
#arrangements w/o restrictions is: $\binom{9}{2,3,4}=\frac{9!}{2!3!4!} = 1260$ ways

If i take #arrangements w/o restrictions - #arrangements with no colour in succession,

would that work out? . Yes!

I solved it exactly like you did . . . then discovered an error in my reasoning . . .

Let us arrange the 4 Blues and 3 Greens.

The Blues can be arranged like this: . $\_\:B\:\_\:B\:\_\:B\:\_\:B\:\_$

I too chose 3 of the 5 spaces for the Greens.

But if I want to separate the Blues,
. . there is only one way: . $B\;\boxed G\;B\;\boxed G\;B\;\boxed G\;B$

Now the two Reds can be placed anywhere between the 7 bottles.
. . And there are: ${8\choose2} = 28$ ways.

But even this is wrong . . .

Let's place the 4 Blues and 2 Reds.

We start with: . $\_\:B\:\_\:B\:\_\:B\:\_\:B\:\_$

I see that there are three cases to consider.

[1] The two Reds are "outboard": . $\boxed{R}\:B\;\_\:B\:\_\:B\: \_\:B\:\boxed{R}$ . . . . one choice
. . .Then the 3 greens must go in the 3 middle spaces: . $R\:B\;\boxed G\;B\;\boxed G\;B\;\boxed G\;B\;R$
. . .There is one way for Case 1.

[2] The two Reds are "inboard".
. . .Two Reds are placed in 3 spaces: . ${3\choose2} = 3$ choices.
. . .So we have (for example): / $\_\:B\:\boxed R\:B\:\boxed R\:B\:\_\:B\:\_$
. . .A green must be placed in that one inner space: . $\_\:B\;R\;B\;R\;B\;\boxed G\:B\;\_$
. . .So we have: . $\_\:B\:\_\:R\:\_\:B\;\_\;R\:\_\:B\;G\;B\:\_$
. . .The other 2 Greens can go in any of the 6 spaces.
. . .There are: . ${6\choose2} = 15$ ways.
. . There are: . $3\cdot15 \:=\:45$ ways for Case 2.

[3] One Red is "outboard", the other is "inboard".
. . .There are 2 choices for the outboard, 3 choices for the inboard.
. . .Hence, there are: . $2\cdot3 \:=\:6$ choices for the Reds' positions.
. . .So we have (for example): . $\boxed R\:B\:\_\:B\:\boxed R\;B\;\_\:B\:\_$
. . .Two Greens must be placed in the two inner spaces: . $R\:B\;\boxed G\:B\:R\:B\;\boxed G\:B\:\_$
. . .So we have: . $\_\:R\:\_\:B\:G\:B\:\_\:R\:\_\:B\:G\;B\:\_$
. . .The remaining green goes in one of the 5 spaces: 5 choices.
. . .Hence, there are: . $6\cdot5 \:=\:30$ ways for Case 3.

Therefore, there are: . $1 + 45 + 30 \:=\:76$ ways for non-consecutive colors.

13. Originally Posted by Soroban

Therefore, there are: . $1 + 45 + 30 \:=\:76$ ways for non-consecutive colors.
You miss BRGRBGBGB, BGBGBRGRB, and BGBRGRBGB

14. Originally Posted by undefined
Well if we treat each of the 5C3 blue green arrangements as separate cases, we can get to the answer, starting with GBGBGBB and next GBGBBGB and ending with BBGBGBG I get sum

8+8+1+8+1+1+28+8+8+8=79

Perhaps it's worth explaining how I did this?

_B_B_B_B_ as lpd suggested

Try each one in systematic order

Imagine blanks labeled 01234, then you put green ones in these slots

012 (GBGBGBB)
013
014
023
024
034
123
124
134
234 (BBGBGBG)

then you have to decide where reds can go. In some cases you must use both reds to split up blues. This gives a 1 term. In other cases you must use a red to separate two blues, but the other red has 8 spots it can freely go to. Then the case BGBGBGB as noted gives 8 choose 2 = 28 ways to place the reds.

You can prove if you want that placing two greens with no blues in between can't possibly lead to a good arrangement, because you won't have enough reds to separate the same-color adjacent pairs.