Results 1 to 14 of 14

Math Help - Number of arrangements

  1. #1
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by lpd View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by lpd View Post
    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++) {
    s = addLeadingZeroes(Integer.toString(i, 3), 9);
    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");
    }

    static String addLeadingZeroes(String s, int x) {
    if (s.length() >= x) return s;
    return addLeadingZeroes("0" + s, x);
    }

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

    Code:
    Unrestricted arrangements: 1260
    Restricted arrangements: 1181
    Elapsed: 0.072 s
    Follow Math Help Forum on Facebook and Google+

  5. #5
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100
    Quote Originally Posted by undefined View Post
    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++) {
    s = addLeadingZeroes(Integer.toString(i, 3), 9);
    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");
    }

    static String addLeadingZeroes(String s, int x) {
    if (s.length() >= x) return s;
    return addLeadingZeroes("0" + s, x);
    }

    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100
    Quote Originally Posted by undefined View Post
    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++) {
    s = addLeadingZeroes(Integer.toString(i, 3), 9);
    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");
    }

    static String addLeadingZeroes(String s, int x) {
    if (s.length() >= x) return s;
    return addLeadingZeroes("0" + s, x);
    }

    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by lpd View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100
    i was trying to find the #arrangements with no colour in succession with that procedure.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by lpd View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100
    Quote Originally Posted by undefined View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by lpd View Post
    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

    matching my first answer.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,686
    Thanks
    617
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Soroban View Post

    Therefore, there are: . 1 + 45 + 30 \:=\:76 ways for non-consecutive colors.
    You miss BRGRBGBGB, BGBGBRGRB, and BGBRGRBGB
    Last edited by undefined; October 3rd 2010 at 12:26 PM. Reason: not necessary to quote Soroban's whole post
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by undefined View Post
    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

    matching my first answer.
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Find Number of Arrangements
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 6th 2010, 03:57 PM
  2. Replies: 7
    Last Post: July 19th 2010, 01:03 PM
  3. number of arrangements of letters ....
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 31st 2009, 10:43 PM
  4. Number of arrangements
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2009, 07:33 AM
  5. Number of arrangements
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 25th 2009, 05:35 PM

Search Tags


/mathhelpforum @mathhelpforum