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 n-2 with co-dimension k faces corresponding to using k non-intersecting 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 (A-clusters); those rooted at a cell (B-clusters); and those rooted at an inside cell (C-clusters). 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 co-dimension k. See Section 3 in Devadoss and Read (2001).
The current triangular array, T(n,k), is the number of non-equivalent A-clusters (i.e., those rooted at an outside edge) having k cells and n outside edges, not counting the root edge, for 1 <= k <= n-1 and n>=2. Two such A-clusters 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 A-clusters "out-rooted clusters". The difference between out-rooted clusters (= A-clusters) in Devadoss and Read (2001) and those in Read (1978) is that, in the first paper, two A-clusters 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 (non-equivalent) A-clusters having k cells and n outside edges, not counting the root edge, is given by sequence A033282(n+1, k-1) = (1/k)*binomial(n-2,k-1)*binomial(n+k-1,k-1) for 1 <= k <= n-1 and n>=2. This is also the number of faces of K_n of co-dimension k-1. See Table 3 in Devadoss 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/(1-C(s,t)) + (1 + C(s,t))*C(s^2, t^2)/(1-C(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 <= n-1} 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 Wedderburn-Etherington numbers; and T(n, k=2) = A024206(n-1) for n>=2.
According to Schöbel and Veselov (2014, 2015), for n>=2 and 0 <= p <= n-1, T(n+1, n-p) = 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. 54-55 and 74-75.
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), 71-98.
Ronald C. Read, On general dissections of a polygon, Preprint (1974).
Ronald C. Read, On general dissections of a polygon, Aequat. Math., 18 (1978), 370-388.
K. Schöbel and A. Veselov, Separation coordinates, moduli spaces and Stasheff polytopes, arXiv:1307.6132 [math.DG], 2013-2014.
K. Schöbel and A. Veselov, Separation coordinates, moduli spaces and Stasheff polytopes, Commun. Math. Phys., 337 (2015), 1255-1274.
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/(1-C(s,t)) + (1 + C(s,t))*C(s^2, t^2)/(1-C(s^2, t^2))).
Note that t*C(s,t) = Sum_{k>=1} T(k,k-1)*(s*t)^k + Sum_{k>=2} (s*t)^k*Sum_{n >= k+1} T(n,k-1)*s^{n-k}. 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,k-1)*w^k satisfies E(w) = w + (1/2)*(E(w)^2 + E(w^2)), which is the g.f. for the Wedderburn-Etherington numbers in sequence A001190. Thus, T(k,k-1) = A001190(k) for k>=1.
Expansion w.r.t to t: C(s,t) = s + t*s^2/(1-s) + t^2*s^3*(1+s-s^2)/((1+s)*(1-s)^3) + t^3*s^4*(2+2*s-2*s^3+s^4)/((1+s)^2*(1-s)^5) + t^4*s^5*(3+8*s+2*s^2-2*s^3-2*s^4+3*s^5-s^6)/((1+s)^3*(1-s)^7) + t^5*s^6*(6+19*s+30*s^2+15*s^3+23*s^4-4*s^5+2*s^6-4*s^7+6*s^8-4*s^9+s^10)/((1+s^2)*(1+s)^4*(1-s)^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 non-intersecting diagonals is given by A033282(n+1, k-1) = A033282(6, k-1): 1, 9, 21, and 14 for k = 1, 2, 3, 4, respectively.
Recall that, according to Devadoss 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 DT-class (D for "dihedral" and T for "twisting"). According to Table 5 (p. 92) in Devadoss and Read (2001), the numbers of DT-classes for regular hexagons dissected into k regions (by k-1 non-intersecting diagonals) are 1, 2, 3, 2 for k = 1, 2, 3, 4, respectively. When an edge is rooted, each one of these DT-classes 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; (DT-class 1 has 6 hexagons)
Class 2a: AD, FC; Class 2b: BE; (DT-class 2 has 3 hexagons).
Note that 6 + 3 = 9 = A033282(5+1, 2-1).
For k=3, we have T(5,3) = 8 equivalent rooted regular hexagons with 2 non-intersecting 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); (DT-class 1 has 6 hexagons)
Class 2a: (DB, EA), (CE, BF);
Class 2b: (DF, CA); (DT-class 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); (DT-class 3 has 12 hexagons)
Note that 6 + 3 + 12 = 21 = A033282(5+1, 3-1).
For k=4, we have T(5,4) = 3 equivalent rooted regular hexagons with 3 non-intersecting diagonals. The equivalence classes are as follows according to the three diagonals:
Class 1: (EA, AC, CE), (BD, DF, FB); (DT-class 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, 4-1).
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 = n-1 above is related to the triangulation of a convex polygon and the Wedderburn-Etherington commutative bracketing problem that appear in Comtet (1974, pp. 54-55). Devadoss and Read (2001, p. 89) claim that T(n,k) is the number of possible ways of using k-1 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/(1-A[s, t])+(1+A[s, t]) A[s^2, t^2] / (1-A[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 (* Jean-François Alcover, Sep 02 2018 *)
PROG
(SageMath)
#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/(1-s) + t^2*s^3*(1+s-s^2)/((1+s)*(1-s)^3) + t^3*s^4*(2+2*s-2*s^3+s^4)/((1+s)^2*(1-s)^5)
B(s, t)=s+(t/2)*(C(s, t)^2/(1-C(s, t))+(1+C(s, t))*C(s^2, t^2)/(1-C(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/(1-p) + (1+p)/subst(subst(1-p, 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((p-x)/x^2)]}
{ my(T=A(10)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Aug 31 2018
CROSSREFS
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