cp's OEIS Frontend

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)

Table 1 of the Schöbel and Veselov paper with initial 1 added. Reverse of Table 2 of the Devadoss and Read paper.

Apparently A032132 contains the row sums.

From Petros Hadjicostas, Jan 28 2018: (Start)

In this triangle, which is read by rows, for 0 <= k <= n-1 and n>=1, let T(n,k) be the number of inequivalent canonical forms for separation coordinates of the hypersphere S^n with k independent continuous parameters. It is the mirror image of sequence A232206, that is, T(n, k) = A232206(n+1, n-k) for 0 <= k <= n-1 and n>=1. (Triangular array A232206(N, K) is defined for N >= 2 and 1 <= K <= N-1.)

If B(x,y) = Sum_{n,k>=0} T(n,k)*x^n*y^k (with T(0,0) = 1, T(0,k) = 0 for k>=1, and T(n,k) = 0 for 1 <= n <= k), then B(x,y) = 1 + (x/2)*(B(x,y)^2/(1-x*y*B(x,y)) + (1 + x*y*B(x,y))*B(x^2,y^2)/(1-x^2*y^2*B(x^2,y^2))). This can be derived from the bivariate g.f. of A232206. See the comments for that sequence.

Let S(n) := Sum_{k>=0} T(n,k). The g.f. of S(n) is B(x, y=1). If we let y=1 in the above functional equation, we get x*B(x,1) = x + (1/2)*((x*B(x,1))^2/(1-x*B(x,1)) + (1 + x*B(x,1))*x^2*B(x^2,1)/(1-x^2*B(x^2,1))). After some algebra, we get 2*x*B(x,1) = x + (1/2)(x*B(x,1)/(1-x*B(x,1)) + (x*B(x,1) + x^2*B(x^2,1))/(1-x^2*B(x,1))), i.e., 2*x*B(x,1) = x + BIK(x*B(x,1)), where we have the "BIK" (reversible, indistinct, unlabeled) transform of C. G. Bower. This proves that S(n) = A032132(n+1) for n>=0, which is Copeland's claim above.

Note that for the second column we have T(n,k=2) = A048739(n-2) for 2 <= n < = 10, but T(11,2) = 4062 <> 4059 = A048739(9). In any case, they have different g.f.s (see the formula section below).

(End)