Lake Mendota, Madison, WI

Courtesy UW-Madison Soil Sciences

#### Priority queues and the Bruhat order

We observe that valid input-output pairs for priority queue sorting—the "Insert/DeleteMaximum" paradigm—can be characterized in terms of paths in the Hasse diagram for the weak Bruhat order on permutations.

#### On the power sum identity

We give a simple bijective proof of this identity.

#### Sierpinski's triangle and the Prouhet-Thue-Morse word

Sierpinski's triangle is a fractal and the Prouhet-Thue-Morse word is sufficiently chaotic to avoid cubes. Here we observe that there is at least a tenuous connection between them: the Sierpinski triangle is evident in Pascal's triangle mod 2 whose inverse, as an infinite lower-triangular matrix, involves the Prouhet-Thue-Morse word.

#### Permutations avoiding a nonconsecutive instance of a 2- or 3-letter pattern

We count permutations avoiding a nonconsecutive instance of a two- or three-letter pattern, that is, the pattern may occur but only as consecutive entries in the permutation. Two-letter patterns give rise to the Fibonacci numbers. The counting sequences for the two representative three-letter patterns, 321 and 132, have respective generating functions $(1+x^2)(C(x)-1)/(1+x+x^2-x C(x))$ and $C(x+x^{3})$ where $C(x)$ is the generating function for the Catalan numbers. Addendum: These results have previously been obtained in a wider context by Anders Claesson.

#### Riordan numbers are differences of trinomial coefficients

The Riordan numbers count Motzkin paths containing no flatsteps at ground level. We show that the*n*th Riordan number is the difference of the*n*th central trinomial coefficient and its predecessor by an adaptation of the "André reflection principle".

#### The Joyal approach to counting edge-labeled trees

A recent Monthly Note by Oleg Pikhurko gives an "algorithmic" proof that there are*n*^(*n*−3) edge-labeled trees on*n*vertices, reminiscent of Prüfer's proof of Cayley's famous*n*^(*n*-2) formula for the number of vertex-labeled trees on*n*vertices. Here we show that Joyal's "conceptual" proof of Cayley's formula readily extends to edge-labeled trees.

#### Cèsaro's integral formula for the Bell numbers (corrected)

Cèsaro (1885) gave a definite integral, all but forgotten today, for the number of partitions of an*n*-set. This note is an exposition, correcting a typographical error in the original.

#### The 136th manifestation of

We show bijectively that the Catalan number*C*_*n**C*_*n*counts Dyck (*n*+1)-paths in which the terminal descent is of even length and all other descents to ground level (if any) are of odd length.

#### Kreweras's Narayana number identity has a simple Dyck path interpretation

We show that Kreweras's identity counts Dyck paths with a given number of peaks by number of peak plateaus, where a peak plateau is a run of consecutive peaks that is immediately preceded by an upstep and followed by a downstep.

#### A one-line description of the Calkin-Wilf enumeration of the rationals

#### A note on downup permutations and increasing 0-1-2 trees

Downup permutations and increasing 0-1-2 trees are equinumerous: both have exponential generating function sec*x*+ tan*x*. Here we give an exposition of a bijection between them, due to Robert Donaghey, and its extension to all permutations, due to Kuznetsov et al. Our explicit description makes invertibility obvious.

#### Near-simultaneous plane crashes

Recently, two planes crashed in Russia 3 minutes apart. Terrorism was immediately suspected and later confirmed. What is the a priori probability of such an occurrence by chance?

#### An unexpected appearance of Dyck paths

American Mathematical Monthly Problem**10978**[2002, p. 921; 2004, p. 629] by Jean-Pierre Grivaux reads as follows:

The published solution by Tsehaye Andebrhan relies on Descartes' Rule of Signs. Here is a solution using Dyck paths.

#### Bijections for the identity

The title identity counts 2*n*-step lattice paths of upsteps and downsteps (a) by number 2*k*of steps before the path's last return to ground level, and (b) by number 2*k*of steps lying above ground level. We review combinatorial proofs of (a) and present a new one for (b).

#### A Putnam problem

Here is the solution the contestants liked.

#### Letter to the Editor

Regarding Pascal's matrix and a recursion for Bernoulli numbers.

#### Banach's matchbox problem

Banach's matchbox problem is solved using lattice paths.

#### Wong's Catalan number identity

An identity of B. C. Wong (in a*Monthly*problem solved by Emma Lehmer) is made obvious using lattice paths.

#### Lagrange inversion and Schroeder trees

We give a formula for the coefficients of the compositional inverse of a power series*F*(*x*) (when it has one) directly in terms of the coefficients of*F*.

#### Why are these equal?

Combinatorial interpretations of three different expressions for the Catalan number*C*_*n*are reviewed and compared.

#### Notes on Stirling cycle numbers

We give a direct combinatorial proof of the basic generating function identity for Stirling cycle numbers.

#### Unimodality of trinomial coefficients

We give a simple combinatorial proof with lattice paths.

#### The cyclotomic identity via Lyndon words

This note presents an elementary approach to a known combinatorial proof of the cyclotomic identity. It shows that the Unique Factorization Theorem for an arbitrary "word" as a weakly descending product of Lyndon words has the cyclotomic identity as an immediate consequence.

#### Notes on Motzkin and Schröder numbers

We give a combinatorial proof that the Motzkin number sequence is log convex. Also, we give a "walk around"-type bijection between the "bushes" and "paths" that are counted by Motzkin numbers and show how it applies to those counted by Schröder numbers.