OFFSET
1,3
COMMENTS
A rooted tree is anti-transitive if the subbranches are disjoint from the branches, i.e., no branch of a branch is a branch.
LINKS
Robert P. P. McKone, Table of n, a(n) for n = 1..63
Gus Wiseman, The a(7) = 36 anti-transitive rooted trees.
Gus Wiseman, The a(10) = 532 anti-transitive rooted trees.
EXAMPLE
The a(1) = 1 through a(6) = 14 anti-transitive rooted trees:
o (o) (oo) (ooo) (oooo) (ooooo)
((o)) ((oo)) ((ooo)) ((oooo))
(((o))) (((oo))) (((ooo)))
((o)(o)) ((o)(oo))
((o(o))) ((o(oo)))
(o((o))) ((oo(o)))
((((o)))) (o((oo)))
(oo((o)))
((((oo))))
(((o)(o)))
(((o(o))))
((o((o))))
(o(((o))))
(((((o)))))
MATHEMATICA
rtall[n_]:=Union[Sort/@Join@@(Tuples[rtall/@#]&/@IntegerPartitions[n-1])];
Table[Length[Select[rtall[n], Intersection[Union@@#, #]=={}&]], {n, 10}]
PROG
(PARI)
an = 0; ax = 'x; axp = 0; at = 0; att = 0; aa = 0; ar = 0;
base(F, sh) = {my(bv = Vec(att * F)); my(C = 1, m, M, iv, j); for(m=1, an-1, if(ar[m], C *= binomial(bv[m], ar[m]))); if(!C, return()); M = an - 1 - sh; if(M < 0, return()); iv = Vec( 1/(F + O(ax^(M+1))) ); for(j=0, M, aa[1 + sh + j] += C * iv[j+1]); };
step(k, rem, F, sh) = {my(maxr = min(rem\k, at[k])); my(v, Fv = F, xk = axp[k]); for(v=0, maxr, ar[k] = v; rec(k+1, rem - k*v, Fv, sh + k*v); if(v < maxr, Fv -= xk*Fv); ); ar[k] = 0; };
rec(k, rem, F, sh) = {if(k == an, base(F, sh), step(k, rem, F, sh)); };
A(N) = {my(n = N, x = 'x); my(t = vector(n), s = vector(n)); my(k, m, acc, T); if(n==1, return([1])); an = n; ax = x; axp = vector(n-1, i, x^i); t[1] = 1; for(m=1, n, s[m] = 1); for(k=2, n, acc = 0; for(m=1, k-1, acc += s[m]*t[k-m]); t[k] = acc/(k-1); forstep(m=k, n, k, s[m] += k*t[k]); ); at = t; T = O(x^(n+1)); for(k=1, n, T += t[k]*x^k); att = T; aa = vector(n); ar = vector(n-1); rec(1, n-1, 1 + 0*x, 0); aa};
a(n) = A(n)[n];
print1(A(32)) \\ Robert P. P. McKone, Jan 27 2026
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, Mar 13 2019
EXTENSIONS
a(16)-a(20) from Jinyuan Wang, Jun 20 2020
a(21)-a(63) from Robert P. P. McKone, Jan 27 2026
STATUS
approved