| Displaying 1-8 of 8 results found.
page
1
1, 10, 66, 366, 1851, 8858, 40890, 184098, 813948, 3549758, 15317294, 65537334, 278489619, 1176688494, 4948173294, 20723897214, 86494746204, 359915608314, 1493718226314, 6184858989714, 25556291840484, 105406847513658
COMMENTS
Partial sums of number of diagonal dissections of a convex n-gon into n-4 regions. Partial sums of number of standard tableaux of shape (n-4,n-4,1,1). All values shown are nonprime.
FORMULA
a(n) = SUM[i=5..n] A002055(i) = SUM[i=5..n] binomial(i-3, 2)*binomial(2*i-6, i-5)/(i-4).
EXAMPLE
a(9) = 1 + 9 + 56 + 300 + 1485 = 1851 = 3 * 617.
Triangle read by rows: T(n, k) is the number of diagonal dissections of a convex n-gon into k+1 regions.
+10
36
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, 143208, 75582, 16796
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, 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 For relation to Lagrange inversion or series reversion and the geometry of associahedra or Stasheff polytopes (and other combinatorial objects) see A133437. - 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. - 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 The general results on the convolution of the refined partition polynomials of A133437, with u_1 = 1 and u_n = -t otherwise, can be applied here to obtain results of convolutions of these polynomials. - Tom Copeland, Sep 20 2016 The signed triangle t(n, k) =(-1)^k* T(n+2, k-1), n >= 1, k = 1..n, seems to be obtainable from the partition array A111785 (in Abramowitz-Stegun order) by adding the entries corresponding to the partitions of n with the number of parts k. E.g., triangle t, row n=4: -1, (6+3) = 9, -21, 14. - Wolfdieter Lang, Mar 17 2017 The preceding conjecture by Lang is true. It is implicit in Copeland's 2011 comments in A086810 on the relations among a gf and its compositional inverse for that entry and inversion through A133437 (a differently normalized version of A111785), whose integer partitions are the same as those for A134685. (An inversion pair in Copeland's 2008 formulas below can also be used to prove the conjecture.) In addition, it follows from the relation between the inversion formula of A111785/ A133437 and the enumeration of distinct faces of associahedra. See the MathOverflow link concernimg Loday and the Aguiar and Ardila reference in A133437 for proofs of the relations between the partition polynomials for inversion and enumeration of the distinct faces of the A_n associahedra, or Stasheff polytopes. - Tom Copeland, Dec 21 2017 The rows seem to give (up to sign) the coefficients in the expansion of the integer-valued polynomial (x+1)*(x+2)^2*(x+3)^2*...*(x+n)^2*(x+n+1)/(n!*(n+1)!) in the basis made of the binomial(x+i,i). - F. Chapoton, Oct 07 2022 Chapoton's observation above is correct: the precise expansion is (x+1)*(x+2)^2*(x+3)^2*...*(x+n)^2*(x+n+1)/ (n!*(n+1)!) = Sum_{k = 0..n-1} (-1)^k*T(n+2,n-k-1)*binomial(x+2*n-k,2*n-k), as can be verified using the WZ algorithm. For example, n = 4 gives (x+1)*(x+2)^2*(x+3)^2*(x+4)^2*(x+5)/(4!*5!) = 14*binomial(x+8,8) - 21*binomial(x+7,7) + 9*binomial(x+6,6) - binomial(x+5,5). - Peter Bala, Jun 24 2023
REFERENCES
S. Devadoss and J. O'Rourke, Discrete and Computational Geometry, Princeton Univ. Press, 2011 (See p. 241.)
Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994. Exercise 7.50, pages 379, 573.
T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Section 5.8.
LINKS
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.) G. Kreweras, Sur les hiérarchies de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973). (Annotated scanned copy) Vincent Pilaud and V. Pons, Permutrees, arXiv:1606.09643 [math.CO], 2016-2017.
FORMULA
G.f. G = G(t, z) satisfies (1+t)*G^2 - z*(1-z-2*t*z)*G + t*z^4 = 0.
T(n, k) = binomial(n-3, k)*binomial(n+k-1, k)/(k+1) for n >= 3, 0 <= k <= n-3.
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). - 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 With a different offset, the row polynomials equal 1/(1 + x)*Integral_{0..x} R(n,t) dt, where R(n,t) = Sum_{k = 0..n} binomial(n,k)*binomial(n+k,k)*t^k are the row polynomials of A063007. - Peter Bala, Jun 23 2016 n-th row polynomial = ( LegendreP(n-1,2*x + 1) - LegendreP(n-3,2*x + 1) )/((4*n - 6)*x*(x + 1)), n >= 3. - Peter Bala, Feb 22 2017 n*T(n+1, k) = (4n-6)*T(n, k-1) + (2n-3)*T(n, k) - (n-3)*T(n-1, k) for n >= 4. - Fang Lixing, May 07 2019
EXAMPLE
The triangle T(n, k) begins:
n\k 0 1 2 3 4 5 6 7 8 9
3: 1
4: 1 2
5: 1 5 5
6: 1 9 21 14
7: 1 14 56 84 42
8: 1 20 120 300 330 132
9: 1 27 225 825 1485 1287 429
10: 1 35 385 1925 5005 7007 5005 1430
11: 1 44 616 4004 14014 28028 32032 19448 4862
12: 1 54 936 7644 34398 91728 148512 143208 75582 16796
MAPLE
T:=(n, k)->binomial(n-3, k)*binomial(n+k-1, k)/(k+1): seq(seq(T(n, k), k=0..n-3), n=3..12); # Muniru A Asiru, Nov 24 2018
MATHEMATICA
t[n_, k_] = Binomial[n-3, k]*Binomial[n+k-1, k]/(k+1);
PROG
(PARI) Q=(1+z-(1-(4*w+2+O(w^20))*z+z^2+O(z^20))^(1/2))/(2*(1+w)*z); for(n=3, 12, for(m=1, n-2, print1(polcoef(polcoef(Q, n-2, z), m, w), ", "))) \\ Hugo Pfoertner, Nov 19 2018 (PARI) for(n=3, 12, for(k=0, n-3, print1(binomial(n-3, k)*binomial(n+k-1, k)/(k+1), ", "))) \\ G. C. Greubel, Nov 19 2018 (Magma) [[Binomial(n-3, k)*Binomial(n+k-1, k)/(k+1): k in [0..(n-3)]]: n in [3..12]]; // G. C. Greubel, Nov 19 2018 (Sage) [[ binomial(n-3, k)*binomial(n+k-1, k)/(k+1) for k in (0..(n-3))] for n in (3..12)] # G. C. Greubel, Nov 19 2018
CROSSREFS
Cf. 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. Cf. A019538 'faces' of the permutohedron. Cf. A063007 (f-vectors type B associahedra), A080721 (f-vectors type D associahedra), A126216 (mirror image). Cf. A248727 for a relation to f-polynomials of simplices. Cf. A111785 (contracted partition array, unsigned; see a comment above).
EXTENSIONS
Missing factor of 2 for expansions of f1 and f2 added by Tom Copeland, Apr 12 2009
Triangle obtained by adding a leading diagonal 1,0,0,0,... to A033282.
+10
26
1, 0, 1, 0, 1, 2, 0, 1, 5, 5, 0, 1, 9, 21, 14, 0, 1, 14, 56, 84, 42, 0, 1, 20, 120, 300, 330, 132, 0, 1, 27, 225, 825, 1485, 1287, 429, 0, 1, 35, 385, 1925, 5005, 7007, 5005, 1430, 0, 1, 44, 616, 4004, 14014, 28028, 32032, 19448, 4862, 0, 1, 54, 936, 7644, 34398, 91728
COMMENTS
With polynomials
P(0,t) = 0
P(1,t) = 1
P(2,t) = t
P(3,t) = t + 2 t^2
P(4,t) = t + 5 t^2 + 5 t^3
P(5,t) = t + 9 t^2 + 21 t^3 + 14 t^4
The o.g.f. A(x,t) = {1+x-sqrt[(1-x)^2-4xt]}/[2(1+t)] (see Drake et al.).
B(x,t)= x-t x^2/(1-x)= x-t(x^2+x^3+x^4+...) is the comp. inverse in x.
Let h(x,t) = 1/(dB/dx) = (1-x)^2/(1+(1+t)*x*(x-2)) = 1/(1-t(2x+3x^2+4x^3+...)), an o.g.f. in x for row polynomials in t of A181289. Then P(n,t) is given by (1/n!)(h(x,t)*d/dx)^n x, evaluated at x=0, A = exp(x*h(y,t)*d/dy) y, eval. at y=0, and dA/dx = h(A(x,t),t). These results are a special case of A133437 with u(x,t) = B(x,t), i.e., u_1=1 and (u_n)=-t for n > 1. See A001003 for t = 1. (End) Let U(x,t) = [A(x,t)-x]/t, then U(x,0) = -dB(x,t)/dt and U satisfies dU/dt = UdU/dx, the inviscid Burgers' equation (Wikipedia), also called the Hopf equation (see Buchstaber et al.). Also U(x,t) = U(A(x,t),0) = U(x+tU,0) since U(x,0) = [x-B(x,t)]/t. - Tom Copeland, Mar 12 2012 T(r, s) is the number of [0,r]-covering hierarchies with s segments (see Kreweras). - Michel Marcus, Nov 22 2014 T(n,k) is the number of small Schröder n-paths (lattice paths from (0,0) to (2n,0) using steps U=(1,1), F=(2,0), D=(1,-1) with no F step on the x-axis) that has exactly k U steps.
T(n,k) is the number of Schröder trees (plane rooted tree where each internal node has at least two children) with exactly n+1 leaves and k internal nodes. (End)
LINKS
G. Kreweras, Sur les hiérarchies de segments, Cahiers Bureau Universitaire Recherche Opérationnelle, Cahier 20, Inst. Statistiques, Univ. Paris, 1973, p. 21-22. G. Kreweras, Sur les hiérarchies de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973). (Annotated scanned copy)
FORMULA
Triangle T(n, k) read by rows; given by [0, 1, 0, 1, 0, 1, ...] DELTA [1, 1, 1, 1, 1, 1, 1, 1, 1, ...] where DELTA is Deléham's operator defined in A084938. For k>0, T(n, k) = binomial(n-1, k-1)*binomial(n+k, k)/(n+1); T(0, 0) = 1 and T(n, 0) = 0 if n > 0. [corrected by Marko Riedel, May 04 2023] Sum_{k=0..n} T(n,k)*x^k = A000007(n), A001003(n), A107841(n), A131763(n), A131765(n), A131846(n), A131926(n), A131869(n), A131927(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, respectively. - Philippe Deléham, Nov 05 2007 Umbrally, P(n,t) = Lah[n-1,-t*a.]/n! = (1/n)*Sum_{k=1..n-1} binomial(n-2,k-1)a_k t^k/k!, where (a.)^k = a_k = (n-1+k)!/(n-1)!, the rising factorial, and Lah(n,t) = n!*Laguerre(n,-1,t) are the Lah polynomials A008297 related to the Laguerre polynomials of order -1. - Tom Copeland, Oct 04 2014 T(n, k) = binomial(n, k)*binomial(n+k, k-1)/n, for k >= 0; T(0, 0) = 1 (see Kreweras, p. 21). - Michel Marcus, Nov 22 2014 P(n,t) = Lah[n-1,-:Dt:]/n! t^(n-1) with (:Dt:)^k = (d/dt)^k t^k = k! Laguerre(k,0,-:tD:) with (:tD:)^j = t^j D^j. The normalized Laguerre polynomials of 0 order are given in A021009. - Tom Copeland, Aug 22 2016
EXAMPLE
Triangle starts:
1;
0, 1;
0, 1, 2;
0, 1, 5, 5;
0, 1, 9, 21, 14;
...
MATHEMATICA
Table[Boole[n == 2] + If[# == -1, 0, Binomial[n - 3, #] Binomial[n + # - 1, #]/(# + 1)] &[k - 1], {n, 2, 12}, {k, 0, n - 2}] // Flatten (* after Jean-François Alcover at A033282, or *) Table[If[n == 0, 1, Binomial[n, k] Binomial[n + k, k - 1]/n], {n, 0, 10}, {k, 0, n}] // Flatten (* Michael De Vlieger, Aug 22 2016 *)
PROG
(PARI) t(n, k) = if (n==0, 1, binomial(n, k)*binomial(n+k, k-1)/n);
tabl(nn) = {for (n=0, nn, for (k=0, n, print1(t(n, k), ", "); ); print(); ); } \\ Michel Marcus, Nov 22 2014
CROSSREFS
Diagonals: A000007, A000012, A000096, A033275, A033276, A033277, A033278, A033279, A000108, A002054, A002055, A002056, A007160, A033280, A033281. Row sums: A001003 (Schroeder numbers).
Triangle read by rows: T(n,k) is the number of Schroeder paths of semilength n containing exactly k peaks but no peaks at level one (n >= 1; 0 <= k <= n-1).
+10
18
1, 2, 1, 5, 5, 1, 14, 21, 9, 1, 42, 84, 56, 14, 1, 132, 330, 300, 120, 20, 1, 429, 1287, 1485, 825, 225, 27, 1, 1430, 5005, 7007, 5005, 1925, 385, 35, 1, 4862, 19448, 32032, 28028, 14014, 4004, 616, 44, 1, 16796, 75582, 143208, 148512, 91728, 34398, 7644, 936, 54, 1
COMMENTS
A Schroeder path of semilength n is a lattice path in the first quadrant, from the origin to the point (2n,0) and consisting of steps U=(1,1), D=(1,-1) and H=(2,0).
Also number of Schroeder paths of semilength n containing exactly k doublerises but no (2,0) steps at level 0 (n >= 1; 0 <= k <= n-1). Also number of doublerise-bicolored Dyck paths (doublerises come in two colors; also called marked Dyck paths) of semilength n and having k doublerises of a given color (n >= 1; 0 <= k <= n-1). Also number of 12312- and 121323-avoiding matchings on [2n] with exactly k crossings.
Essentially the triangle given by [1,1,1,1,1,1,1,1,...] DELTA [0,1,0,1,0,1,0,1,0,1,...] where DELTA is the operator defined in A084938. - Philippe Deléham, Oct 20 2007 For relation to Lagrange inversion, or series reversion and the geometry of associahedra, or Stasheff polytopes (and other combinatorial objects), see A133437. - Tom Copeland, Sep 29 2008
FORMULA
T(n,k) = C(n,k)*C(2*n-k,n+1)/n (0 <= k <= n-1).
G.f.: G(t,z) = (1-2*z-t*z-sqrt(1-4*z-2*t*z+t^2*z^2))/(2*(1+t)*z).
Equals N * P, where N = the Narayana triangle ( A001263) and P = Pascal's triangle, as infinite lower triangular matrices. A126182 = P * N. - Gary W. Adamson, Nov 30 2007 G.f.: 1/(1-x-(x+xy)/(1-xy/(1-(x+xy)/(1-xy/(1-(x+xy)/(1-xy/(1-.... (continued fraction). - 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 A126216 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, Oct 09 2011 With polynomials
P(0,t) = 0
P(1,t) = 1
P(2,t) = 1
P(3,t) = 2 + t
P(4,t) = 5 + 5 t + t^2
P(5,t) = 14 + 21 t + 9 t^2 + t^3
The o.g.f. A(x,t) = (1+x*t-sqrt((1-x*t)^2-4x))/(2(1+t)), and
B(x,t) = x - x^2/(1-t*x) = x - x^2 - ((t*x)^3 + (t*x)^4 + ...)/t^2 is the compositional inverse in x. [series corrected by Tom Copeland, Dec 10 2019] Let h(x,t) = 1/(dB/dx) = (1-tx)^2/(1-(t+1)(2x-tx^2)) = 1/(1 - 2x - 3tx^2 + 4t^2x^3 + ...). Then P(n,t) = (1/n!)(h(x,t)*d/dx)^n x, evaluated at x=0, A = exp(x*h(u,t)*d/du) u, evaluated at u=0, and dA/dx = h(A(x,t),t). (End)
The polynomials in my 2011 formula entry above evaluate to an aerated, alternating sign sequence of the Catalan numbers A000108 with t = -2. The first few are P(2,-2) = 1, P(3,-2) = 0, P(4,t) = -1, P(5,-2) = 0, P(6,-2) = 2, P(7,-2) = 0, P(8,-2) = -5, P(9,-2) = 0, P(10,-2) = 14. Generalizing the relations between w = theta and u = phi in Mizera on pp. 32-34, modify the inverse pair above to w = i * B(-i*u,t) = u + i * u^2/(1+i*t*u), where i is the imaginary number, and u = i*A(-i*w,t) = i*(1 - i*w*t - sqrt((1 + i*w*t)^2 + i*4*w))/(2(1+t)). Then the expression for V'(w) in Mizera generalizes to V'(w) = -i*(w - u) and reduces to V'(w) = (1 - sqrt(1-4 w^2))/2 when evaluated at t = -2, which is an o.g.f. for A126120. Cf. also A086810. (End) Sum_{k = 0..n-1} (-1)^k*T(n,k)*binomial(x + 2*n - k, 2*n - k) = ( (x + 1) * ( Product_{k = 2..n} (x + k)^2 ) * (x + n + 1) )/(n!*(n + 1)!) for n >= 1. Cf. A243660 and A243661. - Peter Bala, Oct 08 2022
EXAMPLE
T(3,1)=5 because we have HUUDD, UUDDH, UUUDDD, UHUDD and UUDHD.
Triangle starts:
n\k 0 1 2 3 4 5 6 7 8
1 1;
2 2, 1;
3 5, 5; 1;
4 14, 21, 9, 1;
5 42, 84, 56, 14, 1;
6 132, 330, 300, 120, 20, 1;
7 429, 1287, 1485, 825, 225, 27, 1;
8 1430, 5005, 7007, 5005, 1925, 385, 35, 1;
9 4862, 19448, 32032, 28028, 14014, 4004, 616, 44, 1;
10 ...
Triangle [1,1,1,1,1,1,1,...] DELTA [0,1,0,1,0,1,0,1,...] begins:
1;
1, 0;
2, 1, 0;
5, 5, 1, 0;
14, 21, 9, 1, 0;
42, 84, 56, 14, 1, 0;
...
MAPLE
T:=(n, k)->binomial(n, k)*binomial(2*n-k, n+1)/n: for n from 1 to 11 do seq(T(n, k), k=0..n-1) od; # yields sequence in triangular form
MATHEMATICA
Table[Binomial[n, k] Binomial[2 n - k, n + 1]/n, {n, 10}, {k, 0, n - 1}] // Flatten (* Michael De Vlieger, Jan 09 2016 *)
PROG
(PARI) tabl(nn) = {mP = matrix(nn, nn, n, k, binomial(n-1, k-1)); mN = matrix(nn, nn, n, k, binomial(n-1, k-1) * binomial(n, k-1) / k); mprod = mN*mP; for (n=1, nn, for (k=1, n, print1(mprod[n, k], ", "); ); print(); ); } \\ Michel Marcus, Apr 16 2015 (PARI)
t(n, k) = binomial(n, k)*binomial(2*n-k, n+1)/n;
Number T(n,k) of length 2n words such that all letters of the k-ary alphabet occur at least once and are introduced in ascending order and which can be built by repeatedly inserting doublets into the initially empty word; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
+10
14
1, 0, 1, 0, 1, 2, 0, 1, 9, 5, 0, 1, 34, 56, 14, 0, 1, 125, 465, 300, 42, 0, 1, 461, 3509, 4400, 1485, 132, 0, 1, 1715, 25571, 55692, 34034, 7007, 429, 0, 1, 6434, 184232, 657370, 647920, 231868, 32032, 1430, 0, 1, 24309, 1325609, 7488228, 11187462, 6191808, 1447992, 143208, 4862
COMMENTS
In general, column k>2 is asymptotic to (4*(k-1))^n / ((k-2)^2 * (k-2)! * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jun 01 2015
FORMULA
T(n,k) = Sum_{i=0..k} (-1)^i * A183135(n,k-i) / (i!*(k-i)!). T(n,k) = A256116(n,k) / (k-1)! for k > 0.
EXAMPLE
T(0,0) = 1: (the empty word).
T(1,1) = 1: aa.
T(2,1) = 1: aaaa.
T(2,2) = 2: aabb, abba.
T(3,1) = 1: aaaaaa.
T(3,2) = 9: aaaabb, aaabba, aabaab, aabbaa, aabbbb, abaaba, abbaaa, abbabb, abbbba.
T(3,3) = 5: aabbcc, aabccb, abbacc, abbcca, abccba.
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 2;
0, 1, 9, 5;
0, 1, 34, 56, 14;
0, 1, 125, 465, 300, 42;
0, 1, 461, 3509, 4400, 1485, 132;
0, 1, 1715, 25571, 55692, 34034, 7007, 429;
0, 1, 6434, 184232, 657370, 647920, 231868, 32032, 1430;
...
MAPLE
A:= proc(n, k) option remember; `if`(n=0, 1, k/n*
add(binomial(2*n, j)*(n-j)*(k-1)^j, j=0..n-1))
end:
T:= (n, k)-> add((-1)^i*A(n, k-i)/(i!*(k-i)!), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..10);
MATHEMATICA
A[n_, k_] := A[n, k] = If[n == 0, 1, k/n*Sum[Binomial[2*n, j]*(n - j)*If[j == 0, 1, (k - 1)^j], {j, 0, n - 1}]];
T[n_, k_] := Sum[(-1)^i*A[n, k - i]/(i!*(k - i)!), {i, 0, k}];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz, updated Jan 01 2021 *)
CROSSREFS
Columns k=0-10 give: A000007, A057427, A010763(n-1) (for n>1), A258490, A258491, A258492, A258493, A258494, A258495, A258496, A258497.
Triangle T(n,k), 0 <= k <= n, read by rows, given by [1,1,1,1,1,1,1,...] DELTA [0,1,0,1,0,1,0,1,0,...] where DELTA is the operator defined in A084938.
+10
7
1, 1, 0, 2, 1, 0, 5, 5, 1, 0, 14, 21, 9, 1, 0, 42, 84, 56, 14, 1, 0, 132, 330, 300, 120, 20, 1, 0, 429, 1287, 1485, 825, 225, 27, 1, 0, 1430, 5005, 7007, 5005, 1925, 385, 35, 1, 0, 4862, 19448, 32032, 28028, 14014, 4004, 616, 44, 1, 0, 16796, 75582, 143208, 148512, 91728, 34398, 7644, 936, 54, 1, 0
FORMULA
Sum_{k=0..n} T(n,k)*x^k = A000108(n), A001003(n), A007564(n), A059231(n), A078009(n), A078018(n), A081178(n), A082147(n), A082181(n), A082148(n), A082173(n) for x = 0,1,2,3,4,5,6,7,8,9,10 respectively. Sum_{k=0..n} T(n,k)*x^(n-k) = A000007(n), A001003(n), A107841(n), A131763(n), A131765(n), A131846(n), A131926(n), A131869(n), A131927(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8 respectively. - Philippe Deléham, Nov 05 2007 T(n,k) = binomial(n-1,k)*binomial(2n-k,n)/(n+1), k <= n. - Philippe Deléham, Nov 02 2009
EXAMPLE
Triangle begins:
1;
1, 0;
2, 1, 0;
5, 5, 1, 0;
14, 21, 9, 1, 0;
42, 84, 56, 14, 1, 0;
132, 330, 300, 120, 20, 1, 0;
429, 1287, 1485, 825, 225, 27, 1, 0;
MATHEMATICA
Table[Binomial[n-1, k]*Binomial[2*n-k, n]/(n+1), {n, 0, 10}, {k, 0, n}] // Flatten (* G. C. Greubel, feb 05 2018 *)
PROG
(PARI) for(n=0, 10, for(k=0, n, print1(binomial(n-1, k)*binomial(2*n-k, n)/(n+1), ", "))) \\ G. C. Greubel, Feb 05 2018 (Magma) [[Binomial(n-1, k)*Binomial(2*n-k, n)/(n+1): k in [0..n]]: n in [0..10]]; // G. C. Greubel, Feb 05 2018
Triangle T(n,k) read by rows: coefficients of polynomials P_n(t) defined in Formula section.
+10
7
1, 1, 1, 2, 4, 1, 5, 15, 9, 1, 14, 56, 56, 16, 1, 42, 210, 300, 150, 25, 1, 132, 792, 1485, 1100, 330, 36, 1, 429, 3003, 7007, 7007, 3185, 637, 49, 1, 1430, 11440, 32032, 40768, 25480, 7840, 1120, 64, 1, 4862, 43758, 143208, 222768, 179928, 77112, 17136, 1836, 81, 1, 16796, 167960, 629850, 1162800, 1162800, 651168, 203490, 34200, 2850, 100, 1
COMMENTS
T(n,k) is the number of Feynman's diagrams with k fermionic loops in the order n of the perturbative expansion in dimension zero for the GW approximation of the self-energy function in a many-body theory of fermions with two-body interaction (see Molinari link).
FORMULA
y(x;t) = Sum_{n>=0} P_n(t)*x^n satisfies y*(1-x*y)^2 = 1 + (t-1)*x*y, where P_n(t) = Sum_{k=0..n} T(n,k)*t^k.
EXAMPLE
A(x;t) = 1 + (1 + t)*x + (2 + 4*t + t^2)*x^2 + (5 + 15*t + 9*t^2 + t^3)*x^3 + ...
Triangle starts:
n\k [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
[0] 1;
[1] 1, 1;
[2] 2, 4, 1;
[3] 5, 15, 9, 1;
[4] 14, 56, 56, 16, 1;
[5] 42, 210, 300, 150, 25, 1;
[6] 132, 792, 1485, 1100, 330, 36, 1;
[7] 429, 3003, 7007, 7007, 3185, 637, 49, 1;
[8] 1430, 11440, 32032, 40768, 25480, 7840, 1120, 64, 1;
[9] 4862, 43758, 143208, 222768, 179928, 77112, 17136, 1836, 81, 1;
[10] ...
MATHEMATICA
Flatten@Table[Binomial[2 n, n + m] Binomial[n + 1, m] / (n + 1), {n, 0, 10}, {m, 0, n}] (* Vincenzo Librandi, Sep 23 2018 *)
PROG
(PARI)
A286784_ser(N, t='t) = my(x='x+O('x^N)); serreverse(Ser(x*(1-x)^2/(1+(t-1)*x)))/x;
concat(apply(p->Vecrev(p), Vec( A286784_ser(12)))) \\ test: y= A286784_ser(50); y*(1-x*y)^2 == 1 + ('t-1)*x*y (Maxima)
T(n, m):=(binomial(2*n, n+m)*binomial(n+1, m))/(n+1); /* Vladimir Kruchinin, Sep 23 2018 */ (Magma) /* As triangle */ [[(Binomial(2*n, n+m)*Binomial(n+1, m))/(n+1): m in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Sep 23 2018
Number of nonintersecting (or self-avoiding) rook paths of length 2n+2 joining opposite corners of an n X n grid.
+10
2
4, 36, 224, 1200, 5940, 28028, 128128, 572832, 2519400, 10943240, 47070144, 200880160, 851809140, 3592795500, 15085939200, 63102895680, 263083395960, 1093683448440, 4535210472000, 18764563053600, 77485731403080, 319402222692696, 1314511549519104
FORMULA
a(n) = 2*(n-1)*binomial(2*n-2, n-3).
G.f.: 2*(s-1+x*(7-5*s+2*x*(2*s-6+x)))/(s^3x^2), where s=sqrt(1-4*x).
E.g.f: 2*E^(2*x)*x*(BesselI(1,2*x)+2*BesselI(2,2*x)+BesselI(3,2*x)).
(End)
MATHEMATICA
a[n_] := 2 Sum[Sum[
Binomial[j + k, k]*Binomial[2 n - k - j - 1, n - k + 1], {k,
n}], {j, 0, n - 2}]
CoefficientList[Series[(2(-1+Sqrt[1-4x]+x(7-5Sqrt[1-4x] +2x(-6+2Sqrt[ 1-4x] +x))))/ ((1-4x)^(3/2)x^2), {x, 0, 20}], x] (* Benedict W. J. Irwin, Jul 13 2016 *)
Search completed in 0.016 seconds
|