Homework 4 Solutions#

The write-ups below model the amount of explanation expected in a complete handwritten submission.

A board with separate components#

Problem. The diagram shows two allowed boards, and . Board consists precisely of the white squares in the left panel. Board consists of the same white squares together with the additional white square , shown in the right panel. In both diagrams, gray squares are forbidden and may not contain a rook.

Two fully gridded five-by-five boards with numbered rows and columns. In B, the white allowed squares are the top-left and bottom-right two-by-two blocks; every other square is gray and forbidden. In B prime, those same squares are white, as is the additional square (1,5); all other squares are gray and forbidden.

Figure 1: The two allowed boards in the separate-components problem.#

  1. Find the rook polynomial of each of the two -by- components of .

  2. Use the disjoint-board product rule to find .

  3. Find . Use the select–not-select rule to discuss the square .

Solution.

(A) A full -by- board has one empty placement, four one-rook placements, and two two-rook placements. Therefore each component has

(B) The two components use disjoint rows and columns, so their rook polynomials multiply:

(C) Let . If is not selected, the board is . If is selected, row 1 and column 5 are removed, leaving a -by- component and a -by- component. Each has rook polynomial . Thus

Rook numbers by inclusion–exclusion#

Problem. Let be the -by- board in the figure below. The white squares in the diagram are the allowed squares of ; the three gray squares are forbidden.

In this exercise we will use the principle of inclusion–exclusion to count rook numbers. This is efficient because there are very few forbidden squares.

A fully gridded four-by-four board with white allowed squares at every position except the gray forbidden squares (1,1), (1,4), and (4,1).

Figure 2: The allowed board for the inclusion–exclusion calculation.#

Let be the set of placements of nonattacking rooks on the full -by- grid. The rook number is the number of placements of nonattacking rooks on the board .

Write the following three conditions on a placement in :

  1. Find for each .

  2. For each , compute the number of placements in each of and in each pairwise intersection Also determine . Explain which intersections are empty and why. Be careful: whether intersections are empty may depend on .

  3. Apply inclusion–exclusion to find for each .

Solution.

(A) Choose the rows, choose the columns, and match them in ways. Therefore

(B) In , one rook is fixed on the corresponding forbidden square. The other rooks lie on a full -by- board, so for , and the value is 0 for .

The squares and share row 1, so is empty. The squares and share column 1, so is also empty. The squares and lie in different rows and columns. After fixing rooks on both, the other rooks lie on a full -by- board, so for , The triple intersection is also empty because it contains the two incompatible same-row or same-column pairs. Therefore

(C) Let and . Inclusion–exclusion gives Using the values above, Therefore

Separate variables before recording value#

Problem. There are 5 2-cent coins on the table. There are also as many 3-cent and 7-cent coins as you need. How many selections of these coins have total value 30 cents?

Suppose , , and record the numbers of 2-cent, 3-cent, and 7-cent coins, respectively.

  1. Write a generating function for the possible numbers of 2-cent coins using . Do the same for the possible numbers of 3-cent and 7-cent coins using and , respectively. Truncate each series at the highest exponent that could matter for a total of 30 cents.

  2. Replace , , and with appropriate powers of to obtain generating functions that record total value.

  3. Use the product of these generating functions to find the number of selections. Identify the coefficient whose value is the answer. You may use https://sagecell.sagemath.org/ to expand the product, but show your generating-function setup. For example, the code to compute is 

    
var('x')
f = (1 + x + x^2 + x^3) * (1 + x^2 + x^4)
show( f.expand() )

Solution.

(A) The generating functions for the possible numbers of coins are The last exponents are and because at most ten 3-cent coins or four 7-cent coins can contribute to 30 cents.

(B) Substituting , , and gives

(C) Let The answer is . For each possible number of 7-cent coins, the remaining counts satisfy with : The table contains nine solutions, so