159
Arrangements with Forbidden Positions
prill y eighteenth century wlirn 111< - l'i <-i i < h mil .ln'in.'il man I'icrre de Montmort* ••••I lín' probléme <lcs rencontres (Mir matching problem). In this problem mi urn contains n balls, numbered l,2,...,n, which are drawn out one at a I line dc Montmort wanted to find the probability that there are no matches in this process; that is, that ball i is not the ith ball drawn. This problem is really one of counting derangements — permutations of a set where no element |l III. in its own position. (The formula for Dn, the number of derangements nl n objects, can be found in Section 5.5 of Discrete Mathematics and Its implications, Second Edition, by Rosen.)
Another problem of arrangements, called the probléme des manages (the problem of the households), asks for the number of ways to arrange n couples around a table so that the sexes alternate and no husband and wife are ii uted together. This problem was solved in 1891 by E. Lucas**. We will solve problems such as these by defining a polynomial called a rook polynomial and ihowing how to use this to count arrangements.
Author: John G. Michaels, Department of Mathematics, State University of New York, College at Brockport.
Prerequisites: The prerequisites for this chapter are basic counting techniques and the inclusion-exclusion principle. See, for example, Sections 4.1, 4.3, 5.4, and 5.5 of Discrete Mathematics and Its Appiications, Second Edition, by Kenneth H. Rosen.
Introduction
In this chapter we will discuss the problem of counting arrangements of objects where there are restrictions in some of the positions in which they can be placed. For example, we may need to match applicants to jobs, where some of the applicants cannot hold certain jobs; or we may wish to pair up players to form two-person teams, but some of the players cannot be paired up with some of the other players.
Problems such as these, where we want to find the number of arrangements with "forbidden" positions, have a long history. They can be traced back to the
158
Arrangements with Forbidden Positions
Example 1 Suppose an office manager places an ad for some part-time help: a keyboard operator (K), a file clerk (F), a stenographer (S), a delivery person (D), and someone to work in the warehouse (W). Five people answer I lie newspaper ad and are interviewed for the jobs. Figure 1 shows which jobs each of the five applicants (1, 2, 3, 4, and 5) is qualified to handle.
Each square in this figure is either shaded or unshaded. A shaded square represents a "forbidden position"; that is, the person cannot perform that job. An unshaded square represents an "allowable position". For example, Applicant 1 cannot hold the job of stenographer, but can hold any of the other jobs. In how many ways can the office manager place the five applicants in jobs for
* Pierre-Remond de Montmort (1678-1719) was born into the French nobility, received his father's large fortune at age 22, studied philosophy and mathematics with Father Nicholas de Malebranche, and held the position of canon at Notre-Dame. lie married and began his study of probability, possibly because of his contacts with the Bernoulli family. In 1708 he published his Essai d'Analyse sui les Jeux de Hasard. One of the games studied in this work was the matching game treize. The significance of his contributions in mathematics lies in his use of algebraic methods to study games of chance.
** Edouard Lucas (1842-1891) was a French number theorist. In 1876 he proved that the Mersenne number M$? = 267 — 1 was not prime. In that year he also proved that M127 = 2127 - 1 was prime; for 75 years this was the largest number proven to be prime. Lucas attached the name "Fibonacci" to the Fibonacci sequence 1,1,2,3,5,8,... and studied the closely-related Lucas sequence, 1,3,4,7, 11, 18.....
Application:, nl I),:,,       Milium, „,
Chnploi 0 AiimmmimnlH
Figure 1.   Job applicants and possible jobs.
which they are qualified?
Solution:     A matching of the applicants with the jobs is called an arrangement with forbidden positions. Two possible job assignments are: 1-keyboard, 2-stenographer, 3-delivery, 4-warehouse, 5-file clerk, 1-warehouse, 2-stenographer, 3—file clerk, 4-delivery, 5-keyboard. We can think of Figure 1 as a 5 x 5 chessboard with nine squares removed. A rook is a chess piece that moves horizontally or vertically and can take (or capture) a piece if that piece rests on a square in the same row or column as the rook (assuming that there are no intervening pieces). For example, a rook on square (2, F) can capture an opponent's piece on any of the squares in row 2 or column F, but cannot capture a piece on square (1, A')- A matching of applicants to jobs corresponds to a placing of five rooks on the unshaded squares so that no rook can capture any other rook. These are called "nontaking" rooks. Thus, the number of acceptable job assignments is equal to the number of ways of placing five nontaking rooks on this chessboard so that none of the rooks is in a forbidden position.
The key to determining this number of arrangements is the inclusion-exclusion principle. To set up the problem so that we can use the inclusion-exclusion principle, we let
Ai — the set of all arrangements of 5 nontaking rooks with the rook in row i in a forbidden square,
for i= 1,2,3,4,5.
If we let U be the set of all possible job assignments, then the solution to our problem is \U-(Ai Uj42UA3L)A4UAs)\. Applying the inclusion-exclusion principle to \A\ u ■ • • u j4s| yields
|iiU-Ui5| = £|i(| - 52\AinAj\ + ^AiDAjnAkl (1)
- ^I^n^nyiifen^l + \At n A2 n A3 n A4 n As\,
where we sum over the appropriate sets of subscripts.
I In- problem of placing mail ukuig roukM 011 nllownMe squares has now l.i 1 n inluoed to a scries 11I prulili nr. ..I counting the number of ways of placing IMUilnkillg rooks on forlmlden squares. We need to determine the size of each n! I lie 111 sets on the right, side of (I). To simplify the solution, we introduce mil.....ol.ation. Let.
r, — the number of ways of placing i nontaking rooks on forbidden squares of a board.
11 >■ need to emphasize the fact that we are working with a particular board B, will write r,(B) instead or r,-.
I'lach of the five expressions on the right side can be written in terms of r,-, foi i = 1,2,3,4,5. The number |^4,| counts the number of ways of placing 5 1.....taking rooks, with the rook in row i on a forbidden square. For example,
=2-4! since there are two ways to place a rook on a forbidden square of fOw 3 and 4! ways to place four other nontaking rooks. Therefore ^ |-*4«| = ri "4!. Similar reasoning applies to     \Ai fl Aj\ = r2 ■ 3!, C[ Aj D Ak \ = r3 ■ 2!,
)l\Ai 0 Aj l~l Ak ("I At\ = r4 • 1!, and \Ai D • • • f~l A5\ = r5 • 0!. Making these Restitutions allows us to rewrite (1) as
\Ax U • • • U A5\ = n ■ 4! - r2 • 3! + r3 • 2! - r4 • 1! + r5 • 0!.
Hence, the solution to our problem can be written as
5! - (ri • 4! - r2 • 3! + r3 • 2! - r4 • 1! + r5 • 0!).
(2)
It is easy to see that r\ = 9, since there are nine ways to place a rook on a forbidden square. It is also not difficult to see that r2 = 28 by counting the 28 ways to place two nontaking rooks on forbidden squares. However the problems grow increasingly more difficult when we try to find the coefficients r3, r4, and r5. This leads us to look for techniques to help simplify the counting process.
Our technique for simplification is one that is often used in problems of counting — relate the given problem to a series of smaller problems, each of which is easier to solve. We begin by taking the given chessboard and changing the order of the rows and the order of the columns to obtain the board B in Figure 2.
With this rearrangement, the original board B of forbidden squares can be broken into two disjoint subboards, B\ and 52, shown in Figure 2. (We say that two boards are disjoint if they have no rows or columns in common.) The problem of computing the right side of (1) by placing nontaking rooks on forbidden squares of B is reduced to two smaller problems: placing nontaking rooks on the forbidden squares of B\ and placing nontaking rooks on the forbidden squares of B2.
162 ApplH.ilH»}:. ol !),:,< tot,) Mathomiilh ,
Ohtsptw 9 Arrmigoments with Forbidden Positions 163
F    S    K    D W
m
F S
K    D W
5! _ (P, . 4! _ ra . gl + r;t. 2| _ r4 • 1! + r5 • 0!)
= 5! - (8 • 4! - 28 • 3! + 35 • 2! - 15 • 1! + 2 • 0!) = 15.
II. net the original job assignment problem can be done in 15 ways. □
Figure 2.   Rearrangement of board of Figure 1, and two disjoint subboards.
For example, to find rx(B) either we place 0 rooks on Bi and 1 on B2, or else we place 1 rook on Bi and 0 on B2. That is,
ri(5) = r0(5i) • n(52) + r1(Bl) • r0(B2) = 1- 6 + 3-1 = 9.
To find r2(B), we observe that placing two nontaking rooks on the forbidden squares of B gives us three cases to consider: place 0 on Bi and 2 on B2, place 1 on Bi and 1 on B2, or place 2 on Bx and 0 on B2. That is,
r2(B) = ro(Bx) • r2(B2) + n(fli) • n(52) + r2(£i) - r0(S2) = 1-9 + 3-6+1-1 = 28.
Similar reasoning can be used to show that:
3
r3(B) = J2ri(B1)-r3_i(B2)
i=0
= 1-2 + 3- 9 + 1- 6 + 0-1 = 35,
4
r4(5) = ^rt(S1)-r4_,(52)
= l-0 + 3-2 + l-9 + 0-6 + 0-l = 15,
5
r5(fl) = ^r,(51)r5_1(52)
= l- 0 + 3- 0 + l- 2 + 0- 9 + 0- 6 + 0- l = 2.
Substituting the values of r,(5) into (2) yields the solution of the original problem:
Rook Polynomials
..... numbers r0(B) = l,n(B) = 9,r2(B) = 28,r3(S) = 35,r4(5) = 15, and
i ,(/<) = 2 in Example 1 can be stored as coefficients of a polynomial:
1 + 9z + 28x2 + 35x3 + 15x4 + 2a;5.
More generally, we have the following.
Definition 1 If B is any board, the rooic polynomial for B, written R(x, B), || I,lie polynomial of the form
R(x, B) = r0(B) + ri(B)x + r2(B)x2 + ■■■ + rn{B)xn
where ri(B) = the number of ways of placing i nontaking rooks on forbidden Hquares of the board. □
The rook polynomial is not only a convenient bookkeeping device for storing the coefficients rt(B), but the algebraic properties of polynomials can also be used to help solve problems of counting arrangements.
In the previous example the coefficients were found by breaking board B into 2 disjoint subboards B\ and B2. Each of these subboards has its own rook polynomial:
R(x, B^ = 1 + 3x + x2,      R(x, B2) = 1 + 6x + 9x2 + 2x3.
(The reader is asked to verify this in Exercise 1.) If we multiply these polynomials, we obtain
R(x,Bi) ■ R(x, B2) = (1 + 3x + x2)(l + 6x + 9x2 + 2x3)
= (1 • 1) + (1 • 6 + 3 ■ l)x + (1 • 9 + 3 • 6 + 1 • l)x2
+ (1 • 2 + 3 • 9 + 1 • 6)x3 + (3 • 2 + 1 • 9)x4 + (1 • 2)x5 = 1 + 9x + 28x2 + 35x3 + 15x4 + 2x5 = R{x,B).
lti-l Applications ol />/.-., into M.itlwin.iti, :
i luiptoi Ii   <\m.i/m/."",.m|-. ii/l/i / oilmlilun /'
i.itions
165
Thus, the rook polynomial lor Ii is Ihr product, ol Um .....I polynomials for Ihl
subboards Bi and B2. The fact that a similar resull in always hue is stated in Theorem 1.
Theorem 1 If a board B is broken into 2 disjoint subboards Bi and Bj, then B(x, 5) =       5i) • R(x,B2).
Proof: We will prove that the 2 polynomials, R(x,B) and R(x, Bi) ■ R(x, B,), are equal. To do this, we will show that, for each i, the x* term of R(x, 11) is equal to the a:* term of the product R{x,B]) ■ R(x,B2). To see that this is always true, consider the product of the two rook polynomials
R(x,Si) • R(x,B2) = (r0(fli) + r^B^x +■■■ + r^B^x™)
■ (r0{B2) + ri(B2)x + ■■■ + rn(B2)xn).
Multiplying these two polynomials and combining like terms yields the x' term
(r0(B0 • n(B2) + n(B0 • n^{B2) + ■■■ + r,(Bi) • r0{B2))xl.
This sum gives the number of ways of placing i nontaking rooks on B, broken down into i + 1 cases according to the number of rooks on B\ and the number of rooks on B2. Therefore this coefficient is equal to ri(B), which yields the term ri(B)x' of R(x, B). Since the corresponding terms of R(x, Bi) • R(x, B2) and R(x,B) are equal, we have R(x,B) = R{x,Bx) ■ R(x,B2). ■
The following example illustrates the technique of this theorem.
Example 2 A woman on a sales trip brought four skirts (blue, brown, gray plaid, green stripe) and five blouses (yellow, pink, white, tan, and blue). Some of the skirts cannot be worn with some of the blouses, as shown by the shaded squares in Figure 3. In how many ways can she make four outfits by pairing the four skirts with four of the five blouses?
o
LU 3
I
5 =
BLUE					
BROWN					■
GREY PLAID	I			Ü	
GREEN STRIPE		M			
'inltillon     (Note that in 111im I'muiiplr wr >........ching a wet of four objects
, mH, ollivc objects. W( will llnd tll< .....k polynomial lor the board B and
H,. n u.se the inclusion-excliwion principle to I'mish the counting process. Since
Hi, hoard is not square, we will need to suitably adjust our counting when we
,1 h I he inclusion-exclusion principle.)
We observe that this board B of forbidden positions can be broken into
two disjoint subboards Bj and B2) as in Figure 4.
o g
z
q-
LU >-
3 —i
m
GREEN STRIPE
m
BLUE BROWN GREY PLAID
			
			
		ü	
Figure 3.   Possible skirt and blouse outfits.
Figure 4.    Disjoint subboards for the board of Figure 3.
It is not difficult to compute the rook polynomials for each of these boards:
R(x,Bi) = l + x
R(x,B2) = l + 4x + 4x2 + x3.
(This is left as Exercise 2.) By Theorem 1,
R(x,B) = R(x,B1)-R(x,B2)
= (1+ x)(l + 4x+ 4z2 + x3) = l+bx + Sx2 + bx3 + x4.
Therefore r0 = 1, n = 5, r2 = 8, r3 = 5, r4 = 1. Now that we know the number of ways to place nontaking rooks on forbidden squares, we use the inclusion-exclusion principle to obtain the final answer:
\U - (Ai U • • • U AA)\ = \U\ - \Ai U • • • U M\
= \U\-fc\Ai\ - £1*04,1
+    \Ai n Aj n Ak\- \AX n A2 n A3 n a4|)
= 5 • 4 • 3 • 2 - (5(4 • 3 • 2) - 8(3 • 2) + 5(2) - 1(1)) = 39.
(Note that \U\ = 5 • 4 • 3 • 2 since |t/| is equal to the number of ways to place four nontaking rooks on the 4x5 board. Also, £ \At\ = 5(4 • 3 • 2) since t\ = 5
166 AppllC.ttlDIIS 1)1 l>l-., mill M.llllllllUlU, :
and there are 4-3-2 ways to place the l.liiri- <>Ui<>.......i J. ing 11hiki in three i■!
the other four columns.) □
The following theorem summarizes the technique of using a rook polynomial together with the inclusion-exclusion principle to count arrangements with forbidden positions.
Theorem 2 The number of ways to arrange n objects among m positions (where m > n) is equal to
P(m, n) [ri{B) ■ P(m - 1, n - 1) - r2(B) ■ P(m - 2, n - 2) + • • •
+(-l)n+lrn(B)-P(m-n,Q)]
where the numbers r,-(B) are the coefficients of the rook polynomial for the board of forbidden positions.
In particular, if m = n, the number of arrangements is nl - [n(B) • (n - 1)! - r2(B) ■ (n - 2)! + • • • + (-l)n+1r„(5) • 0!]. ■
Example 3 Probleme des rencontres An urn contains n balls, numbered 1,2,... ,n. The balls are drawn out one at a time and placed in a tray that has positions marked 1, 2,..., n, with the ball drawn first placed in position 1, the ball drawn second placed in position 2, etc. A rencontre, or match, occurs when ball i happens to be placed in position i. In how many ways can the balls be drawn from the urn so that there are no matches?
Solution: We need to find Dn = the number of derangements of 1,2,... ,n. We will do this by using rook polynomials. Since a match occurs when ball i is in position i, we shade the square (i,»), for i = 1,2,... ,n, of board B, as in Figure 5.
12 3 n
1
m		
	m	
		
	
	i
Figure 5.   An n x n board.
Board B can be broken into n disjoint subboards BX,B2, consisting of the single square (i, i).
( lui,itm II   Ainiiiumi.....I', mill I mtmUlim I'w.iUimr. 167
I hIi Hiihboard luw the molt |><>lyi.....mil l({x,ll{) = 1 + x.  Theorem 1
m|■ j■ 11>■• i here (using n iliHl.cml of 2), mid we hnvr
R(x,B) = R(x,Bi) R{x,B2)...R{x,Bn) = (l + x)(l+x)...(l + x) = (l + x)n
= C(n, 0) + C(n, l)x + C(n, 2)x2 + ■■■ + C(n, n)xn
U ing the Binomial Theorem at the last step to expand (1 + x)n. Therefore, by I K'orem 2, the number of arrangements with no matches is equal to
r»l - [C(n, l)(n - 1)! - C(n, 2)(n - 2)! + • • • + (-l)n+1C(n, n)0!]
= n!(i[_i[ + ...+(-iri).
□
The method of simplifying the counting process by breaking a chessboard Into two or more disjoint subboards works well when it can be done, as in Examples 2 and 3. But suppose it is impossible to break up a given board? The following example illustrates how to handle such a problem.
Example 4 Suppose a person has four gifts (1, 2, 3, 4) to give to four people — Kathy (K), Fred (F), Dave (D), and Wendy (W). The shaded squares in Figure 6 show which gifts cannot be given to the various people. Assuming that each person is to receive a gift, find the number of ways the four gifts can be given to the four people.
K   F   D W
M
,Bn, each
Figure 6.   Possible distributions of gifts.
Solution- In this case it is not possible to break the board into two distinct subboards. (To see why, consider row 1. If square (1, K) is in a subboard Bu
It Hi
Application;. i>t /)/■.! mln M.itlioni.itiL :
this would force 1,1 ir forbidden square (.'i, l\ ) to fcllO bl hi board /'i This force! the forbidden square (3, D) to be in This fortes tlx- forbidden s<|ii;u<-.s in row 2 to be in B\, which in turn forces square (4, W) to be in H\. Therefore l<\ is the entire board B and we have not simplified the problem.)
To solve a problem involving such a board, we simplify the problem by examining cases. We want to find t^e rook polynomial R(x,B). To find ?•;(/<) we begin by choosing a forbidden square, such as (3, K). Either we place a rook on this square (and hence no other rook in row 3 or column K) or else we do not place a rook on this square. In either case we are left with smaller boards to consider.
If we place a rook on square (3, K), then the remaining i — 1 rooks must be placed on forbidden squares of the board B' in Figure 7. This can be done in ri_i(B') ways. If we do not place a rook on square (3, A'), then the i rooks must all be placed on forbidden squares of the board B" in Figure 7. This can be done in r,(5") ways.
D W
		
		
		w
B-
B"
Figure 7.    Subboards of the board of Figure 6.
Since these two cases exhaust all possibilities, we have ri(B) = ri_1(B') + ri(B").
(3)
This recurrence relation can be used to build the rook polynomial for B. Since rj(fl) is to be the coefficient of x' in the rook polynomial for B, multiply equation (3) by x' to obtain
r,(B)x'' =ri_1(B')xi+ri(B")xi. Summing equations (4) with i — 1,2,3,4 gives
(4)
i=i
x=l
»=1
= ^r,_1(BV-1 + Er'(5/V «=i «=i
3 4
i ll,>,ihll H 4ll.MtJ,>illfiiln
i    iK the fact that rt)(H)r{)     I loi any board /', we add i\)(li)x[) to the left I.....I rM(//")x" to the second nuiii on the ri^ht side, obtaining
2 n(BW = x £ r,(BV + £ r,(2?'V.
: = 0 i = () t'=0
ol
R(x,B) = xR(x,B') + R(x,B"). (5)
easy to see that
R(x,B') = l + 3x + x2. H is also not difficult to find the rook polynomial for B", since its board already ippears as disjoint subboards:
R(x,B") = (l + x)(l+4x + 3z2) = l + 5x + 7x2 + 3i3.
Substituting these in equation (5) gives
R(x, B) = xR(x, B') + R(x, B")
= x(l + 3x + x2) + (1 + 5x + 7x2 + 3x3) = 1 + 6x + 10x2 + 4x3. By Theorem 2, the number of ways to distribute the four gifts is 4!-(6-3!-10-21 + 4-1!) =4.
□
The analog of elation (5) holds to, a,, boa*, which *~ tk. fol.owng
theorem.
Theorem 3 If (a, 6) is a square on board B, if board B' is obtained from B by removing all squares in row a and column 6, and if board B" is obtained from B by removing the one square (a, 6), then
R(x,B) = xR(x,B') +R(x,B"). ■
Example 5 A tennis coach wants to pair five men (1, 2, 3, 4, 5) and five women (6, 7, 8, 9, 10) for some practice sessions in preparation for a mixed doubles tournament. Based on the players' schedules and levels of ability, the
i=0
«=i
170 Af>f>li,:.iii,,„>. (.//),,.., ,„/„ Mtitlwnntth ■.
8   7    9   g 10
	......			
				
	Hi		■	
				
		w	■	
Figure 8.   Possible pairings of tennis players.
Chapttr 0 AimnnuiiiiiiiiH with l kiIikI<Iiiii I'liMiioim 171
I I Ik  'Ii I ails iilc left. iis KxiTfiw H.) 'I'lliTi'luri',
K(x,B) = xR{x,li') I R(»,S")
a »(1 + 5x + 7x2 + 2«") + (1 + 8x + 20a:2 + 16a;3 + 2x4) = l + 9x + 25x2 + 23x3 +4x4.
Cfom Theorem 3, it follows that the tennis coach can pair the five men and five
WMiurii in 12 ways.
□
coach knows that certain pairs cannot be formed, as shown by the shaded squares in Figure 8. In how many ways can the five men and the five women be paired?
Solution: Since it is not possible to break board B into disjoint subboards (the reader should check this), we use Theorem 3 to find R(x,B).
If we begin with square (3, 8) in Theorem 3, we obtain the boards B' and B" of Figure 9.
5		7	9	10
1		m		'MM
2				P
4				
5			■	
11		
	n	1
ml in	■	
B"
Figure 9.   Subboards of board of Figure 8.
Board B' can be broken into two disjoint subboards (using squares (5,6) and (5,9) as one board), and its rook polynomial is
R(x, B') = (1 + 2x)(l + 3x + x2) = 1 + 5x + 7x2 + 2x3.
However, it is not possible to break board B" into disjoint subboards.
To find the rook polynomial for board B", we need to use Theorem 3 again. Using square (5,9) in the theorem, we obtain
R{x, B") = x(l + 4x + 3x2) + (1 + 2x)(l + 5x + 6x2 + x3) a l + 8x + 20x2 + 16x3 + 2x4.
Suggested Readings
1. R. Grimaldi, Discrete and Combinatorial Mathematics, Addison-Wesley, Reading, Mass., 1985.
2. J. Riordan, An Introduction to Combinatorial Analysis, Wiley, New York, 1958.
3. F. Roberts, Applied Combinatorics, Prentice-Hall, Englewood Cliffs, N.J., 1984.
4. A. Tucker, Applied Combinatorics, Second Edition, Wiley, New York, 1985.
Exercises
1. Verify that R(x, Bi) - 1 + 3x + x2 and R(x, 52) = 1 + 6x + 9x2 + 2x3 for the boards of Figure 2.
2. Verify that R(x, Bi) = 1 + x and R(x, B2) = 1 + 4x + 4x2 + x3 for the boards of Figure 4.
3. Prove that it is impossible to break the board B of Figure 8 into disjoint subboards.
In Exercises 4-7 find the rook polynomial and the number of arrangements with no object in a forbidden position for the given board.
99
172 4.
Afifiln .iimm. i,l De, ,„,„ Mnlhtmiitihm
			
			
	w		
			M m
É				
				
				I
u				
HP				
				
				
		ü		
				W,
173
I I
i
S li 11( >< >. -<   /' is ;i I - -I I Mian I with lnu i I. .i 1.1.1.In |ic>:.il ions, all in the last
toluimi,   Usr the 11 id IK )< I ol .....I. polym......ils l,o prove that there are no
I» 'ssible arrangements
Suppose B is a 4 x 4 hoard with no forbidden positions. Use the method of .....k polynomials to find the number of arrangements of the four objects.
13. Let A = {1,2,3,4}. Find the number of 1-1 functions / : A —> A such that /(l) # 3, /(2) < 3, and /(4)>1.
II. 'The head of a mathematics department needs to make summer teaching assignments for five courses: numerical analysis, mathematical modeling, discrete mathematics, precalculus, and applied statistics. Professor Bloch does not want to be assigned to either mathematical modeling or precalculus, Professor Mahoney will not teach applied statistics, Professor Nakano does not want to teach numerical analysis or discrete mathematics, Professor Rockhill will teach any course except applied statistics, and Professor Sommer is willing to teach anything except numerical analysis. In how many ways can the department head match the five faculty to the five courses so that the wishes of the faculty are followed?
* 15. (a probléme des manages) Four married couples are to be seated around a circular table so that no two men or two women are seated next to each other and no husband is to sit next to his wife. Assuming that arrangements such as 123 • • • 78 and 234 • • • 81 are different, how many arrangements are possible? (Hint: First determine the number of ways in which the four women can be seated. Then set up a board to determine the forbidden positions for the four men.)
8. Carry out the details to find R(x,B") in Example 5.
9. Find the number of permutations of 1,2,3,4 where 1 is not in position 3, 2 is not in positions 3 or 4, and 4 is not in position 1.
10. A professor has divided a discrete mathematics class into four groups. Each of the groups is to write a biography on one of the following mathematicians: Boole, DeMorgan, Euclid, Euler, Hamilton, and Pascal. Group 1 does not want to write on Euler or Pascal, Group 2 does not want to write on DeMorgan or Hamilton, Group 3 does not want to write on Boole, DeMorgan, or Pascal, and Group 4 does not want to write on Boole or Euler. If the professor wants each group to write on a different mathematician, in how many ways can the professor assign a different mathematician to each group?
Computer Projects
1. Write a computer program that takes a board of forbidden positions as input and determines whether the board can be written as two disjoint subboards.
2. Write a computer program that uses Theorem 3 to find the rook polynomial for a board of forbidden positions.
3. Write a computer program that takes a board of forbidden positions as input and gives as output the number of arrangements such that no object is in a forbidden position.