|
| |
|
|
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).
|
|
6
|
|
|
|
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.
|
|
|
LINKS
|
|
|
|
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
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)
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
(PARI)
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);
};
\\ 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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
