|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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.
A000081 counts unlabeled rooted trees with n nodes.
A331966 counts lone-child avoiding semi-identity trees, ranked by A331965.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|