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
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.