A relation between Catalan Numbers and World Series type problems

- Membership
- Publications
- Meetings
- Competitions
- Community
- Programs
- Students
- High School Teachers
- Faculty and Departments
- Underrepresented Groups
- MAA Awards
- MAA Grants

- News
- About MAA

**Yueh-Gin Gung and Dr. Charles Y. Hu Award for Distinguished Service.**

by Thomas Banchoff

**The Use of Tagged Partitions in Elementary Real Analysis**

by Russell A. Gordon

gordon@whitman.edu

In order to create a Riemann sum of function on an interval, it is first necessary to form a tagged partition of the interval; divide the interval into subintervals and choose one point from each subinterval. Except for their appearance in the definition of the Riemann integral, tagged partitions seem to play a very minor role in real analysis. However, a slight modification in the way in which tagged partitions are formed leads to a result that can be used to prove many of the theorems in elementary real analysis that involve the Completeness Axiom, such as the Extreme Value Theorem, the Riemann integrability of continuous functions, and the fact that functions with positive derivatives are increasing. The new proofs are both elegant and illuminating; clear, crisp proofs that open the door to generalizations of the results. As a fringe benefit, introduction of the concept of tagged partitions early in real analysis can ease the transition to integration theory and the abstract notion of a compact set. In addition, this technique can be applied to results that are a bit beyond the realm of elementary real analysis. One example, a proof that a function that is bounded and continuous almost everywhere is Riemann integrable, is a must read since it is one of the simplest proofs of this important fact. A second example offers a proof that an absolutely continuous singular function is constant without using the Vitali Covering Lemma. If nothing else, reading this paper to discover the use of tagged partitions in elementary real analysis will help you look at familiar territory with a fresh light.

**The Dynamics of a Family of One-Dimensional Maps**

by Susan Bassein

bassein@mills.edu

The purpose of this paper is to classify the dynamics of the following two-parameter family of very simple maps from the unit interval to itself: for given 0 a b ² 1, let *f* be the map from [0,1] to [0,1] whose graph consists of two straight line segments extending from (0,*b*) to (*a*,1) to (1,0).

Despite the simplicity of its maps, this family exhibits a surprising variety of phenomena, including non-chaotic dynamics with and without attracting periodic orbits, nondegenerate homoclinic points inducing chaotic behavior on the entire interval [0,1] with no attracting periodic orbits, renormalization of chaotic subintervals, and an infinite sequence of maps that alternate between having and not having attracting periodic orbits amid the chaos.

I chose to study these maps because they closely resemble the mathematical models of electronic circuits described in S. Bassein, Order and chaos on your desk, *Amer. Math. Monthly * 102 (1995) 409-416 and S. Bassein, *Mathematics Electrified!*, Grant Publishing, Berkeley, 1996. Because we need only elementary geometry and algebra to obtain our results, our analysis can be used in an early introduction of dynamical systems to students. For example, one could give undergraduates (or even strong high school students) the general outline of our analysis and ask them to fill in the details of some or all of the sections, depending on their level and abilities, as an independent project. A more challenging project would be to try to extend the analysis to a wider class of maps, such as those with graphs made from two curves with either fixed or bounded concavity.

**The Bricklayer Problem and the Strong Cycle Lemma**

by Hunter S. Snevily and Douglas B. West

west@math.uiuc.edu

We solve the problem of counting stacks of interlocking bricks built using a natural rule. Like Lego blocks, a *q*-brick of length *q* + 1 has *q* protrusions on its top and q indentations on its bottom; the indentations on the bottom of one block can lock on to the protrusions on the top of another. We have a linear base of length *m* on which we can place bricks. The bricks sitting directly on the base can start at any integer position but must not overlap. When two bricks are contiguous, sharing a common end, we can place another brick on top of them. The interlocking requirement is that each brick placed on top of two others in this way must cover an integer portion of both bricks below it.

The problem is to count the stacks of *q*-bricks that can be built on a base of length *m*. We establish a bijection between this set and a family of 0,1-sequences generalizing the ballot sequences (in which each initial portion has at least as many 0's as 1's). We thus use generalized Catalan numbers to solve the counting problem. Generalized Catalan numbers lead us to the Cycle Lemma of Dvoretzky and Motzkin and its applications. The Strong Cycle Lemma of Kierstead and Trotter goes even farther, giving a special combinatorial meaning to each of the 0's in certain cyclic arrangements of 0's and 1's. We present their lemma and consider further generalizations and applications.

**A Computer Search for Free Actions on Surfaces**

by Craig M. Johnson

johnsonc@ac.marywood.edu

This article focuses on the use of technology to search for connections between topology and algebra. A family of computer programs was written to identify free actions on surfaces and therefore provide a nice example of the use of computers as a tool for discovery in topology.

A group G acts freely on a surface S if every element in G (other than the identity) induces a homeomorphism of S onto itself that has no fixed points. An orientation-reversing free action on an orientable surface S by a finite group G corresponds to a regular covering of a nonorientable surface U with S as the cover. This covering, in turn, is associated with a particular exact sequence of groups and homomorphisms. Beginning with an epimorphism d from the fundamental group of U to G, this exact sequence exists if and only if the image N under d of certain subgroup satisfies the condition that G/N has order 2. We use a computer to search for such free actions by groups of low order by representing the generators of each group with integer matrices, constructing each possible epimorphism and the associated subgroup N, and checking its index. Check the MONTHLY to see how a computer can be programmed to do algebraic topology.

**Division Algebras - Beyond the Quaternions**

by John C. McConnell

pmt6jcm@leeds.ac.uk

This paper is about the early history of division algebras, and, in particular, gives an elementary and elegant proof of the first general result on division algebras. This result was proved by Wedderburn in 1914 and the proof given is best described as Wedderburn's proof with a modern polish. It is self-contained and uses only basic facts on Galois theory and linear algebra.

**NOTES**

Graphical Discovery of a New Identity for Jacobi Polynomials

by Brian Gerard and Lawrence Roberts

schwartz@arch.umsl.edu

The Generalized Level of a Non Prime Finite Field Is Two

by Philippe Revoy

Cutting High-Dimensional Cakes

by Wolfgang Kühn and Zuzana Kühn

wkuhn@math.gatech.edu

**UNSOLVED PROBLEMS**

Kempe Revisited

by Joan Hutchinson and Stan Wagon

hutchinson@macalester.edu, wagon@macalester.edu

**PROBLEMS AND SOLUTIONS**

**REVIEWS**

"Invertible" Polyhedron Models. Distributed by Snyder Engineering

Reviewed by Gerald L. Alexanderson and Jean Pedersen

jpedersen@scuacc.scu.edu

Topology and Geometry. By Glen E. Bredon

Reviewed by William Goldman

mgoldman@sadira.gb.nrao.edu

**TELEGRAPHIC REVIEWS**