login
Number of identity matched trees with n nodes.
(Formerly M3517)
2

%I M3517 #37 Jan 25 2020 01:44:18

%S 0,0,0,1,4,16,64,252,1018,4182,17510,74510,322034,1410362,6251114,

%T 27998532,126583634,577079333,2650573354,12256481666,57021299394,

%U 266754944481,1254245360430,5924659521632,28105641930102,133853504339029,639801068848128

%N Number of identity matched trees with n nodes.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A005755/b005755.txt">Table of n, a(n) for n = 1..450</a>

%H Rodica Simion, <a href="http://dx.doi.org/10.1016/0012-365X(91)90061-6">Trees with 1-factors and oriented trees</a>, Discrete Math., 88 (1991), 93-104.

%H Rodica Simion, <a href="/A005750/a005750.pdf">Trees with 1-factors and oriented trees</a>, Discrete Math., 88 (1981), 97. (Annotated scanned copy)

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F a(n) ~ c * d^n / n^(5/2), where d = A246312 = 5.2490324912281705791649522..., c = 0.089035519570392123219315... . - _Vaclav Kotesovec_, Aug 25 2014

%p with(numtheory): b2:= proc(n) option remember; local m; `if`(n=1, 1, 2/(n-1) *add(b2(m) *add((-1)^((n-m)/d+1) *d*b2(d), d=divisors(n-m)), m=1..n-1)) end: c2:= proc(n) option remember; local m; `if`(n=1, 1, 1/(n-1) *add(c2(m) *add((-1)^((n-m)/d+1) *d*b2(d), d=divisors(n-m)), m=1..n-1)) end: a2:= n-> (b2(n) -add(b2(m) *b2(n-m), m=1..n-1) -`if`(irem(n, 2)=0, b2(n/2), c2((n+1)/2)))/2: seq(a2(n), n=1..30); # _Alois P. Heinz_, Aug 04 2009

%t b2[n_] := b2[n] = If [n == 1, 1, 2/(n-1)*Sum[b2[m]*Sum[(-1)^((n-m)/d+1)*d*b2[d], {d, Divisors[n-m]}], {m, 1, n-1}]]; c2[n_] := c2[n] = If [n == 1, 1, 1/(n-1)*Sum[c2[m]*Sum[(-1)^((n-m)/d+1)*d*b2[d], {d, Divisors[n-m]}], {m, 1, n-1}]]; a2[n_] := (b2[n] - Sum[b2[m]*b2[n-m], {m, 1, n-1}] - If[Mod[n, 2] == 0, b2[n/2], c2[(n+1)/2]])/2; Table[a2[n], {n, 1, 30}] (* _Jean-François Alcover_, Mar 17 2014, after _Alois P. Heinz_ *)

%Y Cf. A005753, A005754, A102755, A246312.

%K nonn

%O 1,5

%A _N. J. A. Sloane_

%E More terms from _Alois P. Heinz_, Aug 04 2009