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

Author

N. J. A. Sloane, Apr 09 2000

Keywords

• nonn
• tabl
• easy

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

Examples

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

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.
• 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).

Crossrefs

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

Programs

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

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

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)

Extensions

More terms from Emeric Deutsch, Apr 01 2005