cp's OEIS Frontend

A343663 Number of unlabeled binary rooted semi-identity plane trees with 2*n - 1 nodes.

%I A343663 #29 Apr 23 2022 01:34:19
%S A343663 1,1,2,4,12,34,108,344,1136,3796,12920,44442,154596,542336,1917648,
%T A343663 6825464,24439008,87962312,318087216,1155090092,4210494616,
%U A343663 15400782912,56508464736,207935588586,767162495940,2837260332472,10516827106016,39063666532784,145378611426512
%N A343663 Number of unlabeled binary rooted semi-identity plane trees with 2*n - 1 nodes.
%C A343663 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 if the non-leaf branches of the root are all distinct and are themselves semi-identity trees.
%H A343663 Andrew Howroyd, <a href="/A343663/b343663.txt">Table of n, a(n) for n = 1..500</a>
%H A343663 Samuele Giraudo, <a href="https://arxiv.org/abs/2204.03586">The combinator M and the Mockingbird lattice</a>, arXiv:2204.03586 [math.CO], 2022.
%H A343663 Samuele Giraudo, <a href="https://igm.univ-mlv.fr/~giraudo/Data/Papers/Mockingbird%20lattices.pdf">Mockingbird lattices</a>, Séminaire Lotharingien de Combinatoire XX, Proceedings of the 34th Conf. on Formal Power, Series and Algebraic Combinatorics (Bangalore, India, 2022).
%F A343663 G.f.: x*A(x) where A(x) satisfies A(x) = 1 + x + x*(A(x)^2 - A(x^2)). - _Andrew Howroyd_, May 07 2021
%e A343663 The a(1) = 1 through a(5) = 12 trees:
%e A343663   o  (oo)  ((oo)o)  (((oo)o)o)  ((((oo)o)o)o)
%e A343663            (o(oo))  ((o(oo))o)  (((o(oo))o)o)
%e A343663                     (o((oo)o))  (((oo)o)(oo))
%e A343663                     (o(o(oo)))  ((o((oo)o))o)
%e A343663                                 ((o(o(oo)))o)
%e A343663                                 ((o(oo))(oo))
%e A343663                                 ((oo)((oo)o))
%e A343663                                 ((oo)(o(oo)))
%e A343663                                 (o(((oo)o)o))
%e A343663                                 (o((o(oo))o))
%e A343663                                 (o(o((oo)o)))
%e A343663                                 (o(o(o(oo))))
%t A343663 crsiq[n_]:=Join@@Table[Select[Union[Tuples[crsiq/@ptn]],#=={}||#=={{},{}}||Length[#]==2&&(UnsameQ@@DeleteCases[#,{}])&],{ptn,Join@@Permutations/@IntegerPartitions[n-1]}];
%t A343663 Table[Length[crsiq[n]],{n,1,11,2}]
%t A343663 (* Second program: *)
%t A343663 m = 29; p[_] = 1;
%t A343663 Do[p[x_] = 1 + x + x (p[x]^2 - p[x^2]) + O[x]^m // Normal, {m}];
%t A343663 CoefficientList[p[x], x] (* _Jean-François Alcover_, May 09 2021, after _Andrew Howroyd_ *)
%o A343663 (PARI) seq(n)={my(p=O(1)); for(n=1, n, p=1 + x + x*(p^2-subst(p,x,x^2))); Vec(p)} \\ _Andrew Howroyd_, May 07 2021
%Y A343663 The not necessarily semi-identity version is A000108.
%Y A343663 The non-plane version is A063895, ranked by A339193.
%Y A343663 The Matula-Goebel numbers in the non-plane case are A339193.
%Y A343663 The not-necessarily binary version is A343937.
%Y A343663 A000081 counts unlabeled rooted trees with n nodes.
%Y A343663 2*A001190 - 1 counts binary trees, ranked by A111299.
%Y A343663 A001190 counts semi-binary trees, ranked by A292050.
%Y A343663 A004111 counts identity trees, ranked by A276625.
%Y A343663 A306200 counts semi-identity trees, ranked by A306202.
%Y A343663 A306201 counts balanced semi-identity trees, ranked by A306203.
%Y A343663 A331966 counts lone-child avoiding semi-identity trees, ranked by A331965.
%Y A343663 Cf. A001678, A320230, A331934, A331963, A331964.
%K A343663 nonn
%O A343663 1,3
%A A343663 _Gus Wiseman_, May 05 2021
%E A343663 Terms a(13) and beyond from _Andrew Howroyd_, May 07 2021