1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Rook-Chessboard problem. 6 rooks on 8 by 8 board

  1. Feb 9, 2014 #1
    1. The problem statement, all variables and given/known data
    How many ways can two red and four blue rooks be placed on an 8-by-8 chessboard so that no two rooks can attack one another.



    2. Relevant equations
    1)Number of permutations with two types=(n choose n1)=n!/((n1!)(n-n11))
    2)Number of ways to place n rooks which have k object types(colors) on n-by-n board=(n!)2/((n1!)(n2!)...(nk!))


    3. The attempt at a solution
    With the two equations on top I thought that they answer would be (8 choose 6)((8 choose 6) choose 2)) since it will be a 6 rooks on an 8-by-8 board.

    *(8 choose 6)=(8!)/(6!((8-6)!)=8x7/2=28
    This will simply to:
    28(28!/(2!(28-2)!)=
    28(28x27/2)=
    14x28x27=28x27x14.

    Did I do this correct or am I wrong in my reasoning.


    P.S. I am sorry for the format. I am new to this site and tried to make it as clean as possible.
     
  2. jcsd
  3. Feb 9, 2014 #2
    I don't see what you're doing here.
    The answer should be a lot bigger however.

    It's possible to choose the both the columns and the rows that will have blue and red rooks independently.
    The number of ways to choose the colums is the number of ways of ordering (b,b,b,b,r,r,e,e) (e=empty).
    Same for the rows.
    No matter wich columns and rows you choose you will end up with a 4x4 square of possible locations for the blue rooks and a 2x2 square of possible locations for the red rooks.
     
  4. Feb 9, 2014 #3
    Ok so I can regard my multiset of "rooks" as being a set m={4*b,2*r,2*e} like you stated and use this theorem in my book that states:

    For n rooks of k colors the number or arrangements is equal to

    n!(n!/(the repetition number of each object)!).

    So the number of arrangements would be (8!)2/(4!*2!*2!).

    Which equals 10*7*6*8! Since 8!/(4!*4)=10*7*6.
     
  5. Feb 9, 2014 #4
    You could just count directly.

    With 6 non-attacking rooks on an 8x8 board, there will be exactly two rows and two columns that are free of rooks. Choose the two rows, there are (8 choose 2) ways to do so. Now choose the rows for your 4 blue rooks, there are (6 choose 4) ways to do so. At this point the rows of the remaining two rooks has already been determined by your choices. Now think of your six rooks and two empty places for a total of 8 objects. Take any of the 8! permutations of these and throw them in columns that way to get a non-attacking position. Thus the number of possible positions is:

    ((8 choose 2)*(6 choose 4))*8!​
     
    Last edited: Feb 9, 2014
  6. Feb 9, 2014 #5
    Oh ok thank you for the other alternative to look at this problem. It does make sense now.
     
  7. Feb 9, 2014 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    A factor of 2 too many. When choosing the columns, the two blank rows are interchangeable.
     
  8. Feb 9, 2014 #7
    8! <> 10 so the arithmetic here is wrong. (8!)2/(4!*2!*2!) is a factor of 2 too high.

    You'd have 8!/(4!2!2!) arrangements for the rows, and the same number for the columns, and than 4! ways to order the blue and 2! ways to order the red rooks, wich ends up being equal to
    (8!/4! 2! 2!)^2 * 4! * 2! wich is equal to ((8 choose 2) (6 choose 4) * 8!) / 2 as has been given by kduna and haruspex.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Rook-Chessboard problem. 6 rooks on 8 by 8 board
  1. Rook polynomials (Replies: 1)

  2. 6 roots of -8 issue (Replies: 8)

Loading...