A006416 -id:A006416 - cp's OEIS frontend

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

1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 8, 1, 0, 0, 1, 20, 20, 1, 0, 0, 1, 38, 131, 38, 1, 0, 0, 1, 63, 469, 469, 63, 1, 0, 0, 1, 96, 1262, 3008, 1262, 96, 1, 0, 0, 1, 138, 2862, 12843, 12843, 2862, 138, 1, 0, 0, 1, 190, 5780, 42602, 83088, 42602, 5780, 190, 1, 0

Offset: 0

Andrew Howroyd, Apr 01 2021

The number of vertices is n + 2 - k.

For k >= 2, columns k without the initial zero term is a polynomial of degree 3*(k-2). This is because adding a face can increase the number of vertices whose degree is greater than two by at most two.

			Triangle begins:
  1;
  0, 0;
  0, 1,   0;
  0, 1,   1,    0;
  0, 1,   8,    1,     0;
  0, 1,  20,   20,     1,     0;
  0, 1,  38,  131,    38,     1,    0;
  0, 1,  63,  469,   469,    63,    1,   0;
  0, 1,  96, 1262,  3008,  1262,   96,   1, 0;
  0, 1, 138, 2862, 12843, 12843, 2862, 138, 1, 0;
  ...

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

Columns (and diagonals) are A006416, A006417, A006418.
Row sums are A099553(n+1).
Cf. A082680, A269920, A342981, A342985, A343090.

G[m_, y_] := Sum[x^n*Sum[(n + k - 1)!*(2*n - k)!*y^k/(k!*(n + 1 - k)!*(2*k - 1)!*(2*n - 2*k + 1)!), {k, 1, n}], {n, 1, m}] + O[x]^m;
H[n_] := With[{g = 1 + x*G[n - 1, y]}, Sqrt[InverseSeries[x/g^2 + O[x]^(n + 1), x]/x]];
Join[{{1}, {0, 0}}, Append[CoefficientList[#, y], 0]& /@ CoefficientList[ H[11], x][[3;;]]] // Flatten (* Jean-François Alcover, Apr 15 2021, after Andrew Howroyd *)

\\ here G(n,y) gives A082680 as g.f.
G(n,y)={sum(n=1, n, x^n*sum(k=1, n, (n+k-1)!*(2*n-k)!*y^k/(k!*(n+1-k)!*(2*k-1)!*(2*n-2*k+1)!))) + O(x*x^n)}
H(n)={my(g=1+x*G(n-1, y), v=Vec(sqrt(serreverse(x/g^2)/x))); vector(#v, n, Vecrev(v[n], n))}
{ my(T=H(8)); for(n=1, #T, print(T[n])) }

T(n,n+2-k) = T(n,k).

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

A167630 Riordan array (1/(1-x),xm(x)) where m(x) is the g.f. of Motzkin numbers A001006.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 8, 8, 4, 1, 1, 17, 20, 13, 5, 1, 1, 38, 50, 38, 19, 6, 1, 1, 89, 126, 107, 63, 26, 7, 1, 1, 216, 322, 296, 196, 96, 34, 8, 1, 1, 539, 834, 814, 588, 326, 138, 43, 9, 1, 1, 1374, 2187, 2236, 1728, 1052, 507, 190, 53, 10, 1

Offset: 0

Philippe Deléham, Nov 07 2009

			Triangle begins:
  1;
  1,  1;
  1,  2,  1;
  1,  4,  3,  1;
  1,  8,  8,  4,  1;
  1, 17, 20, 13,  5, 1;
  1, 38, 50, 38, 19, 6, 1;
  ...

Alois P. Heinz, Rows n = 0..200, flattened

Antidiagonal sums give A082395.
Row sums give A383527.
Diagonals include: A006416, A034856, A086615, A140662.
Cf. A001006, A003462, A064189, A082397, A094531.

T:= proc(n, k) option remember; `if`(k=0, 1,
      `if`(k>n, 0, T(n-1, k-1)+T(n-1, k)+T(n-1, k+1)))
    end:
seq(seq(T(n, k), k=0..n), n=0..12);  # Alois P. Heinz, Apr 20 2018

T[, 0] = T[n, n_] = 1;
T[n_, k_] /; 0, ] = 0;
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 09 2019 *)

T(n,0)=1, T(0,k)=0 for k>0, T(n,k)=0 if k>n, T(n,k)=T(n-1,k-1)+T(n-1,k)+T(n-1,k+1).
Sum_{k=0..n} k * T(n,k) = A003462(n). - Alois P. Heinz, Apr 20 2018
Sum_{k=0..n} (-1)^(k+1) * T(n,k) = A082397(n-2) for n>=2. - Alois P. Heinz, May 02 2025

A027378 Expansion of (1+x^2-x^3)/(1-x)^4.

Original entry on oeis.org

1, 4, 11, 23, 41, 66, 99, 141, 193, 256, 331, 419, 521, 638, 771, 921, 1089, 1276, 1483, 1711, 1961, 2234, 2531, 2853, 3201, 3576, 3979, 4411, 4873, 5366, 5891, 6449, 7041, 7668, 8331, 9031, 9769, 10546

Offset: 0

N. J. A. Sloane

If Y is a 3-subset of an n-set X then, for n>=4, a(n-4) is the number of (n-3)-subsets of X which do not have exactly one element in common with Y. - Milan Janjic, Dec 28 2007

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A006416, A006503, A034857, A116721.
Appears to be first differences of A252814.
First differences at A027379 (omitting first term).

[(n^3 +9*n^2 +8*n +6)/6: n in [0..50]]; // G. C. Greubel, Jul 30 2022

CoefficientList[Series[(1+x^2-x^3)/(1-x)^4,{x,0,50}],x] (* or *) LinearRecurrence[{4,-6,4,-1},{1,4,11,23},50] (* Harvey P. Dale, May 17 2021 *)

[(n^3 +9*n^2 +8*n +6)/6 for n in (0..50)] # G. C. Greubel, Jul 30 2022

a(n) = binomial(n+4, 3) - 3*(n+1). - Milan Janjic, Dec 28 2007 [Correction by Mathew Englander, Feb 03 2022]
a(n) = A006503(n) + 1 = A034857(n) + 5 = A116721(n+2) - 1 = A006416(n+1) + 3. - Mathew Englander, Feb 03 2022
E.g.f.: (1/6)*(6 + 18*x + 12*x^2 + x^3)*exp(x). - G. C. Greubel, Jul 30 2022

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A167630 Riordan array (1/(1-x),xm(x)) where m(x) is the g.f. of Motzkin numbers A001006.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A027378 Expansion of (1+x^2-x^3)/(1-x)^4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula