|
%I #38 Oct 11 2023 11:30:12
%S 0,0,0,1,2,6,14,37,92,239,613,1607,4215,11185,29814,80070,216061,
%T 586218,1597292,4370721,12003163,33077327,91431425,253454781,
%U 704425087,1962537755,5479843060,15332668869,42983623237,120716987723,339595975795,956840683968
%N Number of rooted unlabeled trees where the root node has degree 2 and both branches are distinct.
%D F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973, page 57.
%H Alois P. Heinz, <a href="/A217420/b217420.txt">Table of n, a(n) for n = 1..1000</a>
%H Charlie Liou and Anthony Mendes, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Mendes/mendes4.pdf">Matrix Representations From Labeled Trees</a>, J. Int. Seq. (2023) Vol. 26, No. 7, Article 23.7.6.
%F O.g.f.: x * (T(x)^2/2 - T(x^2)/2) where T(x) is o.g.f. for A000081.
%F a(n) = A000081(n-1) - A000055(n-1) for n > 1.
%F a(n) = Sum_{1 <= i < j, i + j = m} A000081(i) * A000081(j) + (1 - (-1)^n) * binomial(A000081(m/2),2) / 2 where m = n - 1. - _Walt Rorie-Baety_, Aug 30 2021
%p with(numtheory):
%p b:= proc(n) option remember; `if`(n<=1, n,
%p (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
%p end:
%p a:= proc(n) option remember; (add(b(k)*b(n-1-k), k=0..n-1)-
%p `if`(irem(n, 2, 'r')=1, b(r), 0))/2
%p end:
%p seq(a(n), n=1..50); # _Alois P. Heinz_, May 16 2013
%t Needs["Combinatorica`"]
%t nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i]s[n-1,i]i,{i,1,n-1}]/(n-1);rt=Table[a[i],{i,1,nn}];Take[CoefficientList[CycleIndex[AlternatingGroup[2],s]-CycleIndex[SymmetricGroup[2],s]/.Table[s[j]->Table[Sum[rt[[i]]x^(i*k),{i,1,nn}],{k,1,nn}][[j]],{j,1,nn}],x],nn] (* after code by _Robert A. Russell_ in A000081 *)
%o (Python)
%o # uses function in A000081
%o def A217420(n): return sum(A000081(i)*A000081(n-1-i) for i in range(1,(n-1)//2+1)) - ((A000081((n-1)//2)+1)*A000081((n-1)//2)//2 if n % 2 else 0) # _Chai Wah Wu_, Feb 03 2022
%Y Cf. A000081 (rooted trees), A000055 (free trees).
%K nonn
%O 1,5
%A _Geoffrey Critzer_, Oct 19 2012
|
