Catalan Numbers and Baskets

How many undip words are there?

The famous Catalan numbers turn up in many places ( see "Exercises on Catalan and Related Numbers" and "Catalan Addendum" by Richard P. Stanley.) One of the classic examples is counting the number of ways 2n people seated around a table can simultaneously form n handshakes without crossings. The answer to this problem is the nth Catalan number. For example, the Catalan numbers for n = {0, 1, 2, 3, 4, 5} are {1, 1, 2, 5, 14, 42}.

Another set counted by the Catalan numbers are the number of words in the Dyck language that contain n pairs of parentheses. The Dyck language comprises all strings of open and close parentheses that follow the usual rules of arithmetic expressions. For example:

()

(()) ()()

((())) ()(())) (())() (()()) ()()()

etc.

The undip language is a shuffle of two Dyck languages: a {u,d} language and an {n,p} language. We can think of {u,d} as {(,)} and {n,p} as {[,]}, but unlike a Dyck language on two types of parentheses, in a shuffle of two Dyck languages the two types of parentheses ignore each other grammatically speaking. For example, a word such as:

( [ ) ]

is permitted.

R. Cori, S. Dulucq, and G. Viennot explain how the Catalan numbers are related to the planar hamiltonian cubic maps (the structures described by undip codes) in "Shuffle of Parenthesis Systems and Baxter Permutations," Journal of Combinatorial Theory, Series A 43, 1-22 (1986):

"...hamiltonian cubic maps are planar maps with a hamiltonian circuit in which all vertices have degree three. In such a map any vertex is incident with only one edge not in the hamiltonian polygon, this edge may be inside the polygon or outside. Thus to build a 'Hamiltonian rooted cubic map' one has to choose 2k vertices among the 2n (those incident with inside edges) then draw a planar map inside the polygon (it is easy to see that this can be done in Ck ways*) and a planar map outside."

*This is easy to see because it is essentially the handshaking problem.

A map is rooted by distinguishing a vertex and direction. In a hamiltonian circuit this is combinatorially equivalent to labeling all the vertices, since, given a direction and a place to start, we can reliably label the vertices with sequential integers. Working with a rooted map, every rotation of a pattern counts as a distinct pattern because the root occupies a different place in each rotation. Counting rooted maps exhaustively counts all of the possible undip codes even when they trivially encode the same shape by virtue of merely starting at a different location on the hamiltonian cycle.

Cori, Dulucq, and Viennot go on to show that the number of rooted hamiltonian planar cubic maps are counted by the product of two sequential Catalan numbers. For a hamiltonian circuit with 2n vertices the number of maps is the product of the nth Catalan number and the (n+1)th Catalan number.

Tthe number of undip words of length 2n for n= {1, 2, 3, 4, 5} are {2, 10, 70, 588, 5544}. This is sequence A005568 in the On-Line Encyclopedia of Integer Sequences (OEIS).

For better or worse, there are a great many more undip words than there are shapes to be described by them. Synonyms will abound.