A343937 - OEIS

%I #10 May 09 2021 06:12:07

%S 1,1,2,5,13,38,117,375,1224,4095,13925,48006,167259,588189,2084948,

%T 7442125,26725125,96485782,350002509,1275061385,4662936808,

%U 17111964241,62996437297,232589316700,861028450579,3195272504259,11884475937910,44295733523881,165420418500155

%N Number of unlabeled semi-identity plane trees with n nodes.

%C In a semi-identity tree, only the non-leaf branches of any given vertex are required to be distinct. Alternatively, a rooted tree is a semi-identity tree iff the non-leaf branches of the root are all distinct and are themselves semi-identity trees.

%H Andrew Howroyd, <a href="/A343937/b343937.txt">Table of n, a(n) for n = 1..200</a>

%F G.f.: A(x) satisfies A(x) = x*Sum_{j>=0} j!*[y^j] exp(x*y - Sum_{k>=1} (-y)^k*(A(x^k) - x^k)/k). - _Andrew Howroyd_, May 08 2021

%e The a(1) = 1 through a(5) = 13 trees are the following. The number of nodes is the number of o's plus the number of brackets (...).

%e   o  (o)  (oo)   (ooo)    (oooo)

%e           ((o))  ((o)o)   ((o)oo)

%e                  ((oo))   ((oo)o)

%e                  (o(o))   ((ooo))

%e                  (((o)))  (o(o)o)

%e                           (o(oo))

%e                           (oo(o))

%e                           (((o))o)

%e                           (((o)o))

%e                           (((oo)))

%e                           ((o(o)))

%e                           (o((o)))

%e                           ((((o))))

%t arsiq[n_]:=Join@@Table[Select[Union[Tuples[arsiq/@ptn]],#=={}||(UnsameQ@@DeleteCases[#,{}])&],{ptn,Join@@Permutations/@IntegerPartitions[n-1]}];

%t Table[Length[arsiq[n]],{n,10}]

%o (PARI)

%o F(p)={my(n=serprec(p,x)-1, q=exp(x*y + O(x*x^n))*prod(k=2, n, (1 + y*x^k + O(x*x^n))^polcoef(p,k,x)) ); sum(k=0, n, k!*polcoef(q,k,y))}

%o seq(n)={my(p=O(x)); for(n=1, n, p=x*F(p)); Vec(p)} \\ _Andrew Howroyd_, May 08 2021

%Y The not necessarily semi-identity version is A000108.

%Y The non-plane binary version is A063895, ranked by A339193.

%Y The non-plane version is A306200, ranked by A306202.

%Y The binary case is A343663.

%Y A000081 counts unlabeled rooted trees with n nodes.

%Y A001190*2 - 1 counts binary trees, ranked by A111299.

%Y A001190 counts semi-binary trees, ranked by A292050.

%Y A004111 counts identity trees, ranked by A276625.

%Y A306201 counts balanced semi-identity trees, ranked by A306203.

%Y A331966 counts lone-child avoiding semi-identity trees, ranked by A331965.

%Y Cf. A001678, A320230, A331934, A331963, A331964.

%K nonn

%O 1,3

%A _Gus Wiseman_, May 07 2021

%E Terms a(17) and beyond from _Andrew Howroyd_, May 08 2021