Results 1 to 13 of 13

Math Help - Problem related to permutation and combination.

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    52

    Problem related to permutation and combination.

    Hi,

    Can anyone suggest me?
    In how many ways we can arrange three digits say 1,2,3 in a row of six so that no two same digits are together?

    Any help is appreciated.

    Thanks!!
    Ashish
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member MacstersUndead's Avatar
    Joined
    Jan 2009
    Posts
    291
    Thanks
    32
    Construct a diagram with your row of six as underscores

    ___ X ___ X ___ X ___ X ___ X ___

    The first underscore can have any of the three integers

    3 X ____ X ____ X ____ X ____ X ____

    The second underscore can have any of the remaining two integers

    3 X 2 X ____ X ____ X ____ X ____

    The remaining underscore can be filled with the integer 2, since the possibilities are the integers that are not the one integer to the left of it.

    so 3 X 2 X 2 X 2 X 2 X 2 = 3 * 2^5 = 96
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Reckoner's Avatar
    Joined
    May 2008
    From
    Baltimore, MD (USA)
    Posts
    1,024
    Thanks
    75
    Awards
    1

    Smile

    Quote Originally Posted by a69356 View Post
    Hi,

    Can anyone suggest me?
    In how many ways we can arrange three digits say 1,2,3 in a row of six so that no two same digits are together?
    You have three choices for the first digit. For the next digit, there are only two choices, because the second digit must be different than the first. Similarly for the third, and the fourth, and so on. Thus, the total number of arrangements is

    3\cdot2^5=96.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Mar 2009
    Posts
    52
    Thanks for the quick reply.

    Actually I am trying to solve the below question?

    Three variant of GMAT paper are to be given to 12 students(so that each variant is used for 4 students) and In how many ways can the student be placed in the two rows of six each so that there should be no identical variant side by side and the student sitting one behind the other should have the same variant?

    kindly help me out in this?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Mar 2009
    Posts
    52
    There is little modification in the question mentioned in the first post
    sorry I missed that earlier.

    In how many ways we can arrange 1,2,3,1,2,3 in a row of six so that no two same digits are together?

    I think we can do in the manner mentioned below.

    We can select the first digit in the 3 ways (from 1,2,3)
    This can be done in 3 ways as mentioned above.let's say it is 1

    1 _ _ _ _ _

    Now we have to select the next digit from 2,3 as per the condition.
    this can be done in 2 ways.let's say it is 2.

    1 2 _ _ _ _

    we have to select the third digit either from 1 or 3 that is again selected in the 2 ways.
    let's say third digit is 1.
    now our number becomes.

    1 2 1 _ _ _

    For 4th digit we have the choice of either 2 or 3 but we cannot select 2 as if we select 2 then two consecutive 3 are placed in last two position which is contrary to what is required.

    so the 4 digit is selected in 1 way

    1 2 1 3 _ _

    similarly the fifth and the last position.

    Hence the total number of ways of selecting the numbers are
    3 *2*2*1*1*1 = 12 ways

    Please let me know if the way I am thinking is right or not.
    suggestions are welcome.

    Thanks,
    Ashish
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,386
    Thanks
    1476
    Awards
    1
    Quote Originally Posted by a69356 View Post
    Three variant of GMAT paper are to be given to 12 students(so that each variant is used for 4 students) and In how many ways can the student be placed in the two rows of six each so that there should be no identical variant side by side and the student sitting one behind the other should have the same variant?
    If you look at the part above that I highlighted, you will realize that there is no solution as stated.
    It may be that “should” is actually “could”.

    Quote Originally Posted by a69356 View Post
    There is little modification in the question mentioned in the first post. In how many ways we can arrange 1,2,3,1,2,3 in a row of six so that no two same digits are together? number of ways of selecting the numbers are 3 *2*2*1*1*1 = 12 ways
    For this new modification in the question, that is correct.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jan 2009
    Posts
    44
    Quote Originally Posted by a69356 View Post
    Hello everyone,

    I am stuck in the below question so need assistance.

    Three variant of GMAT paper are to be given to 12 students(so that each variant is used for 4 students) and In how many ways can the student be placed in the two rows of six each so that there should be no identical variant side by side and the student sitting one behind the other should have the same variant?


    Thanks
    I like using this calculator for working out permutations and calculations.

    Combinations and Permutations Calculator
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Combinatorics question

    Hello a69356
    Quote Originally Posted by a69356 View Post
    Hello everyone,

    I am stuck in the below question so need assistance.

    Three variant of GMAT paper are to be given to 12 students(so that each variant is used for 4 students) and In how many ways can the student be placed in the two rows of six each so that there should be no identical variant side by side and the student sitting one behind the other should have the same variant?


    Thanks
    Call the three variants A, B and C. Work out first the number of ways in which these three variants can be placed in the twelve seats, and then, for each selection, arrange each group of 4 students within their 4 seats.

    We note that row 2 will be identical to row 1 as far as the position of the variant papers is concerned, since equal variants must be placed one behind the other.

    So we may choose 2 seats from the 6 for the variant A papers in
    \binom{6}{2} = 15 ways. Of these, \binom{5}{1} = 5 will have two seats side-by-side. So the places for variant A may be chosen in 10 ways. In 5 of these, there will be 3 or 4 adjacent seats left vacant - see below, where these are marked with (*):

    A . A . . . (*)
    A . . A . .
    A . . . A . (*)
    A . . . . A (*)
    . A . A . .
    . A . . A .
    . A . . . A (*)
    . . A . A .
    . . A . . A
    . . . A . A (*)

    In each of the five marked (*), there are 2 ways of placing papers B and C so that no two of the same variant are adjacent. In the remaining 5, there are 4 ways of placing B & C. So the total number of ways of placing all three sets of papers is 5 x 2 + 5 x 4 = 30.

    Having chosen which seats are to be occupied by each variant, there are then 4! ways of arranging the 4 variant A students in their seats; 4! for the B's and 4! for the C's.

    So the total number of ways of seating the students altogether is 30 x 4! x 4! x 4! = 414720.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,386
    Thanks
    1476
    Awards
    1
    Grandad, I admit that the wording of this problem mystifies me.
    I do not follow your solution. Does it allow the arrangement?
    AAAABB
    BBCCCC
    Clearly valid if “should” becomes “could”.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Combinatorics question

    Hello Plato
    Quote Originally Posted by Plato View Post
    Grandad, I admit that the wording of this problem mystifies me.
    I do not follow your solution. Does it allow the arrangement?
    AAAABB
    BBCCCC
    Clearly valid if “should” becomes “could”.
    Clearly, there are two posts that have been merged here. The OP amplified his first question (in which he talked about arranging 1, 1, 2, 2, 3, 3 in a line with no two identical digits adjacent to one another) into the question about GMAT, in which he introduced the wording that you queried:
    Quote Originally Posted by a69356 View Post
    ...and the student sitting one behind the other should have the same variant?
    So, to answer your question above: No, on two counts:

    • Because you cannot have two identical variants adjacent to one another in the same row. Even if you replace 'should' by 'could' this still rules out AAAABB.
    • Because I interpret the word 'should' to mean 'must'. 'This student should sit here' means, to me, 'This student is obliged to sit here'. So in row 2, a student with a variant A paper should (i.e. is obliged to) sit behind another student with an A paper. This interpretation is, I think, confirmed by the OP's initial problem (which I have only just seen) in which he refers to just six items in one row.

    (The idea of these seating requirements is presumably to reduce the possibility of students cheating.)

    Since there are only 30 arrangements, it is relatively simple to list them. I do so here, using the method outlined in my first posting, where I place the A's first and then arrange the B's and C's in the remaining places. I have adopted the strategy of placing an A in the first available space on the left, and then working from left to right to find all possible positions of the second A. Then, within each of these 'A' selections, I have placed the B's again working from left to right to find all possible positions.

    The ordered pairs above each group indicate the positions occupied by the A's, and * indicates A's in a pattern that leaves only two possibilities for B & C, the others yielding four possible positions for B & C (as per my first posting).

    (1, 3)
    ABACBC *
    ACABCB *
    (1, 4)
    ABCABC
    ABCACB
    ACBABC
    ACBACB
    (1, 5)
    ABCBAC *
    ACBCAB *
    (1, 6)
    ABCBCA *
    ACBCBA *
    (2, 4)
    BACABC
    BACACB
    CABABC
    CABACB
    (2, 5)
    BABCAC
    BACBAC
    CABCAB
    CACBAB
    (2, 6)
    BACBCA *
    CABCBA *
    (3, 5)
    BCABAC
    BCACAB
    CBABAC
    CBACAB
    (3, 6)
    BCABCA
    BCACBA
    CBABCA
    CBACBA
    (4, 6)
    BCBACA *
    CBCABA *

    Grandad
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,386
    Thanks
    1476
    Awards
    1
    Quote Originally Posted by Grandad View Post
    ABACBC *
    ACABCB
    Well I think that I now see the confusion.
    In the schools of US, I think it is safe to say that:
    ABACBC
    ACABCB
    would be considered six rows of two each whereas
    A B
    A B
    A C
    A C
    B C
    B C
    would be considered two rows of six each.

    I assumed he was dealing with the test given for graduate business school admission in this country.
    What is the GMAT?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Quote Originally Posted by Plato View Post
    ...
    What is the GMAT?
    I have no idea. I assumed that, since the OP is flying the US flag, that y'all would know!

    Grandad

    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,386
    Thanks
    1476
    Awards
    1
    Here is what I know as the GMAT: Prep smarter, score higher—guaranteed, or your money back!.
    I would like to see the actual question.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combination and Permutation problem.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 2nd 2011, 08:58 PM
  2. permutation/combination problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 15th 2011, 06:25 AM
  3. Replies: 2
    Last Post: July 9th 2009, 02:14 PM
  4. Permutation/Combination Problem Help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 18th 2008, 08:32 PM
  5. Permutation and Combination problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 27th 2008, 07:29 PM

Search Tags


/mathhelpforum @mathhelpforum