Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Very difficult permutation

  1. Nov 28, 2005 #1
    This is mind boggling.

    There is an array of 16 squares, arranged in a 4 x 4 grid. A supply of 4 A's, B's, C's, and D's are given. How many distinguishable ways are there of placing each of the letters in a square, if, one letter must appear once in each row and each column?

    I'm lost. There are 4! ways of placing the letters in the first row. But then when you get to the second row, you can place the A, which has 3 possible locations. But then the B, depends on where the A was placed. If the A was placed under the B in row 1, then you have 3 possible spots left, but if the A was placed under the C, then there are only 2 spots left. Shown below.

    The letters represent their placement, the 0 represents a spot that a B can't be placed, and a - represents a spot the B CAN be placed.
    R1: ABCD
    R2: -A--


    R1: ABCD
    R2: -0A-

    See the problem? How do I get around this????:surprised :surprised :surprised
  2. jcsd
  3. Nov 28, 2005 #2
    Ok, I thought about another way I might be able to do this.

    I'm assuming that for ever arrangement of the 4 A's, there is an arrangement for the other letters that works.

    There are 4 ways of placing the A in the first row, 3 in the second, 2 in the third, and 1 in the last, making 24 arrangements of the A placement.

    For each of these there are 3 other arrangements possible, for the other 3 letters. So there are 24*3 ways of arranging the letters if the A's always occupy those positions.

    Now if B takes A's place there are 24*2 ways of arranging them, because the B's and A's switching places has already been counted in the above.

    If C takes it's place, there are 24*1 ways of arranging them that haven't already been counted.

    And when D takes A's place, everything is a repeat of what has already been counted.

    THEREFORE, am I correct in saying that there are 144 arrangements???????
  4. Dec 1, 2005 #3
    A can be placed in any of the four rows in the first column. In the second row there are three possible places for A while in the third row there are two and if all these are once fixed there is just one fixed position for A in the fourth row. In any such possibilities, B can be placed in the first column in any of the three rows where b is not kept. In the second row we similarly have two likely positions for B since 1 position is avoided by the existence of b in that row in the first column while the other is restricted due to the presence of the A in that square. Then the other positions of B are fixed. Again there are two possible places for C in the first column and once this is fixed the other three placement of C is also fixed. Once the placement of these three alphabets is fixed then the placement of D is also fixed. Thus the number of possible cases as given above is 4*3*2*3*2*2 = 2^5*3^2.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook