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 nth Riordan number is the difference of the nth 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 C_n

  We show bijectively that the Catalan number 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 2n-step lattice paths of upsteps and downsteps (a) by number 2k of steps before the path's last return to ground level, and (b) by number 2k 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.