login
A343937
Number of unlabeled semi-identity plane trees with n nodes.
2
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
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.
Sequence in context: A149857 A001475 A360271 * A369729 A149858 A148303
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 07 2021
EXTENSIONS
Terms a(17) and beyond from Andrew Howroyd, May 08 2021
STATUS
approved