A128709 -id:A128709 - cp's OEIS frontend

A053979 Triangle T(n,k) giving number of rooted maps regardless of genus with n edges and k nodes (n >= 0, k = 1..n+1).

1, 1, 1, 3, 5, 2, 15, 32, 22, 5, 105, 260, 234, 93, 14, 945, 2589, 2750, 1450, 386, 42, 10395, 30669, 36500, 22950, 8178, 1586, 132, 135135, 422232, 546476, 388136, 166110, 43400, 6476, 429, 2027025, 6633360, 9163236, 7123780, 3463634, 1092560, 220708, 26333, 1430

Offset: 0

N. J. A. Sloane, Apr 09 2000

Triangle T(n,k), read by rows, given by (1,2,3,4,5,6,7,8,9,...) DELTA (1,1,1,1,1,1,1,1,1,1,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 21 2011.

A127160*A007318 as infinite lower triangular matrices. - Philippe Deléham, Jan 06 2012

			A(x;t) = t + (t + t^2)*x + (3*t + 5*t^2 + 2*t^3)*x^2 + (15*t + 32*t^2 + 22*t^3 + 5*t^4)*x^3 + ...
Triangle begins :
n\k [1]     [2]     [3]     [4]     [5]     [6]    [7]   [8]
[0] 1;
[1] 1,      1;
[2] 3,      5,      2;
[3] 15,     32,     22,     5;
[4] 105,    260,    234,    93,     14;
[5] 945,    2589,   2750,   1450,   386,    42;
[6] 10395,  30669,  36500,  22950,  8178,   1586,  132;
[7] 135135, 422232, 546476, 388136, 166110, 43400, 6476, 429;
[8] ...

Gheorghe Coserea, Rows n=0..100, flattened
D. Arques and J.-F. Beraud, Rooted maps on orientable surfaces, Riccati's equation and continued fractions, Discrete Math., 215 (2000), 1-12.
R. Cori, Indecomposable permutations, hypermaps and labeled Dyck paths, arXiv:0812.0440v1 [math.CO], 2008.
R. Cori, Indecomposable permutations, hypermaps and labeled Dyck paths, Journal of Combinatorial Theory, Series A 116 (2009) 1326-1343.
J. Courtiel, K. Yeats, Connected chord diagrams and bridgeless maps, arXiv:1611.04611, eq. (18)
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. I, J. Comb. Theory B 13 (1972), 192-218, eq. (5).

Cf. A000108, A000346, A001147, A084938. A000698, A025192, A084120, A127160, A167872.

G:=t/(1-(t+1)*z/(1-(t+2)*z/(1-(t+3)*z/(1-(t+4)*z/(1-(t+5)*z/(1-(t+6)*z/(1-(t+7)*z/(1-(t+8)*z/(1-(t+9)*z/(1-(t+10)*z/(1-(t+11)*z/(1-(t+12)*z)))))))))))):Gser:=simplify(series(G,z=0,10)):P[0]:=t:for n from 1 to 9 do P[n]:=sort(expand(coeff(Gser,z^n))) od:seq(seq(coeff(P[n],t^k),k=1..n+1),n=0..9); # Emeric Deutsch, Apr 01 2005

g = t/Fold[1-((t+#2)*z)/#1&, 1, Range[12, 1, -1]]; T[n_, k_] := SeriesCoefficient[g, {z, 0, n}, {t, 0, k}]; Table[T[n, k], {n, 0, 9}, {k, 1, n+1}] // Flatten (* Jean-François Alcover, Jan 08 2014 *)

A053979_ser(N,t='t) = {
  my(x='x+O('x^N), y0=1, y1=0, n=1);
  while(n++, y1 = (1 + t*x*y0^2 + 2*x^2*y0')/(1-x);
    if (y1 == y0, break()); y0 = y1); y0;
};
concat(apply(p->Vecrev(p), Vec(A053979_ser(10))))
\\ test: y=A053979_ser(50); 2*x^2*deriv(y,x) == -t*x*y^2 + (1-x)*y - 1
\\ Gheorghe Coserea, May 31 2017

A053979_seq(N) = {
  my(t='t, R=vector(N), S=vector(N)); R[1]=S[1]=t;
  for (n=2, N,
    R[n] = t*subst(S[n-1],t,t+1);
    S[n] = R[n] + sum(k=1, n-1, R[k]*S[n-k]));
  apply(p->Vecrev(p), R/t);
};
concat(A053979_seq(10))
\\ test: y=t*Ser(apply(p->Polrev(p,'t), A053979_seq(50)),'x); y == t + x*y^2 + x*y + 2*x^2*deriv(y,x) && y == t + x*y*subst(y,t,t+1) \\ Riccati eq && Dyck eq
\\ Gheorghe Coserea, May 31 2017

G.f.: t/(1-(t+1)z/(1-(t+2)z/(1-(t+3)z/(1-(t+4)z/(1-(t+5)z/(1-... (Eq. (5) in the Arques-Beraud reference). - Emeric Deutsch, Apr 01 2005
Sum_{k = 0..n} (-1)^k*2^(n-k)*T(n,k) = A128709(n). Sum_{k = 0..n} T(n,k) = A000698(n+1). - Philippe Deléham, Mar 24 2007
From Peter Bala, Dec 22 2011: (Start)
The o.g.f. in the form G(x,t) = x/(1 - (t+1)*x^2/(1 - (t+2)*x^2/(1 - (t+3)*x^2/(1 - (t+4)*x^2/(1 - ... ))))) = x + (1+t)*x^3 + (3+5*t+2*t^2)*x^5 + ... satisfies the Riccati equation (1 - t*x*G)*G = x + x^3*dG/dx. The cases t = 0, t = 1 and t = 2 give A001147, A000698 and A167872, respectively. The cases t = -2, t = -3 and t = -4 give rational generating functions for aerated and signed versions of A000012, A025192 and A084120, respectively.
The identity G(x,1+t) = 1/(1+t)(1/x-1/G(x,t)) provided t <> -1 allows us to express G(x,n), n = 1,2,..., in terms of G(x,0), a generating function for the double factorial numbers.
Writing G(x,t) = Sum_{n >= 1} R(n,t)*x^(2*n-1), the row generating polynomials R(n,t) satisfy the recurrence R(n+1,t) = (2*n-1)*R(n,t) + t*sum {k = 1..n} R(k,t)*R(n+1-k,t) with initial condition R(1,t) = 1.
G(x,t-1) = x + t*x^3 + (t+2*t^2)*x^5 + (3*t+7*t^2+5*t^3)*x^7 + ... is an o.g.f. for A127160.
The function b(x,t) = - t*G(1/x,t) satisfies the partial differential equation d/dx(b(x,t)) = -(t + (x + b(x,t))*b(x,t)). Hence the differential operator (D^2 + x*D + t), where D = d/dx, factorizes as (D - a(x,t))*(D - b(x,t)), where a(x,t) = -(x + b(x,t)). In the particular case t = -n, a negative integer, the functions a(x,-n) and b(x,-n) become rational functions of x expressible as the ratio of Hermite polynomials.
(End)

More terms from Emeric Deutsch, Apr 01 2005

A292186 Number of rooted unlabeled connected four-regular maps on a compact closed oriented surface with n vertices (and thus 2*n edges), with a(0) = 1.

Original entry on oeis.org

1, 3, 24, 297, 4896, 100278, 2450304, 69533397, 2247492096, 81528066378, 3280382613504, 145009234904922, 6986546222800896, 364418301804218028, 20459842995693256704, 1230262900677124568397, 78884016707711348637696, 5372823210133041283250178, 387394283866652086938107904

Offset: 0

Sasha Kolpakov, Sep 11 2017

Equivalently, the number of rooted quadrangulations of oriented surfaces with n quadrangles (and thus 2*n edges) for n > 0.
Equivalently, the number of pairs (alpha,sigma) of permutations on a pointed set of size 4*n up to simultaneous conjugacy such that alpha (resp. sigma) has only cycles of length 2 (resp. 4) and the subgroup generated by them acts transitively, for n > 0.
This is also the S(4, -6, 1) sequence of Martin and Kearney, if the offset is set to 1.
This sequence is not D-finite (or holonomic).

Sasha Kolpakov, Table of n, a(n) for n = 0..119
Laura Ciobanu and Alexander Kolpakov, Free subgroups of free products and combinatorial hypermaps, Discrete Mathematics, 342 (2019), 1415-1433; arXiv:1708.03842 [math.CO], 2017-2019.
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, Aequat. Math., 80 (2010), 291-318; arXiv:1103.4936 [math.CO], 2011.
A. N. Stokes, Continued fraction solutions of the Riccati equation, Bull. Austral. Math. Soc. Vol. 25 (1982), 207-214.

Column 4 of A380622.

Cf. A172455, A292187, A128709.

from sympy.core.cache import cacheit
@cacheit
def a(n): return 1 if n == 0 else (4*n - 2)*a(n - 1) + sum([a(k)*a(n - k - 1) for k in range(n)])
[a(n) for n in range(21)]

a(0)=1, a(1)=3, a(n) = 4*n*a(n-1) + Sum_{k=1..n-2} a(k)*a(n-k-1) for n>=2.
From Peter Bala, Aug 22 2023: (Start)
The o.g.f. A(x) = 1 + 3*x + 24*x^2 + 297*x^3 + 4896*x^4 + 100278*x^5 + 2450304*x^6 + ... satisfies the Riccati differential equation (4*x^2)*A'(x) = -1 + (1 - 2*x)*A(x) - x*A(x)^2 with A(0) = 1.
O.g.f. as a continued fraction of Stieltjes type: 1/(1 - 3*x/(1 - 5*x/(1 - 7*x/(1 - 9*x/(1 - ... - (2*n+1)*x/(1 - ... )))))).
Also A(x) = 1/(1 + 2*x - 5*x/(1 - 3*x/(1 - 9*x/(1 - 7*x/(1 - ... - (4*n+1)*x/(1 - (4*n-1)*x/(1 - ... ))))))). (End)

Edited by Andrey Zabolotskiy, Jan 23 2025

A094344 Triangle T(n,k), 0<= k <= n, read by rows; given by [0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, ...] DELTA [1, 0, 2, 1, 3, 2, 4, 3, 5, 4, 6, 5, ...] where DELTA is the operator defined in A084938.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 4, 1, 0, 6, 18, 13, 1, 0, 24, 96, 119, 46, 1, 0, 120, 600, 1059, 777, 199, 1, 0, 720, 4320, 9890, 10760, 5536, 1072, 1, 0, 5040, 35280, 99158, 142990, 111316, 44228, 6985, 1, 0, 40320, 322560, 1073692, 1926312, 2009578, 1217352, 395865, 53218, 1

Offset: 0

Philippe Deléham, Jun 02 2004

			Triangle begins:
  1;
  0,  1;
  0,  1,  1;
  0,  2,  4,   1;
  0,  6, 18,  13,  1;
  0, 24, 96, 119, 46, 1;
  ...

Row sums: A094664.
Columns: A000007, A000142, A001563.
Diagonals: A000012, A014145.

Sum_{k=0..n} T(n,k)*3^(n-k) = A128709(n). - Philippe Deléham, Mar 27 2007

Row 9 completed by Michel Marcus, Jun 20 2023

A168440 a(n) = Product_{k=0..n} ((4k+1)(4*k+3))^(n-k).

Original entry on oeis.org

1, 3, 315, 3274425, 6637341335625, 4345660353133020796875, 1374246178519871776155872382421875, 293343904920011883594420118662644304008056640625

Offset: 0

Paul Barry, Nov 25 2009

Hankel transform of A128709.

Cf. A128709.

Table[Product[((4*k+1)*(4*k+3))^(n-k), {k,0,n}], {n,0,10}] (* Vaclav Kotesovec, Jan 23 2024 *)

a(n) ~ A^(1/4) * sqrt(Gamma(1/4)) * 2^(2*n^2 + 5*n/2 + 1/8) * n^(n^2 + n + 7/48) / (Pi^(1/4) * exp(3*n^2/2 + n + 1/48)), where A is the Glaisher-Kinkelin constant A074962. - Vaclav Kotesovec, Jan 23 2024

A291261 Square array A(n,k), n >= 0, k >= 0, read by antidiagonals, where column k is the expansion of continued fraction 1/(1 - x/(1 - 3^kx/(1 - 5^kx/(1 - 7^kx/(1 - 9^kx/(1 - ...)))))).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 4, 5, 1, 1, 10, 31, 14, 1, 1, 28, 325, 364, 42, 1, 1, 82, 4159, 22150, 5746, 132, 1, 1, 244, 57349, 1790452, 2586250, 113944, 429, 1, 1, 730, 818911, 162045118, 1691509906, 461242900, 2719291, 1430, 1, 1, 2188, 11923525, 15520964284, 1289803048426, 2978600051368, 116651486125, 75843724, 4862

Offset: 0

Ilya Gutkovskiy, Aug 21 2017

			Square array begins:
   1,     1,        1,           1,              1,                 1,  ...
   1,     1,        1,           1,              1,                 1,  ...
   2,     4,       10,          28,             82,               244,  ...
   5,    31,      325,        4159,          57349,            818911,  ...
  14,   364,    22150,     1790452,      162045118,       15520964284,  ...
  42,  5746,  2586250,  1691509906,  1289803048426,  1063421637466546,  ...

Columns k=0..2 give A000108, A128709, A127823.
Main diagonal gives A291332.
Cf. A034472 (row 2), A290569, A291260.

Table[Function[k, SeriesCoefficient[1/(1 + ContinuedFractionK[-(2 i - 1)^k x, 1, {i, 1, n}]), {x, 0, n}]][j - n], {j, 0, 9}, {n, 0, j}] // Flatten

G.f. of column k: 1/(1 - x/(1 - 3^k*x/(1 - 5^k*x/(1 - 7^k*x/(1 - 9^k*x/(1 - ...)))))), a continued fraction.

A127160 Triangle T(n,k), 0<=k<=n, read by rows given by [0,1,2,3,4,5,6,...] DELTA [1,1,1,1,1,1,1,1,...] where DELTA is the operator defined in A084938.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 3, 7, 5, 0, 15, 39, 37, 14, 0, 105, 296, 326, 176, 42, 0, 945, 2838, 3458, 2228, 794, 132, 0, 10395, 32859, 43191, 31235, 13553, 3473, 429, 0, 135135, 445767, 622259, 489899, 241225, 76417, 14893, 1430

Offset: 0

Philippe Deléham, Mar 25 2007

This triangle enumerates fixed-point-free involutions in S_n by number of left-to-right maxima. For instance there are 15 fixed point free involutions on 6 elements: 3 have 1 left to right maxima, namely (1,6)(2,3)(4,5), (1,6)(2,4)(3,5) and (3,6)(2,5)(3,4); 7 have 2 left-to right maxima and 5 have 3 left to right maxima. - Robert Cori (rcori(AT)cs.brown.edu), Apr 25 2008

A053979*A130595 as infinite lower triangular matrices. - Philippe Deléham, Jan 06 2012

			Triangle begins:
1;
0, 1;
0, 1, 2;
0, 3, 7, 5;
0, 15, 39, 37, 14;
0, 105, 296, 326, 176, 42;
0, 945, 2838, 3458, 2228, 794, 132;
0, 10395, 32859, 43191, 31235, 13553, 3473, 429;
0, 135135, 445767, 622259, 489899, 241225, 76417, 14893, 1430;

A053979.

nmax = 8;
DELTA[r_, s_, m_] := Module[{p, q, t, x, y}, q[k_] := x r[[k + 1]] + y s[[k + 1]]; p[0, ] = 1; p[, -1] = 0; p[n_ /; n >= 1, k_ /; k >= 0] := p[n, k] = p[n, k-1] + q[k] p[n-1, k+1] // Expand; t[n_, k_] := Coefficient[ p[n, 0], x^(n - k) y^k]; t[0, 0] = p[0, 0]; Table[t[n, k], {n, 0, m}, {k, 0, n}]];
DELTA[Range[0, nmax], Table[1, {nmax+1}], nmax] // Flatten (* Jean-François Alcover, Nov 12 2019 *)

Sum_{k=0..n} T(n,k)*x^(n-k) = A000012(n), A000108(n), A001147(n), A128709(n) for x = -1,0,1,2 respectively.
From Peter Bala, Dec 22 2011: (Start)
The o.g.f. in the form G(x,t) = x/(1 - t*x^2/(1 - (t+1)*x^2/(1 - (t+2)*x^2/(1 - (t+3)*x^2/(1 - ... ))))) = x + t*x^3 + (t+2*t^2)*x^5 + ... satisfies the Riccati differential equation (1 - (t-1)*x*G)*G = x + x^3*dG/dx. Writing G(x,t) = sum {n = 1..inf} R(n,t)*x^(2*n-1), the row generating polynomials R(n,t) satisfy the recurrence R(n+1,t) = (2*n-1)*R(n,t) + (t-1)*sum {k = 1..n} R(k,t)*R(n+1-k,t) with initial condition R(1,t) = 1.
G(x,t+1) = x + (1+t)*x^3 + (3+5*t+2*t^2)*x^5 + ... is an o.g.f. for A053979.
(End)

Corrected and extended by Peter Bala, Dec 20 2011

A178104 Inverse of coefficient array of orthogonal polynomials P(n,x)=xP(n-1,x)-(2n-3)P(n-2,x), P(0,x)=1,P(1,x)=x.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 0, 4, 0, 1, 4, 0, 9, 0, 1, 0, 31, 0, 16, 0, 1, 31, 0, 111, 0, 25, 0, 1, 0, 364, 0, 286, 0, 36, 0, 1, 364, 0, 1794, 0, 610, 0, 49, 0, 1, 0, 5746, 0, 6064, 0, 1149, 0, 64, 0, 1, 5746, 0, 36066, 0, 16405, 0, 1981, 0, 81, 0, 1, 0, 113944, 0, 150901, 0, 38196, 0, 3196

Offset: 0

Paul Barry, May 20 2010

Inverse is A178103. First row is aerated version of A128709.

			Triangle begins
1,
0, 1,
1, 0, 1,
0, 4, 0, 1,
4, 0, 9, 0, 1,
0, 31, 0, 16, 0, 1,
31, 0, 111, 0, 25, 0, 1,
0, 364, 0, 286, 0, 36, 0, 1,
364, 0, 1794, 0, 610, 0, 49, 0, 1
Production matrix is
0, 1,
1, 0, 1,
0, 3, 0, 1,
0, 0, 5, 0, 1,
0, 0, 0, 7, 0, 1,
0, 0, 0, 0, 9, 0, 1,
0, 0, 0, 0, 0, 11, 0, 1,
0, 0, 0, 0, 0, 0, 13, 0, 1,
0, 0, 0, 0, 0, 0, 0, 15, 0, 1

cp's OEIS Frontend

A053979 Triangle T(n,k) giving number of rooted maps regardless of genus with n edges and k nodes (n >= 0, k = 1..n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A292186 Number of rooted unlabeled connected four-regular maps on a compact closed oriented surface with n vertices (and thus 2*n edges), with a(0) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

Extensions

A094344 Triangle T(n,k), 0<= k <= n, read by rows; given by [0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, ...] DELTA [1, 0, 2, 1, 3, 2, 4, 3, 5, 4, 6, 5, ...] where DELTA is the operator defined in A084938.

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions

A168440 a(n) = Product_{k=0..n} ((4*k+1)*(4*k+3))^(n-k).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A291261 Square array A(n,k), n >= 0, k >= 0, read by antidiagonals, where column k is the expansion of continued fraction 1/(1 - x/(1 - 3^k*x/(1 - 5^k*x/(1 - 7^k*x/(1 - 9^k*x/(1 - ...)))))).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A127160 Triangle T(n,k), 0<=k<=n, read by rows given by [0,1,2,3,4,5,6,...] DELTA [1,1,1,1,1,1,1,1,...] where DELTA is the operator defined in A084938.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A178104 Inverse of coefficient array of orthogonal polynomials P(n,x)=x*P(n-1,x)-(2n-3)*P(n-2,x), P(0,x)=1,P(1,x)=x.

Views

Author

Keywords

Comments

Examples

A168440 a(n) = Product_{k=0..n} ((4k+1)(4*k+3))^(n-k).

A291261 Square array A(n,k), n >= 0, k >= 0, read by antidiagonals, where column k is the expansion of continued fraction 1/(1 - x/(1 - 3^kx/(1 - 5^kx/(1 - 7^kx/(1 - 9^kx/(1 - ...)))))).

A178104 Inverse of coefficient array of orthogonal polynomials P(n,x)=xP(n-1,x)-(2n-3)P(n-2,x), P(0,x)=1,P(1,x)=x.