Suggested Problems

(Ralph P. Grimaldi, 5th edition)

This is not a homework. I do not expect you to solve all these problems; just make sure that you know how to solve them, and you'll do well in the exams. Do not try to write down all solutions; most problems are solved in two words provided that you understand the subject. (That, of course, doesn't apply to those where you actually need to calculate something; solve these ones till you feel confident. Neither does this apply to exams, where you are supposed to explain your solution in details!)

Principles of counting (1.1--1.4). Formulas for the number of linear arrangements (without or with repetitions), circular arrangements (without repetitions), and combinations (without or with repetitions). Algebraic properties of binomial coefficients; identities; applications.
No amount of formulas can substitute for experience; study examples and see how various problems are reduced to standard ones (usually via a case by case consideration; a good approach would reduce the number of cases). Note also that it is much easier to remember the ideas behind the formulas than the formulas themselves and the conditions for their applicability. Learn to extract the mathematical essence of a problem from its textual shell! Avoid overcounting!

  • 1.1, 1.2: 5, 6, 11 (this one is stated incorrectly. Why?), 15, 16, 19, 21-28, 30-32, 35-38; 39 (this one is just for fun :)
  • 1.3: 4, 6-13, 19-21, 24-32
  • 1.4: 1, 2, 4, 5, 7, 9, 12, 15-18, 21, 22, 25, 28

    • Fundamentals of logic (2.1, 2.2, 2.4). The concept of (closed) statement = Boolean variable. Elementary Boolean operations and Boolean expressions, properties (identities), simplification. Disjunctive normal form. Applications. Open statements; quantifiers and their simplest properties. (Remark: we do not do formal proofs as they are not proofs :)

  • 2.1: 1-3, 5, 8-10, 12, 13, 17
  • 2.2: 4-8, 12-17, 19, 20
  • 2.4: 1, 3-5, 7, 12, 15, 18, 21, 22, 24-26

    • Set theory (3.1--3.3). Sets, elements, subsets. Sets as open statements. The number of subsets; applications (counting and combinatorial identities). Set operations (union, intersection, complement, difference, symmetric difference) and their properties. Venn diagrams; applications to counting.

  • 3.1: 1-15, 18-21, 23, 26
  • 3.2: 1-5, 7, 8, 12, 17-19
  • 3.3: 1-5, 7-10

    • Properties of integers (4.1, 4.3--4.5). Well ordering and its applications; induction. Divisibility of integers, primes, greatest common divisor, Euclidean algorithm, prime factorization and its uniqueness.

  • 4.1: 1-4, 6-8, 12-18, 23, 24, 26
  • 4.3: 2-7, 9-11
  • 4.4: 1-13, 16, 17, 19
  • 4.5: 3, 5, 8, 12-16, 18, 26

    • Relations and functions (5.1--5.3). Cartesian product. Relation as a subset. Functions. Counting relations, functions, injections, and surjections. Stirling numbers.

  • 5.1: 3, 5, 10-12
  • 5.2: 1, 2, 5, 18, 20-22, 28
  • 5.3: 2-4, 6-8, 10, 12, 13, 15, 17-19

    • ^^^ Midterm I ^^^

    The Pigeonhole principle (5.5). Solve the problems and study the examples in the book. In addition to the principle itself, there are quite a few tricks!

  • 5.5: 2-24

    • Properties of relations (7.1, 7.3--7.4). Terminology related to relations: reflexive, (anti-)symmetric, transitive; relation matrix (discussed in class; see 7.2). Counting relations. Partial orders and Hasse diagrams; common examples (usual numeric order, divisibility, inclusion); minimal, maximal, greatest etc. elements. Equivalence relations, partitions, and quotient sets.

  • 7.1: 1, 4-9, 11-17
  • 7.3: 2-5, 8, 9, 11, 15, 16, 18, 19, 21, 23-28
  • 7.4: 1-4, 6-11, 13, 14, 17

    • The principle of inclusion and exclusion (8.1--8.2). The principle (no condition holds), generalizations (exactly m conditions, at least m conditions), applications (Stirling numbers, Euler function and its properties, miscellaneous applications to counting)

  • 8.1: 1, 2, 4-10, 13, 15, 16, 18, 19, 23-30 (in 'probability' questions, remember that probability is merely the ratio of two counts; most questions involving the Euler function can be solved using the formula obtained in Example 8.8, which should be treated as a theorem)
  • 8.2: 2-4, 6, 7, 8*

    • Generating functions (9.1--9.5). The concepts of ordinary and exponential generating functions. Theirs usage: ordinary functions for 'combination problems' (more precisely, number of integral solutions to a linear equation with various restrictions to the unknowns) and exponential functions for 'permutation problems' (the ship with flags in Example 9.28 is a very typical one). Other applications: partitions of integers, the summation operator and its usage. Dealing with functions: most often used power series, ways to obtain new series from known ones (multiplication by x, multiplying out, differentiation, representing a 'long' polynomial as (xk-1)/(x-1), etc.)

  • 9.1: 1-5
  • 9.2: 1-13, 17, 18, 29, 30 (learn to write down the function! learn dealing with simple power series)
  • 9.3: 2-8 (proving statements without knowing what the numbers are)
  • 9.4: 1-6, 8-10 (again, learn to write down the generating function!)
  • 9.5: 1-7

    • ^^^ Midterm II ^^^

    Recurrence relations (10.1--10.4). Solving linear recurrence relations with constant coefficients, both homogeneous and nonhomogeneous (via undetermined coefficients and using generating functions). Applications to counting problems ('counting by induction').

  • 10.1: 2-6, 10
  • 10.2: 1-9, 11-14, 16, 17, 20, 21, 23-25, 29, 32, 33; 15 (this one is beyond the scope of the standard techniques; just think!)
  • 10.3: 1-13
  • 10.4: 1-3

    • Graphs (11.1--11.4, 11.6(?)). The notion of (multi-)graph (informally and formally); related terminology (vertices, edges, incidence, adjacency, degree = valency, walks, trails/circuits, paths/cycles, etc.) Connectedness of graphs; connected components. Subgraphs. Graph isomorphisms, detecting (non-)isomorphic graphs (no algorithm, just common sense + practice!) Applications of graphs. (Since we don't know much about graphs, the latter mainly means the ability to restate various problems in the graph language.) Counting in graphs (walks, trails, paths, etc.; again, there's no algorithm here; just use common sense and your intuition). Bipartite graphs. Planar graphs. Kuratowski's theorem (statement only). Euler's theorem and its applications (detecting non-planar graphs, Platonic solids, etc.) Chromatic polynomials. (Remark: note that most problems here are 'proof' problems; there's no common recipe to solve them, although there are quite a few tricks; hence, what you need is practice!)

  • 11.1: 1-16
  • 11.2: 1-6, 8-11, 12*, 13*, 14*, 15-17
  • 11.3: 1*, 2, 3, 4*, 5-7, 11, 13, 15, 16, 18, 19*, 20-25, 27*, 30* (I like this one a lot!), 31-35
  • 11.4: 2-14, 18-25, 28, 29
  • 11.6: 1-10

    • Last update: May 12, 2005