A Nameless Number

Triangle-free Polygon Dissections

Len Smiley, Univ. of Alaska Anchorage

We consider the following variant of the dissection questions of Catalan, Schroeder, [etc.]. In a convex (n+2)-gon with n+2 labeled nodes, what is a(n), the number of ways of drawing non-intersecting diagonals so that no triangles are formed? This question resonates somewhat with the parallel universe of "triangle-free graphs" where dwells an enormous literature, and so it is a 'natural' inquiry.

The generating function for a(n), A(x), satisfies the "rebus" equation

A = 1 + x2A3 + x3A4 + ....

derived by interpreting


                            /\ 
                          A/  \A
              _A_         /    \
            A|   |A      A\    /A
A = ___  +   |___|   +     \__/    + ....

The idea is that the baseline in each term is edge 1--2 of the (n+2)-gon and sitting above it (or not) is the diagonal-free k-gon of which it is the 'bottom'. We must let A's grow from each other side of this k-gon to assemble all the pictures we're counting. Now because

A = 1 + x2A3 (1 + xA + x2A2 + ....)

we may sum the geometric series and get

x2A3 + xA2 - (x+1)A + 1 =0

or, writing F = xA, its mnemonic cousin F3 + (F-1)(F-x) = 0 . The Italian problemists who perfected the 'cubic formula', although aware of Gutenberg technology, could not have forseen the limitations of HTML, and we will simply note that a formula for A in terms of x is possible. In what follows, we will show that

A(x)= a(0) + a(1)x + a(2)x2 +... = 1 + x2 + x3 + 4 x4 + 8 x5 + 25 x6 + 64 x7 + ...

We will emphasize the geometry of the problem in the second half of the page, but we should note that an easy application of the Lagrange Inversion Formula shows that


                                 __            __
                                 |              | n+1
                          1      |    1 - x     |
a(n) = coeff. of xn in -------   |  ----------- |
                         n+1     |   1 - x - x2 |
                                 |              |
                                 --            --

and that a formula for a(n) as a finite sum of signed products of binomial coefficients may be derived from this. The rational function within the square brackets generates the generalized Fibonacci sequence 1,0,1,1,2,3,5,8,..., and so a simpler formula in terms of this sequence (or the standard Fibonacci numbers) may also be concocted.

Since the power series A is algebraic (it satisfies the rebus equation), the coefficients a(n) must satisfy a fixed length linear recurrence relation with coefficients which are polynomial functions of n. Finding this recurrence is, by now, routine: one accesses a package such as Zeilberger's and enters the cubic equation, reading the recurrence relation as output. The Maple code, in this case, reads

algtodiff(x^2*A^3+x*A^2-x*A-A+1,A,x,3);

difftorec(",D,x,n,N);

The answer turns out to be a 4th-order recurrence with cubic coefficients:

20(n+5)(n+4)(n+3)an+4=(n+4)(n+3)(17n+97)an+3+4(n+3)(38n2+213n+304)an+2+40(2n+3)(n+2)(n+1)an+1-6(2n+1)(n+2)(n+1)an 

Geometric Recurrences

To calculate the numbers we want, it's slightly more convenient to shift the index by one: our 'new' sequence, a(n) = a(n+1). Thus a(1)=a(2)=1 because the quadrilateral has 1 acceptable diagonal placement (namely the placement of no diagonals). In the above generating function approach the 2-gon was crucial; now we ignore it!. Also, it is now lazier to consider the labelling as on a clock, with vertex n+3 at the top and vertex 1 to its clockwise direction.

We formulate a system of recurrences. The treatment could be compressed, but we want to create a variety of integer sequences.

a(n) = number of (non-crossing) diagonal placements in the (n+3)-gon with vertices 1, 2, ..., n+3 such that no triangles appear.

b(n) = number of above having a diagonal with endpoint vertex n+3.

c(n) = those with no diagonal at n+3 so

a(n)=b(n)+c(n)

p(n) = those with diagonals neither at n+3 nor 1.

q(n) = those with a diagonal at 1, but no diagonal at n+3 so

c(n)=p(n)+q(n)

r(n) = those with diagonals at both n+3 and 1 so

b(n)=q(n)+r(n)


To derive a recurrence for b(n), we consider the "earliest" or "rightmost" diagonal extending from vertex n+3. It may end at any vertex j with 2<j<n+1. To its right we count c(j-2) possibilities. To its left we have an (n-j+4)-gon with a(n-j+1) possible dissections. So


                n
               ____
               \
                \ 
        b(n) =  /   cj-2an-j+1 
               /
              /____
               j=3

The same procedure gives


                 n
               ____
               \
                \ 
        q(n) =  /   pj-2an-j+1 
               /
              /____
               j=3


Next we notice that

p(n)=c(n-1)+a(n-2)
for n>2. For any dissection counted by p(n) we may draw a false edge from vertex n+2 to 1 and see a dissection counted by c(n-1). But a diagonal from vertex n+2 to 2 is legal for the p(n) count, but illegal for the c(n-1) count. With this diagonal considered as a false edge, the extras are counted by a(n-2).

If a dedicated person now decides to eliminate b(n), p(n), q(n) from the previous identities, a coupled system emerges:



                         n-3
                        ____
                        \
                         \ 
 a(n) = c(n-1)+ 3a(n-2)+ /   (cn-i-1+ cn-i-2+ an-i-3)ai 
                        /
                       /____
                        i=1


                          n-3
                         ____
                         \
                          \ 
 c(n) = c(n-1)+ 2a(n-2)+  /   (cn-i-2+ an-i-3)ai 
                         /
                        /____
                         i=1

It is clear that this engine is sufficient to tabulate a(n). However, we are looking for new integer sequences, so we'll employ the following Mathematica code (written for clarity, not efficiency, by Brian Wick). (In this case the object model is much more readable than the procedural alternative offered by Maple.)



Clear[n,a,b,c,p,q,r]
{a[1],b[1],c[1],p[1],q[1],r[1]}={1,0,1,1,0,0};
{a[2],b[2],c[2],p[2],q[2],r[2]}={1,0,1,1,0,0};

b[n_]:= b[n] = Sum[c[i-2]a[n-i+1],{i,3,n}];

q[n_]:= q[n] = Sum[p[i-2]a[n-i+1],{i,3,n}];

p[n_]:= p[n] = c[n-1] + a[n-2];

a[n_]:= a[n] = b[n] + p[n] + q[n];

c[n_]:= c[n] = p[n] + q[n];

r[n_]:= r[n] = b[n] - q[n];

TableForm[Table[{n,a[n],b[n],c[n],p[n],q[n],r[n]},{n, 1, 20}],
  TableHeadings -> {{},{"n","a","b","c","p","q","r"}}]


n   a          b          c          p          q          r

1   1          0          1          1          0          0
2   1          0          1          1          0          0
3   4          1          3          2          1          0
4   8          2          6          4          2          0
5   25         8          17         10         7          1
6   64         21         43         25         18         3
7   191        68         123        68         55         13
8   540        197        343        187        156        41
9   1616       612        1004       534        470        142
10  4785       1847       2938       1544       1394       453
11  14512      5721       8791       4554       4237       1484
12  44084      17628      26456      13576      12880      4748
13  135545     54948      80597      40968      39629      15319
14  418609     171518     247091     124681     122410     49108
15  1302340    538833     763507     382636     380871     157962
16  4070124    1697790    2372334    1182116    1190218    507572
17  12785859   5372740    7413119    3674674    3738445    1634295
18  40325828   17054171   23271657   11483243   11788414   5265757
19  127689020  54313148   73376140   36057516   37318624   16994524
20  405689020  173450670  232238350  113701968  118536382  54914288

Our a(n) is entry A046736 in the On-Line Encyclopedia of Integer Sequences.

Of course many other dissection counts may be made in terms of a(n). For instance, dissection with exactly k triangles or exactly n-k triangles. The recursive scheme here may clearly be adapted to quadrilateral-free dissections, etc.

A review of the literature is not appropriate here. Online references include the Catalan exercise set of Stanley, some other papers of Stanley on dissections and Schroeder numbers, an E-print of Przyticki and Sikora on the dissection numbers of Euler, Fuss, Kirkman, and Cayley. More on Schroeder may be found in a paper of Foata and Zeilberger. Offline, the papers of Etherington and Erdelyi/Etherington (Edinburgh Math. Notes, #32, 1941, pp.1-6,7-12) are indispensible.


Leonard Smiley
Created: Wed Apr 7 14:41:05 AKDT 1999 Last modified: Wed Jun 16 10:26:38 AKDT 1999