|
|
A005751
|
|
Number of matched trees with 2n nodes.
(Formerly M1478)
|
|
3
|
|
|
1, 1, 2, 5, 15, 49, 180, 701, 2891, 12371, 54564, 246319, 1133602, 5300255, 25119554, 120441076, 583373822, 2851023191, 14044428996, 69677569603, 347904448580, 1747195558582, 8820848574074, 44747514381341, 228004950808983, 1166498678253839, 5990376960443432
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
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
|
|
REFERENCES
|
S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 307 and 564.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
Aviezri S. Fraenkel, Edward R. Scheinerman, and Daniel Ullman, Undirected Edge Geography, Theoretical Computer Science, 112, (1993), 371-381.
|
|
FORMULA
|
a(n) ~ c * d^n / n^(5/2), where d = A245870 = 5.646542616232949712892713..., c = 0.1128580768964135711615258... . - Vaclav Kotesovec, Aug 25 2014
|
|
EXAMPLE
|
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
|
|
MAPLE
|
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
|
|
MATHEMATICA
|
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 *)
|
|
CROSSREFS
|
Cf. A000151 for the rooted version.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|