Homework 4#

Due: Thursday, September 24, 2026 23:59 Submit: Gradescope, through Blackboard’s assignment area.

Please write your homework by hand. Start each exercise on a new page, scan your work to a legible PDF, and clearly mark the pages associated with every exercise.

1. (A board with separate components)#

Points: 10

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. 2 points. Find the rook polynomial of each of the two -by- components of .

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

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

2. (Rook numbers by inclusion–exclusion)#

Points: 16

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 nonattacking rooks on the board .

Write the following three conditions on a placement in :

  1. 4 points. Find for each .

  2. 7 points. 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 or not may depend on .

  3. 5 points. Apply inclusion–exclusion to find for each .

3. (Separate variables before recording value)#

Points: 14

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 -, -, and -cent coins, respectively.

  1. 5 points. 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. 3 points. Replace , , and with appropriate powers of to obtain generating functions that record total value.

  3. 6 points. 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() )