Unknown

1.1. The Anatomy of a Polynomial of a Single Variable 7

which the sum of the kth powers of the numbers of the two subsets are equal

fork=1,2,3 ,..., m.

For the case m = 2, (1, 5, 6) and (2, 3, 7) have equal sums (12) and

square sums (62). Show that it is not possible to find two sets with only

two numbers in each whose sums and square sums are equal.

For each fixed m, we ask for sets (ai) and (bi) for which the number

n of elements is as small as possible. From (a), we can see that n can be

made equal to 2”. Can it be made significantly smaller? Examine the cases

m = 3, 4, 5, 6.

E.3. Polynomials as Generating Functions. We do not always want to

think of the variable as a placeholder for a number. In combinatorial prob-

lems, we focus on the coefficients of polynomials as carriers of information.

Consider this problem: A furniture company has warehouses at Albany,

Buffalo, Montreal and Toronto. Deliveries have to be made to Kingston,

Rochester and Syracuse. Each warehouse has one truck which can visit at

most one city in a day. There are other constraints:

(i) the Albany warehouse does not serve Kingston and Rochester;

(ii) the Buffalo warehouse does not serve Kingston;

(iii) the Toronto warehouse does not serve Syracuse;

(iv) the Montreal warehouse does not serve American cities.

In how many ways can the dispatcher arrange the deliveries for today?

The dispatcher is free to defer any delivery until a later day. However,

there is no point sending trucks from two different depots to the same

destination. With these points in mind, we can reformulate the problem.

Make a chart to show the origins, destinations and forbidden links:

ABMT

KXX

R X X

S x x

Each city is represented by its initial letter. We can regard the chart as
a 3 x 4 chessboard with the X-squares not available for the placement of
a chessman. The problem is to find the number of ways of choosing no
more than three of the available squares so that no two are in the same
row or column. Choice of the (R, B) square, for instance, indicates that the
Buffalo truck is to make the delivery to Rochester. Equivalently, we have
to find the number of ways of placing at most three rooks (castles) in the
available squares of the chessboard so that no one threatens any other.
This particular problem is sufficiently simple that the possibilities can be
enumerated without difficulty. However, for more complicated problems, we