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

1, 1, 2, 5, 13, 38, 117, 375, 1224, 4095, 13925, 48006, 167259, 588189, 2084948, 7442125, 26725125, 96485782, 350002509, 1275061385, 4662936808, 17111964241, 62996437297, 232589316700, 861028450579, 3195272504259, 11884475937910, 44295733523881, 165420418500155

Offset

1,3

Comments

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.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..200

Formula

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

Example

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 (...).
  o  (o)  (oo)   (ooo)    (oooo)
          ((o))  ((o)o)   ((o)oo)
                 ((oo))   ((oo)o)
                 (o(o))   ((ooo))
                 (((o)))  (o(o)o)
                          (o(oo))
                          (oo(o))
                          (((o))o)
                          (((o)o))
                          (((oo)))
                          ((o(o)))
                          (o((o)))
                          ((((o))))

Mathematica

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

Prog

(PARI)
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))}
seq(n)={my(p=O(x)); for(n=1, n, p=x*F(p)); Vec(p)} \\ Andrew Howroyd, May 08 2021

Crossrefs

The not necessarily semi-identity version is A000108.

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

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

The binary case is A343663.

A000081 counts unlabeled rooted trees with n nodes.

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

A001190 counts semi-binary trees, ranked by A292050.

A004111 counts identity trees, ranked by A276625.

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

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

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

Sequence in context: A149857 A001475 A360271 * A369729 A149858 A148303

Adjacent sequences: A343934 A343935 A343936 * A343938 A343939 A343940

Keyword

nonn

Author

Gus Wiseman, May 07 2021

Extensions

Terms a(17) and beyond from Andrew Howroyd, May 08 2021

Status

approved