login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A033282 Triangle read by rows: T(n,k) is the number of diagonal dissections of a convex n-gon into k+1 regions. 19
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 Deléham, 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]

P. Barry, On the Inverses of a Family of Pascal-Like Matrices Defined by Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.5.6.

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

J. Cigler, Some remarks on lattice paths in strips along the x-axis; http://homepage.univie.ac.at/johann.cigler/preprints/lattice-paths.pdf, 2014.

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.

J.-C. Novelli, J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962, 2014

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]] (* 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified November 27 09:21 EST 2014. Contains 250176 sequences.