

A232206


Triangle read by rows: T(n,k) is the number of nonequivalent regular polygons with n+1 edges, one of which is rooted, which are dissected by nonintersecting diagonals into k regions, such that two such polygons are identified up to reflection along the rooted edge and twisting along the diagonals that does not affect the root edge (for 1 <= k <= n1 and n>=2).


4



1, 1, 1, 1, 3, 2, 1, 5, 8, 3, 1, 8, 22, 20, 6, 1, 11, 46, 73, 49, 11, 1, 15, 87, 206, 233, 119, 23, 1, 19, 147, 485, 807, 689, 288, 46, 1, 24, 236, 1021, 2320, 2891, 1988, 696, 98, 1, 29, 356, 1960, 5795, 9800, 9737, 5561, 1681, 207, 1, 35, 520, 3525, 13088, 28586, 38216, 31350, 15322, 4062, 451, 1, 41, 730, 5989, 27224, 74280, 127465, 139901, 97552, 41558, 9821, 983
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,5


COMMENTS

From Petros Hadjicostas, Jan 20 2018: (Start)
According to Devadoss and Read (2001), the associahedron or Stasheff polytope K_n is a convex polytope of dim n2 with codimension k faces corresponding to using k nonintersecting diagonals on a regular (n+1)gon. If we redraw the picture of the dissected regular (n+1)gon so that "every region of the dissection becomes a regular polygon without diagonals", then the resulting object is called a cluster, "where each regular polygon of the cluster is called a cell".
Two regular polygons G_1 and G_2 are of the same "dimension if their corresponding faces [on K_n] are of the same dimension"; of the same "type if their corresponding faces [on K_n] are the same polytope"; and of the same "class if they are identified under the actions of D_n [= dihedral group of order 2*n] and twisting [along the diagonals]".
In order to count how many faces of K_n belong to a given class (as defined above), Devadoss and Read (2001) follow the methodology of Read (1974, 1978) and first transform the regular (n+1)gons (corresponding to the faces of K_n) into clusters, as mentioned above. Then they enumerate three kinds of clusters: those rooted at an outside edge (Aclusters); those rooted at a cell (Bclusters); and those rooted at an inside cell (Cclusters). In each one of these three kinds of clusters, two clusters are identified up to twisting along an edge (inside or outside depending on the case). Thus, the enumeration has to take twisting into account.
The g.f.s of these three kinds of clusters (A, B, and C) are derived, and these three g.f.s are used to derive the g.f. of the number of different classes of K_n of codimension k. See Section 3 in Devadoss and Read (2001).
The current triangular array, T(n,k), is the number of nonequivalent Aclusters (i.e., those rooted at an outside edge) having k cells and n outside edges, not counting the root edge, for 1 <= k <= n1 and n>=2. Two such Aclusters are equivalent up to twisting the rooted edge or an inside edge separating two cells (as long as the inside twisting does not affect the rooted edge).
Read (1974, 1978) calls the Aclusters "outrooted clusters". The difference between outrooted clusters (= Aclusters) in Devadoos and Read (2001) and those in Read (1978) is that, in the first paper, two Aclusters are considered equivalent if one can be obtained from the other by twisting the rooted edge or an inside edge (separating two cells), while in the second paper twisting is not allowed.
If twisting is not allowed, then the number of (nonequivalent) Aclusters having k cells and n outside edges, not counting the root edge, is given by sequence A033282(n+1, k1) = (1/k)*binomial(n2,k1)*binomial(n+k1,k1) for 1 <= k <= n1 and n>=2. This is also the number of faces of K_n of codimension k1. See Table 3 in Davadoos and Read (2001) and Table 1 in Read (1978). Unfortunately, in Table 1 in Read (1978), the label of each column is the number of outside edges including the rooted edge (i.e., n+1 rather than n).
Define T(n,k) = 0 for 0 <= n <= k, and T(n=1, k=0) = 1. Let also C(s,t) = Sum_{n>=0, k>=0} T(n,k)*s^n*t^k. (On p. 78 of their paper, Devadoss and Read (2001) use the notation a_{m,n} for T(n,m) and the notation A(x,y) for C(y,x), i.e., A(x,y) = Sum_{m>=0, n>=0} a_{m,n}*x^m*y^n in their paper.)
On p. 79, Eq. (3.2), of their paper, they prove that C(s,t) = s + (t/2)*(C(s,t)^2/(1C(s,t)) + (1 + C(s,t))*C(s^2, t^2)/(1C(s^2, t^2))). Unfortunately, the factor t in the previous formula is left out (i.e., it is a typo), and the same typo is reproduced in Schöbel and Veselov (2014, 2015).
We have C(s,t) = s+ t*s^2 + (t^2 + t)*s^3 + (2*t^3 + 3*t^2 + t)*s^4 + (3*t^4 + 8*t^3 + 5*t^2 + t)*s^5 + ...
Note that Sum_{0 <= k <= n1} T(n,k) = A032132(n) for n>=1; T(n, k=1) = 1 for n>=2; T(k+1,k) = A001190(k+1) for k>=1, which are the WedderburnEtherington numbers; and T(n, k=2) = A024206(n1) for n>=2.
According to Schöbel and Veselov (2014, 2015), for n>=2 and 0 <= p <= n1, T(n+1, np) = A295380(n,p) is the number of inequivalent canonical forms for separation coordinates of the hypersphere S^n with p independent continuous parameters.
(End)


REFERENCES

L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 5455 and 7475.


LINKS

Andrew Howroyd, Table of n, a(n) for n = 2..1276
S. L. Devadoss and R. C. Read, Cellular structures determined by polygons and trees, Ann. Combin., 5 (2001), 7198.
R. C. Read, On general dissections of a polygon, Preprint (1974)
C. R. Read, On general dissections of a polygon, Aequat. Math., 18 (1978), 370388.
K. Schöbel and A. Veselov, Separation coordinates, moduli spaces and Stasheff polytopes, arXiv:1307.6132 [math.DG], 2014.
K. Schöbel and A. Veselov, Separation coordinates, moduli spaces and Stasheff polytopes, Commun. Math. Phys., 337 (2015), 12551274.
Wikipedia, Associahedron.


FORMULA

From Petros Hadjicostas, Jan 20 2018: (Start)
G.f.: If C(s,t) = Sum_{n>=0, k>=0} T(n,k)*s^n*t^k (with T(n=1,k=0) = 1), then C(s,t) = s + (t/2)*(C(s,t)^2/(1C(s,t)) + (1 + C(s,t))*C(s^2, t^2)/(1C(s^2, t^2))).
Note that t*C(s,t) = Sum_{k>=1} T(k,k1)*(s*t)^k + Sum_{k>=2} (s*t)^k*Sum_{n >= k+1} T(n,k1)*s^{nk}. If we let w = s*t and D(s,w) = (w/s)*C(s,w/s), then the above functional equation implies that E(w): = lim_{s > 0} D(s,w) = Sum_{k>=1} T(k,k1)*w^k satisfies E(w) = w + (1/2)*(E(w)^2 + E(w^2)), which is the g.f. for the WedderburnEtherington numbers in sequence A001190. Thus, T(k,k1) = A001190(k) for k>=1.
Expansion w.r.t to t: C(s,t) = s + t*s^2/(1s) + t^2*s^3*(1+ss^2)/((1+s)*(1s)^3) + t^3*s^4*(2+2*s2*s^3+s^4)/((1+s)^2*(1s)^5) + t^4*s^5*(3+8*s+2*s^22*s^32*s^4+3*s^5s^6)/((1+s)^3*(1s)^7) + t^5*s^6*(6+19*s+30*s^2+15*s^3+23*s^44*s^5+2*s^64*s^7+6*s^84*s^9+s^10)/((1+s^2)*(1+s)^4*(1s)^9) + ... (It can be proven using a symbolic computation package by manipulating the above functional equation by Devadoss and Read.)
This means that, in the above expansion for C(s,t), the coefficient of t is the g.f. of the first column of the triangle below, the coefficient of t^2 is the g.f. of the second column of the triangle below, and so on.
(End)


EXAMPLE

From Petros Hadjicostas, Jan 20 2018: (Start)
According to Devadoss and Read (2015), triangle T(n,k) begins as follows:
(n=2) 1,
(n=3) 1, 1,
(n=4) 1, 3, 2,
(n=5) 1, 5, 8, 3,
(n=6) 1, 8, 22, 20, 6,
(n=7) 1, 11, 46, 73, 49, 11,
(n=8) 1, 15, 87, 206, 233, 119, 23,
(n=9) 1, 19, 147, 485, 807, 689, 288, 46,
(n=10) 1, 24, 236, 1021, 2320, 2891, 1988, 696, 98,
(n=11) 1, 29, 356, 1960, 5795, 9800, 9737, 5561, 1681, 207,
...
Geometrical example for n=5: If no twisting is allowed, the number of regular (n+1)gons (= hexagons) with a rooted edge and dissected into k regions by nonintersecting diagonals is given by A033282(n+1, k1) = A033282(6, k1): 1, 9, 21, and 14 for k = 1, 2, 3, 4, respectively.
Recall that, according to Devadoos and Read (2001), two regular (unrooted) polygons G_1 and G_2 are of the same "class" if they are identified under the actions of D_n (= dihedral group of order 2*n) and twisting along the diagonals. To avoid confusion, we call two such unrooted equivalent polygons as being of the same DTclass (D for "dihedral" and T for "twisting"). According to Table 5 (p. 92) in Devadoos and Read (2001), the numbers of DTclasses for regular hexagons dissected into k regions (by k1 nonintersecting diagonals) are 1, 2, 3, 2 for k = 1, 2, 3, 4, respectively. When an edge is rooted, each one of these DTclasses is subdivided into subclasses.
Call the regular hexagons ABCDEF with FA being the rooted edge (base).
For k=1, we have T(5,1) = 1 rooted regular hexagon with no intersecting diagonals.
For k=2, we have T(5,2) = 5 equivalent rooted regular hexagons with 1 diagonal. The equivalence classes are as follows according to the single dissecting diagonal:
Class 1a: AE, FB; Class 1b: AC, FD; Class 1c: BD, EC; (DTclass 1 has 6 hexagons)
Class 2a: AD, FC; Class 2b: BE; (DTclass 2 has 3 hexagons).
Note that 6 + 3 = 9 = A033282(5+1, 21).
For k=3, we have T(5,3) = 8 equivalent rooted regular hexagons with 2 nonintersecting diagonals. The equivalence classes are as follows according to the two diagonals:
Class 1a: (AC, AE), (FB, FD), (BD, BF), (EA, EC);
Class 1b: (DB, DF), (CE, CA); (DTclass 1 has 6 hexagons)
Class 2a: (DB, EA), (CE, BF);
Class 2b: (DF, CA); (DTclass 2 has 3 hexagons)
Class 3a: (DA, EA), (FC, FB), (EA, EB), (BE, BF);
Class 3b: (AC, AD), (FC, FD), (DA, DB), (CE, CF);
Class 3c: (BD, BE), (EC, EB);
Class 3d: (CF, CA), (DA, DF); (DTclass 3 has 12 hexagons)
Note that 6 + 3 + 12 = 21 = A033282(5+1, 31).
For k=4, we have T(5,4) = 3 equivalent rooted regular hexagons with 3 nonintersecting diagonals. The equivalence classes are as follows according to the three diagonals:
Class 1: (EA, AC, CE), (BD, DF, FB); (DTclass 1 has 2 hexagons)
Class 2a: (DF, DA, AC), (DF, FC, CA), (CE, CF, CA), (DF, DA, DB);
Class 2b: (CE, BE, BF), (BD, BE, BF), (EC, EB, EA), (DB, EB, EA), (EC, CF, FB), (DB, DA, AE), (FD, FC, FB), (AE, AD, AC); (DT class 2 has 12 hexagons)
Note that 2 + 12 = 14 = A033282(5+1, 41).
Recall that two rooted hexagons are equivalent iff they are a reflection of each other along the rooted edge or one can be obtained from the other by twisting a diagonal as long as the twisting does not affect the rooted edge.
The case k = 4 = n1 above is related to the triangulation of a convex polygon and the WedderburnEtherington commutative bracketing problem that appear in Comtet (1974, pp. 5455). Devadoos and Read (2001, p. 89) claim that T(n,k) is the number of possible ways of using k1 pairs of brackets on n commutative variables, but it is not clear how each one of the above hexagons (from k=1 to k=3) can be transformed into some kind of a generalized commutative bracketing problem.
(End)


MATHEMATICA

rows = 12; A[_, _] = 0;
Do[A[s_, t_] = Series[s+(t/2)(A[s, t]^2/(1A[s, t])+(1+A[s, t]) A[s^2, t^2] / (1A[s^2, t^2])), {s, 0, rows+1}, {t, 0, rows+1}] // Normal, {rows+1}];
Rest[CoefficientList[#, t]]& /@ Drop[CoefficientList[A[s, t], s], 2] // Flatten (* JeanFrançois Alcover, Sep 02 2018 *)


PROG

(Sage)
#This is a crude Sage program on how to derive the g.f. of any column in the triangle given that you have correctly derived the g.f.s of the previous columns. Suppose you have the expansion for C(s, t) w.r.t. t up to the power of 3 and you want to get the coefficient of t^4.
s, t=var('s, t')
C(s, t) = s + t*s^2/(1s) + t^2*s^3*(1+ss^2)/((1+s)*(1s)^3) + t^3*s^4*(2+2*s2*s^3+s^4)/((1+s)^2*(1s)^5)
B(s, t)=s+(t/2)*(C(s, t)^2/(1C(s, t))+(1+C(s, t))*C(s^2, t^2)/(1C(s^2, t^2)))C(s, t)
factor(taylor(B(s, t), t, 0, 4)/t^4)
# Petros Hadjicostas, Jan 21 2018
(PARI)
BIKxy(p)={(1/(1p) + (1+p)/subst(subst(1p, x, x^2), y, y^2))/2}
A(n)={my(p=x); for(i=2, n+1, p+=x^i*y*polcoeff(BIKxy(p + O(x*x^i)), i)); [Vecrev(q/y)  q<Vecrev((px)/x^2)]}
{ my(T=A(10)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Aug 31 2018


CROSSREFS

Cf. A001190 (main diagonal), A024206 (second column), A032132 (row sums), A295380 (mirror image).
Sequence in context: A073370 A208511 A129675 * A209559 A081277 A079628
Adjacent sequences: A232203 A232204 A232205 * A232207 A232208 A232209


KEYWORD

nonn,tabl


AUTHOR

N. J. A. Sloane, Nov 21 2013


EXTENSIONS

Name edited by Petros Hadjicostas, Jan 20 2018
Offset corrected by Andrew Howroyd, Aug 31 2018


STATUS

approved



