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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 4
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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

LINKS

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.

FORMULA

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)

EXAMPLE

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

MAPLE

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

MATHEMATICA

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

PROG

(PARI)

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

(PARI)

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

CROSSREFS

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

Sequence in context: A217859 A108426 A163237 * A130847 A188815 A010615

Adjacent sequences:  A053976 A053977 A053978 * A053980 A053981 A053982

KEYWORD

nonn,tabl,easy

AUTHOR

N. J. A. Sloane, Apr 09 2000

EXTENSIONS

More terms from Emeric Deutsch, Apr 01 2005

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified February 23 07:28 EST 2018. Contains 299473 sequences. (Running on oeis4.)