Midterm 1 Information

Format and rules

Midterm 1 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 counting method that justifies each answer. A numerical answer without supporting work may receive only partial credit.

Coverage

The exam covers Lectures 1–11, from the start of the course through the September 11 lecture, and Lecture Notes 1–5. The five problems will be variants of problems in the two Midterm 1 practice banks published on MyOpenMath.

Problem types to practice

You should be able to read a counting problem, decide what an outcome records, and choose a method that counts each permitted outcome exactly once. In particular, practice solving problems of the following kinds.

• Counting principles

  • Use the addition principle to count disjoint cases.

  • Use the subtraction principle to count a complement or remove prohibited outcomes.

  • Use the multiplication principle to count a sequence of choices.

  • Use the division principle when each outcome has been counted the same number of times.

• Strings and functions

  • Count strings and identifiers with repetition allowed or with no repeated symbols.

  • Count nonconstant strings by subtracting the constant strings.

  • Count all functions between finite sets and injective functions between finite sets.

  • Count assignments to labeled recipients and splits into labeled parts.

• Permutations and anagrams

  • Count ordered selections and arrangements of distinct objects.

  • Count anagrams with repeated symbols using multinomial coefficients.

• Combinations

  • Count unordered selections without repetition and subsets of a set.

  • Count two- and three-dimensional lattice paths with binomial or multinomial coefficients.

  • Count paths through a specified point or avoiding a specified point.

  • Solve compound selection problems, such as committee selection with named offices and ordinary members.

• Combinations with repetition

  • Count unordered selections with repetition, such as purchases by type.

  • Use stars and bars / combinations with repetition to count nonnegative integer solutions.

  • Count integer solutions with lower bounds by first translating to nonnegative variables.

  • Count strictly increasing and weakly increasing integer sequences.

• Binomial and multinomial coefficients

  • Expand binomial and multinomial expressions.

  • Extract ordinary, weighted, and signed coefficients from binomial and multinomial expressions.

• Inclusion–exclusion

  • Use inclusion–exclusion for two or three overlapping conditions, including Venn-diagram and union computations.

  • Count a desired collection by defining violation sets and counting the complement of their union.

  • Count integer solutions with one or several upper bounds, including a common upper bound.

  • Count strings or permutations avoiding specified consecutive substrings, using blocks and inclusion–exclusion; determine whether overlapping substring conditions are compatible.

  • Compute Euler’s totient function from the distinct prime divisors of an integer.

  • Recognize when intersection sizes depend only on the number of imposed conditions and group terms using binomial coefficients.

  • Count derangements and permutations with exactly a prescribed number of fixed points.

  • Count surjective functions by excluding omitted symbols or outputs.

  • Count labeled simple graphs with no isolated vertices.