A005751 Number of matched trees with 2n nodes. (Formerly M1478)

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

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

Alois P. Heinz, Table of n, a(n) for n = 1..400

Aviezri S. Fraenkel, Edward R. Scheinerman, and Daniel Ullman, Undirected Edge Geography, Theoretical Computer Science, 112, (1993), 371-381.

Indranil Ghosh, Python program for computing this sequence (translated from Maple code)

Rodica Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1991), 93-104.

Rodica Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1981), 97. (Annotated scanned copy)

Index entries for sequences related to trees

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.

Cf. A245870.

Sequence in context: A079146 A000734 A148366 * A202182 A149944 A149945

Adjacent sequences: A005748 A005749 A005750 * A005752 A005753 A005754

Keyword

nonn

Author

N. J. A. Sloane

Extensions

More terms from Alois P. Heinz, Aug 04 2009

Status

approved