Staircase tilings and kk-Catalan structures

Many interesting combinatorial objects are enumerated by the kk-Catalan numbers, one possible generalization of the Catalan numbers. We will present a new combinatorial object that is enumerated by the kk-Catalan numbers, staircase tilings. We give a bijection between staircase tilings and kk-good paths, and between kk-good paths and kk-ary trees. In addition, we enumerate kk-ary paths according to DD, UDU, and UU, and connect these statistics for kk-ary paths to statistics for the staircase tilings. Using the given bijections, we enumerate statistics on the staircase tilings, and obtain connections with Catalan numbers for special values of kk. The second part of the paper lists a sampling of other combinatorial structures that are enumerated by the kk-Catalan numbers. Many of the proofs generalize from those for the Catalan structures that are being generalized, but we provide one proof that is not a straightforward generalization. We propose a web site repository for these structures, similar to those maintained by Richard Stanley for the Catalan numbers [R.P. Stanley, Catalan addendum. Available at: http://www-math.mit.edu/~rstan/ec/] and by Robert Sulanke for the Delannoy numbers [R. Sulanke, Objects counted by the central Delannoy numbers, J. Integer Seq. 6 (1) (2003), Article 03, 1, 5, 19 pp. Available also at: math.boisestate.edu/~sulanke/infowhowasdelannoy.html]. On the website, we list additional combinatorial objects, together with hints on how to show that they are indeed enumerated by the kk-Catalan numbers.