Midterm 2 Information#

Format and rules#

Midterm 2 lasts 50 minutes and has five problems.

You may bring one handwritten study sheet or formula sheet on one A4 page, written on both sides. No other notes or outside materials may be used during the exam. You are encouraged to use an offline calculator.

Show the method that justifies each answer. A numerical answer or a closed formula without supporting work may receive only partial credit. When you solve a recurrence, state the characteristic polynomial, the form of the general solution, and how you used the initial conditions.

Coverage#

The exam covers rook polynomials, generating functions, and recurrence relations: the material from Lecture 12 (rook polynomials) through the end of the unit on finite state machines and vector recurrence relations. It corresponds to Lecture Notes in Unit 2 (generating functions) and Unit 3 (recurrence relations), together with the notes on complex numbers and on finite state machines. Material from Unit 1 is not tested directly, but you will still use binomial coefficients, counting arguments, and algebra.

Topics to practice#

You should be able to model a counting problem by a generating function or a recurrence and then compute with it: extract coefficients, find closed formulas, and check them on small cases. In particular, practice solving problems of the following kinds.

  • Rook polynomials

    • Compute rook numbers and the rook polynomial of a complete rectangular board.

    • Compute rook numbers of a small board of allowed squares by listing placements.

    • Use the product rule for a board that splits into pieces with disjoint rows and disjoint columns.

    • Use the use-or-omit rule for a chosen square to reduce a board to smaller boards.

  • Writing generating functions

    • Write the generating function for choices of objects where the exponent records the number of objects chosen: subsets, finitely many items, identical objects from one pile.

    • Write the generating function for choices where the exponent records the total value, such as making change with coins of given denominations.

    • Encode conditions on each type of object: upper bounds, lower bounds, finite ranges, even or odd numbers, multiples of a fixed number, unlimited supply.

    • Write generating functions for unordered selections with repetition (combinations with repetition) and integer solutions of with constraints on each variable, using a product of generating functions.

  • Computing coefficients for generating functions by hand

  • Generating functions for common combinatorial quantities

    • for fixed

    • for fixed

    • for fixed

    • for fixed

  • Ordered choices with a constrained total

    • Count compositions of an integer with a fixed number of parts, or with parts from a given set, using powers of a one-part generating function.

    • Count all compositions with parts from a given set using , for example stair climbing with strides or .

  • Operations on generating functions and coefficient extraction

    • Use the closed forms , , , and , and the coefficient formula .

    • Find how scaling (), substitution (), and shifting (multiplying by ) change the coefficients.

    • Use the operator to pass from to and ; for example, find the generating functions of , , and .

    • Use division by to form cumulative sums, and use it to find a closed formula for sums such as or .

    • Extract a coefficient from a product by summing over complementary degrees (the Cauchy product).

  • Writing recurrence relations

    • Find a recurrence and initial conditions for strings avoiding a pattern, such as binary or ternary strings with no two consecutive equal symbols, no 00, no 22, or no 10, by conditioning on the last (or first) character.

    • Find a recurrence for tilings of a or board by squares, dominoes, and longer or colored tiles, by conditioning on the final tile.

    • Find a recurrence for stair climbing, compositions, and walks with forbidden moves.

    • Compute the first few terms both directly and from the recurrence, and state the range of for which the recurrence holds.

    • Classify a recurrence by order, linearity, homogeneity, and constant or nonconstant coefficients.

  • From a recurrence to a generating function

    • Multiply a linear recurrence with constant coefficients by , sum over its valid range, and solve for as a rational function.

    • Include the initial terms correctly in the numerator.

    • Handle a nonhomogeneous term such as , , or a constant, using the standard series for and .

  • From a generating function to a recurrence

    • Given , read the recurrence from the denominator , state its valid range, and find the initial values from the numerator .

    • Use the recurrence to compute further coefficients.

  • Solving homogeneous linear recurrences

    • Form the characteristic polynomial, paying attention to signs and missing terms.

    • Solve second-order recurrences with two distinct real roots.

    • Solve recurrences with a repeated root, using , including a double or triple root.

    • Solve a third-order recurrence with a repeated root and a simple root, or with three distinct roots, by factoring a cubic and solving a three-equation system.

    • Check the closed formula against a term computed from the recurrence.

  • Solving nonhomogeneous linear recurrences

    • Choose the trial form for driving terms that are polynomial, exponential, or polynomial times exponential: , where is the multiplicity of as a characteristic root.

    • Find a particular solution when the exponential base is not a root, is a simple root, and is a double root.

    • Handle two driving terms (for example ) with separate trial forms.

    • Add the homogeneous solution and fit the constants to the initial values using the full solution.

  • Complex numbers

    • Add, multiply, divide, and conjugate complex numbers.

    • Find the modulus and argument of a complex number, and convert between rectangular and polar forms.

    • Compute powers using polar form (De Moivre’s formula).

    • Solve a recurrence whose characteristic polynomial has complex conjugate roots , writing the solution as and fitting and .

  • Finite state machines and vector recurrence relations

    • Count strings of length that avoid one or more forbidden substrings by modeling them with a finite state machine.

    • Find the states: decide what each state must record about the end of the string (the longest suffix that is a beginning of a forbidden substring), and identify the start state.

    • Draw the state diagram and write the transition matrix: for each state and each symbol, determine the next state, or that the string becomes forbidden.

    • Write the vector recurrence for the numbers of allowed strings of length ending in each state, with the initial vector .

    • Use the vector recurrence to compute the number of allowed strings of a given length.