Conference rusure::math

	This problem is also discussed in SIEVAX::ALGORITHMS topic 88.

	Dan

    That is correct. I posted the original note (88) there. However
    _generating_ all the possibilities is an algorithm to me. The question
    of the maximum number of combinations is (al least to me) a
    mathematical problem. Agree?
    
             0^0
    Wildrik   |
             \-/

	I agree it is a mathematical problem.  Reply .1 was giving
	a pointer to more information on the problem to other readers
	here, it wasn't saying that posting .0 here was inappropriate.

	Dan

Can rook polynomials be used for this sort of problem?

Tony.

    If I knew what "rook polynomials" are, I could answer. As it is I don't
    know. Could you explain?
    
             0^0
    Wildrik   |
             \~/ 

        They have something to do with how many different ways a
        rook could move from A to B on a chess board.  I think.
        
        Dan

    Could you give an example. And do they also apply to non-square chess
    boards (e.g. 4x6, 7x4, 9x8 ...)?
    
    Wildrik (-8

	I don't really know all that much about them, I just recognized
	the name.

	Dan

    Ok, then. Is there anyone who can give an example, or provide pointers
    to books etc. so that I can get at least an idea of what rook
    polynomials are; what they are used for, and if they are applicable to
    my problem?
    
             0^0
    Wildrik,  |   (Confused).
             \~/

    The following books contain discussions of rook polynomials:-
    
    C.L. Liu, Introduction to Combinatorial Mathematics, McGraw-Hill, New
    York, 1968.
    
    I. Anderson, A First Course in Combinatorial Mathematics, Oxford
    University Press, New York, 1974.
    
    I'll try to give an example in a following reply but the basic
    technique is about the number of ways of placing non-taking rooks on a
    board of not only any size but any shape and  including prohibited
    squares (this may be of use in your problem but will need quite a lot
    of work).
    
    Tony.
     

    
Consider a job allocation problem in which a number of people are skilled at
various different jobs. The problem is to determine the number of ways of
assigning an appropriately skilled person to each job. For example, we may have
the following situation, in which x in a square indicates those people skilled
at particular jobs.

                         People
                     A   B   C   D
                   +---+---+---+---+
                 1 | x | x | x | x |
                   +---+---+---+---+
                 2 | x |   |   | x |
      Jobs         +---+---+---+---+
                 3 | x | x |   | x |
                   +---+---+---+---+
                 4 | x | x | x | x |
                   +---+---+---+---+

To solve this problem using rook polynomials, we find the rook polynomial of
the board formed by the white squares (prohibited), if this rook polynomial
is:-
                     2            n
	1 + r x + r x  + ... + r x
             1     2            n

then the number of ways of assigning people to jobs is:-
                                             n
	n! - r (n-1)! + r (n-2)! - ... + (-1) r
              1          2                     n

For example, the rook polynomial of the white squares above is:-

                   2     3     4
	1 + 3x + 2x  + 0x  + 0x

(1 way to place no rooks, 3 ways to place 1 rook, 2 ways to place 2 rooks, no
ways to place 3 rooks and no ways to place 4 rooks)

and so the number of ways of assigning people to jobs is:-

	4! - 3x3! + 2x2! - 0x1! + 0 = 10.


This has been a simple case as more complex boards require and understanding of
the various operations on board shapes (product, inclusion-exclusion) and the
resultant algebra looks like chopped up bits of chess board!

Hope this helps.

Tony.
    

>	is n/2. However for 8 + 8 people, I can never come up with more than
>	3 *unique* rounds.
    
	I *have* come up with 4 unique rounds. However it was by trial and
    error, and does not lend itself to a general solution. But is it the
    maximum.... ?
    
    Wildrik 8-)

.12> (1 way to place no rooks, 3 ways to place 1 rook, 2 ways to place 2 rooks,
.12> no ways to place 3 rooks and no ways to place 4 rooks)

	This should say "1 way to place 2 rooks".

.13> I *have* come up with 4 unique rounds.

	Great!  Would you post the solution?

	Re: .14  This is my solution:
    
	First of all I created a matrix and assigned the entries as follows:

                        +--+--+--+--+
			|M1|F3|M5|F7|     M for one gender
                        +--+--+--+--+     F for the *other*
			|F1|M3|F5|M7|
                        +--+--+--+--+
			|M2|F4|M6|F8|
                        +--+--+--+--+
			|F2|M4|F6|M8|
                        +--+--+--+--+

	(Notice the simularity to a 4x4 chessbboard, where M's are the black
squares (No pun intended!)).

I then assigned "courts" to the players:

+--+--+--+--+    +--+--+--+--+    +--+--+--+--+    +--+--+--+--+
| 1| 2| 3| 4|    | 1| 3| 3| 1|    | 1| 2| 1| 2|    | 1| 1| 4| 4|    
+--+--+--+--+    +--+--+--+--+    +--+--+--+--+    +--+--+--+--+
| 1| 2| 3| 4|    | 3| 1| 1| 3|    | 4| 3| 4| 3|    | 3| 3| 2| 2|    
+--+--+--+--+    +--+--+--+--+    +--+--+--+--+    +--+--+--+--+
| 1| 2| 3| 4|    | 2| 4| 4| 2|    | 2| 1| 2| 1|    | 2| 2| 3| 3|    
+--+--+--+--+    +--+--+--+--+    +--+--+--+--+    +--+--+--+--+
| 1| 2| 3| 4|    | 4| 2| 2| 4|    | 3| 4| 3| 4|    | 4| 4| 1| 1|    
+--+--+--+--+    +--+--+--+--+    +--+--+--+--+    +--+--+--+--+

	Writing it out I obtain:

Round 1  M1+F1  M3+F3  M5+F5  M7+F7
	 M2+F2  M4+F4  M6+F6  M8+F8

Round 2  M1+F5  M2+F6  M5+F1  M6+F4
	 M3+F7  M4+F8  M7+F3  M8+F2

Round 3  M1+F4  M2+F7  M3+F6  M4+F5
	 M5+F8  M6+F3  M7+F2  M8+F1

Round 4  M1+F3  M2+F4  M3+F1  M4+F2
	 M8+F6  M7+F5  M6+F8  M5+F7

(Barring typo's).

       	Again, this was done by hand, so I have no code to do it. Neither
do I have generalization(sp?) for Nx4 or MxN.

N.B. This is partly due to the algorithm of Nasser in note 88 in the ALGORITHMS
conference (credit where credit's due).

         0^0
Wildrik	  |
         \ /