|
| |
|
|
A033282
|
|
Triangle read by rows: T(n,k) is the number of diagonal dissections of a convex n-gon into k+1 regions.
|
|
18
|
|
|
|
1, 1, 2, 1, 5, 5, 1, 9, 21, 14, 1, 14, 56, 84, 42, 1, 20, 120, 300, 330, 132, 1, 27, 225, 825, 1485, 1287, 429, 1, 35, 385, 1925, 5005, 7007, 5005, 1430, 1, 44, 616, 4004, 14014, 28028, 32032, 19448, 4862, 1, 54, 936, 7644, 34398, 91728, 148512
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
3,3
|
|
|
COMMENTS
|
T(n+3,k) is also the number of compatible k-sets of cluster variables in Fomin and Zelevinsky's cluster algebra of finite type A_n. Take a row of this triangle regarded as a polynomial in x and rewrite as a polynomial in y := x+1. The coefficients of the polynomial in y give a row of the triangle of Narayana numbers A001263. For example x^2+5*x+5=y^2+3*y+1. - Paul Boddington (psb(AT)maths.warwick.ac.uk), Mar 07 2003
Number of standard Young tableaux of shape (k+1,k+1,1^(n-k-3)), where 1^(n-k-3) denotes a sequence of n-k-3 1's (see the Stanley reference).
Number of k dimensional 'faces' of the n dimensional associahedron (see Simion, p. 168). - Mitch Harris, Jan 16 2007
Mirror image of triangle A126216 . - Philippe DELEHAM, Oct 19 2007
For relation to Lagrange inversion or series reversion and the geometry of associahedra or Stasheff polytopes (and other combinatorial objects) see A133437. [From Tom Copeland, Sep 29 2008]
Row generating polynomials 1/(n+1)*Jacobi_P(n,1,1,2*x+1). Row n of this triangle is the f-vector of the simplicial complex dual to an associahedron of type A_n [Fomin & Reading, p.60]. See A001263 for the corresponding array of h-vectors for associahedra of type A_n. See A063007 and A080721 for the f-vectors for associahedra of type B and type D respectively. [From Peter Bala, Oct 28 2008]
f-vectors of secondary polytopes for Grobner bases for optimization and integer programming (see De Loera et al. and Thomas). - Tom Copeland, Oct 11 2011
From Devadoss and O'Rourke's book: The Fulton-MacPherson compactification of the configuration space of n free particles on a line segment with a fixed particle at each end is the n-Dim Stasheff associahedron whose refined f-vector is given in A133437 which reduces to A033282. - Tom Copeland, Nov 29 2011
Diagonals of A132081 are rows of A033282. - Tom Copeland, May 08 2012
|
|
|
REFERENCES
|
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4. [From Tom Copeland, Nov 03 2008]
D. Beckwith, Legendre polynomials and polygon dissections?, Amer. Math. Monthly, 105 (1998), 256-257.
A. Cayley, On the partitions of a polygon, Proc. London Math. Soc., 22 (1891), 237-262 = Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 93ff. (See p. 239.)
S. Devadoss and J. O'Rourke, Discrete and Computational Geometry, Princeton Univ. Press, 2011 (See pg. 241)
B. Drake, I. M. Gessel and G. Xin, Three proofs and a generalization of the Goulden-Litsyn-Shevelev conjecture ..., J. Integer Sequences, Vol. 10 (2007), #07.3.7.
P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 1999, 203-229.
S. Fomin and A. Zelevinsky, Cluster algebras I: Foundations, J. Amer. Math. Soc. 15 (2002) no.2, 497-529.
S. Fomin and A. Zelevinsky, Y-Systems and generalized associahedra, Ann. of Math. (2) 158 (2003), no. 3, 977-1018.
Kreweras, G. Sur les partitions non croisees d'un cycle. (French) Discrete Math. 1 (1972), no. 4, 333--350. MR0309747 (46 #8852)
R. C. Read, On general dissections of a polygon, Aequat. Math. 18 (1978), 370-388.
R. Simion, "Convex Polytopes and Enumeration", Adv. in Appl. Math. 18 (1997) pp. 149-180.
R. P. Stanley, Polygon dissections and standard Young tableaux, J. Comb. Theory, Ser. A, 76, 175-177, 1996.
|
|
|
LINKS
|
Vincenzo Librandi, Table of n, a(n) for n = 3..2000
F. Chapoton, Enumerative properties of generalized associahedra
J. De Loera, J. Rambau, and F. Leal, Triangulations of Point Sets [From Tom Copeland Oct 11 2011]
S. Devadoss, Combinatorial Equivalence of Real Moduli Spaces [From Tom Copeland Nov 29 2011]
P. Flajolet and M. Noy, Analytic Combinatorics of Non-crossing Configurations, Discrete Math., 204, 1999, 203-229.
S. Fomin and N. Reading, Root systems and generalized associahedra, Lecture notes for IAS/Park-City 2004. [From Peter Bala, Oct 28 2008]
S. Fomin and A. Zelevinsky, Cluster algebras I: Foundations, J. Amer. Math. Soc. 15 (2002), no. 2, 497-529.
S. Fomin and A. Zelevinsky, Y-systems and generalized associahedra, Ann. of Math. (2) 158 (2003), no. 3, 977-1018.
R. C. Read, On general dissections of a polygon, Aequat. Math. 18 (1978), 370-388.
R. P. Stanley, Polygon dissections and standard Young tableaux, J. Comb. Theory, Ser. A, 76, 175-177, 1996.
R. Thomas, Lectures in Geometric Combinatorics [From Tom Copeland Oct 11 2011]
|
|
|
FORMULA
|
G.f. G=G(t, z) satisfies (1+t)G^2-z(1-z-2tz)G+tz^4=0.
T(n, k)=binomial(n-3, k)*binomial(n+k-1, k)/(k+1) for n >= 3, 0 <=k <=n-3.
Contribution from Tom Copeland, Nov 03 2008: (Start)
Two g.f.s (f1 and f2) for A033282 and their inverses (x1 and x2) can be derived from the Drake and Barry references.
1. a: f1(x,t) = y = {1 - (2t+1) x - sqrt[1 - (2t+1) 2x + x^2]}/[2x (t+1)]
= t x + (t + 2 t^2) x^2 + (t + 5 t^2 + 5 t^3) x^3 + ...
b: x1 = y/[t + (2t+1)y + (t+1)y^2] = y {1/[t/(t+1) + y] - 1/(1+y)}
= (y/t) - (1+2t)(y/t)^2 + (1+ 3t + 3t^2)(y/t)^3 +...
2. a: f2(x,t) = y = {1 - x - sqrt[(1-x)^2 - 4xt]}/[2(t+1)]
= (t/(t+1)) x + t x^2 + (t + 2 t^2) x^3 + (t + 5 t^2 + 5 t^3) x^4 + ...
b: x2 = y(t+1) [1- y(t+1)]/[t + y(t+1)]
= (t+1) (y/t) - (t+1)^3 (y/t)^2 + (t+1)^4 (y/t)^3 + ...
c: y/x2(y,t) = [t/(t+1) + y] / [1- y(t+1)]
= t/(t+1) + (1+t) y + (1+t)^2 y^2 + (1+t)^3 y^3 + ...
x2(y,t) can be used along with the Lagrange inversion for an o.g.f. (A133437)
to generate A033282 and show that A133437 is a refinement of A033282,
i.e., a refinement of the f-polynomials of the associahedra, the Stasheff polytopes.
y/x2(y,t) can be used along with the indirect Lagrange inversion (A134264)
to generate A033282 and show that A134264 is a refinement of A001263, i.e.,
a refinement of the h-polynomials of the associahedra.
f1[x,t](t+1) gives a generator for A088617.
f1[xt,1/t](t+1) gives a generator for A060693, with inverse y/[1 + t + (2+t) y + y^2].
f1[x(t-1),1/(t-1)]t gives a generator for A001263, with inverse y/[t + (1+t) y + y^2].
The unsigned coefficients of x1(y t,t) are A074909, reverse rows of A135278. (End)
G.f.: 1/(1-x*y-(x+x*y)/(1-x*y/(1-(x+x*y)/(1-x*y/(1-(x+x*y)/(1-x*y/(1-.... (continued fraction). [From Paul Barry, Feb 06 2009]
Let h(t) = (1-t)^2/(1+(u-1)*(1-t)^2) = 1/(u+2*t+3*t^2+4*t^3+...), then a signed (n-1)-th row polynomial of A033282 is given by u^(2n-1)*(1/n!)*((h(t)*d/dt)^n) t, evaluated at t=0, with initial n=2. The power series expansion of h(t) is related to A181289 (cf. A086810). - Tom Copeland, Sep 06 2011
|
|
|
EXAMPLE
|
Triangle begins:
1;
1,2;
1,5,5;
1,9,21,14;
1,14,56,84,42;
|
|
|
MATHEMATICA
|
t[n_, k_] = Binomial[n-3, k]*Binomial[n+k-1, k]/(k+1);
Flatten[Table[t[n, k], {n, 3, 12}, {k, 0, n-3}]][[1 ;; 52]] (* From Jean-François Alcover, Jun 16 2011 *)
|
|
|
CROSSREFS
|
Diagonals : A000012, A000096, A033275, A033276, A033277, A033278, A033279; A000108, A002054, A002055, A002056, A007160, A033280, A033281 Row sums : A001003 (Schroeder numbers, first term omitted) . See A086810 for another version.
A007160 is a diagonal. Cf. A001263.
With leading zero: A086810.
Cf. A019538 'faces' of the permutohedron.
Cf. A063007 (f-vectors type B associahedra), A080721 (f-vectors type D associahedra), A126216 (mirror image). [From Peter Bala, Oct 28 2008]
Sequence in context: A021468 A209830 A209695 * A126350 A204111 A079502
Adjacent sequences: A033279 A033280 A033281 * A033283 A033284 A033285
|
|
|
KEYWORD
|
nonn,tabl,easy
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
Added a missing factor of 2 for expansions of f1 and f2 Tom Copeland, Apr 12 2009
|
|
|
STATUS
|
approved
|
| |
|
|
