cp's OEIS Frontend

A005173 Number of rooted trees with 3 nodes of disjoint sets of labels with union {1..n}. If a node has an empty set of labels then it must have at least two children.

%I A005173 M4844 #41 Mar 28 2025 16:11:13
%S A005173 0,1,12,61,240,841,2772,8821,27480,84481,257532,780781,2358720,
%T A005173 7108921,21392292,64307941,193185960,580082161,1741295052,5225982301,
%U A005173 15682141200,47054812201,141181213812,423577195861,1270798696440,3812530307041,11437859356572,34314114940621
%N A005173 Number of rooted trees with 3 nodes of disjoint sets of labels with union {1..n}. If a node has an empty set of labels then it must have at least two children.
%D A005173 F. R. McMorris and T. Zaslavsky, The number of cladistic characters, Math. Biosciences, 54 (1981), 3-10.
%D A005173 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005173 Andrew Howroyd, <a href="/A005173/b005173.txt">Table of n, a(n) for n = 1..500</a>
%H A005173 F. R. McMorris and T. Zaslavsky, <a href="/A005172/a005172.pdf">The number of cladistic characters</a>, Math. Biosciences, 54 (1981), 3-10. [Annotated scanned copy]
%H A005173 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A005173 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.
%H A005173 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H A005173 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6, -11, 6).
%F A005173 G.f.: x*(1 + 6*x) / ((1 - x)*(1 - 2*x)*(1 - 3*x)). [corrected by _Ray Chandler_, Jun 26 2023]
%F A005173 First differences give A003063, 3^(n-1) - 2^n.
%F A005173 From _Andrew Howroyd_, Mar 28 2025: (Start)
%F A005173 a(n) = (3^(n+1) - 2^(n+3) + 7)/2.
%F A005173 E.g.f.: (3*exp(x)/2 - 1)*(exp(x) - 1)^2. (End)
%e A005173 From _Andrew Howroyd_, Mar 28 2025: (Start)
%e A005173 The a(3) = 12 trees up to relabeling have one of the following 3 forms:
%e A005173      {}         {1}        {1}
%e A005173     /  \       /   \        |
%e A005173   {1} {2,3}   {2}  {3}     {2}
%e A005173                             |
%e A005173                            {3}
%e A005173 (End)
%p A005173 A005173:=-z*(1+6*z)/(z-1)/(3*z-1)/(2*z-1); # conjectured by _Simon Plouffe_ in his 1992 dissertation
%t A005173 CoefficientList[Series[x (1+6 x)/(1-x)/(1-2 x)/(1-3 x),{x,0,30}],x] (* _Harvey P. Dale_, Jul 03 2023 *)
%Y A005173 Column 3 of A094262.
%Y A005173 Cf. A003063.
%K A005173 nonn,easy
%O A005173 1,3
%A A005173 _N. J. A. Sloane_
%E A005173 More terms from Larry Reeves (larryr(AT)acm.org), Feb 06 2001
%E A005173 Name clarified by _Andrew Howroyd_, Mar 28 2025