|
%I M1478 #69 Jan 25 2020 01:44:04
%S 1,1,2,5,15,49,180,701,2891,12371,54564,246319,1133602,5300255,
%T 25119554,120441076,583373822,2851023191,14044428996,69677569603,
%U 347904448580,1747195558582,8820848574074,44747514381341,228004950808983,1166498678253839,5990376960443432
%N Number of matched trees with 2n nodes.
%C This sequence also describes the number of trees on 2n vertices that are in P-position (a player 2 win) in unrooted UVG (Undirected Vertex Geography). This connection is discussed by Fraenkel, Scheinerman, and Ullman in their paper "Undirected Edge Geography." - _Kaitlin Bruegge_, Jul 14 2017
%D S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 307 and 564.
%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="/A005751/b005751.txt">Table of n, a(n) for n = 1..400</a>
%H Aviezri S. Fraenkel, Edward R. Scheinerman, and Daniel Ullman, <a href="https://doi.org/10.1016/0304-3975(93)90026-P">Undirected Edge Geography</a>, Theoretical Computer Science, 112, (1993), 371-381.
%H Indranil Ghosh, <a href="/A005751/a005751.txt">Python program for computing this sequence</a> (translated from Maple code)
%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 = A245870 = 5.646542616232949712892713..., c = 0.1128580768964135711615258... . - _Vaclav Kotesovec_, Aug 25 2014
%e a(3)=2; indeed we have the path P_6 and the tree obtained by identifying one endpoint of each of P_2, P_3, and P_3. - _Emeric Deutsch_, Apr 13 2014
%p with(numtheory): r2:= proc(n) option remember; local m; `if`(n=1, 1, 2/(n-1) *add(r2(m) *add(d*r2(d), d=divisors(n-m)), m=1..n-1)) end: p2:= proc(n) option remember; local m; `if`(n=1, 1, 1/(n-1) *add(p2(m) *add(d*r2(d), d=divisors(n-m)), m=1..n-1)) end: m2:= n-> (r2(n) -add(r2(m) *r2(n-m), m=1..n-1) +`if`(irem(n, 2)=0, r2(n/2), p2((n+1)/2)))/2: seq(m2(n), n=1..30); # _Alois P. Heinz_, Aug 04 2009
%t r2[n_] := r2[n] = If[n == 1, 1, 2/(n-1)*Sum[r2[m]*Sum[d*r2[d], {d, Divisors[n-m]}], {m, 1, n-1}]]; p2[n_] := p2[n] = If[n == 1, 1, 1/(n-1)*Sum[p2[m]*Sum[d*r2[d], {d, Divisors[n-m]}], {m, 1, n-1}]]; m2[n_] := (r2[n] - Sum[r2[m]*r2[n-m], {m, 1, n-1}] + If[Mod[n, 2] == 0, r2[n/2], p2[(n+1)/2]])/2; Table[m2[n], {n, 1, 30}] (* _Jean-François Alcover_, Mar 17 2014, after _Alois P. Heinz_ *)
%Y Cf. A000151 for the rooted version.
%Y Cf. A245870.
%K nonn
%O 1,3
%A _N. J. A. Sloane_
%E More terms from _Alois P. Heinz_, Aug 04 2009
|
