|
| |
|
|
A027852
|
|
Number of connected functions on n points with a loop of length 2.
|
|
19
|
|
|
|
0, 1, 1, 3, 6, 16, 37, 96, 239, 622, 1607, 4235, 11185, 29862, 80070, 216176, 586218, 1597578, 4370721, 12003882, 33077327, 91433267, 253454781, 704429853, 1962537755, 5479855546, 15332668869, 42983656210, 120716987723, 339596063606, 956840683968
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
Number of unordered pairs of rooted trees with a total of n nodes.
Equivalently, the number of rooted trees on n+1 nodes where the root has degree 2.
Number of trees on n nodes rooted at an edge. - Washington Bomfim, Jul 06 2012
Guy (1988) calls these tadpole graphs. - N. J. A. Sloane, Nov 04 2014
Number of unicyclic graphs of n nodes with a cycle length of two (in other words a double edge). - Washington Bomfim, Dec 02 2020
|
|
|
LINKS
|
Alois P. Heinz, Table of n, a(n) for n = 1..2136
Washington Bomfim, Illustration of initial terms
R. K. Guy, Letter to N. J. A. Sloane, 1988-04-12 (annotated scanned copy) Includes illustrations for n <= 6.
R. J. Mathar, Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603.00077 [math.CO] (2016), Eq. (75).
Index entries for sequences related to rooted trees
|
|
|
FORMULA
|
G.f.: A(x) = (B(x)^2 + B(x^2))/2 where B(x) is g.f. of A000081.
a(n) = Sum_{k=1..(n-1)/2}( f(k)*f(n-k) ) + [n mod 2 = 0] * ( f(n/2)^2+f(n/2) ) /2, where f(n) = A000081(n). - Washington Bomfim, Jul 06 2012 and Dec 01 2020
a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = A187770 = 0.43992401257102530404090339... . - Vaclav Kotesovec, Sep 12 2014
2*a(n) = A000106(n) + A000081(n/2), where A(.)=0 if the argument is non-integer. - R. J. Mathar, Jun 04 2020
|
|
|
MAPLE
|
with(numtheory): b:= proc(n) option remember; local d, j; `if`(n<=1, n, (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1)) end: a:= n-> (add(b(i) *b(n-i), i=0..n) +`if`(irem(n, 2)=0, b(n/2), 0))/2: seq(a(n), n=1..50); # Alois P. Heinz, Aug 22 2008, revised Oct 07 2011
# second, re-usable version
A027852 := proc(N::integer)
local dh, Nprime;
dh := 0 ;
for Nprime from 0 to N do
dh := dh+A000081(Nprime)*A000081(N-Nprime) ;
end do:
if type(N, 'even') then
dh := dh+A000081(N/2) ;
end if;
dh/2 ;
end proc: # R. J. Mathar, Mar 06 2017
|
|
|
MATHEMATICA
|
Needs["Combinatorica`"]; nn = 30; s[n_, k_] := s[n, k] = a[n + 1 - k] + If[n < 2 k, 0, s[n - k, k]]; a[1] = 1; a[n_] := a[n] = Sum[a[i] s[n - 1, i] i, {i, 1, n - 1}]/(n - 1); rt = Table[a[i], {i, 1, nn}]; Take[CoefficientList[CycleIndex[DihedralGroup[2], s] /. Table[s[j] -> Table[Sum[rt[[i]] x^(k*i), {i, 1, nn}], {k, 1, nn}][[j]], {j, 1, nn}], x], {2, nn}] (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
b[n_] := b[n] = If[n <= 1, n, (Sum[Sum[d b[d], {d, Divisors[j]}] b[n-j], {j, 1, n-1}])/(n-1)];
a[n_] := (Sum[b[i] b[n-i], {i, 0, n}] + If[Mod[n, 2] == 0, b[n/2], 0])/2;
Table[a[n], {n, 1, 50}] (* Jean-François Alcover, Oct 30 2018, after Alois P. Heinz *)
|
|
|
PROG
|
(PARI) seq(max_n)= { my(V = f = vector(max_n), i=1, s); f[1]=1;
for(j=1, max_n - 1, f[j+1] = 1/j * sum(k=1, j, sumdiv(k, d, d * f[d]) * f[j-k+1]));
for(n = 1, max_n, s = sum(k = 1, (n-1)/2, ( f[k] * f[n-k] ));
if(n % 2 == 1, V[i] = s, V[i] = s + (f[n/2]^2 + f[n/2])/2); i++); V };
\\ Washington Bomfim, Jul 06 2012 and Dec 01 2020
|
|
|
CROSSREFS
|
Column 2 of A033185 (forests of rooted trees), A217781 (unicyclic graphs), A339303 (unoriented linear forests) and A339428 (connected functions).
Cf. A000081, A000106, A000226, A000631, A001372, A002861.
Sequence in context: A293993 A072824 A089406 * A203068 A321229 A114410
Adjacent sequences: A027849 A027850 A027851 * A027853 A027854 A027855
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Christian G. Bower, Dec 14 1997
|
|
|
EXTENSIONS
|
Edited by Christian G. Bower, Feb 12 2002
|
|
|
STATUS
|
approved
|
| |
|
|
