A006470 -id:A006470 - cp's OEIS frontend

A342987 Triangle read by rows: T(n,k) is the number of tree-rooted planar maps with n edges, k faces and no isthmuses, n >= 0, k = 1..n+1.

1, 0, 1, 0, 2, 2, 0, 3, 15, 5, 0, 4, 60, 84, 14, 0, 5, 175, 650, 420, 42, 0, 6, 420, 3324, 5352, 1980, 132, 0, 7, 882, 13020, 42469, 37681, 9009, 429, 0, 8, 1680, 42240, 246540, 429120, 239752, 40040, 1430, 0, 9, 2970, 118998, 1142622, 3462354, 3711027, 1421226, 175032, 4862

Offset: 0

Andrew Howroyd, Apr 03 2021

The number of vertices is n + 2 - k.

For k >= 2, column k is a polynomial of degree 4*(k-2)+1.

			Triangle begins:
  1;
  0, 1;
  0, 2,    2;
  0, 3,   15,     5;
  0, 4,   60,    84,     14;
  0, 5,  175,   650,    420,     42;
  0, 6,  420,  3324,   5352,   1980,    132;
  0, 7,  882, 13020,  42469,  37681,   9009,   429;
  0, 8, 1680, 42240, 246540, 429120, 239752, 40040, 1430;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. III: Nonseparable maps, J. Combinatorial Theory Ser. B 18 (1975), 222-259, Table VIIIb.

Columns k=1..4 are A000007, A000027, A006470, A006471.
Diagonals are A000108, A002740, A006432, A006433.
Row sums are A342988.
Cf. A342981, A342982, A342984, A342985.

\\ here G(n,y) is A342984 as g.f.
F(n,y)={sum(n=0, n, x^n*sum(i=0, n, my(j=n-i); y^i*(2*i+2*j)!/(i!*(i+1)!*j!*(j+1)!))) + O(x*x^n)}
G(n,y)={my(g=F(n,y)); subst(g, x, serreverse(x*g^2))}
H(n)={my(g=G(n,y)-x, v=Vec(sqrt(serreverse(x/g^2)/x))); [Vecrev(t) | t<-v]}
{ my(T=H(8)); for(n=1, #T, print(T[n])) }

G.f.: A(x,y) satisfies A(x,y) = G(x*A(x,y)^2,y) where G(x,y) + x is the g.f. of A342984.

A027789 a(n) = 2(n+1)binomial(n+3,4).

Original entry on oeis.org

4, 30, 120, 350, 840, 1764, 3360, 5940, 9900, 15730, 24024, 35490, 50960, 71400, 97920, 131784, 174420, 227430, 292600, 371910, 467544, 581900, 717600, 877500, 1064700, 1282554, 1534680, 1824970, 2157600, 2537040, 2968064, 3455760, 4005540, 4623150, 5314680

Offset: 1

Thi Ngoc Dinh (via R. K. Guy)

Number of 8-subsequences of [ 1, n ] with just 3 contiguous pairs.

Also the number of 3-cycles in the n+3 tetrahedral graph. - Eric W. Weisstein, Jul 12 2017

Harvey P. Dale, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Graph Cycle.
Eric Weisstein's World of Mathematics, Tetrahedral Graph.
Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Cf. A006470, A289792 (4-cycles), A289793 (5-cycles), A289794 (6-cycles).

[2*(n+1)*Binomial(n+3,4): n in [1..40]]; // Vincenzo Librandi, Jul 13 2017

A027789:=n->2*(n+1)*binomial(n+3,4): seq(A027789(n), n=1..60); # Wesley Ivan Hurt, Oct 23 2017

Table[2 (n + 1) Binomial[n + 3, 4], {n, 40}] (* Harvey P. Dale, Jan 20 2015 *)
LinearRecurrence[{6, -15, 20, -15, 6, -1}, {4, 30, 120, 350, 840, 1764},40] (* Harvey P. Dale, Jan 20 2015 *)
Table[n (1 + n)^2 (2 + n) (3 + n)/12, {n, 20}] (* Eric W. Weisstein, Jul 12 2017 *)
CoefficientList[Series[(2 (2 + 3 x))/(-1 + x)^6, {x, 0, 20}], x] (* Eric W. Weisstein, Jul 12 2017 *)

for(n=1,50, print1(2*(n+1)*binomial(n+3,4), ", ")) \\ G. C. Greubel, Oct 22 2017

G.f.: 2*(2+3x)*x/(1-x)^6.
a(n) = 2*A006470(n).
a(n) = C(n+1, 2)*C(n+3, 3). - Zerinvary Lajos, May 10 2005, corrected by R. J. Mathar, Feb 13 2016
a(n) = 6*a(n-1) - 15*a(n-2) + 20*a(n-3) - 15*a(n-4) + 6*a(n-5) - a(n-6). - Harvey P. Dale, Jan 20 2015
a(n) = Sum_{k=1..n+1} Sum_{i=1..n+1} (n-i+1) * C(k+1,k-1). - Wesley Ivan Hurt, Sep 21 2017
From Amiram Eldar, Jan 28 2022: (Start)
Sum_{n>=1} 1/a(n) = 61/6 - Pi^2.
Sum_{n>=1} (-1)^(n+1)/a(n) = Pi^2/2 - 8*log(2) + 5/6. (End)

A108838 Triangle of Dyck paths counted by number of long interior inclines.

Original entry on oeis.org

2, 3, 2, 4, 8, 2, 5, 20, 15, 2, 6, 40, 60, 24, 2, 7, 70, 175, 140, 35, 2, 8, 112, 420, 560, 280, 48, 2, 9, 168, 882, 1764, 1470, 504, 63, 2, 10, 240, 1680, 4704, 5880, 3360, 840, 80, 2, 11, 330, 2970, 11088, 19404, 16632, 6930, 1320, 99, 2

Offset: 2

David Callan, Jul 25 2005

T(n,k) is the number of Dyck n-paths (A000108) containing k long interior inclines. An incline is an ascent or a descent where an ascent (resp. descent) is a maximal sequence of contiguous upsteps (resp. downsteps). An incline is long if it consists of at least 2 steps and is interior if it does not start or end the path.
T(n,k) is the number of Dyck (n+1)-paths whose last descent has length 2 and which contain n-k peaks. For example T(3,0)=3 counts UUDUDUDD, UDUUDUDD, UDUDUUDD. - David Callan, Jul 03 2006
T(n,k) is the number of parallelogram polyominoes of semiperimeter n+1 having k corners. - Emeric Deutsch, Oct 09 2008
T(n,k) is the number of rooted ordered trees with n non-root nodes and k leaves; see example. - Joerg Arndt, Aug 18 2014

			Table begins
\ k..0....1....2....3....4....5
n\
2 |..2
3 |..3....2
4 |..4....8....2
5 |..5...20...15....2
6 |..6...40...60...24....2
7 |..7...70..175..140...35....2
The paths UUUDDD, UUDUDD, UDUDUD have no long interior inclines; so T(3,0)=3.
From _Joerg Arndt_, Aug 18 2014: (Start)
The rooted ordered trees with n=3 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
:
:     1:  [ 0 1 1 1 ]   2
:  O--o
:  .--o
:  .--o
:
:     2:  [ 0 1 1 2 ]   2
:  O--o
:  .--o--o
:
:     3:  [ 0 1 2 1 ]   1
:  O--o--o
:  .--o
:
:     4:  [ 0 1 2 2 ]   1
:  O--o--o
:     .--o
:
:     5:  [ 0 1 2 3 ]   1
:  O--o--o--o
:
This gives [3, 2], row n=3 of the triangle.
(End)

Michael De Vlieger, Table of n, a(n) for n = 2..11176 (rows 2 <= n <= 150, flattened)
Per Alexandersson, Svante Linusson, Samu Potka, and Joakim Uhlin, Refined Catalan and Narayana cyclic sieving, arXiv:2010.11157 [math.CO], 2020.
Tewodros Amdeberhan, Victor H. Moll, and Christophe Vignat, A probabilistic interpretation of a sequence related to Narayana Polynomials, arXiv:1202.1203 [math.NT], 2012. - From _N. J. A. Sloane_, Sep 19 2012
Tewodros Amdeberhan, Victor H. Moll, and Christophe Vignat, A probabilistic interpretation of a sequence related to Narayana Polynomials, Online Journal of Analytic Combinatorics, Issue 8, 2013.
David Callan, Some Identities for the Catalan and Fine Numbers, arXiv:math/0502532 [math.CO], 2005.
M. Delest, J. P. Dubernard, and I. Dutour, Parallelogram polyominoes and corners, J. Symbolic Computation, 20(1995),503-515. [From _Emeric Deutsch_, Oct 09 2008]
M. P. Delest, D. Gouyou-Beauchamps, and B. Vauquelin, Enumeration of parallelogram polyominoes with given bond and site parameter, Graphs and Combinatorics, 3 (1987), 325-339.
Emeric Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202.
T. Doslic, Handshakes across a (round) table, JIS 13 (2010) #10.2.7.
Sergi Elizalde, Johnny Rivera Jr., and Yan Zhuang, Counting pattern-avoiding permutations by big descents, arXiv:2408.15111 [math.CO], 2024. See pp. 6, 18, 27.

Row sums are the Catalan numbers A000108. Column k=1 is A007290, k=2 is A006470. The Narayana numbers A001263 count Dyck paths by number of long nonterminal inclines. A091894 (Touchard distribution) counts Dyck paths by number of long nonterminal descents.

Cf. A145596.

T:=(n,k)->2*binomial(n-1,k)*binomial(n,k+2)/(n-1): for n from 2 to 11 do seq(T(n,k),k=0..n-2) od; # yields sequence in triangular form; Emeric Deutsch, Jul 23 2006

T[n_, 0] = n;
T[n_, k_] := T[n, k] = If[k == n-2, 2, T[n, k-1](n-k-1)(n-k)/(k(k+2))];
Table[T[n, k], {n, 2, 11}, {k, 0, n-2}] // Flatten (* Jean-François Alcover, Jul 27 2018, after Werner Schulte *)

T(n, k) = 2*binomial(n+1, k+2)*binomial(n-2, k)/(n+1).
G.f.: G(z, t) = Sum_{n>=1, k>=0} T(n, k)*z^n*t^k satisfies z - ( (1-z)^2 - (2*t-t^2)*z^2 )*G + (t^2*z)*G^2 = 0.
G.f.: 1+z(1+r)^2, where r=r(t,z) is the Narayana function defined by (1+r)*(1+tr)z=r, r(t,0)=0. - Emeric Deutsch, Jul 23 2006
For n >= 0, the row polynomials Sum_{k=0..n} T(n+2,k)*x^k = (2/(n+1))*(1-x)^n*P(n,2,1,(1+x)/(1-x)), where P(n,a,b,x) denotes the Jacobi polynomial. It follows that the row polynomials have negative real zeros. - Peter Bala, Jan 21 2008
The trivariate g.f. G=G(t,s,z) of Dyck paths with respect to number of DUU's (marked by t), number of DDU's (marked by s) and semilength (marked by z) satisfies G = 1 + z*G + z^2*(1+t*(G-1))*(1+s*(G-1))/(1-z*(1+t*s*(G-1))) (the number of long interior inclines is equal to the number of DUU and DDU's). - Emeric Deutsch, Oct 09 2008
Recurrence: T(n, k) = T(n, k-1)*(n-1-k)*(n-k)/(k*(k+2)) for k > 0 and n >= 2. - Werner Schulte, Jan 04 2017
The array can be extended to negative values of n: T(-n,k) = 2*binomial(-n+1, k+2)*binomial(-n-2, k)/(-n+1) = -A145596(n+k,k+1) for n >= 2. - Peter Bala, Apr 26 2022

cp's OEIS Frontend

A342987 Triangle read by rows: T(n,k) is the number of tree-rooted planar maps with n edges, k faces and no isthmuses, n >= 0, k = 1..n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A027789 a(n) = 2(n+1)binomial(n+3,4).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A108838 Triangle of Dyck paths counted by number of long interior inclines.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

cp's OEIS Frontend

A342987 Triangle read by rows: T(n,k) is the number of tree-rooted planar maps with n edges, k faces and no isthmuses, n >= 0, k = 1..n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A027789 a(n) = 2*(n+1)*binomial(n+3,4).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A108838 Triangle of Dyck paths counted by number of long interior inclines.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A027789 a(n) = 2(n+1)binomial(n+3,4).