Twongs Thronged at NY Maker Faire!

Visitors thronging the Twongs Table at the New York Maker Faire, September 25-26, 2010.

That's me in orange. Some tried making the carbon chemistry models (annulenes) displayed in steel, but most went freeform.

All ages advanced to level 101: having fun.

The steel models wore their undip codes attached.

Tetrahedrane in foreground, acetylene in back.

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.

O-Knitting

Making an o-knitting vertex, Step 1: Hold Needle upright.

Toss Quoit on Needle.

Feed Thread through Needle.

Pull Quoit through Thread.

Voila! a completed vertex.

Close-up of completed o-knitting vertex.

All sorts of things that I'll call o's are available to the craftsperson: rubber bands, ponytail holders, potholder loops, etc. O's can also be made at home by slicing across a can or plastic bottle, or anything else of tubular cross-section. O's can be knit together to form 3D shapes without the increases and decreases traditionally depended upon in knitting and crochet. O-knitting can optionally be guided by a string of letters drawn from a four-letter alphabet, what I call an undip word, that describes the step-by-step construction of a surface. Using undip words, o-knitting becomes a sort of genetic knitting.

There are only two big things to learn about o-knitting: how to make a vertex, and how to follow an undip code. Learn those two things and you will be a able to build a spaceship on a desert island, or at least a floppy grass model of one.

An o-knitting vertex is an inter-looped union of three o's. An o-knitting vertex is a reciprocal structure. That is, each of the o's plays the same role in the union. We'll give each o a name according to how it first enters the union, but by the time we are done making the vertex they'll all be equivalent. An o-knitting vertex is a three-way version of Mrs. Bright's (four-way) True Lovers' Knot (Ashley Book of Knots #2425.)

OK, let's make an o-knitting vertex. The first o is called Needle. Except at the very first vertex (call it the origin,) Needle will already be attached to the work. Hold Needle with its free end upward.

The second o is called Quoit. Quoit is always free at both ends. Toss Quoit over Needle.

The third o is called Thread. Feed Thread through Needle. It is best to always feed Thread from the right side (or always from the left side, if you prefer.) Feeding from the same side makes vertices that are all of the same handedness, giving the fabric a more even look. Thread will be free at both ends when making u and n vertices, but already in the work when making p and d vertices.

Now feed Quoit through Thread (i.e., through the end of Thread that pushed out through Needle.)

Voila! One vertex made. 3D shapes are made by repeating the above moves.

3-D shapes may be specified by an undip word or genotype, a character string made up of the four emoticons: u, n, d, and p.

For example, a genotype for the cube is

nuupdd .

The the letters are called emoticons because they are meant to be read with the head tilting sideways (toward the right) and their meanings are visually obvious—no need to wake up the left side of the brain at all. The four o-knitting actions they encode are:

"Open left," meaning: "make a new vertex and leave the o on the left side dangling," (i.e., continue to the right. )

"Open right," meaning: "make a new vertex and leave the o on the right side dangling," (i.e., continue to the left.)

"Close left," meaning: "make a new vertex employing the nearest dangling o on the left side."

"Close right," meaning: "make a new vertex employing the nearest dangling o on the right side."

(Figure out for yourself which emoticon encodes which action.)

Note that at a close vertex the roles of Needle and Thread can be assigned so that Thread enters Needle consistently from the right (or, alternatively, consistently from the left.) A switch causes no confusion about how to continue, since just a single o is left dangling after a close vertex.

You have to work consistently from the outside of the piece (or consistently from the inside.) Early on this will mean taking care that o's do not get twisted. At the end, should you find you have made the enantiomorph of what you intended—no problem. Just evert the piece through one of its openings.

Quoit must always be free at both ends, but at the final vertex all three o's will already be attached to the work. The final vertex must be joined by some other technique. The simplest way is to add a fourth o as Quoit, making the last vertex a regular fourway Mrs. Bright's knot. The extra o is left dangling, permanently marking the origin (and terminus) of the undip word.

Hansel & Gretel's Hint: mark your very first o with a twist tie or special color—should you get lost, you can can retrace the word from the beginning.