Results 1 to 2 of 2

Math Help - counting problem

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    15

    counting problem

    Let
    Rn be the number of ways to place n non-attacking rooks on an nxn chess-board.
    (a) Prove that |
    Rn|= n!.
    (b) Define
    f : Rn =>Z by

    f
    (r) = number of rooks in r on the diagonal squares

    (for r is an element of
    Rn). Is f injective? Is it surjective? Is there a partition of Rn described by f?

    The first part i get that |Rn| is n^2!/n! because there are n^2 places to go and n rooks, not sure if right.

    part b has me confused. It should be injective and surjective since there is only one choice for the rook to go to at one time. Any help would be great.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by smellatron View Post
    [LEFT]Let Rn be the number of ways to place n non-attacking rooks on an nxn chess-board.
    (a) Prove that |
    Rn|= n[FONT=CMR10][SIZE=3]!.
    Consider a (n+1)\times (n+1) board. By pigeonhole principle each rook must be located at its own row alone. Let us give each square a name, a_{ij} will represent the square at the i-th row and j-th coloumn. If we put a rook at a_{11} then the remaining rooks can only be placed everywhere except the first row and first coloumn deleted. Thus, the remaining n rooks go on the n\times n subboard. There are R_n ways of doing that. The same argument for a_{12},a_{13},...,a_{1n} and so R_{n+1} = R_n + R_n + ... + R_n = (n+1)R_n with R_2= 2. Therefore, R_n = n!.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Another counting problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 19th 2011, 08:11 AM
  2. Counting problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 11th 2010, 07:47 AM
  3. counting problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 16th 2010, 07:43 AM
  4. Replies: 3
    Last Post: April 13th 2009, 06:42 PM
  5. Counting problem
    Posted in the Statistics Forum
    Replies: 4
    Last Post: August 13th 2007, 01:01 PM

Search Tags


/mathhelpforum @mathhelpforum