Combinatorial Poppies

Year: 2016 Authors: Karl Kattchee; Craig S. Kaplan

Core claim

Asymmetrical poppies on n by n square grids can be counted by a derived formula, and the resulting structures have notable visual and artistic appeal.

Topics

grid paths, enumerative combinatorics, mathematical aesthetics

Domains

combinatorics, permutation patterns, lattice paths, mathematical art, information visualization, digital print

Methods

path classification, permutation encoding, symmetry counting

Media

square grids, digital print, colored winding-number diagrams

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges Finland Conference Proceedings

Combinatorial Poppies

Karl Kattchee Dept. of Mathematics and Statistics University of Wisconsin-La Crosse kkattchee@uwlax.edu

Craig S. Kaplan Cheriton School of Computer Science University of Waterloo csk@uwaterloo.ca

Abstract

In this paper, we consider orthogonal closed paths that dwell on the edges of square grids. A certain subset of these paths are called “poppies.” We derive a formula for the number of asymmetrical poppies on an $n$ by $n$ grid, and we explore the aesthetics of the poppies.

Introduction

Once a class of mathematical objects is defined, it is of interest to count up how many such objects exist. Combinatorics is the field of mathematics dedicated to this task. Creativity is often necessary in crafting counting arguments. Moreover, it is usually helpful to have a clear visual interpretation of combinatorial objects. In addition to serving as a powerful aid to mathematical intuition, these visuals open the door to artistic interpretation and creative variations.

The authors share a fascination with geometric doodles that follow different kinds of rules and constraints. In some cases, these doodles can be abstracted into combinatorial spaces. Thinking mathematically, we might then articulate counting arguments for the sizes of these spaces. Thinking computationally, we might be more interested in developing algorithms that can enumerate and draw all the individual doodles. And thinking artistically, we would naturally consider the aesthetics of the individual doodles and their visual impact when presented collectively.

In particular, Kattchee’s 2015 paper “Theory of Intersection” [2] shows an example of what Kaplan had previously called a “Grid-based decorative corner” [1]. Immediately adjacent to that example was a doodle that Kattchee described as a “closed path that swirled around a common center”. It turns out that Kaplan, too, had been doodling such swirling closed paths for many years, and this realization set us on a quest to characterize these paths, to study their combinatorial properties, and to turn them into artworks. This paper defines a class of geometric doodles we call “poppies,” and discusses their properties.

No Left Turn

Let $n=2k$, where $k$ is a positive integer, and consider the grid formed by the superposition of $n$ horizontal and $n$ vertical lines. We are interested in closed paths made up of edges of this grid. In particular, we seek paths that obey the following rules:

1. As one walks a complete circuit along the path, every turn is a 90-degree turn to the right. (Equivalently, we might ask that every turn be a left turn.)
2. The path has exactly one horizontal segment on every horizontal line in the grid, and exactly one vertical segment on every vertical line in the grid.

Kattchee and Kaplan

Figure 1: The two possible NLT paths on a $4\times 4$ grid. Each path is accompanied by symbolic notation that encodes its shape. The diagram on the left also includes a column of copies of the notation with pairs of numbers highlighted; each pair shows the coordinates of one vertex in the path.

Figure 2: Two of the set of NLT paths on a $6\times 6$ grid. The path on the right is also shown coloured by winding number in the style of a poppy.

We refer to a path satisfying these two conditions as a “no-left-turn path,” or an “NLT path.” On an $n\times n$ grid, an NLT path will be made from $n$ horizontal and $n$ vertical line segments, visiting every row and column of the grid exactly once. Figure 1 shows the only two NLT paths on a $4\times 4$ grid, up to symmetry. Each path is accompanied by a convenient notation that will be explained below. Figure 2 shows two examples of NLT paths on a $6\times 6$ grid. Note that no NLT paths can exist on an $n\times n$ grid when $n$ is odd. Consider just the horizontal segments of an NLT path: in order to form a closed loop, we would have to travel to the right for half of those segments and to the left for the other half, which implies that there must be an even number of horizontal lines in the grid (and likewise for the vertical lines).

The notation for an NLT path consists of two rows of integers, each one a permutation of the numbers $0,\dots ,n-1$ . We can reconstruct the complete path by walking along these permutations from left to right. We begin with the ordered pair encoded by the first column of the array. Then we replace its first coordinate with the top entry in the second column and write down the result. The coordinates of the third ordered pair come from the second column, and we continue in that manner. We “wrap around” when we reach the

Combinatorial Poppies

(340215) 032514

(0123) 0123 Figure 3: The array in the diagram on the left describes a legal NLT path (though not a poppy); the permutations on the right are not cyclic and alternating, and so the resulting path is not NLT.

right-hand side. The result is a list which represents the turning points on the NLT path.

Next to the left-hand diagram in Figure 1 is a column of copies of the array, showing the extraction of the coordinates of the path’s vertices. We are writing the vertices in column/row notation. The array accompanying the second path in Figure 1 encodes the sequence

Since the path is closed, there is no true starting point. But, by starting at the turning point in the top row and on the left, the bottom left entry of the array turns out to be zero, and in this case we call the array canonical. Note that any noncanonical array can be replaced with a canonical array by simultaneously translating the two permutations so that the bottom one begins with a zero (the underlying path is not affected).

It is natural to wonder how to create an array, canonical or otherwise, so that the corresponding path has the NLT property. To this end, let $(a_0{a}_1{a}_2\dots a_{n-1})$ be a permutation of the integers $0,1,2,\dots ,n-1$ (in “one-line notation” or “word notation”). The permutation is called alternating if no $a_i$ is between $a_{i-1}$ and $a_{i+1}$ , for all $i=1,\dots ,n-2$ . This means the permutation alternately increases and decreases. We will further call the permutation “cyclic alternating” if this condition holds at $a_0$ (i.e. $a_0$ is not between $a_{n-1}$ and $a_1$ ) and at $a_{n-1}$ (i.e. $a_{n-1}$ is not between $a_{n-2}$ and $a_0$ ). Now, take any array

where $(a_0{a}_1{a}_2\dots a_{n-1})$ and $(b_0{b}_1{b}_2\dots b_{n-1})$ are cyclic alternating permutations that are aligned with each other, in the sense that a_0 < a_1 if and only if b_0 < b_1 . Then $\alpha$ corresponds to an NLT path. (If the permutations are cyclic and alternating but not aligned, then the resulting path will be a legal “no-right-turn” path.) Notice that the first array in Figure 3 is a stack of two cyclic alternating permutations, properly aligned, but the second one is not. Consequently, the first path is an NLT path, and the second one is not.

In what follows, we will be particularly interested in NLT paths that circulate clockwise around the centerpoint of the grid, as in Figures 1 and 2. The arrays which correspond to closed paths of this type have the additional property that their entries alternate between values above and below $\frac{n-1}{2}$ . These closed paths are referred to as poppies, because in the event the regions defined by the path are colored according to winding number, in shades of red ranging from primary red to black (as on the right in Figure 2), the result resembles a poppy. Note that neither path in Figure 3 is a poppy.

Kattchee and Kaplan

(142503) 031425

(031524) 031524

(240315) 031524 Figure 4: Examples of symmetric poppies. From left to right, the diagrams have diagonal symmetry, two-fold rotational symmetry, and four-fold rotational symmetry.

Symmetric Poppies

Poppies can be either symmetric or asymmetric. Note that two-fold and four-fold rotational symmetry can occur, and symmetry across the main- and off-diagonals can occur, but symmetry across the horizontal or vertical axes does not happen (with the exception of the trivial path on the $2\times 2$ grid). For example, if a horizontal path segment were to be reflected across the horizontal bisector of the grid, it would then be necessary to join the endpoints of those two segments with vertical lines, forming an illegal rectangle. Figures 1 and 4 provide examples of the possible symmetries.

It is pretty easy to tell whether a poppy is symmetric by looking at it, but if we know how the underlying array is affected after flipping the poppy across the main diagonal, for example, then we can tell whether the poppy possesses that sort of symmetry without actually seeing the poppy. The following table provides that information, which will be helpful when counting up symmetric poppies. For convenience, $\overline{x}:=n-1-x$ .

Figure 5 illustrates these ideas by means of an asymmetrical poppy on a $6\times 6$ grid.

Now, if $a_0$ in the canonical array of the poppy $\alpha$ in the table happens to be zero, then we can describe general forms that correspond to poppies with the various symmetries:

For a poppy to have symmetry about its main diagonal, it must have the form

Combinatorial Poppies

Figure 5: The effect of geometric transformations on the arrays used to encode poppies. The poppy on the left is shown reflected across the main diagonal, then reflected across the off-diagonal, and finally rotated 180 degrees. In each case we see the effect on the notation.

If we identify where the entry $n-1$ occurs in the bottom row, say $b_i=n-1$ , then the necessary form for symmetry about the off-diagonal is

For the 180-degree rotational symmetry, it is necessary that $n-1$ occur in the $k$ th entry of the bottom row, and the array must have the form

Evidently, poppies with 180-degree rotational symmetry occur only when $k$ is odd, a fact we will use below.

Asymmetrical Poppies

Let $n=2k$ , where $k$ is a positive integer, and suppose that the meaning of a “poppy” on an $n\times n$ grid and the corresponding array notation are as above. There is obvious mathematical interest in counting and classifying all poppies on a $n\times n$ grid. We derive the following formula.

Formula 1. Let $n=2k$ , where $k$ is an integer greater than 1. Then, on an $n\times n$ grid, the number of asymmetrical poppies, up to rotation and reflection, is given by

To begin our derivation, note that, since every poppy lives on a square grid, we can apply all symmetries of the square (dihedral group $D_8$ ) to a given poppy and get a collection of eight poppies, each having a corresponding canonical array. The original poppy is asymmetric if and only if no two poppies among these eight (or among their canonical arrays) are precisely the same.

If a canonical array is to represent a poppy, then there are $(k-1)!k!$ ways to write its bottom row

and $(k!{)}^2$ ways to write its top row. So, there are $(k-1)!(k!{)}^3$ canonical arrays. For example, there are 8 canonical arrays when $n=4$, and 432 of them for $n=6$. It follows that if there were nothing but asymmetrical poppies, then there would be $\frac{1}{8}(k-1)!(k!{)}^3$ distinct asymmetrical poppies on the $n\times n$ grid (after ignoring the distinctions between poppies that differ by a flip or rotation). This would imply that there is one asymmetric poppy on the $4\times 4$ grid and 54 of them on the $6\times 6$ grid. Of course these are overestimates, since there do in fact exist symmetric poppies (see Figures 1 and 4). Consequently, there must in fact be no asymmetric poppies at all on the $4\times 4$ grid. This agrees with the fact that $f(4)=0$ and can also be verified by inspection.

We also have $f(6)=45$, which agrees with the fact that 54 is an overestimate of the number of asymmetric poppies on the $6\times 6$ grid. Kattchee’s 2015 artwork “45 Poppies” comprises an enumeration of all asymmetric $6\times 6$ poppies (see Figure 6). Kaplan verified this enumeration via brute-force computation.

The next step towards confirming Formula 1 above is to notice that every canonical array can arise from an array of the form

[ \left(\begin{array}[]{cccc}0&a_{1}&a_{2}&\ldots&a_{n-1}\ 0&b_{1}&b_{2}&\ldots&b_{n-1}\end{array}\right) ]

by translating the top row, if necessary, by an even number of steps (to preserve the aforementioned alignment condition), with wraparound, of course. The poppies in Figure 1 provide the simplest example of this. Notice that the poppies are not the same, but they do possess the same reflectional symmetry. See also Figure 2, where both poppies are asymmetrical, and the latter two poppies in Figure 4, which both possess rotational symmetry. These observations motivate the following.

Proposition 1.

A given array

[ \alpha=\left(\begin{array}[]{cccc}0&a_{1}&a_{2}&\ldots&a_{n-1}\ 0&b_{1}&b_{2}&\ldots&b_{n-1}\end{array}\right) ]

represents a symmetric poppy if and only if any array acquired by translating the top row of $\alpha$ by an even number of steps also represents a symmetric poppy.

Because of Proposition 1, if we can find the number of canonical arrays of the form

[ \left(\begin{array}[]{cccc}0&a_{1}&a_{2}&\ldots&a_{n-1}\ 0&b_{1}&b_{2}&\ldots&b_{n-1}\end{array}\right) ]

which represent symmetric poppies, then we can count up all arrays corresponding to symmetric poppies by multiplying by $k$, since that is the number of distinct ways to translate the top row, as described.

Proposition 2.

Suppose $k$ is even. Then, for each cyclic alternating permutation of the form $(0b_1{b}_2\dots b_{n-1})$, there are precisely TWO permutations of the form $(0a_1{a}_2\dots a_{n-1})$ such that the canonical array

[ \alpha=\left(\begin{array}[]{cccc}0&a_{1}&a_{2}&\ldots&a_{n-1}\ 0&b_{1}&b_{2}&\ldots&b_{n-1}\end{array}\right) ]

represents a symmetric poppy.

To see why this is true, recall that rotational symmetry cannot happen when $k$ is even. Thus, the only possible symmetries are across the main diagonal or across the off diagonal, and each of these happen, according to Eqs. (1) and (2). Their canonical arrays are

[ \left(\begin{array}[]{cccc}0&b_{n-1}&b_{n-2}&\ldots&b_{1}\ 0&b_{1}&b_{2}&\ldots&b_{n-1}\end{array}\right)\ \text{and}\ \left(\begin{array}[]{cccc}0&\overline{b_{i-1}}&\ldots&\overline{b_{1}}&n-1&\overline{b_{n-1}}&\ldots&\overline{b_{i+1}}\ 0&b_{1}&\ldots&b_{i-1}&n-1&b_{i+1}&\ldots&b_{n-1}\end{array}\right), ]

where $\overline{x}:=n-1-x$, as before.

Proposition 3.

Suppose $k$ is odd. Then the statement of Proposition 2 holds, unless $(0b_1{b}_2\dots b_{n-1})$ is of the form $\left(0b_1\dots b_{k-1}n-1\overline{b_1}\dots \overline{b_{k-1}}\right),$ and in this case there are $(k-1)!$ permutations of the form $(0a_1{a}_2\dots a_{n-1})$ such that

[ \alpha=\left(\begin{array}[]{cccccc}0&a_{1}&a_{2}&\ldots&a_{n-1}\ 0&b_{1}&b_{2}&\ldots&b_{n-1}\end{array}\right) ]

represents a symmetric poppy.

Recall that a poppy on an $n\times n$ grid can have rotational symmetry only if $k$ is odd and, even then, it only happens when the underlying canonical array is of the form

[ \alpha=\left(\begin{array}[]{cccccccc}0&a_{1}&\ldots&a_{k-1}&n-1&\overline{a_{1}}&\ldots&\overline{a_{i-1}}\ 0&b_{1}&\ldots&b_{k-1}&n-1&\overline{b_{1}}&\ldots&\overline{b_{i-1}}\end{array}\right) ]

(or one of the variations with top row translated by an even number of steps). See Eq. (3) above.

Now, if $(0b_1{b}_2\dots b_{n-1})$ has any form other than $(0b_1\dots b_{k-1}n-1\overline{b_1}\dots \overline{b_{k-1}})$ then Proposition 2 applies. But if it is a cyclic alternating permutation that does have that form (there are $(k-1)!$ of them), then we can choose any of the $(k-1)!$ permutations of the form $(0a_1\dots a_{k-1}n-1\overline{a_1}\dots \overline{a_{k-1}})$ to represent a poppy with the canonical array $\alpha$ above. The other types of symmetry can happen too, in this case, but only in the presence of rotational symmetry. This establishes Proposition 3.

To finish the derivation, suppose $k$ is even. Then, the number of canonical arrays corresponding to asymmetric poppies is

$(k!{)}^3(k-1)!-(k-1)!k!\cdot 2\cdot k.$ (4)

Recall that $(k!{)}^3(k-1)!$ is the total number of canonical arrays. The subtracted quantity is the product of the number of permutations of the form $(0b_1{b}_2\dots b_{n-1})$, the number of permutations of the form $(0a_1{a}_2\dots a_{n-1})$ that give rise to an array corresponding to a symmetric poppy (Proposition 2), and the number of ways to translate the top row of such an array (Proposition 1).

On the other hand, if $k$ is odd, then the number of canonical arrays corresponding to asymmetric poppies is

$(k!{)}^3(k-1)!-[(k-1)!k!-(k-1)!]\cdot 2\cdot k-(k-1)!\cdot (k-1)!\cdot k.$ (5)

The two subtracted terms are necessary, because Proposition 3 distinguishes between poppies with reflection symmetry and rotational symmetry, respectively.

By simplifying Eqs. (4) and (5), and dividing by 8, we get the expressions in Formula 1.

Applications and Extensions

In 2015 Kattchee created the artwork shown in Figure 6, showing all asymmetric $6\times 6$ poppies. The poppies are coloured by winding number, with colours chosen on a ramp from red (winding number 1) to black (maximum winding number, in this case 3). Part of the appeal of such a piece lies in the aesthetic of exhaustive enumeration: the ability to take in, at a glance, the subtle variations in a family of objects that are obviously related to one another. Within this narrow context, the variations give each individual a unique character that can be studied in isolation. The viewer might also attempt to puzzle out the rules that define the family as a whole. This visual style is explored by many artists familiar to the mathematical art world, for example Conan Chadbourne, Margaret Kepner, and James Mai. We speculate that similar aesthetic considerations explain the visual appeal of Tufte’s Small Multiples in information visualization *[3]

Kattchee and Kaplan

Figure 6: 45 Poppies by Karl Kattchee; $18\mathrm{cm}\times 31\mathrm{cm}$ ; Digital print, 2015. The two images on the right are zoomed-in views of two of the poppies.

Moving up, we can compute $f(8)=10224$ . While that many poppies might be difficult to depict on a single canvas, Kaplan and Kattchee gathered them, together with the 288 symmetric $8\times 8$ poppies, into a 219 page document, entitled “10512 Poppies.” There are over five million $10\times 10$ poppies, offering a difficult challenge should one wish to depict them all.

Symbolically, the poppy is most obviously associated with war remembrance, a tradition that goes back to McCrae’s 1915 poem “In Flanders Fields.” In 2014, the art installation “Blood Swept Lands and Seas of Red” commemorated the outbreak of World War I by filling the moat of the Tower of London with hundreds of thousands of ceramic poppies. Because of their narcotic properties, poppies are also frequently associated with sleep and death, with the notable example of a field of soporific poppies in Baum’s The Wizard of Oz.

Acknowledgments

The authors thank the referees for their careful read and many helpful comments.

References

[1] Craig S. Kaplan. Grid-based decorative corners. In George W. Hart and Reza Sarhangi, editors, Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture, pages 317-324, Phoenix, Arizona, 2013. Tessellations Publishing. Available online at http://archive.bridgesmathart.org/2013/bridges2013-317.. [2] Karl Kattchee. Theory of intersection. In Douglas McKenna Kelly Delp, Craig S. Kaplan and Reza Sarhangi, editors, Proceedings of Bridges 2015: Mathematics, Music, Art, Architecture, Culture, pages 487-490, Phoenix, Arizona, 2015. Tessellations Publishing. Available online at http://archive. bridgesmathart.org/2015/bridges2015-487.. [3] Edward Tufte. The Visual Display of Quantitative Information. Graphics Press, 1983.