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

%I #62 Dec 06 2018 11:26:21

%S 1,1,1,3,5,2,15,32,22,5,105,260,234,93,14,945,2589,2750,1450,386,42,

%T 10395,30669,36500,22950,8178,1586,132,135135,422232,546476,388136,

%U 166110,43400,6476,429,2027025,6633360,9163236,7123780,3463634,1092560,220708,26333,1430

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

%C 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.

%C A127160*A007318 as infinite lower triangular matrices. - _Philippe Deléham_, Jan 06 2012

%H Gheorghe Coserea, <a href="/A053979/b053979.txt">Rows n=0..100, flattened</a>

%H D. Arques and J.-F. Beraud, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00197-1">Rooted maps on orientable surfaces, Riccati's equation and continued fractions</a>, Discrete Math., 215 (2000), 1-12.

%H R. Cori, <a href="https://arxiv.org/abs/0812.0440">Indecomposable permutations, hypermaps and labeled Dyck paths</a>, arXiv:0812.0440v1 [math.CO], 2008.

%H R. Cori, <a href="https://doi.org/10.1016/j.jcta.2009.02.008">Indecomposable permutations, hypermaps and labeled Dyck paths</a>, Journal of Combinatorial Theory, Series A 116 (2009) 1326-1343.

%H J. Courtiel, K. Yeats, <a href="https://arxiv.org/abs/1611.04611">Connected chord diagrams and bridgeless maps</a>, arXiv:1611.04611, eq. (18)

%H T. R. S. Walsh and A. B. Lehman, <a href="http://dx.doi.org/10.1016/0095-8956(72)90056-1">Counting rooted maps by genus. I</a>, J. Comb. Theory B 13 (1972), 192-218, eq. (5).

%F 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

%F 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

%F From Peter Bala, Dec 22 2011: (Start)

%F 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.

%F 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.

%F 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.

%F 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.

%F 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.

%F (End)

%e 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 + ...

%e Triangle begins :

%e n\k [1] [2] [3] [4] [5] [6] [7] [8]

%e [0] 1;

%e [1] 1, 1;

%e [2] 3, 5, 2;

%e [3] 15, 32, 22, 5;

%e [4] 105, 260, 234, 93, 14;

%e [5] 945, 2589, 2750, 1450, 386, 42;

%e [6] 10395, 30669, 36500, 22950, 8178, 1586, 132;

%e [7] 135135, 422232, 546476, 388136, 166110, 43400, 6476, 429;

%e [8] ...

%p 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

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

%o (PARI)

%o A053979_ser(N,t='t) = {

%o my(x='x+O('x^N), y0=1, y1=0, n=1);

%o while(n++, y1 = (1 + t*x*y0^2 + 2*x^2*y0')/(1-x);

%o if (y1 == y0, break()); y0 = y1); y0;

%o };

%o concat(apply(p->Vecrev(p), Vec(A053979_ser(10))))

%o \\ test: y=A053979_ser(50); 2*x^2*deriv(y,x) == -t*x*y^2 + (1-x)*y - 1

%o \\ _Gheorghe Coserea_, May 31 2017

%o (PARI)

%o A053979_seq(N) = {

%o my(t='t, R=vector(N), S=vector(N)); R[1]=S[1]=t;

%o for (n=2, N,

%o R[n] = t*subst(S[n-1],t,t+1);

%o S[n] = R[n] + sum(k=1, n-1, R[k]*S[n-k]));

%o apply(p->Vecrev(p), R/t);

%o };

%o concat(A053979_seq(10))

%o \\ 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

%o \\ _Gheorghe Coserea_, May 31 2017

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

%K nonn,tabl,easy

%O 0,4

%A _N. J. A. Sloane_, Apr 09 2000

%E More terms from _Emeric Deutsch_, Apr 01 2005