Douglas R. Shier

Department of Mathematical Sciences

Clemson University

Clemson, SC 29634-0975

Abstract: Analysis of a seemingly innocuous counting problem reinforces an important pedagogical lesson: there often are several routes from problem to answer. In the course of presenting seven solution approaches to the original counting problem, this note provides a minitour of elementary combinatorial mathematics --- with excursions into matrices, generating functions, inclusion-exclusion, and recursion.

Key Words: counting, generating function, inclusion-exclusion, recursion, spanning tree